std::unique : Élimination des doublons consécutifs

L'algorithme std::unique permet de supprimer les éléments en double qui se suivent directement. Les doublons non adjacents ne sont pas concernés. Pour garantir la spupression de tous les doublons, il est recommandé de trier la collection au préalable.

Il est important de noter que std::unique ne réduit pas la taille physique du conteneur. Il déplace les éléments uniques vers l'avant et renvoie un itérateur pointant vers la nouvelle fin logique. La suppression physique des éléments superflus à la fin nécessite l'utilisation de la méthode erase.

À noter qu'un std::set gère naturellement l'unicité des éléments, ce qui peut parfois remplacer l'usage de std::unique.

Prototype

template <class ForwardIt>
ForwardIt unique(ForwardIt first, ForwardIt last);

template <class ForwardIt, class BinaryPredicate>
ForwardIt unique(ForwardIt first, ForwardIt last, BinaryPredicate pred);

Implémentation conceptuelle

template <class ForwardIt>
ForwardIt filtreUniques(ForwardIt debut, ForwardIt fin) {
    if (debut == fin) return fin;
    
    ForwardIt curseurUnique = debut;
    for (ForwardIt courant = std::next(debut); courant != fin; ++courant) {
        if (*courant != *curseurUnique) {
            ++curseurUnique;
            *curseurUnique = *courant;
        }
    }
    return std::next(curseurUnique);
}

Exemples d'application

std::vector<int> donnees{5, 5, 4, 3, 2, 2, 8};
auto finLogique = std::unique(donnees.begin(), donnees.end());
// donnees : 5, 4, 3, 2, 8, ?, ? (finLogique pointe vers le premier '?')

std::vector<int> valeurs{1, 9, 2, 8, 3, 7};
auto nouvelleFin = std::unique(valeurs.begin(), valeurs.end(), [](int x, int y) {
    return x + y == 10; // Supprime le second élément si leur somme vaut 10
});

La fonction std::unique_copy effectue une opération similaire mais copie le résultat vers un autre conteneur.

std::sort : Tri des éléments

Par défaut, std::sort organise les éléments par ordre croissant en utilisant operator<.

Fonceturs de comparaison usuels

• std::equal_to : x == y
• std::not_equal_to : x != y
• std::greater : x > y
• std::less : x < y
• std::greater_equal : x >= y
• std::less_equal : x <= y

Exemples d'aplpication

std::vector<int> nombres{10, 5, 20, 15, 5};

std::sort(nombres.begin(), nombres.end()); // Tri croissant : 5, 5, 10, 15, 20
std::sort(nombres.begin(), nombres.end(), std::greater<int>()); // Tri décroissant : 20, 15, 10, 5, 5
std::sort(nombres.begin(), nombres.end(), std::less<int>()); // Tri croissant explicite

// Tri personnalisé avec lambda
std::sort(nombres.begin(), nombres.end(), [](int a, int b) {
    return a > b; // Décroissant
});

erase : Suppression effective dans les conteneurs

L'en-tête <algorithm> ne fournit pas de fonction erase. La suppression d'éléments se fait via les méthodes membres des conteneurs (comme std::vector, std::list, etc.).

Pour un std::vector, la méthode erase se décline en deux surcharges :

iterator erase(const_iterator position); // Supprime un seul élément
iterator erase(const_iterator first, const_iterator last); // Supprime une plage d'éléments

L'idiome classique pour effacer définitivement les doublons après un appel à std::unique consiste à utiliser erase avec la plage allant de l'itérateur renvoyé jusqu'à la fin du conteneur :

auto itFin = std::unique(donnees.begin(), donnees.end());
donnees.erase(itFin, donnees.end());