C++ inizia/fine/rbegin/rend viene eseguito in tempo costante per std::set, std::map, ecc.?

Question

Per tipi di dati come std::set e std::map in cui la ricerca avviene in tempo logaritmico, è necessaria l'implementazione per mantenere gli iteratori di inizio e fine?L'accesso all'inizio e alla fine implica una ricerca che potrebbe avvenire in tempo logaritmico?

Ho sempre pensato che l'inizio e la fine avvengano sempre in un tempo costante, tuttavia non riesco a trovare alcuna conferma di ciò in Josuttis.Ora che sto lavorando su qualcosa in cui devo essere attento alle prestazioni, voglio assicurarmi di coprire le mie basi.

Grazie

Answer 1

Accadono in un tempo costante.Sto guardando la pagina 466 dello standard ISO/IEC 14882:2003:

Tabella 65 – Requisiti dei contenitori

a.begin(); (complessità costante)

a.end(); (complessità costante)

Tabella 66 – Requisiti del contenitore reversibile

a.rbegin(); (complessità costante)

a.rend(); (complessità costante)

Answer 2

Sì, secondo http://www.cplusplus.com/reference/stl/, Begin(), End() ecc sono tutti O(1).

Answer 3

Nello standard C++, la Tabella 65 in 23.1 (Requisiti dei contenitori) elenca Begin() ed End() che richiedono tempo costante.Se la tua implementazione viola questo, non è conforme.

Answer 4

Basta guardare il codice, qui puoi vedere gli iteratori in std::map in GNU libstdc++

std::map

vedrai che tutto end rend cend...sono tutti implementati in tempo costante.

Answer 5

Fai attenzione però con hash_map.Begin() non è costante.

Answer 6

Per std::set

inizio:costante, fine:costante, rbegin:costante, rend:costante,

Per std::map

sono anche costanti (tutti)

se hai qualche dubbio, controlla www.cplusplus.com