Skip to main content

Why is STL Container list<>::size() linear time?

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())
...
Labels:

Comments

Post a Comment

Popular posts from this blog

Explain Polymorphism and Flavors of Polymorphism...

Polymorphism is the ability of different objects to react in an individual manner to the same message. This notion was imported from natural languages. For example, the verb "to close" means different things when applied to different objects. Closing a door, closing a bank account, or closing a program's window are all different actions; their exact meaning is determined by the object on which the action is performed. Most object-oriented languages implement polymorphism only in the form of virtual functions. But C++ has two more mechanisms of static (meaning: compile-time) polymorphism: Operator overloading. Applying the += operator to integers or string objects, for example, is interpreted by each of these objects in an individual manner. Obviously, the underlying implementation of += differs in every type. Yet, intuitively, we can predict what results are. Templates. A vector of integers, for example, reacts differently from a vector of string objects when it receives ...
17 comments
Read more

Function name mangling for C++ and Java

G++ internals - Mangling Both C++ and Jave provide overloaded function and methods, which are methods with the same types but different parameter lists. Selecting the correct version is done at compile time. Though the overloaded functions have the same name in the source code, they need to be translated into different assembler-level names, since typical assemblers and linkers cannot handle overloading. This process of encoding the parameter types with the method name into a unique name is called name mangling . The inverse process is called demangling . It is convenient that C++ and Java use compatible mangling schemes, since the makes life easier for tools such as gdb, and it eases integration between C++ and Java. Note there is also a standard "Jave Native Interface" (JNI) which implements a different calling convention, and uses a different mangling scheme. The JNI is a rather abstract ABI so Java can call methods written in C or C++; we are concerned he...
5 comments
Read more