C++ does begin/end/rbegin/rend execute in constant time for std::set, std::map, etc?

Question

For data types such as std::set and std::map where lookup occurs in logarithmic time, is the implementation required to maintain the begin and end iterators? Does accessing begin and end imply a lookup that could occur in logarithmic time?

I have always assumed that begin and end always occur in constant time, however I can't find any confirmation of this in Josuttis. Now that I'm working on something where I need to be anal about performance, I want to make sure to cover my bases.

Thanks

Answer 1

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

Answer 2

In the C++ standard, Table 65 in 23.1 (Container Requirements) lists begin() and end() as requiring constant time. If your implementation violates this, it isn't conforming.

Answer 3

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

[http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/a02142.html#l00312][1]

you'll see that all end rend cend ... are all implemented in constant time.

Answer 4

For std::set

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

For std::map

they are also constant (all of them)

if you have any doubt, just check www.cplusplus.com

Answer 5

They happen in constant time. I'm looking at page 466 of the ISO/IEC 14882:2003 standard:

Table 65 - Container Requiments

a.begin(); (constant complexity)

a.end(); (constant complexity)

Table 66 - Reversible Container Requirements

a.rbegin(); (constant complexity)

a.rend(); (constant complexity)

Answer 6

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