Jonathan Boccara's blog

Tweet

How to Use is_permutation on Collections of Different Types

Published June 28, 2019 - 0 Comments

std::is_permutation is an STL algorithm that checks if two collections contain the same values, but not necessarily in the same order.

We have encountered is_permutation in the STL algorithms on permutations, and we’ve seen how it was implemented. If you’d like a refresher on std::permutation, check out those two articles to get warmed up.

Today we’re focusing on a particular requirement that the C++ standard specifies for std::permutation: both collections have to contain values of the same type.

More precisely, given the prototype of is_permutation:

template<typename ForwardIterator1, typename ForwardIterator2>
bool is_permutation(ForwardIterator1 first1, ForwardIterator1last1,
                    ForwardIterator2 first2, ForwardIterator2 last2,
                    Predicate comparator)

Then the value types of ForwardIterator1 and ForwardIterator2 must be the same.

Why is there such a requirement? Is this a problem? How can we work around it? This is what we tackle in this article.

The reason of the requirement

…is unknown to me. If you know why it’s there, please let us know.

At first glance, it seems like it doesn’t make sense. Indeed, if you take std::equal for example, you’ll see that it doesn’t have such a requirement. Indeed, if you pass in a custom comparison operator to std::equal, the algorithm is happy to use it to compare elements of potentially different types.

So why the requirement for is_permutation?

We can take a guess. There is something different between std:equal and std::is_permutation. If you remember the implementation of std::is_permutation, we had to perform comparisons between elements from the two collections, but also between elements inside of the first collection:

template<typename ForwardIterator1, typename ForwardIterator2, typename Predicate>
bool my_is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
                       ForwardIterator2 first2, ForwardIterator2 last2,
                       Predicate pred)
{
    if (std::distance(first1, last1) != std::distance(first2, last2)) return false;

    auto const [firstDifferent1, firstDifferent2] = std::mismatch(first1, last1, first2, last2, pred);
    
    for (auto current1 = firstDifferent1; current1 != last1; ++current1)
    {
        auto equalToCurrent1 = [&pred, &current1](auto const& value){ return pred(value, *current1); };
        if (std::find_if(firstDifferent1, current1, equalToCurrent1) == current1)
        {
            auto const numberOfOccurencesIn2 = std::count_if(firstDifferent2, last2, equalToCurrent1);
            if (numberOfOccurencesIn2 == 0 || numberOfOccurencesIn2 != std::count_if(std::next(current1), last1, equalToCurrent1) + 1)
            {
                return false;
            }
        }
    }
    return true;
}

So maybe the requirement comes from the fact that the comparison function needs to also be able to compare elements from the first collection together, and making sure that both collections have the same value type makes things easier.

But whatever the reason, is this requirement a problem in practice?

What having the same value types prevents us to do

It is. Consider the following example:

std::vector<int> numbers = {1, 2, 42, 100, 256 };
std::vector<std::string> textNumbers = {"100", "256", "2", "1", "42" };

We have two collections representing the same values, but expressed with different types. An embodying use case would be to validate user inputs (in text format) against expected inputs (in numerical format) without taking account of the order.

A more elaborate example would be a collection of values that embed a key, such as an ID, and that we’d like to compare with a collection of such IDs:

class Object
{
public:
    explicit Object(int ID) : ID_(ID) {}
    int getID() const { return ID_; }
private:    
    int ID_;
};

We would like to write a piece of code like this:

std::vector<Object> objects = { Object(1), Object(2), Object(3), Object(4), Object(5) };
std::vector<int> IDs = {4, 5, 2, 3, 1};

auto const sameIDs = std::is_permutation(begin(objects), end(objects),
                                         begin(IDs), end(IDs),
                                         compareObjectWithID);

But there are two problems with this code:

  • Problem 1:std::is_permutation is not allowed to take two collections of different value types,
  • Problem 2: even if it was, how do we write the function compareObjectWithID?

Alternatively, we could make a transform of the objects into a new collection of keys. But let’s say that we don’t want to instantiate a new collection and burden our calling code with it.

Checking for a permutation on different types

To solve problem 1, one way is to use a custom implementation, like the one provided at the beginning of this post.

It’s a sad solution, because it prevents us from using the standard implementation of std::is_permutation. And what makes it even sadder is that the standard implementations I’ve checked produced the correct result anyway.

But the C++ standard forbids it, so using std::is_permutation with elements of different types is technically undefined behaviour. We don’t want to go down that road.

So let’s assume that we use our own implementation of is_permutation. How do we implement a comparison function that works on different types? How do we solve Problem 2?

Indeed, notice that just comparing the two different types in the function is not enough. For example, if we use the following comparison function:

bool compareObjectWithID(int ID1, Object const& object2)
{
    return ID1 == object2.getID();
}

We get the following lovely compilation error (open only if you appreciate template errors):

