How does std::map provide a constant size() operation?

Question

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.

Answer 1

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.