Another problem with templates

The following code snippet defines two binary predicates Cmp1 and Cmp2 for sorting. Cmp1 is templated, and Cmp2 is just a special case with T == int*. The code compiles (using gcc) with the second std::sort commented out, but not with it included, though the two should be identical. (I know that the memory between b and b_end isn't initialized; it doesn't matter, that's not where the error is coming from.) The problem seems to be that sort() doesn't like a comparison function with explicit pointer types, even though it's perfectly valid, so one has to sneak them in using a template. Any ideas why?

Code:

#include <algorithm>

template<class T>
class Cmp1 {
public:
  bool operator() (const T &x1, const T &x2) const {
    return true;
  }
};

class Cmp2 {
public:
  bool operator() (const int* &x1, const int* &x2) const {
    return true;
  }
};

int main() {
  int **b, **b_end;
  std::sort(b, b_end, Cmp1<int*>());
//  std::sort(b, b_end, Cmp2());
}

What's the error message? It compiles in VC++ 2003.

BTW, your compare functions aren't valid. They should return false if you don't want to do any actual checking. x1 < x2 should be true if and only if x2 < x1 is not true.

I was afraid someone would ask that; there are LOTS of them. (I knew the compare functions were questionable, but I was trying to distill the problem down to its essence, so stripped out everything that didn't seem to be relevant.) I was able to find a really ugly-looking workaround to this, but don't want to make a habit of it.

/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h: In function ‘void std::partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int**, _Compare = Cmp2]’:
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h:2666: instantiated from ‘void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = int**, _Size = int, _Compare = Cmp2]’
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h:2749: instantiated from ‘void std::sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int**, _Compare = Cmp2]’
B.cxx:21: instantiated from here
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h:2477: error: no match for call to ‘(Cmp2) (int*&, int*&)’
B.cxx:13: note: candidates are: bool Cmp2::operator()(const int*&, const int*&) const
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h: In function ‘const _Tp& std::__median(const _Tp&, const _Tp&, const _Tp&, _Compare) [with _Tp = int*, _Compare = Cmp2]’:
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h:2679: instantiated from ‘void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = int**, _Size = int, _Compare = Cmp2]’
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h:2749: instantiated from ‘void std::sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int**, _Compare = Cmp2]’
B.cxx:21: instantiated from here
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h:125: error: no match for call to ‘(Cmp2) (int* const&, int* const&)’
B.cxx:13: note: candidates are: bool Cmp2::operator()(const int*&, const int*&) const
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h:126: error: no match for call to ‘(Cmp2) (int* const&, int* const&)’
B.cxx:13: note: candidates are: bool Cmp2::operator()(const int*&, const int*&) const
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h:128: error: no match for call to ‘(Cmp2) (int* const&, int* const&)’
B.cxx:13: note: candidates are: bool Cmp2::operator()(const int*&, const int*&) const
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h:132: error: no match for call to ‘(Cmp2) (int* const&, int* const&)’
B.cxx:13: note: candidates are: bool Cmp2::operator()(const int*&, const int*&) const
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h:134: error: no match for call to ‘(Cmp2) (int* const&, int* const&)’
B.cxx:13: note: candidates are: bool Cmp2::operator()(const int*&, const int*&) const
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h: In function ‘_RandomAccessIterator std::__unguarded_partition(_RandomAccessIterator, _RandomAccessIterator, _Tp, _Compare) [with _RandomAccessIterator = int**, _Tp = int*, _Compare = Cmp2]’:
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h:2679: instantiated from ‘void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = int**, _Size = int, _Compare = Cmp2]’
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h:2749: instantiated from ‘void std::sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int**, _Compare = Cmp2]’
B.cxx:21: instantiated from here
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h:2199: error: no match for call to ‘(Cmp2) (int*&, int*&)’
B.cxx:13: note: candidates are: bool Cmp2::operator()(const int*&, const int*&) const
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h:2202: error: no match for call to ‘(Cmp2) (int*&, int*&)’
B.cxx:13: note: candidates are: bool Cmp2::operator()(const int*&, const int*&) const
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h: In function ‘void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int**, _Compare = Cmp2]’:
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h:2378: instantiated from ‘void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int**, _Compare = Cmp2]’
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h:2751: instantiated from ‘void std::sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int**, _Compare = Cmp2]’
B.cxx:21: instantiated from here
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h:2303: error: no match for call to ‘(Cmp2) (int*&, int*&)’
B.cxx:13: note: candidates are: bool Cmp2::operator()(const int*&, const int*&) const
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h: In function ‘void std::__unguarded_linear_insert(_RandomAccessIterat or, _Tp, _Compare) [with _RandomAccessIterator = int**, _Tp = int*, _Compare = Cmp2]’:
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h:2309: instantiated from ‘void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int**, _Compare = Cmp2]’
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h:2378: instantiated from ‘void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int**, _Compare = Cmp2]’
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h:2751: instantiated from ‘void std::sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int**, _Compare = Cmp2]’
B.cxx:21: instantiated from here
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h:2251: error: no match for call to ‘(Cmp2) (int*&, int*&)’
B.cxx:13: note: candidates are: bool Cmp2::operator()(const int*&, const int*&) const
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_heap.h: In function ‘void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = int**, _Distance = int, _Tp = int*, _Compare = Cmp2]’:
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_heap.h:404: instantiated from ‘void std::make_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int**, _Compare = Cmp2]’
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h:2475: instantiated from ‘void std::partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int**, _Compare = Cmp2]’
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h:2666: instantiated from ‘void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = int**, _Size = int, _Compare = Cmp2]’
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h:2749: instantiated from ‘void std::sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int**, _Compare = Cmp2]’
B.cxx:21: instantiated from here
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_heap.h:279: error: no match for call to ‘(Cmp2) (int*&, int*&)’
B.cxx:13: note: candidates are: bool Cmp2::operator()(const int*&, const int*&) const
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_heap.h: In function ‘void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = int**, _Distance = int, _Tp = int*, _Compare = Cmp2]’:
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_heap.h:291: instantiated from ‘void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = int**, _Distance = int, _Tp = int*, _Compare = Cmp2]’
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_heap.h:404: instantiated from ‘void std::make_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int**, _Compare = Cmp2]’
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h:2475: instantiated from ‘void std::partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int**, _Compare = Cmp2]’
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h:2666: instantiated from ‘void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = int**, _Size = int, _Compare = Cmp2]’
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h:2749: instantiated from ‘void std::sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int**, _Compare = Cmp2]’
B.cxx:21: instantiated from here
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_heap.h:166: error: no match for call to ‘(Cmp2) (int*&, int*&)’
B.cxx:13: note: candidates are: bool Cmp2::operator()(const int*&, const int*&) const

