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
Solution
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)
OTHER TIPS
Yes, according to http://www.cplusplus.com/reference/stl/, begin(), end() etc are all O(1).
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.
Just look at the code, here you can see the iterators in the std::map in the GNU libstdc++
you'll see that all end rend cend ... are all implemented in constant time.
Be careful with hash_map though. begin() is not constant.
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