Chapter 9.  Containers

Table of Contents

Sequences
list
list::size() is O(n)
Associative
Insertion Hints
bitset
Size Variable
Type String
Unordered Associative
Insertion Hints
Hash Code
Hash Code Caching Policy
Interacting with C
Containers vs. Arrays

Sequences

list

list::size() is O(n)

Yes it is, and that was okay until the 2011 edition of the C++ standard. In future GCC will change it to O(1) but O(N) was a decision that we preserved when we imported SGI's STL implementation. The following is quoted from their FAQ:

The size() member function, for list and slist, takes time proportional to the number of elements in the list. This was a deliberate tradeoff. The only way to get a constant-time size() for linked lists would be to maintain an extra member variable containing the list's size. This would require taking extra time to update that variable (it would make splice() a linear time operation, for example), and it would also make the list larger. Many list algorithms don't require that extra word (algorithms that do require it might do better with vectors than with lists), and, when it is necessary to maintain an explicit size count, it's something that users can do themselves.

This choice is permitted by the C++ standard. The standard says that size() should be constant time, and should does not mean the same thing as shall. This is the officially recommended ISO wording for saying that an implementation is supposed to do something unless there is a good reason not to.

One implication of linear time size(): you should never write

	 if (L.size() == 0)
	     ...
	 

Instead, you should write

	 if (L.empty())
	     ...