Why can't std::is_permutation act between two different types of data?

Question

Suppose I have a vector of integers and of strings, and I want to compare whether they have equivalent elements, without consideration of order. Ultimately, I'm asking if the integer vector is a permutation of the string vector (or vice versa). I'd like to be able to just call is_permutation, specify a binary predicate that allows me to compare the two, and move on with my life. eg:

bool checkIntStringComparison( const std::vector<int>& intVec,
                 const std::vector<std::string>& stringVec,
                 const std::map<int, std::string>& intStringMap){
  return std::is_permutation<std::vector<int>::const_iterator, std::vector<std::string>::const_iterator>(
        intVec.cbegin(), intVec.cend(), stringVec.cbegin(), [&intStringMap](const int& i, const std::string& string){
    return string == intStringMap.at(i);
  });
}

But trying to compile this (in gcc) returns an error message that boils down to:

no match for call to stuff::< lambda(const int&, const string& >)(const std::_cxx11::basic_string&, const int&)

see how it switches the calling signature from the lambda's? If I switch them around, the signature switches itself the other way.

Digging around about this error, it seems that the standard specifies for std::is_permutation that ForwardIterator1 and 2 must be the same type. So I understand the compiler error in that regard. But why should it be this way? If I provide a binary predicate that allows me to compare the two (or if we had previously defined some equality operator between the two?), isn't the real core of the algorithm just searching through container 1 to make sure all its elements are in container 2 uniquely?

Answer 1

The problem is that an element can occur more than once. That means that the predicate needs to be able to not only compare the elements of the first range to the elements of the second range, but to compare the elements of the first range to themselves:

if (size(range1) != size(range2))
    return false;
for (auto const& x1 : range1)
    if (count_if(range1, [&](auto const& y1) { return pred(x1, y1); }) !=
        count_if(range2, [&](auto const& y2) { return pred(x1, y2); }))
        return false;
return true;

Since it's relatively tricky to create a function object that takes two distinct signatures, and passing two predicates would be confusing, the easiest option was to specify that both ranges must have the same value type.

Your options are:

• Wrap one range (or both) in a transform that gives the same value type (e.g. use Boost.Adaptors.Transformed);
• Write your own implementation of std::is_permutation (e.g. copying the example implementation on cppreference);
• Actually, note that the gcc (i.e. libstdc++) implementation does not enforce that the value types are the same; it just requires several signatures which you'd have to provide anyway, so write a polymorphic predicate as e.g. a function object or a polymorphic lambda, or with parameter types convertible from both range value types (e.g. in your case boost::variant<int, string> - ugly, but probably not that bad). This is non-portable, as another implementation might choose to enforce that requirement.