C++ hace begin/end/rbegin/rend ejecutar en tiempo constante para std::set, std::map, etc?

Question

Para los tipos de datos, tales como std::set y std::map donde la búsqueda se produce en tiempo logarítmico, es la aplicación necesaria para mantener el comienzo y el final de los iteradores?El acceso a comenzar y terminar implica una búsqueda que podría ocurrir en un tiempo logarítmico?

Yo siempre he asumido que comienzan y terminan siempre ocurren en tiempo constante, sin embargo no puedo encontrar ninguna confirmación de esto en Josuttis.Ahora que estoy trabajando en algo que me falta para ser anal sobre el rendimiento, la quiero para asegurarse de cubrir mis bases.

Gracias

Answer 1

Que suceden en tiempo constante.Estoy buscando en la página 466 de la ISO/IEC 14882:2003 estándar:

Tabla 65 - Contenedor Requiments

una.begin(); (constante de la complejidad)

una.end(); (constante de la complejidad)

Tabla 66 - Reversible Requisitos De Contenedor

una.rbegin(); (constante de la complejidad)

una.rend(); (constante de la complejidad)

Answer 2

Sí, de acuerdo a http://www.cplusplus.com/reference/stl/, begin(), end (), etc son todos los O(1).

Answer 3

En el estándar de C++, Tabla 65 en 23.1 (Requisitos de Contenedor) listas de begin() y end() requiere de tiempo constante.Si su aplicación viola esto, no es conforme.

Answer 4

Acabo de mirar el código, aquí puedes ver los iteradores en el std::map en el GNU libstdc++

std::map

verás que todos los finales de rend fin ...se realizan en tiempo constante.

Answer 5

Tenga cuidado con hash_map aunque.begin() no es constante.

Answer 6

Para std::set

comenzar:constante, al final:constante, rbegin:constante, rend:constante,

Para std::map

también son constantes (todos ellos)

si tienes alguna duda, consulta www.cplusplus.com