ArrayList-style indexOf für std :: Vektor in C++?

Question

Ich komme aus Java in C++ und habe eine gemeinsame Design-Situation, in der ich ein Element (ein nicht-primitives) habe, das ich aus einem std :: vector entfernen möchte.

in Java würde ich etwas wie schreiben: arrayList.remove (arrayList.indexOf (myClassInstance));

in C++, mit einem std :: vector, was ist die beste/leistungsfähigste/sauberste Art, dies zu tun?

Das Beste, was ich mir vorstellen kann, ist, einen Verweis auf die Instanz zu erstellen, nach der ich suche, und dann durch den Vektor zu iterieren, bis ich diese Referenz finde. im Wesentlichen, um die Speicheradresse jedes Elements in dem Vektor mit der Referenz zu vergleichen, bis ich eine Übereinstimmung erhalte.

Bin ich auf dem richtigen Weg? oder gibt es einen besseren Weg? (vielleicht mit einem anderen Std-Container, ich habe bisher nur std :: vector verwendet.)

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

Verwenden Sie std::find, um das Element zu finden und vector::erase, um es zu entfernen.

std::find iteriert im Wesentlichen durch den Vektor, um das Element zu finden, und Sie können nicht besser mit einem einfachen Vektor (das gleiche ist der Fall mit Javas ArrayList). Ob Sie einen anderen Container verwenden oder nicht, hängt von Ihren Anforderungen ab.

Answer 3

Wenn Sie möchten, linear durch den Vektor suchen dann

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

Wenn Sie ein Prädikat und wollen alle Elemente entfernen, die das Prädikat entsprechen dann:

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

Keines Diese Methoden sind am leistungsfähigsten, da sie eine lineare Suche erfordern. Selbst wenn Ihr Element zu einem frühen Zeitpunkt gefunden wird, ist das Löschen teuer, da alle anderen Elemente durch eine Position verschoben werden müssen, um sie zusammenhängend zu halten s.

Die Verwendung von std :: list würde letzteres adressieren: Die Suche wäre linear, aber das Löschen wäre eine konstante Zeit.

Wenn es möglich ist, Ihre Elemente in einem assoziativen Container zu speichern, der eine Schlüsselsuche verwendet, wäre das effizienter: O (log N) Lookup und konstante Zeitentfernung.

Eine Hash-Karte kann sogar besser sein, in der Nähe von konstanter Zeit suchen und entfernen.

Für was Sie vorschlagen, d. H. Löschen durch den Zeiger des Objekts, könnten Sie std :: set für Ihren Typ T verwenden. Dann verwenden Sie mySet.erase(pt); wo pt ist Ihr Zeiger. Sie müssen natürlich die Lebensdauer Ihrer Zeiger verwalten, aber die Tatsache, dass Sie wissen, welche Sie aus Ihrer Sammlung löschen möchten, legt nahe, dass Sie eine Kopie davon noch woanders haben.

Sie könnten std :: set verwenden, SharedPtrLess>

wo Sie SharedPtrLess wie folgt definieren:

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()); 
    } 
};