Menu
I know all containers provide a constant size() operation, except forward_list. But how can map, whose internal data structure is red-black tree, provide size() in constant complexity? Same for others like vector and string. Do they use a counter? If so, why doesn't forward_list?
I am confused when I read the book The c++ standard library: a tutorial and reference.
888
map::size() function is an inbuilt function in C++ STL, which is defined in header file. size() is used to check the size of the map container. This function gives size or we can say gives us the number of elements in the map container associated.
Initialize the map directly. The map knows the size up front if initialized directly with iterators: auto mymap = std::map(it_begin, it_end); This is the best way to dodge the issue.
Yes, a std::map<K,V> is ordered based on the key, K , using std::less<K> to compare objects, by default.
map::size() In C++, size() function is used to return the total number of elements present in the map. Return Value: It returns the number of elements present in the map.
This is a long and twisted story. :-)
Yes, map, set, list, etc. keep counters to supply a constant time size(). Prior to C++11, none of the containers were required to keep counters, as their size() should be constant time, but not shall be constant time. In the standard, "should" means maybe, maybe not, and "shall" means definitely.
In practice, in C++98/03 all containers had a constant time size(), except for list, even map and set (by using a counter). This made for some horribly non portable code using list, some of which assumed a constant time size(), and some of which assumed a constant time "splice some from other." Both of those operations can not be constant time, implementations had to choose one or the other.
In C++11, the standard was changed to say that size() must be constant time. However forward_list was also introduced at the same time. And the whole point of forward_list is to be an optimization of list. And the committee did not want to repeat the mistake of list::size(), sometimes being constant time, and sometimes being linear time. So the decision was to not give forward_list a size() at all. Thus clients would never fall victim to an unexpected linear time size(). Clients of forward_list who want to do that computation still have distance(fl.begin(), fl.end()) at their disposal if they should choose to do so.
See N2543 for more details on the rationale for omitting size() from forward_list.
154
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
