sort()で使うpair型の比較関数をテンプレート化するとエラーが出るので解消したい

Question

質問

Ｑ：エラーを解消する方法を知りたい

実現したいこと

比較関数のbool comp1(pi a, pi b) {}をtemplate化してsort()で使いたい

発生している問題・エラーメッセージ

sort
+4 個のオーバーロード
オーバーロードされた関数 "sort" のインスタンスが引数リストと一致しませんC/C++(304)
q2.cpp(28, 3): 引数の型: (__gnu_cxx::__normal_iterator<pi *, std::vector<pi, std::allocator<pi>>>, __gnu_cxx::__normal_iterator<pi *, std::vector<pi, std::allocator<pi>>>, <unknown-type>)

該当のソースコード

C++17

#include <bits/stdc++.h>
using namespace std;

using pi = pair<int, int>;

// template無し
bool comp1(pi a, pi b) { return a.first != b.first ? a.first < b.first : a.second < b.second; }

// template化したいがsort()関数で使うとエラーになる
template<class T, class U>
bool comp2(pair<T, U> a, pair<T, U> b) {
  return a.first != b.first ? a.first < b.first : a.second < b.second;
}

void output(vector<pi> v) {
  for (auto e : v) cout << e.first << " " << e.second << "/n";
}

void solve() {
  // input
  vector<pi> v {{1, 3}, {2, 2}, {3, 1}, {9, 7}, {8, 8}, {7, 9}};

  // sort1
  sort(v.begin(), v.end(), comp1);
  output(v);

  // sort2
  // ↓※このsort()でエラーとなるが原因が分からない
  sort(v.begin(), v.end(), comp2);
  output(v);
}

int main() { (solve()); }

試したこと

・comp1のように比較関数の引数の型を明示するとエラーは出なかった
・comp2を使ったsort2をコメントアウトしてコンパイルすると通るのでtemplate化したcomp2は間違っていない気がする
・sort2のsort()の引数の指定の仕方がtemplate化したことによって違っているとエラーから推測出来るのですが
どのように指定したらエラーが解消するのか分からない

Answer 1

関数だとstd::sortのtemplate _Compareが関数ポインタになるわけで、 引数のためにsort2関数をインスタンス化する必要があるわけだけど、このsortを呼び出す時点では、sort2に与えるT,Uが分からなくて詰むんじゃない？

sort2<int,int>とかで手動でテンプレートを指定しても動くけど、functor classにしとけばインスタンス化をsortの_Compareの呼び出し時点まで引き延ばせるので、T、Uが自動解決できるのでは。

struct sort2{
template<class T, class U>
bool operator()(pair<T, U> a, pair<T, U> b) {return a.first != b.first ? a.first < b.first : a.second < b.second;}
};

Comments

[moko3]

回答ありがとうございます。

[moko3]

「functor class」（ファンクタ）という概念を知らなかったので勉強になりました。
引数で型を指定して渡すのはテンプレート化する意味が無いような気がするので
struct{}にしておいた方が汎用性があると思いました。

Answer 2

解決方法は出てきているようなので背景にある理屈を少し補足しておきます。

テンプレートの詳細は複雑なのですが大雑把には

• 関数テンプレートは関数ではない。 クラステンプレートはクラスではない。
• 関数テンプレートにテンプレート引数を当てはめたものは関数、クラステンプレートにテンプレート引数を当てはめたものはクラス
• テンプレートはそれが必要とされるところで暗黙に実体化される (明示的に実体化することもできる)
• 状況によってはテンプレート引数は自動的に推論してくれることもある

たとえば

template<class T>
T foo(T x) {
    return x;
}

int main(void) {
    foo(1);
}

というようなコードがあれば 1 が int であることを元にして T が int であることが推論されて foo<int>(1); というように呼び出したのと同じであることになります。 つまり実引数から仮引数が推論されました。 テンプレート実引数を省略したときにテンプレート実引数が無いのではなく、推論によって埋められて具体的な型になって処理されているのです。

逆に仮引数から実引数が推論されることもあります。

template<class T>
T foo(T x) {
    return x;
}

void bar(int (*)(int)) {}

int main(void) {
    bar(foo);
}

では引数を与えるほうも受け取るほうもテンプレートだったらどうなるかというとエラーです。 std::sort も関数テンプレートなので質問の事例はこの場合に当てはまります。

template<class T>
T foo(T x) {
    return x;
}

template<class T>
void bar(T x) {}

int main(void) {
    // テンプレート引数を埋めるための推論ができないのでエラー
    bar(foo);
}

解決方法としては二種類が考えられます。

• 推論に頼らずにテンプレート引数を与える (lehshell 氏の提案)
• 推論可能なように変形する (matukeso 氏の提案)

状況によりますが汎用的に使うライブラリとしてまとめることを指向するなら基本的には推論可能な形になっているほうが好ましいでしょう。 (いちいち型を書かずに済むならそのほうがよいので。)

Comments

[moko3]

回答ありがとうございます。
＞＞std::sort も関数テンプレート
＞＞推論可能な形になっているほうが好ましい
丁寧な説明をして頂いてとても勉強になります。

Answer 3

//sort(v.begin(), v.end(), comp2);
sort(v.begin(), v.end(), comp2<int, int>);

Comments

[moko3]

回答ありがとうございます。

Answer 4

C++17まで使ってよければ、std::pair<T1,T2>型はstd::less<>を使って昇順ソート可能です。比較時にはT1→T2順に<比較が行われます。

#include <functional>  // std::less

sort(v.begin(), v.end(), less<>{});

std::less<>の仕組みは matukeso さん回答の通りで、同クラスoperator()がテンプレート化されています。
実際の比較処理は std::pairのoperator< が呼び出されます。

Comments

[moko3]

回答ありがとうございます。
質問をなるべく簡単にするためにtemplate化でエラーが出ることだけに絞って質問していました。
first昇順,first降順,second昇順,second降順の4種類を何かしらの形でテンプレとしたかったです。
後出しで条件追加のようになってしまいすみません。