Keeping vettore di iteratori dei dati

Question

Ho una funzione:

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

Questa funzione dovrebbe controllare tutti i dati e trovare gli oggetti che soddisfa una condizione e tornare dove sono in good_items.

cosa è meglio invece di std::vector<XXX>?

1. std::vector<size_t> che contiene tutti gli indici validi.
2. std::vector<T*> che contengono un puntatore agli articoli.
3. std::vector<std::vector<T>::iterator> che contiene iteratori per gli articoli.
4. altro ??

EDIT:

Cosa farò con il good_items? Molte cose ... una di queste è cancellarle dal vettore e salvarle in altro luogo. forse qualcos'altro dopo

EDIT 2:

Uno dei più importante per me è come sarà l'accesso alle voci in data sarà veloce a seconda della struct di good_items?

EDIT 3:

Ho appena relized che il mio pensiero era sbagliato. Non è meglio mantenere puntatori grezzi (o intelligenti) come elementi del vettore in modo da poter mantenere i valori reali del vettore (che sono i puntatori) e non ho paura della copia pesante perché sono solo indicatori?

Answer 1

Se rimuovi gli elementi dal vettore originale, ognuno dei metodi che hai elencato sarà un problema.

Se si aggiungono elementi al vettore originale, il secondo e il terzo saranno problematici. Il primo non sarà un problema se si utilizza push_back per aggiungere elementi.

Tutti loro andranno bene se non si modifica il vettore originale.

Dato che, mi consiglia di utilizzare std::vector<size_t>.

Answer 2

Se si intende rimuovere gli elementi che soddisfano il predicato, l'idioma di cancellazione-rimozione è la soluzione più semplice.

Se si intende copiare tali elementi, quindi std::copy_if è la soluzione più semplice.

Se si intende finire con due partizioni del contenitore, vale a dire un contenitore ha i buoni e un altro i cattivi, quindi std::partition_copy è una buona scelta.

Per consentire generalmente l'iterazione di tali elementi, una soluzione efficiente sta restituendo un intervallo di tali iteratori che controlleranno il predicato durante l'iterazione. Non penso che esistano tali iteratori nella libreria standard, quindi dovrai implementarli tu stesso. Per fortuna hai già fatto questo per te: http://www.boost.org/doc/libs/release/libs/iterator/doc/filter_iterator.html

Answer 3

Vorrei andare con std::vector<size_t> o std::vector<T*> perché sono più facili da digitare. Altrimenti, quei tre vettori sono praticamente equivalenti, tutti identificano le posizioni degli elementi.

std::vector<size_t> può essere utilizzato per utilizzare un tipo più piccolo per gli indici se si conoscono i limiti.

Se ci si aspetta che ci siano molti elementi in questo vettore, si potrebbe considerare di utilizzare boost::dynamic_bitset invece di risparmiare memoria e aumentare l'utilizzo della cache della CPU. Un po 'per elemento, la posizione del bit è l'indice nel vettore originale.

Answer 4

Il problema si sta risolvendo, dalla mia comprensione, è l'intersezione di due set, e vorrei andare per la soluzione dalla libreria standard: std::set_intersection