Table of Contents
+ 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()) + ... +