C ++ runs / end / rbegin / rend runs at constant time for std :: set, std :: map, etc.?

Question

For data types such as std :: set and std :: map, where the search takes place in logarithmic time, is the implementation necessary to maintain iterators of the beginning and the end? Does the beginning and end of access have the beginning of a search that can occur in logarithmic time?

I always assumed that the beginning and the end always occur in constant time, however I cannot find confirmation of this in Josuttis. Now that I'm working on something where I need to be indifferent to performance, I want to be sure to cover my bases.

thanks

Answer 1

They occur in constant time. I look at page 466 of the ISO / IEC 14882: 2003 standard:

Table 65 - Container requirements

a.begin (); (constant difficulty)

a.end (); (constant difficulty)

Table 66 - Requirements for a reversible container

a.rbegin (); (constant difficulty)

a.rend (); (constant difficulty)

Answer 2

Yes, according to http://www.cplusplus.com/reference/stl/ , begin (), end (), etc. all O (1).

Answer 3

In the C ++ standard, table 65 in 23.1 (Container Requirements) lists begin () and end () as requiring constant time. If your implementation violates this, this is not appropriate.

Answer 4

Just look at the code, here you can see iterators on std :: map in GNU libstdC ++

std::map

you will see that all endend cend ... all are implemented in constant time.

Answer 5

Be careful with hash_map. begin () is not constant.

Answer 6

For std :: set

begin: constant, end: constant, rbegin: constant, rend: constant,

For std :: map

they are also permanent (all of them)

If you have any doubts, just check www.cplusplus.com