Devo restituire un iteratore o un puntatore a un elemento in un contenitore STL?

Question

Sto sviluppando un motore per il porting di codice esistente su una piattaforma diversa. Il codice esistente è stato sviluppato utilizzando un'API di terze parti e il mio motore ridefinirà quelle funzioni API di terze parti in termini della mia nuova piattaforma.

Le seguenti definizioni provengono dal API:

typedef unsigned long shape_handle;  
shape_handle make_new_shape(int type); 

ho bisogno di ridefinire make_new_shape e ho la possibilità di ridefinire shape_handle.

ho definito tale struttura (semplificata):

struct Shape 
{ 
    int type 
}; 

chiamante della make_new_shape non interessa la struttura sottostante di Shape, ha bisogno solo un "ansa" ad esso in modo che possa chiamare funzioni come:

void `set_shape_color(myshape, RED);` 

dove myshape è la maniglia per la forma.

Il mio motore gestirà la memoria per gli oggetti Shape e altri requisiti impongono che il motore memorizzi gli oggetti Shape in un elenco o in un altro contenitore iterabile.

La mia domanda è, qual è il modo più sicuro per rappresentare questo handle - se lo Shape stesso verrà memorizzato in un elenco std :: un iteratore, un puntatore, un indice?

Answer 1

La risposta dipende dalla vostra rappresentazione:

• per std::list, utilizzare un iterator (non un puntatore), perché un iterator consente di rimuovere l'elemento senza camminare l'intera lista.
• per std::map o boost::unordered_map, utilizzare il Key (ovviamente)

Il vostro disegno sarebbe molto più forte se è stato utilizzato un contenitore associativa, in quanto contenitori associativi ti danno la possibilità di interrogare per la presenza dell'oggetto, piuttosto che invocare il comportamento indefinito.

Prova comparativa sia map e unordered_map per vedere quale è più veloce nel tuo caso :)

Answer 2

Sia un iteratore che un puntatore fanno cose cattive se si tenta di accedervi dopo che l'oggetto è stato eliminato, quindi nessuno dei due è intrinsecamente più sicuro. Il vantaggio di un iteratore è che può essere utilizzato per accedere ad altri membri della tua collezione.

Quindi, se si desidera accedere al proprio Shape, un puntatore sarà il più semplice. Se si desidera scorrere l'elenco, utilizzare un iteratore.

Un indice è inutile in un elenco poiché std :: list non sovraccarica l'operatore [].

Answer 3

IIF la rappresentazione interna sarà un elenco di forme, quindi i puntatori e gli iteratori sono sicuri. Una volta assegnato un elemento, non si verificherà mai alcuna ricollocazione. Non consiglierei un indice per ovvi motivi di prestazioni di accesso. O (n) in caso di liste.

Se si utilizzava un vettore, non utilizzare iteratori o puntatori, poiché gli elementi possono essere spostati quando si supera la capacità dei vettori e i puntatori/iteratori diventano non validi.

Se si desidera una rappresentazione che sia sicura indipendentemente dal contenitore interno, quindi creare un contenitore (elenco/vettore) di puntatori alle forme e restituire il puntatore forma al client. Anche se il contenitore viene spostato in memoria, gli oggetti Shape rimarranno nella stessa posizione.

Answer 4

Iteratori non sono più sicuro di puntatori, ma hanno molto diagnostica migliori rispetto puntatori prime se si sta utilizzando un controllato l'implementazione STL!

Ad esempio, in una build di debug, se si restituisce un puntatore a un elemento di elenco, quindi si cancella quell'elemento di elenco, si dispone di un puntatore pendente. Se accedete, si verifica un arresto anomalo e tutto ciò che potete vedere sono dati spazzatura. Ciò può rendere difficile capire cosa è andato storto.

Se si utilizza un iteratore e si dispone di un'implementazione STL controllata, non appena si accede all'iteratore a un elemento cancellato, viene visualizzato un messaggio come "iteratore è stato invalidato". Questo perché hai cancellato l'elemento a cui punta. Boom, ti sei appena salvato potenzialmente un sacco di sforzi di debug.

Quindi, non indici per prestazioni O (n). Tra puntatori ed iteratori - sempre iteratori!