Comment effacer les éléments des conteneurs STL ?

Question

Comment effacer les éléments des conteneurs STL, ayant une spécification valeur ou en satisfaisant certaines condition ?

Existe-t-il une façon commune ou uniforme de procéder pour les différents types de conteneurs ?

Answer 1

Malheureusement, il n'y a pas une seule uniforme interface ou un modèle pour effacer les éléments des conteneurs STL. Mais trois comportements émergent :

std::vector Pattern

Pour effacer les éléments qui remplissent une certaine condition d'une std::vector une technique courante est celle dite effacer-renverser idiome .

Si v est une instance de std::vector et nous voulons effacer les éléments ayant une valeur x du vecteur, un code comme celui-ci peut être utilisé :

// Erase elements having value "x" from vector "v"
v.erase( std::remove(v.begin(), v.end(), x), v.end() );

Si le critère à remplir pour l'effacement des éléments est plus complexe que le simple "élément à effacer == x" le std::remove_if() peut être utilisé à la place de l'algorithme std::remove() :

// Erase elements matching "erasing_condition" from vector "v"
v.erase( std::remove_if(v.begin(), v.end(), erasing_condition), v.end() );

donde erasing_condition est un prédicat unaire, qui peut être exprimé sous plusieurs formes : par exemple, il peut être un bool -Retourner la fonction en prenant le type d'élément vectoriel comme entrée (donc si la valeur retournée est true l'élément sera effacé du vecteur ; s'il est false il ne le fera pas) ; ou bien on peut l'exprimer de la manière suivante en ligne en tant que lambda ; il peut s'agir d'un foncteur etc.

(Les deux std::remove() y std::remove_if() sont des algorithmes génériques de <algorithm> tête.)

Voici une explication claire de Wikipedia :

El algorithm La bibliothèque fournit le remove y remove_if algorithmes pour cela. Comme ces algorithmes fonctionnent sur une gamme de éléments dénotés par deux itérateurs directs, ils n'ont aucune connaissance de le conteneur ou la collection sous-jacente. Ainsi, aucun élément n'est réellement retiré du conteneur. Au contraire, tous les éléments qui ne correspondent pas aux critères de suppression de l'algorithme critères de suppression sont rassemblés à l'avant de la plage, dans la même ordre relatif. Les éléments restants sont laissés dans un état valide, mais non spécifié. mais non spécifié. Lorsque cela est fait, remove renvoie un itérateur pointant une fois le dernier élément non supprimé.

Pour éliminer réellement les éléments du conteneur, remove est combiné avec l'étiquette du conteneur erase fonction membre, d'où le nom "idiome d'effacement".

En gros, std::remove() y std::remove_if() compact les éléments qui font pas satisfont aux critères d'effacement jusqu'à l'avant de la plage (c'est-à-dire jusqu'au début de l'élément vector ), et ensuite erase() élimine en fait les éléments restants du conteneur.

Ce modèle s'applique également à d'autres conteneurs comme std::deque .

std::list Pattern

Pour effacer des éléments d'un std::list simple remove() y remove_if() méthodes sont disponibles :

// Erase elements having value "x" from list "l"
l.remove( x )

// Erase elements satisfying "erasing_condition" from list "l"
l.remove_if( erasing_condition );

(Où erasing_condition est un prédicat unaire, avec les mêmes caractéristiques que celles discutées pour std::remove_if() dans la section ci-dessus).

Le même schéma peut être appliqué à des conteneurs similaires, tels que std::forward_list .

Conteneurs associatifs (par exemple, std::map, std::set, ...) Modèle

Conteneurs associatifs comme std::map , std::set , std::unordered_map etc. suivent le modèle commun décrit ici :

1. Si la condition d'effacement est une simple concordance des clés (c.-à-d. "Effacer l'élément ayant la clé x" ), alors un simple erase() méthode peut être appelé :

   // Erase element having key "k" from map "m":
   m.erase( k );

2. Si la condition d'effacement est plus complexe, et est exprimée par un prédicat unaire personnalisé (par ex. prédicat unaire (par exemple "effacer tous les éléments impairs" ), alors a for peut être utilisée (avec une vérification explicite de la condition d'effacement dans le corps de la boucle, et un appel à erase(iterator) méthode) :

   //
   // Erase all elements from associative container "c", satisfying "erasing_condition":
   //
   for (auto it = c.begin(); it != c.end(); /* "it" updated inside loop body */ )
   {
       if ( erasing_condition(*it) )
       {   
           // Erase the element matching the specified condition 
           // from the associative container.
           it = c.erase(it);
   
           // Note:
           // erase() returns an iterator to the element 
           // that follows the last element removed, 
           // so we can continue the "for" loop iteration from that position.
       }
       else
       {
           // Current element does _not_ satisfy erasing condition,
           // so we can just move on to the next element.
           ++it;
       }       
   }     

La nécessité d'une approche unifiée

Comme on peut le constater à partir de l'analyse ci-dessus, il n'existe malheureusement pas d'approche commune uniforme pour effacer les éléments des conteneurs STL.

Le tableau suivant résume les tendances susmentionnées :

----------------+------------------------------------------             
   Container    |            Erasing Pattern
----------------+------------------------------------------                
                |
 vector         |    Use erase-remove idiom.
 deque          |
                |
----------------+------------------------------------------               
                |
 list           |    Call remove()/remove_if() methods.
 forward_list   |
                |
----------------+------------------------------------------  
                |
 map            |    Simple erase(key) method call, 
 set            |    or 
 unordered_map  |    loop through the container,
 multimap       |    and call erase(iterator) on matching
                |    condition.
 ...            |
                |
----------------+------------------------------------------

Écrire un code spécifique différent en fonction du conteneur particulier est source d'erreurs, difficile à maintenir, difficile à lire, etc.

Cependant, il est possible d'écrire des modèles de fonctions avec des noms communs (par exemple erase() y erase_if() ) surchargé pour différents types de conteneurs, et intégrer les implémentations des modèles susmentionnés dans ces fonctions.
Ainsi, le client peut simplement appeler ces erase() y erase_if() et le compilateur enverra l'appel à l'implémentation appropriée (à l'adresse suivante temps de compilation ), en fonction du type de conteneur.

Une approche plus élégante, utilisant une technique de métaprogrammation de modèles, est présentée. par Stephan T. Lavavej ici .