std::is_permutation

template< class ForwardIt1, class ForwardIt2 >
bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,
                     ForwardIt2 first2 );

template< class ForwardIt1, class ForwardIt2,
          class BinaryPredicate >
bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,
                     ForwardIt2 first2, BinaryPredicate p );

template< class ForwardIt1, class ForwardIt2 >
bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,
                     ForwardIt2 first2, ForwardIt2 last2 );

template< class ForwardIt1, class ForwardIt2,
          class BinaryPredicate >
bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,
                     ForwardIt2 first2, ForwardIt2 last2,
                     BinaryPredicate p );

Vérifie si [first1, last1) est une permutation d’une plage commençant à first2:

• Pour les surcharges (1,2), la deuxième plage a std::distance(first1, last1) éléments.
• Pour les surcharges (3,4), la deuxième plage est [first2, last2).

Si ForwardIt1 et ForwardIt2 ont des types de valeur différents, le programme est mal formé.

Si la fonction de comparaison n’est pas une relation d’équivalence, le comportement est indéfini.

Paramètres

Valeur de retour

true si la plage [first1, last1) est une permutation de la plage [first2, last2), false sinon.

Complexité

Étant donné \(\scriptsize N\)N comme std::distance(first1, last1):

Implémentation possible

template<class ForwardIt1, class ForwardIt2>
bool is_permutation(ForwardIt1 first, ForwardIt1 last,
                    ForwardIt2 d_first)
{
    // skip common prefix
    std::tie(first, d_first) = std::mismatch(first, last, d_first);
    
    // iterate over the rest, counting how many times each element
    // from [first, last) appears in [d_first, d_last)
    if (first != last)
    {
        ForwardIt2 d_last = std::next(d_first, std::distance(first, last));
        for (ForwardIt1 i = first; i != last; ++i)
        {
            if (i != std::find(first, i, *i))
                continue; // this *i has been checked
            
            auto m = std::count(d_first, d_last, *i);
            if (m == 0 || std::count(i, last, *i) != m)
                return false;
        }
    }
    return true;
}

Note

La std::is_permutation peut être utilisée dans les tests, à savoir pour vérifier la correction des algorithmes de réarrangement (par ex. tri, mélange, partitionnement). Si x est une plage d’origine et y est une plage permutée, alors std::is_permutation(x, y) == true signifie que y consistent en "les mêmes" éléments, peut-être situés à d’autres positions.

Exemple

#include <algorithm>
#include <iostream>

template<typename Os, typename V>
Os& operator<<(Os& os, const V& v)
{
    os << "{ ";
    for (const auto& e : v)
        os << e << ' ';
    return os << '}';
}

int main()
{
    static constexpr auto v1 = {1, 2, 3, 4, 5};
    static constexpr auto v2 = {3, 5, 4, 1, 2};
    static constexpr auto v3 = {3, 5, 4, 1, 1};
    
    std::cout << v2 << " is a permutation of " << v1 << ": " << std::boolalpha
              << std::is_permutation(v1.begin(), v1.end(), v2.begin()) << '\n'
              << v3 << " is a permutation of " << v1 << ": "
              << std::is_permutation(v1.begin(), v1.end(), v3.begin()) << '\n';
}

{ 3 5 4 1 2 } is a permutation of { 1 2 3 4 5 }: true
{ 3 5 4 1 1 } is a permutation of { 1 2 3 4 5 }: false

Voir aussi