Cancellazione di vettore STL e mappa

Question

Nell'STL quasi tutti i contenitori hanno una funzione di cancellazione.La domanda che ho è in un vettore, la funzione di cancellazione restituisce un iteratore che punta all'elemento successivo nel vettore.Il contenitore della mappa non lo fa.Restituisce invece un vuoto.Qualcuno sa perché c'è questa incoerenza?

Answer 1

Vedere http://www.sgi.com/tech/stl/Map.html

La mappa ha la proprietà importante che l'inserimento di un nuovo elemento in una mappa non invalida gli iteratori che indicano elementi esistenti.Anche la cancellazione di un elemento da una mappa non invalida alcuna iteratrici, tranne, ovviamente, per gli iteratori che indicano effettivamente l'elemento che viene cancellato.

Il motivo per cui si restituisce un iteratore durante la cancellazione è che è possibile scorrere l'elenco cancellando gli elementi man mano che si procede.Se la cancellazione di un elemento non invalida gli iteratori esistenti, non è necessario farlo.

Answer 2

erase restituisce un iterator nel C++11.Questo è dovuto a rapporto di difetto 130:

La Tabella 67 (23.1.1) dice che container::erase(iterator) restituisce un iteratore.La Tabella 69 (23.1.2) dice che oltre a questo requisito, i contenitori associativi dicono anche che container::erase(iterator) restituisce void.Questa non è un'aggiunta;si tratta di una modifica ai requisiti, che ha l'effetto di far sì che i contenitori associativi non soddisfino i requisiti per i contenitori.

Il comitato per gli standard ha accettato questo:

il LWG concorda che il tipo di restituzione dovrebbe essere iteratore, non void.(Anche Alex Stepanov è d'accordo.)

(LWG = Gruppo di Lavoro Biblioteca).

Answer 3

L'incoerenza è dovuta all'uso. vector è una sequenza avente un ordinamento sugli elementi.Se è vero che gli elementi in a map sono ordinati anche secondo qualche criterio di confronto, tale ordinamento non è evidente dalla struttura.Non esiste un modo efficiente per passare da un elemento a quello successivo (efficiente = tempo costante).In effetti, eseguire l'iterazione sulla mappa è piuttosto costoso;sia la creazione dell'iteratore che l'iteratore stesso implicano una passeggiata sull'intero albero.Questo non può essere fatto O(N), a meno che non venga utilizzata una pila, nel qual caso lo spazio richiesto non è più costante.

Tutto sommato, semplicemente non esiste un modo economico per restituire l'elemento "successivo" dopo la cancellazione.Per le sequenze, lì È lontano.

Inoltre, Rob ha ragione.Non è necessario che Map restituisca un iteratore.

Answer 4

Per inciso, l'STL fornito con MS Visual Studio C++ (Dinkumware IIRC) fornisce un'implementazione della mappa con un erase funzione che restituisce un iteratore all'elemento successivo.

Fanno notare che non è conforme agli standard.

Answer 5

Non ho idea se questa sia la risposta, ma una ragione potrebbe essere il costo per individuare l'elemento successivo.L'iterazione di una mappa è intrinsecamente "lenta".