Chapter 9. Containers

Chapter 9. + Containers + +
Prev	Part II. + Standard Contents +	Next

+ Yes it is, and that's okay. This is 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())
+	     ...
+	 

+ In this + message to the list, Daniel Kostecky announced work on an + alternate form of std::vector that would support + hints on the number of elements to be over-allocated. The design + was also described, along with possible implementation choices. +

+ The first two alpha releases were announced here + and here. +

Prev	Up	Next
Facets	Home	Associative

Chapter 9. + Containers + +

Sequences

list

list::size() is O(n)

vector

Space Overhead Management