Comment superposer std :: remove pour std :: list?

Question

J'ai appris une fois que la manière générale d'effacer des éléments d'un conteneur est via l'idiome erase-remove. Mais j'ai été surpris de découvrir qu'au moins l'implémentation STL de g ++ ne surcharge pas std :: remove() pour std :: list, puisque dans ce cas beaucoup d'affectations d'objets pourraient être sauvées en faisant le réordonnancement via la manipulation du pointeur.

Y a-t-il une raison pour laquelle la norme C++ n'impose pas une telle optimisation? Mais ma question principale est comment je peux surcharger std :: remove() (il ne doit pas être portable au-delà de g ++), donc je pourrais fournir une implémentation qui utilise list :: splice()/list :: merge() à la place. J'ai essayé quelques signatures, mais obtenir une erreur d'ambiguïté au mieux, par exemple:

template <typename T> 
typename std::list<T>::iterator 
remove(typename std::list<T>::iterator first, 
     typename std::list<T>::iterator last, const T &v); 

P.S .: Je suis désolé que je n'étais pas assez clair. S'il vous plaît ignorer que les fonctions proviennent de l'espace de noms std et ce qu'ils font spécifiquement. Je souhaite juste en savoir plus sur les règles template/typetraits/overload en C++.

Answer 1

list::remove ou list::erase seul fera ce que vous avez vu l'idiome effacer/supprimer pour les vecteurs.

remove pour les valeurs ou les prédicats. erase pour les itérateurs simples ou les gammes.

Answer 2

Le conseil que vous avez reçu est bon, mais pas universel. Il est bon pour std::vector, par exemple, mais complètement inutile pour std::list puisque std::list::erase() et std::list::remove() font déjà la bonne chose. Ils font tout le magicien de pointeur que vous demandez, quelque chose que std::vector::erase() ne peut pas faire parce que son stockage interne est différent. C'est la raison pour laquelle std::remove() n'est pas spécialisé pour std::list: car il n'est pas nécessaire de l'utiliser dans ce cas.

Answer 3

Ce n'est pas obligatoire parce qu'il est non seulement une optimisation, il a une sémantique différente de ce que vous attendez pour un conteneur de séquence:

std::list<int> l; 
l.push_back(1); 
l.push_back(2); 

std::list<int>::iterator one = l.begin(); 
std::list<int>::iterator two = l.end(); --two; 

if (something) { 
    l.erase(remove(l.begin(), l.end(), 1), l.end()); 
    // one is still valid and *one == 2, two has been invalidated 
} else { 
    l.remove(1); 
    // two is still valid and *two == 2, one has been invalidated 
} 

En ce qui concerne la question réelle: ISWYM, je suis coincé pour le moment comment écrire une paire de modèles de fonction de sorte que l'un corresponde à des itérateurs arbitraires et l'autre à des itérateurs de liste, sans ambiguïté.

Sachez qu'il n'y a aucune garantie dans la norme que list<T>::iterator est un type différent de some_other_container<T>::iterator. Donc, bien qu'en pratique, vous vous attendiez à ce que chaque conteneur ait son propre itérateur, en principe l'approche est erronée, à part le fait que vous avez suggéré de mettre la surcharge en std. Vous ne pouvez pas utiliser les itérateurs seuls pour apporter des modifications "structurelles" à leurs conteneurs correspondants.

Vous pouvez le faire sans ambiguïté:

template <typename Container> 
void erase_all(Container &, const typename Container::value_type &); 

template <typename T> 
void erase_all(std::list<T> &, const T &);