Suppression de plusieurs éléments de la liste stl pendant l'itération

Question

Ceci n'est pas similaire à Can you remove elements from a std::list while iterating through it?. Le mien est un scénario différent.

Disons que j'ai une liste comme celle-ci.

1 2 3 1 2 2 1 3 

Je veux itérer cette liste stl de telle sorte que première fois que je rencontre un élément X que je fais une activité, puis-je enlever tous les éléments X dans cette liste et continuer itérer. Quel est un moyen efficace de le faire en C++.

Je suis inquiet que quand je fais un enlèvement ou un effacement je invaliderai les itérateurs. Si ce n'était qu'un élément, je pourrais éventuellement incrémenter l'itérateur et l'effacer ensuite. Mais dans mon scénario, je devrais supprimer/effacer toutes les occurrences.

Pensais quelque chose comme ça

while (!list.empty()) { 
    int num = list.front(); 
    // Do some activity and if successfull 
    list.remove(num); 
    } 

Ne pas savoir si cela est le meilleur.

Answer 1

Enregistrer un ensemble de nombres vus et si vous rencontrez un nombre dans l'ensemble ignorez-le. Vous pouvez le faire comme suit:

list<int> old_list = {1, 2, 3, 1, 2, 2, 1, 3}; 
list<int> new_list; 
set<int> seen_elements; 
for(int el : old_list) { 
    if (seen_elements.find(el) == seen_elements.end()) { 
    seen_elements.insert(el); 
    new_list.push_back(el); 
    } 
} 
return new_list; 

Cela traitera chaque valeur qu'une seule fois et la new_list ne contiendra que la première copie de chaque élément dans le old_list. Cela s'exécute dans O (n * log (n)) car chaque itération effectue une recherche de set (vous pouvez faire ce O (n) en utilisant un hashset). Ceci est significativement meilleur que le O (n^2) dans lequel votre approche s'exécute.