Another problem with templates

This is a discussion on Another problem with templates within the C++ Programming forums, part of the General Programming Boards category; The following code snippet defines two binary predicates Cmp1 and Cmp2 for sorting. Cmp1 is templated, and Cmp2 is just ...

  1. #1
    Registered User
    Join Date
    Sep 2006
    Posts
    835

    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());
    }

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    7,319
    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.

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    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

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    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.

  5. #5
    Registered User
    Join Date
    Jan 2005
    Posts
    7,319
    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.

  6. #6
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    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.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    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

  8. #8
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    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 &".
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  9. #9
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Laptop Problem
    By Boomba in forum Tech Board
    Replies: 1
    Last Post: 03-07-2006, 05:24 PM
  2. Questions about Templates
    By Shamino in forum C++ Programming
    Replies: 4
    Last Post: 12-17-2005, 11:22 PM
  3. Replies: 5
    Last Post: 11-07-2005, 10:34 PM
  4. Problem with templates
    By Lazy Student in forum C++ Programming
    Replies: 3
    Last Post: 11-17-2002, 11:57 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21