effective stl digest I

Item 1. Choose your containers with care.

The standard STL sequence containers, vector, string, deque, and list.

The standard STL associative containers, set, multiset, map and multimap.


Contiguous-memory containers (also known as array-based containers] store their elements in one or more (dynamically allocated) chunks of memory, each chunk holding more than one container element. If a new element is inserted or an existing element is erased, other elements in the same memory chunk have to be shifted up or down to make room for the new element or to fill the space formerly occupied by the erased element. This kind of movement affects both performance (see Items 5 and 14) and exception safety (as we’ll soon see). The standard contiguous-memory containers are vector, string, and deque. The nonstandard rope is also a contiguous-memory container.


Node-based containers store only a single element per chunk of (dynamically allocated) memory. Insertion or erasure of a container element affects only pointers to nodes, not the contents of the nodes themselves, so element values need not be moved when something is inserted or erased. Containers representing linked lists, such as list and slist, are node-based, as are all the standard associative containers. (They’re typically implemented as balanced trees.)


Do you need to minimize iterator, pointer, and reference invalidation? If so, you’ll want to use node-based containers, because insertions and erasures on such containers never invalidate iterators, pointers, or references (unless they point to an element you are erasing). In general, insertions or erasures on contiguous-memory containers may invalidate all iterators, pointers, and references into the container.

Item 2. Beware the illusion of container-independent code.

Given the inevitability of having to change container types from time to time, you can facilitate such changes in the usual manner: by encapsulating, encapsulating, encapsulating.

//java has more abstract container types such as Collection, which support many common operations of containers such as sort, size, iteration and etc. Java is better at supporting implementation independent code.

Once you’ve used the STL a little while, you’ll realize that typedefs are your friends.

Item 3. Make copying cheap and correct for objects in containers.

Containers hold objects, but not the ones you give them.

Copy in, copy out. That’s the STL way.

Yes, copying objects is the STL way.

If you fill a container with objects where copying is expensive, the simple act of putting the objects into the container could prove to be a performance bottleneck.

In the presence of inheritance, of course, copying leads to slicing.

An easy way to make copying efficient, correct, and immune to the slicing problem is to create containers of pointers instead of containers of objects.

you’ll probably discover that containers of smart pointers are an attractive option.

Item 4. Call empty instead of checking size() against zero.

empty is a constant-time operation for all standard containers, but for some list implementations, size takes linear time.

Item 5. Prefer range member functions to their single-element counterparts.