strange error at std::cout

[nuderobmonkey]

I tried to implement a partitioning algorithm for later using at quicksort, but when I try to compile, I get a long list of errors (several pages long).

#include <algorithm>


template <typename Iterator, class Compare>
int partitition( Iterator begin, Iterator end, Compare cmp)
{
    if( end - begin < 1 ) return -1;
    if( end - begin == 1 ) return 0; 
    
    Iterator pivot = begin;
    Iterator last_greater = begin + 1;
    Iterator current = begin + 1;
    
    while( current != end )
    {
        if( cmp(*current,*pivot) ) {
            std::swap(*last_greater,*pivot);
            ++ last_greater;
        }
        ++ current;
    }
    std::swap( *(last_greater-1), *pivot );
    return last_greater - 1 - begin;
}

#include <iostream>
#include <string>

int main()
{
    std::string test = "cbad";
    std::cout << test << '\n';
    std::cout << partition( test.begin(),test.end(),[](char a, char b){return a < b;} ) << '\n';
    std::cout << test << '\n';
}

Any idea what's wrong with?

[MikeyBoy]

You missed the semicolon at the and of your class template definition.
Apologies - it's not a class template, it's a function template.

[nuderobmonkey]

What do you mean?

[nuderobmonkey]

I found my error: a misspell at the function template. So far ok.

But now I get an error about my function name:

sort.cpp:33:87: error: call of overloaded ‘partition(std::__cxx11::basic_string<char>::iterator, std::__cxx11::basic_string<char>::iterator, main()::<lambda(char, char)>)’ is ambiguous
 partition( test.begin(),test.end(),[](char a, char b){return a < b;} ) << '\n';
                                                                      ^
sort.cpp:5:5: note: candidate: int partition(Iterator, Iterator, Compare) [with Iterator = __gnu_cxx::__normal_iterator<char*, std::__cxx11::basic_string<char> >; Compare = main()::<lambda(char, char)>]
 int partition( Iterator begin, Iterator end, Compare cmp)
     ^~~~~~~~~
In file included from /usr/include/c++/7/algorithm:62:0,
                 from sort.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:4643:5: note: candidate: _BIter std::partition(_BIter, _BIter, _Predicate) [with _BIter = __gnu_cxx::__normal_iterator<char*, std::__cxx11::basic_string<char> >; _Predicate = main()::<lambda(char, char)>]
     partition(_ForwardIterator __first, _ForwardIterator __last,
     ^~~~~~~~~

This error disappears if I chose another name for this function.
But, why could my partition() be overloaded although it's not in the std namespace?

[Ganado]

This... Might be Argument Dependent lookup (ADL). Try putting your function template in it's own namespace like "util:: partition"

[nuderobmonkey]

Thanks, this works.

[doug4]

The namespace may be a fine resolution, but I don't understand why std::partition() was originally found as a candidate for partition().

"Corrected" code from the first post:

#include <algorithm>


template <typename Iterator, class Compare>
int partition( Iterator begin, Iterator end, Compare cmp)
{
    if( end - begin < 1 ) return -1;
    if( end - begin == 1 ) return 0; 
    
    Iterator pivot = begin;
    Iterator last_greater = begin + 1;
    Iterator current = begin + 1;
    
    while( current != end )
    {
        if( cmp(*current,*pivot) ) {
            std::swap(*last_greater,*pivot);
            ++ last_greater;
        }
        ++ current;
    }
    std::swap( *(last_greater-1), *pivot );
    return last_greater - 1 - begin;
}

#include <iostream>
#include <string>

int main()
{
    std::string test = "cbad";
    std::cout << test << '\n';
    std::cout << partition( test.begin(),test.end(),[](char a, char b){return a < b;} ) << '\n';
    std::cout << test << '\n';
}

[Ganado]

The part I don't understand is that std::partition expects a UnaryPredicate for the syntax to succeed, but nuderobmonkey is providing a BinaryPredicate.

I guess it sees the overload resolution conflict before it even tries to parse the function generated?

This is a similar SO post, but they're using a UnaryPredicate so it makes more sense that it's failing: https://stackoverflow.com/questions/30943466/clang-error-call-to-partition-is-ambiguous
I don't know enough about template overload resolution, but I think the issue is that both the user-defined partition and std::partition are both of type

template <typename T, class U>
<???> partitition(T begin, T end, U cmp)

Same error without using <algorithm>, so that we can see everything:

// Trying to avoid #include <algorithm>
#include <utility> // std::swap
#include <iterator> // std::next

// https://en.cppreference.com/w/cpp/algorithm/find (2nd version)
template<class InputIt, class UnaryPredicate>
constexpr InputIt find_if(InputIt first, InputIt last, UnaryPredicate p)
{
    for (; first != last; ++first) {
        if (p(*first)) {
            return first;
        }
    }
    return last;
}

#if 1
// https://en.cppreference.com/w/cpp/algorithm/partition
template<class ForwardIt, class UnaryPredicate>
ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPredicate p)
{
    first = find_if_not(first, last, p);
    if (first == last) return first;
 
    for (ForwardIt i = std::next(first); i != last; ++i) {
        if (p(*i)) {
            std::iter_swap(i, first);
            ++first;
        }
    }
    return first;
}
#endif

