Come i container ordinati da STL conoscono la loro fine?

So che lo standard non stabilisce il modo in cui i container STL devono essere implementati, ma piuttosto impone una serie di requisiti per ognuno di essi.Come i container ordinati da STL conoscono la loro fine?

Tuttavia, è ampiamente noto che i contenitori ordinati STL vengono in genere implementati come red–black trees.

È possibile scorrere tra gli elementi di un std::set o un std::map utilizzando i rispettivi iteratori o dal C++ 11 utilizzando loop a intervalli.

Ciò che mi imbarazza tuttavia, è come un contenitore ordinato in STL "conosce" la sua "fine". In altre parole, poiché sono implementati come alberi, come viene implementata la fine del contenitore o potrebbe essere implementata la ?

So che la norma impone requisiti §23.2.1/c contenitore Di (sottolineatura mia):

begin() restituisce un iteratore riferimento al primo elemento nel contenitore . end() restituisce un iteratore che rappresenta il valore passato- per il contenitore. Se il contenitore è vuoto, quindi begin() == end();

OK, per i contenitori contigui questo è facile, ma come questo "past-the-end" potrebbe essere materializzato per gli alberi?

fonte

2015-11-11 101010

Renditi conto che "il passato è il concetto logico, non fisico". Significa letteralmente l'iteratore che ottieni quando passi oltre l'ultima voce valida, ma il contenuto interno di quell'iteratore potrebbe essere qualsiasi cosa. –

Esiste una nozione naturale di next() e end() di terminare gli attraversamenti di alberi come ampiezza prima e profondità prima, quindi non c'è nulla di concettualmente speciale sui rispettivi iteratori. –

@MarkRansom Abbastanza buono, è un concetto logico. Ma come implementa un concetto così logico? Intendo nel codice – 101010

Tutti i contenitori "lista-like" come questo bisogno di avere un qualche tipo di linfonodo sentinella per la fine, perché l'utente può ottenere end(), inserire qualcosa nel contenitore, decrementare l'iteratore, e il decrementato end() deve puntare a quell'elemento inserito. La mia comprensione è che alcune implementazioni verranno allocate dinamicamente per questo, e alcune metterà il nodo sentinella dinamico all'interno del contenitore stesso.

fonte

2015-11-11 16:28:05

Non riesco a trovare un posto nello standard che implichi che 'std :: map :: end()' o 'std :: set :: end()' deve restituire un iteratore decrementabile. Quello che dici è vero per 'basic_string',' array', 'deque',' list' e 'vector', ma l'OP ha chiesto di' set' e 'map'. –

@ АндрейБеньковский: N4527 23.2.1 [container.requirements.general]/12: Salvo diversa indicazione [...] che richiama una funzione membro del contenitore [...] non deve invalidare gli iteratori o modificare i valori di, oggetti all'interno di quel contenitore. - e map :: insert non indica esplicitamente altrimenti. 23.2.4 [associative.reqmts]/9: I membri di insert ed emplace non influiscono sulla validità degli iteratori e dei riferimenti al container, ei membri di cancellazione invalideranno solo iteratori e riferimenti agli elementi cancellati. –

@ АндрейБеньковский: In particolare, è * NOT * true per 'basic_string',' deque' o 'vector' - in questi casi se una riallocazione viene attivata dagli iteratori di inserimento e i riferimenti sono invalidati. E non puoi inserire in un 'array', quindi non è rilevante qui. –

Ho appena ispezionato l'implementazione del contenitore map in Visual Studio 2013 STL ed ecco come viene implementato end. Quando viene creato map, viene assegnato un elemento head dell'albero RB e questo elemento viene dichiarato come la fine del contenitore.

Quando si attraversa il contenitore tramite un iteratore valido, operator++ e operator-- saltare semplicemente l'elemento di testa. E quando raggiungete l'ultimo elemento dell'albero e incrementate un iteratore, sale verso l'alto (cercando una sottostruttura giusta) e alla fine raggiunge la testa dell'albero, che è end.

fonte

2015-11-11 16:47:38 AlexStepanov

Come i container ordinati da STL conoscono la loro fine?

risposta

Problemi correlati