In file included from /usr/local/include/c++/8.1.0/bits/stl_algobase.h:71,
from /usr/local/include/c++/8.1.0/algorithm:61,
from main.cpp:1:
/usr/local/include/c++/8.1.0/bits/predefined_ops.h: In instantiation of ‘constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = __gnu_cxx::__normal_iterator<Object*, std::vector<Object> >; _Iterator2 = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = bool (*)(int, const Object&)]’:
/usr/local/include/c++/8.1.0/bits/stl_algobase.h:1356:23:   required from ‘std::pair<_T1, _T2> std::__mismatch(_InputIterator1, _InputIterator1, _InputIterator2, _InputIterator2, _BinaryPredicate) [with _InputIterator1 = __gnu_cxx::__normal_iterator<Object*, std::vector<Object> >; _InputIterator2 = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _BinaryPredicate = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, const Object&)>]’
/usr/local/include/c++/8.1.0/bits/stl_algobase.h:1426:40:   required from ‘std::pair<_T1, _T2> std::mismatch(_InputIterator1, _InputIterator1, _InputIterator2, _InputIterator2, _BinaryPredicate) [with _InputIterator1 = __gnu_cxx::__normal_iterator<Object*, std::vector<Object> >; _InputIterator2 = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _BinaryPredicate = bool (*)(int, const Object&)]’
main.cpp:14:66:   required from ‘bool my_is_permutation(ForwardIterator1, ForwardIterator1, ForwardIterator2, ForwardIterator2, Predicate) [with ForwardIterator1 = __gnu_cxx::__normal_iterator<Object*, std::vector<Object> >; ForwardIterator2 = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; Predicate = bool (*)(int, const Object&)]’
main.cpp:72:51:   required from here
/usr/local/include/c++/8.1.0/bits/predefined_ops.h:143:18: error: cannot convert ‘Object’ to ‘int’ in argument passing
{ return bool(_M_comp(*__it1, *__it2)); }
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp: In instantiation of ‘my_is_permutation(ForwardIterator1, ForwardIterator1, ForwardIterator2, ForwardIterator2, Predicate) [with ForwardIterator1 = __gnu_cxx::__normal_iterator<Object*, std::vector<Object> >; ForwardIterator2 = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; Predicate = bool (*)(int, const Object&)]::<lambda(const auto:1&)> [with auto:1 = Object]’:
/usr/local/include/c++/8.1.0/bits/predefined_ops.h:283:11:   required from ‘bool __gnu_cxx::__ops::_Iter_pred<_Predicate>::operator()(_Iterator) [with _Iterator = __gnu_cxx::__normal_iterator<Object*, std::vector<Object> >; _Predicate = my_is_permutation(ForwardIterator1, ForwardIterator1, ForwardIterator2, ForwardIterator2, Predicate) [with ForwardIterator1 = __gnu_cxx::__normal_iterator<Object*, std::vector<Object> >; ForwardIterator2 = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; Predicate = bool (*)(int, const Object&)]::<lambda(const auto:1&)>]’
/usr/local/include/c++/8.1.0/bits/stl_algo.h:3194:12:   required from ‘typename std::iterator_traits<_Iterator>::difference_type std::__count_if(_InputIterator, _InputIterator, _Predicate) [with _InputIterator = __gnu_cxx::__normal_iterator<Object*, std::vector<Object> >; _Predicate = __gnu_cxx::__ops::_Iter_pred<my_is_permutation(ForwardIterator1, ForwardIterator1, ForwardIterator2, ForwardIterator2, Predicate) [with ForwardIterator1 = __gnu_cxx::__normal_iterator<Object*, std::vector<Object> >; ForwardIterator2 = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; Predicate = bool (*)(int, const Object&)]::<lambda(const auto:1&)> >; typename std::iterator_traits<_Iterator>::difference_type = long int]’
/usr/local/include/c++/8.1.0/bits/stl_algo.h:4105:29:   required from ‘typename std::iterator_traits<_Iterator>::difference_type std::count_if(_IIter, _IIter, _Predicate) [with _IIter = __gnu_cxx::__normal_iterator<Object*, std::vector<Object> >; _Predicate = my_is_permutation(ForwardIterator1, ForwardIterator1, ForwardIterator2, ForwardIterator2, Predicate) [with ForwardIterator1 = __gnu_cxx::__normal_iterator<Object*, std::vector<Object> >; ForwardIterator2 = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; Predicate = bool (*)(int, const Object&)]::<lambda(const auto:1&)>; typename std::iterator_traits<_Iterator>::difference_type = long int]’
main.cpp:22:85:   required from ‘bool my_is_permutation(ForwardIterator1, ForwardIterator1, ForwardIterator2, ForwardIterator2, Predicate) [with ForwardIterator1 = __gnu_cxx::__normal_iterator<Object*, std::vector<Object> >; ForwardIterator2 = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; Predicate = bool (*)(int, const Object&)]’
main.cpp:72:51:   required from here
main.cpp:18:82: error: cannot convert ‘const Object’ to ‘int’ in argument passing
auto equalToCurrent1 = [&pred, ¤t1](auto const& value){ return pred(value, *current1); };
~~~~^~~~~~~~~~~~~~~~~~
In file included from /usr/local/include/c++/8.1.0/bits/stl_algobase.h:71,
from /usr/local/include/c++/8.1.0/algorithm:61,
from main.cpp:1:
/usr/local/include/c++/8.1.0/bits/predefined_ops.h: In instantiation of ‘bool __gnu_cxx::__ops::_Iter_pred<_Predicate>::operator()(_Iterator) [with _Iterator = __gnu_cxx::__normal_iterator<Object*, std::vector<Object> >; _Predicate = my_is_permutation(ForwardIterator1, ForwardIterator1, ForwardIterator2, ForwardIterator2, Predicate) [with ForwardIterator1 = __gnu_cxx::__normal_iterator<Object*, std::vector<Object> >; ForwardIterator2 = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; Predicate = bool (*)(int, const Object&)]::<lambda(const auto:1&)>]’:
/usr/local/include/c++/8.1.0/bits/stl_algo.h:3194:12:   required from ‘typename std::iterator_traits<_Iterator>::difference_type std::__count_if(_InputIterator, _InputIterator, _Predicate) [with _InputIterator = __gnu_cxx::__normal_iterator<Object*, std::vector<Object> >; _Predicate = __gnu_cxx::__ops::_Iter_pred<my_is_permutation(ForwardIterator1, ForwardIterator1, ForwardIterator2, ForwardIterator2, Predicate) [with ForwardIterator1 = __gnu_cxx::__normal_iterator<Object*, std::vector<Object> >; ForwardIterator2 = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; Predicate = bool (*)(int, const Object&)]::<lambda(const auto:1&)> >; typename std::iterator_traits<_Iterator>::difference_type = long int]’
/usr/local/include/c++/8.1.0/bits/stl_algo.h:4105:29:   required from ‘typename std::iterator_traits<_Iterator>::difference_type std::count_if(_IIter, _IIter, _Predicate) [with _IIter = __gnu_cxx::__normal_iterator<Object*, std::vector<Object> >; _Predicate = my_is_permutation(ForwardIterator1, ForwardIterator1, ForwardIterator2, ForwardIterator2, Predicate) [with ForwardIterator1 = __gnu_cxx::__normal_iterator<Object*, std::vector<Object> >; ForwardIterator2 = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; Predicate = bool (*)(int, const Object&)]::<lambda(const auto:1&)>; typename std::iterator_traits<_Iterator>::difference_type = long int]’
main.cpp:22:85:   required from ‘bool my_is_permutation(ForwardIterator1, ForwardIterator1, ForwardIterator2, ForwardIterator2, Predicate) [with ForwardIterator1 = __gnu_cxx::__normal_iterator<Object*, std::vector<Object> >; ForwardIterator2 = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; Predicate = bool (*)(int, const Object&)]’
main.cpp:72:51:   required from here
/usr/local/include/c++/8.1.0/bits/predefined_ops.h:283:11: error: void value not ignored as it ought to be
{ return bool(_M_pred(*__it)); }
^~~~~~~~~~~~~~~~~~~~

