Keeping Vektor von Iteratoren der Daten

Question

Ich habe eine Funktion:

void get_good_items(const std::vector<T>& data,std::vector<XXX>& good_items); 

Diese Funktion sollte alle Daten überprüfen und Gegenstände finden, die eine Bedingung erfüllt, und zurück, wo sie in good_items sind.

Was ist das beste anstelle von std::vector<XXX>?

1. std::vector<size_t>, die alle guten Indizes enthält.
2. std::vector<T*>, die einen Zeiger auf die Elemente enthalten.
3. std::vector<std::vector<T>::iterator> enthält Iteratoren zu den Elementen.
4. andere ??

EDIT:

Was werde ich mit dem good_items tun? Viele Dinge ... einer von ihnen ist, sie aus dem Vektor zu löschen und sie an anderer Stelle zu speichern. vielleicht etwas anderes später

EDIT 2:

Einer der wichtigsten ist für mich, wie die Einzelteile in data Zugriff wird schnell sein, abhängig von der Struktur des good_items?

EDIT 3:

Ich habe gerade relized, dass mein Gedanke falsch war. Ist nicht besser, rohe Zeiger (oder Smart) als Elemente des Vektors zu behalten, damit ich die reellen Werte des Vektors behalten kann (welche Zeiger sind), und ich habe keine Angst vor schwerer Kopie, weil sie nur Zeiger sind?

Answer 1

Wenn Sie Elemente aus dem ursprünglichen Vektor entfernen, wird jede der aufgelisteten Methoden ein Problem sein.

Wenn Sie Elemente zum ursprünglichen Vektor hinzufügen, sind die zweite und dritte problematisch. Der erste wird kein Problem sein, wenn Sie push_back verwenden, um Elemente hinzuzufügen.

Alle werden in Ordnung sein, wenn Sie den ursprünglichen Vektor nicht ändern.

Gegeben, würde ich empfehlen, std::vector<size_t> zu verwenden.

Answer 2

Wenn Sie beabsichtigen, die Elemente zu entfernen, die das Prädikat statifizieren, dann ist das Löschen-Entfernen-Idiom die einfachste Lösung.

Wenn Sie solche Elemente kopieren möchten, dann ist std::copy_if die einfachste Lösung.

Wenn Sie beabsichtigen, mit zwei Partitionen des Containers zu enden, d. H. Der eine Container hat die guten und der andere die schlechten, dann ist std::partition_copy eine gute Wahl.

Um die Iteration solcher Elemente allgemein zuzulassen, gibt eine effiziente Lösung eine Reihe solcher Iteratoren zurück, die das Prädikat während der Iteration überprüfen. Ich glaube nicht, dass es solche Iteratoren in der Standardbibliothek gibt, also müssen Sie sie selbst implementieren. Zum Glück hat Boost das bereits für Sie getan: http://www.boost.org/doc/libs/release/libs/iterator/doc/filter_iterator.html

Answer 3

Ich würde mit std::vector<size_t> oder std::vector<T*> gehen, weil sie einfacher zu schreiben sind. Ansonsten sind diese drei Vektoren ziemlich gleichwertig, sie identifizieren alle Positionen von Elementen.

std::vector<size_t> kann gemacht werden, um einen kleineren Typ für Indizes zu verwenden, wenn Sie die Grenzen kennen.

Wenn Sie erwarten, dass in diesem Vektor viele Elemente enthalten sind, sollten Sie stattdessen boost::dynamic_bitset verwenden, um Speicher zu sparen und die CPU-Cache-Auslastung zu erhöhen. Ein Bit pro Element, wobei die Bitposition der Index in den ursprünglichen Vektor ist.

Answer 4

Das Problem, das Sie lösen, aus meinem Verständnis ist der Schnittpunkt von zwei Sätzen, und ich würde für die Lösung von Standardbibliothek gehen: std::set_intersection