Forgot to mention, I tried compiling with "true" replaced by "false", no difference. Also, when you say it compiles for you, did you uncomment out the second-to-last line in the snippet? That one's the killer.

Yes, I did. Other than several warnings, the compile succeeded.

>> error: no match for call to ‘(Cmp2) (int*&, int*&)’
>> candidates are: bool Cmp2::operator()(const int*&, const int*&) const

Perhaps your const's are wrong.

Seems to be like a problem of conversion between various pointers. That is, the type of (*b) is int*&, which you can't assign to the parameter of Cmp2, which is const int*&. I forgot the reason, but basically, while you can assign a pointer to non-const to a pointer to const, you cannot assign a pointer/reference to a pointer to non-const to a pointer/reference to a pointer to const.

So all in all, I think GCC is right and VC++ is wrong.

When I take out the first two const's in the definition of Cmp2, I get a shorter set of errors (taking out the third doesn't seem to matter):

/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h: In function ‘const _Tp& std::__median(const _Tp&, const _Tp&, const _Tp&, _Compare) [with _Tp = int*, _Compare = Cmp2]’:
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h:2679: instantiated from ‘void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = int**, _Size = int, _Compare = Cmp2]’
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h:2749: instantiated from ‘void std::sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int**, _Compare = Cmp2]’
B.cxx:21: instantiated from here
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h:125: error: no match for call to ‘(Cmp2) (int* const&, int* const&)’
B.cxx:13: note: candidates are: bool Cmp2::operator()(int*&, int*&) const
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h:126: error: no match for call to ‘(Cmp2) (int* const&, int* const&)’
B.cxx:13: note: candidates are: bool Cmp2::operator()(int*&, int*&) const
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h:128: error: no match for call to ‘(Cmp2) (int* const&, int* const&)’
B.cxx:13: note: candidates are: bool Cmp2::operator()(int*&, int*&) const
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h:132: error: no match for call to ‘(Cmp2) (int* const&, int* const&)’
B.cxx:13: note: candidates are: bool Cmp2::operator()(int*&, int*&) const
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_algo.h:134: error: no match for call to ‘(Cmp2) (int* const&, int* const&)’
B.cxx:13: note: candidates are: bool Cmp2::operator()(int*&, int*&) const

WTF?
> error: no match for call to ‘(Cmp2) (int* const&, int* const&)’

OK, now I'm confused. Try changing the type of Cmp2's parameters to "int *const &".

I changed the line in Cmp2's definition to

bool operator() (int *const &x1, int *const &x2) const {

and now it compiles! Thank you! A similar change fixed the problem I was having in my original code. It will take a while to understand exactly what's going on, though.