Error C2914: sort function unable to identify which version of an overloaded predicate to use

Question

I have recently started trying to teach myself C++ and am new to the board. I have created a strut called permuted_index, and a vector of permuted_index objects called perm_index.

I have written an overloaded predicate called "stringCompare" to be used with the sort function to sort either a vector of strings or a vector of permuted_index objects. However, when I try and run my program get error C2914 - which as I understand it means that the sort function can not identify which of version of stringCompare to use.

I have been looking at this for days and am completely stumped! I can force my program to work by commenting out one version of the predicate, but I would really like to understand the underlying program and would appreciate any help. I have provided everything that I think will help anyone looking at this below but if you need any more information please let me know.

This is the permuted index strut;

struct permuted_index{

std::string word ;

std::vector<std::string>::size_type line ;
std::string::size_type position ; 

std::vector<std::string> full_line ;
std::vector<std::string> rotated_line ; 

std::string before_word ;
std::string after_word ; };

This is the overloaded predicate;

#include <string>  
#include <vector> 
#include "split.h" 
#include "Permuted_index.h"

using std::string ; 
using std::vector ; 

bool stringCompare(const string& x, const string& y) {

vector<string> p ;
vector<string> q ; 

p = split(x) ; 
q = split(y) ; 

return p[0] < q[0] ;
}


bool stringCompare(const permuted_index& x, const permuted_index& y){

return x.rotated_line[0] < y.rotated_line[0] ; 
}

This is the split function called above;

vector<string> split(const string& s) 
{
    vector<string> ret ;
    typedef string::size_type string_size ; 

    string_size i = 0 ; 

    while(i != s.size())
    {
    while(i != s.size() && isspace(s[i]))
    {
        ++i ;
    }

    string_size j = i ; 

    while(j != s.size() && !isspace(s[j]))
    {
        ++j ;
    }

    if(i != j)
    {
        ret.push_back(s.substr(i, j-i)) ;
        i = j ;
    }
}

return ret ;
}

The line within my main() program that is causing the error is;

sort(perm_index.begin(), perm_index.end(), stringCompare) ;

and the the exact error message is:

error C2914: 'std::sort' : cannot deduce template argument as function   argument is ambiguous

Answer 1

Try the following

sort(perm_index.begin(), perm_index.end(), 
     static_cast<bool(*)( const permuted_index &, const permuted_index & )>(stringCompare) );

Answer 2

For some reason, using a cast seems a little iffy to me. But this works:

void foo(std::vector<permuted_index> &pi)
{
    using Compare = bool (*)(const permuted_index &, const permuted_index&);
    Compare cmp = stringCompare;
    std::sort(pi.begin(), pi.end(), cmp);
}

This declares a type alias, Compare.

Before C++ 11 this was done with what is called a typedef, as in:

typedef bool (*Compare)(const permuted_index &, const permuted_index &);

These both just say that Compare is a name for a function that takes two permuted_index objects and returns a bool. (Technically Compare is a pointer to a function but function names by themselves are also pointers.) The C/C++ syntax for function type names is not exactly the easiest thing to parse but if you read the typedef from the inside out it in sort of a left-right order (the "spiral" rule) it says Compare is a pointer (the asterisk) to a function taking two permuted_index references (the parentheses enclosing the reference declarations to the right) and returning bool) You can find a nice SO description of these topics here and there are various tutorials on function pointer syntax (evidence in and of itself that it isn't the simplest aspect of C/C++) around the web, such as this article that explains the spiral rule.

Anyway, Compare is an alias for a function of precisely the type that sort expects for a comparator when sorting permuted_index objects. We then declare a pointer instance, cmp that points to stringCompare. The compiler now knows precisely the type of cmp so there is no ambiguity as to which stringCompare we can assign to cmp.

As another aside, cmp is a pointer and you could actually write

Compare cmp = &stringCompare;

In C++, the name of a function by itself "decays" to a pointer to that function, so this is redundant and I left it out in my example.

Another approach is to an inline lambda. Lambdas are a new part of the language that allow you to declare a function in-place. This is a very useful syntax for things like comparators that are often only used once, when the algorithm is called. Like function pointers, the syntax takes a bit of getting used to. Here is a nice SO article on the subject. Basically the [] signals that this is a simple lambda (not a "closure" of any sort), this is followed by the arguments to the lambda, which is then followed by its body. (You can optionally declare the return type right after the arguments as

[](const permuted_index &, const permuted_index &) -> bool { ... }

but this isn't usually necessary as the compiler can infer the type from the function body.)

Anyway, as with the typedef above, this approach works because the lambda has declared what the arguments are so the right stringCompare will be chosen, and the type of the lambda is obvious to the compiler so there is no confusion over which function type to use to figure out the second template type in sort.

void bar(std::vector<permuted_index> &pi)
{
    std::sort(pi.begin(), pi.end(), 
              [](const permuted_index &a, const permuted_index &b) 
              { return stringCompare(a,b); });
}

I believe the issue is that the Compare template parameter is completely independent of the type being compared - there isn't currently a way for the library to specify that its type should have the signature of a comparison between the two value types being sorted on. (Though I'm not exactly sure why SFINAE doesn't remove the possibility of using the first overload.)