The problem is that the algorithm can call the predicates with different combinations of types: it can be with one Object and one int, or with two Objects for example. So to be on the safe side, we’d like to cram the 4 possible combinations of int and Object into the comparison function.

How do we cram several functions into one? With the double functor trick!

Or rather here, it would be the quadruple functor trick:

struct CompareObjectWithID
{
bool operator()(int ID1, int ID2)
{
return ID1 == ID2;
}
bool operator()(int ID1, Object const& object2)
{
return ID1 == object2.getID();
}
bool operator()(Object const& object1, int ID2)
{
return (*this)(ID2, object1);
}
bool operator()(Object const& object1, Object const& object2)
{
return object1.getID() == object2.getID();
}
};

We can use it this way:

std::vector<Object> objects = { Object(1), Object(2), Object(3), Object(4), Object(5) };
std::vector<int> IDs = {4, 5, 2, 3, 1};
auto const sameIDs = my_is_permutation(begin(objects), end(objects),
begin(IDs), end(IDs),
CompareObjectWithID{}) << '\n';

Thoughts?

All this lets us perform a check for permutations on two collections with different value types. But if you have a different view on this subject, I’d be glad to hear it.

Do you know the reason for the requirement on is_permutation to operate on values of the same type?

Do you see a better way to work around that constraint, without resorting to creating an intermediary collection?

Did you ever encouter that need for is_permutation?

You will also like

Don't want to miss out ? Follow:   twitterlinkedinrss
Share this post!Facebooktwitterlinkedin