std::ranges:: unique

Les entités de type fonction décrites sur cette page sont des objets fonction d'algorithme (informellement appelés niebloids ), c'est-à-dire :

• Les listes d'arguments de modèle explicites ne peuvent pas être spécifiées lors de l'appel de l'une d'entre elles.
• Aucune d'entre elles n'est visible pour la recherche dépendante des arguments .
• Lorsque l'une d'entre elles est trouvée par la recherche non qualifiée normale comme nom à gauche de l'opérateur d'appel de fonction, la recherche dépendante des arguments est inhibée.

Paramètres

Valeur de retour

Retourne { ret, last } , où ret est un itérateur past-the-end pour la nouvelle fin de la plage.

Complexité

Pour les plages non vides, exactement ranges:: distance ( first, last ) - 1 applications du prédicat correspondant comp et pas plus de deux fois plus d'applications de toute projection proj .

Notes

La suppression s'effectue en décalant (au moyen d'une assignation de déplacement) les éléments de la plage de telle manière que les éléments à ne pas supprimer apparaissent au début de la plage. L'ordre relatif des éléments restants est préservé et la taille physique du conteneur reste inchangée. Les itérateurs dans [ ret , last ) (s'il y en a) restent déréférençables, mais les éléments eux-mêmes ont des valeurs non spécifiées (conformément à la post-condition de MoveAssignable ).

Un appel à ranges::unique est parfois suivi d'un appel à la fonction membre erase d'un conteneur, ce qui efface les valeurs non spécifiées et réduit la taille physique du conteneur pour correspondre à sa nouvelle taille logique . Ces deux invocations modélisent ensemble l' idiome Effacer-Supprimer .

Implémentation possible

struct unique_fn
{
    template<std::permutable I, std::sentinel_for<I> S, class Proj = std::identity,
             std::indirect_equivalence_relation<std::projected<I, Proj>>
                 C = ranges::equal_to>
    constexpr ranges::subrange<I>
        operator()(I first, S last, C comp = {}, Proj proj = {}) const
    {
        first = ranges::adjacent_find(first, last, comp, proj);
        if (first == last)
            return {first, first};
        auto i {first};
        ++first;
        while (++first != last)
            if (!std::invoke(comp, std::invoke(proj, *i), std::invoke(proj, *first)))
                *++i = ranges::iter_move(first);
        return {++i, first};
    }
    template<ranges::forward_range R, class Proj = std::identity,
             std::indirect_equivalence_relation<std::projected<ranges::iterator_t<R>, Proj>>
                 C = ranges::equal_to>
    requires std::permutable<ranges::iterator_t<R>>
    constexpr ranges::borrowed_subrange_t<R>
        operator()(R&& r, C comp = {}, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r), ranges::end(r),
                       std::move(comp), std::move(proj));
    }
};
inline constexpr unique_fn unique {};

Exemple

#include <algorithm>
#include <cmath>
#include <complex>
#include <iostream>
#include <vector>
struct id {
    int i;
    explicit id(int i) : i {i} {}
};
void print(id i, const auto& v)
{
    std::cout << i.i << ") ";
    std::ranges::for_each(v, [](auto const& e) { std::cout << e << ' '; });
    std::cout << '\n';
}
int main()
{
    // un vecteur contenant plusieurs éléments dupliqués
    std::vector<int> v {1, 2, 1, 1, 3, 3, 3, 4, 5, 4};
    print(id {1}, v);
    // supprimer les doublons consécutifs (adjacents)
    const auto ret = std::ranges::unique(v);
    // v contient maintenant {1 2 1 3 4 5 4 x x x}, où 'x' est indéterminé
    v.erase(ret.begin(), ret.end());
    print(id {2}, v);
    // tri suivi de unique, pour supprimer tous les doublons
    std::ranges::sort(v); // {1 1 2 3 4 4 5}
    print(id {3}, v);
    const auto [first, last] = std::ranges::unique(v.begin(), v.end());
    // v contient maintenant {1 2 3 4 5 x x}, où 'x' est indéterminé
    v.erase(first, last);
    print(id {4}, v);
    // unique avec comparaison et projection personnalisées
    std::vector<std::complex<int>> vc { {1, 1}, {-1, 2}, {-2, 3}, {2, 4}, {-3, 5} };
    print(id {5}, vc);
    const auto ret2 = std::ranges::unique(vc,
        // considérer deux nombres complexes égaux si leurs parties réelles sont égales en module :
        [](int x, int y) { return std::abs(x) == std::abs(y); }, // comp
        [](std::complex<int> z) { return z.real(); }             // proj
    );
    vc.erase(ret2.begin(), ret2.end());
    print(id {6}, vc);
}

1) 1 2 1 1 3 3 3 4 5 4
2) 1 2 1 3 4 5 4
3) 1 1 2 3 4 4 5
4) 1 2 3 4 5
5) (1,1) (-1,2) (-2,3) (2,4) (-3,5)
6) (1,1) (-2,3) (-3,5)

Voir aussi