C ++ faz começar / end / rbegin / rend executar em tempo constante para std :: set, std :: map, etc?

Question

Para tipos de dados, tais como std :: set e std :: mapa onde a pesquisa ocorre em tempo logarítmica, é a implementação obrigados a manter a iterators finais começar e? Será acessando começam e terminam implica uma pesquisa que poderia ocorrer em tempo logarítmica?

Eu sempre assumiu que começam e terminam sempre ocorrem em tempo constante, no entanto não consigo encontrar qualquer confirmação desta em Josuttis. Agora que eu estou trabalhando em algo onde eu preciso ser anal sobre o desempenho, eu quero ter certeza de cobrir minhas bases.

Graças

Answer 1

Eles acontecem em tempo constante. Eu estou olhando para página 466 da ISO / IEC 14882: 2003:

Tabela 65 - Container requiments

a.begin (); (complexidade constante)

a.end (); (complexidade constante)

Tabela 66 - Requisitos reversível contentores

a.rbegin (); (complexidade constante)

a.rend (); (complexidade constante)

Answer 2

Sim, de acordo com a http://www.cplusplus.com/reference/stl/, começam (), fim () etc, são todos O (1).

Answer 3

No padrão C ++, Tabela 65 em 23.1 (Requisitos de contentores) listas de começar () e final () como requerendo tempo constante. Se a sua aplicação viola isso, não está em conformidade.

Answer 4

Apenas olhada no código, aqui você pode ver os iteradores no std :: map no GNU libstdc ++

std::map

Você verá que tudo cend final rend ... são todas implementadas em tempo constante.

Answer 5

Tenha cuidado com hash_map embora. begin () não é constante.

Answer 6

Para std :: set

começar: constante, final: constante, rbegin: constante, rend: constante,

Para std :: map

Eles também são constantes (todos eles)

Se você tiver alguma dúvida, basta verificar www.cplusplus.com