CODEWITHSUNDEEP
c++stl
Nicolas Grebille
Nicolas Grebille

Reputation: 1332

implementation of size in standard containers

This is a purely theoretical question, I know that the standard containers interface are not likely to change now...

I read recently one of Herb Sutter "guru of the week" where he complained about the fact that empty() was implemented as a member function in std::string. I did not agree with all the arguments, because e.g. std::list would require a different implementation of the same function, as size() is O(n) and empty() is obviously O(1).

However, is there a reason why the standard specify that the empty() member function of (for instance) std::string is implemented as "size () == 0" instead of "begin () == end ()" ?

It seems to me that the latter allow the same O(1) implementation of the empty() function for all containers, and I can't think of any drawback. Is it less efficient?

Thanks,

N.G.

Upvotes: 0

Views: 173

Answers (4)

David Rodríguez - dribeas
David Rodríguez - dribeas

Reputation: 208353

Herb suggests making length() a non-member function implemented in terms of size(), and equivalently with empty():

What about length()? Easy, again -- it's defined to give the same result as size(). What's more, note that the other containers don't have length(), and it's there in the basic_string interface as a sort of "string thing", but by making it a nonmember suddenly we can consisently say "length()" about any container. Not too useful in this case because it's just a synonym for size(), I grant you, but a noteworthy point in the principle it illustrates -- making algorithms nonmembers immediately also makes them more widely useful and usable.

The reason for size() being a member function is that in most cases the implementations will cache the value for containers where it is expensive to calculate (i.e. for a list or a map, the number of contained elements is stored in the container itself to avoid having to walk the structure), to comply with the recommendation in the standard that size should be a O(1) operation (§23.1/5).

Upvotes: 0

Nicol Bolas
Nicol Bolas

Reputation: 473437

The standard doesn't specify exactly how anything in the library is implemented. It merely specifies the meaning of something. So if empty() is true, then size() must also be 0. That doesn't mean that empty() must actually call std::basic_string::size() and compare it to 0. The spec is simply saying that if empty() returns true, then calling size() immediately after will return 0, and if empty() returned false, then calling size() immediately after will not return 0.

The spec could have said that its begin() would equal its end(), and it would force no implementations to change.

The inconsistency is most likely a consequence of the std::basic_string class having come from a different place from the rest of the STL containers during the development of C++98. That's why it has so many member functions for doing things that STL containers would typically do with algorithms.

Upvotes: 4

Bo Persson
Bo Persson

Reputation: 92261

The specifications that empty() is to be equivalent to size() == 0 is not to be taken literally. The code snippets only show the intent of the functions, not exactly how they are to be implemented.

I have this confirmed from committee members in another forum.

In your example, it is also possible that size() is implemented as the equivalent of end() - begin(), so there might be no difference anyway.

Upvotes: 2

Viktor Sehr
Viktor Sehr

Reputation: 13099

Yes, it would be less efficient as string::end() usually is implemented as something like return (_STRING_ITERATOR(_Myptr() + this->_Mysize));

Thus, using size() == 0 reduces the need for an addition.

Upvotes: 0

Related Questions