Menu
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
506
vector rbegin() and rend() function in C++ STL Return value: The function returns a reverse iterator pointing to the last element in the container.
The rbegin() is a function in C++ STL. It returns a reverse iterator which points to the last element of the map. The reverse iterator iterates in reverse order and incrementing it means moving towards beginning of map.
map::end() end() function is used to return an iterator pointing to past the last element of the map container.
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)
186
Yes, according to http://www.cplusplus.com/reference/stl/, begin(), end() etc are all O(1).
34
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
