IndexOf de style ArrayList pour std :: vector en C++?

Question

Je viens de Java en C++, et j'ai une situation de conception commune dans laquelle j'ai un élément (un non-primitif) que je voudrais retirer d'un fichier std :: vector. En Java, j'écrirais quelque chose comme arrayList.remove (arrayList.indexOf (myClassInstance));

en C++, avec un std :: vector, quel est le meilleur moyen/le plus performant/le plus propre de faire cela? La meilleure chose à laquelle je puisse penser est de créer une référence à l'instance que je recherche, puis de parcourir le vecteur jusqu'à trouver cette référence. essentiellement, comparer l'adresse mémoire de chaque élément du vecteur avec la référence jusqu'à ce que j'obtienne une correspondance.

suis-je sur la bonne voie? ou y a-t-il une meilleure façon de le faire? (Peut-être en utilisant un autre conteneur std, je ne l'ai utilisé std :: vecteur à ce jour.)

Answer 1

#include <algorithm> 

std::vector<Foo>::iterator it = std::find(vec.begin(), vec.end(), foo_2b_found); 
if (it != vec.end()) vec.erase(it); 

Answer 2

Utilisez std::find pour trouver l'élément et vector::erase pour le supprimer. Passe par le vecteur pour trouver l'élément, et vous ne pouvez pas faire mieux avec un vecteur simple (le même est le cas avec ArrayList de Java). Que vous utilisiez ou non un conteneur différent dépend de vos besoins.

Answer 3

Si vous souhaitez rechercher de façon linéaire à travers le vecteur puis

seq.erase(std::find(seq.begin(), seq.end(), elt)); 

Si vous avez un prédicat et que vous voulez supprimer tous les éléments qui correspondent au prédicat alors:

seq.erase(std::remove_if(seq.begin(), seq.end(), Pred), seq.end()); 

Aucun ces méthodes sont les plus performantes car elles nécessitent une recherche linéaire et même si votre élément est trouvé très tôt, l'effacement est coûteux car il doit déplacer tous les autres éléments en les gardant contigu s. L'utilisation de std :: list traiterait de la dernière de celles-ci: la recherche serait linéaire mais l'effacement serait un temps constant.

S'il est possible de stocker vos éléments dans un conteneur associatif qui utilise une recherche de clé, cela serait plus efficace: recherche O (log N) et suppression du temps constant.

Une carte de hachage peut être encore meilleure, proche de la recherche et de la suppression du temps constant. Pour ce que vous suggérez, c'est-à-dire en effaçant par le pointeur de l'objet, vous pouvez utiliser std :: set pour votre type T. Ensuite, utilisez mySet.erase(pt); où pt est votre pointeur. Vous devez gérer la durée de vie de vos pointeurs, bien sûr, mais le fait que vous sachiez lequel effacer de votre collection suggère que vous en ayez une copie ailleurs.

Vous pouvez utiliser std :: set, SharedPtrLess>

où vous définissez SharedPtrLess comme suit:

template< typename T > 
struct SharedPtrLess 
{ 
    bool operator()(boost::shared_ptr<T> left, boost::shared_ptr<T> right) const 
    { 
    return std::less<T>()(left.get(), right.get()); 
    } 
};