Why does the std::copy_if signature not constrain the predicate type

Question

Imagine we have the following situation:

struct A
{
    int i;
};

struct B
{
    A a;
    int other_things;
};

bool predicate( const A& a)
{
    return a.i > 123;
}

bool predicate( const B& b)
{
    return predicate(b.a);
}

int main()
{
    std::vector< A > a_source;
    std::vector< B > b_source;

    std::vector< A > a_target;
    std::vector< B > b_target;

    std::copy_if(a_source.begin(), a_source.end(), std::back_inserter( a_target ), predicate);
    std::copy_if(b_source.begin(), b_source.end(), std::back_inserter( b_target ), predicate);

    return 0;
}

Both the call to std::copy_if generate a compile error, because the correct overload of predicate() function cannot be infered by the compiler since the std::copy_if template signature accepts any type of predicate:

template<typename _IIter, 
         typename _OIter, 
         typename _Predicate>
_OIter copy_if( // etc...

I found the overload resolution working if I wrap the std::copy_if call into a more constrained template function:

template<typename _IIter, 
         typename _OIter, 
         typename _Predicate = bool( const typename std::iterator_traits<_IIter>::value_type& ) >
void copy_if( _IIter source_begin, 
              _IIter source_end, 
              _OIter target,  
              _Predicate pred)
{
    std::copy_if( source_begin, source_end, target, pred );
} 

My question is: why in the STL is it not already constrained like this? From what I've seen, if the _Predicate type is not a function that returns bool and accepts the iterated input type, it is going to generate a compiler error anyway. So why not putting this constrain already in the signature, so that overload resolution can work?

Answer 1

Because the predicate does not have to be a function, but it can be a functor too. And restricting functor type is close to impossible since it can be anything at all as long as it has operator() defined.

Actually I suggest you convert the overloaded function to a polymorphic functor here:

struct predicate {
    bool operator()( const A& a) const
    {
        return a.i > 123;
    }

    bool operator()( const B& b) const
    {
        return operator()(b.a);
    }
}

and call the functor with an instance, i.e.

std::copy_if(a_source.begin(), a_source.end(), std::back_inserter( a_target ), predicate());
std::copy_if(b_source.begin(), b_source.end(), std::back_inserter( b_target ), predicate());
//                                                                                      ^^ here, see the ()

Then the correct overload will be selected inside the algorithm.

Answer 2

This problem does not only affect predicates to algorithms. It occurs anywhere that template type deduction deduces an overloaded function. Template type deduction happens before overload resolution, so the compiler lacks the contextual information to resolve the ambiguity.

The correctly written constraint would be hideously complex, as it would need to take into account argument and return type conversions, binds, lambdas, functors, mem_fns and so on.

An easy way to solve the ambiguity (IMHO) is to call the predicate through a lambda.

std::copy_if(a_source.begin(), a_source.end(), 
         std::back_inserter( a_target ), 
         [](auto&& x){ return predicate(std::forward<decltype(x)>(x)); });

This defers overload resolution until after template type deduction.

What if I refuse (or my boss refuses) to upgrade to c++14

Then hand-roll the same lambda:

struct predicate_caller
{
  template<class T>
  decltype(auto) operator()(T&& t) const 
  {
    return predicate(std::forward<T>(t));
  }
};

and call like so:

std::copy_if(b_source.begin(), b_source.end(), 
             std::back_inserter( b_target ), 
             predicate_caller());