// http://www.cplusplus.com/forum/general/265317/
template <typename Iterator, class Compare>
int partition( Iterator begin, Iterator end, Compare cmp)
{
    if( end - begin < 1 ) return -1;
    if( end - begin == 1 ) return 0; 
    
    Iterator pivot = begin;
    Iterator last_greater = begin + 1;
    Iterator current = begin + 1;
    
    while( current != end )
    {
        if( cmp(*current,*pivot) ) {
            std::swap(*last_greater,*pivot);
            ++ last_greater;
        }
        ++ current;
    }
    std::swap( *(last_greater-1), *pivot );
    return last_greater - 1 - begin;
}

#include <iostream>
#include <string>

int main()
{
    std::string test = "cbad";
    std::cout << test << '\n';
    std::cout << partition( test.begin(),test.end(),[](char a, char b){return a < b;} ) << '\n';
    std::cout << test << '\n';
}

Will compile if you change the #if 1 to an #if 0

[mbozzi]

Some implementations have the type of test.begin() as part of the standard namespace (it could be char*).

Those implementations will perform argument-dependent lookup, find std::partition (if it happens to be included, directly or indirectly, by the user or the implementation), and fail to choose between the two unconstrained candidates.

Very roughly, the process works like this:
1. Name lookup finds all the functions and function templates with a particular name, and produces a list of all the stuff;
2. Template arguments are deduced, if required, then substituted into each function template in the list from step one, producing a list of candidate functions from the list of functions and function templates. Finally,
3. Overload resolution selects the single best choice from all the candidates.

To disable ADL, either qualify the function name ::partition(...) or parenthesize it (partition)(...).

I guess it sees the overload resolution conflict before it even tries to parse the function generated?

In step 2, there is an opportunity to reject function templates early, but the standard library is not taking advantage of it:

If either:
a.) template argument deduction would form an invalid type or expression in the template argument list; or
b.) template argument substitution would form an invalid type or expression in the signature of the new candidate function;
then the candidate function is discarded.

This is called Substitution Failure is Not an Error, or SFINAE. It turns out to be a really powerful (if awkward) tool for manipulating overload resolution.

The compiler only considers the function signature. Even though a call to std::partition wouldn't compile, it's not rejected because the candidate's signature is completely fine.

In order to exploit SFINAE here, the standard library would need to write a meta-program that provokes substitution failure when the template arguments don't meet std::partition's requirements - in this case, when the user doesn't pass a UnaryFunction.

This is a difficult and subtle task, so C++20 is introducing a new major feature, called concepts, to address exactly this problem:
http://www.stroustrup.com/good_concepts.pdf

[Ganado]

The compiler only considers the function signature. Even though a call to std::partition wouldn't compile, it's not rejected because the candidate's signature is completely fine.

Makes sense, thanks. I also had the thought that this could be solved with concepts; I look forward to that.