The C++ STL provides four components:

  1. algorithms
  2. containers
  3. iterators
  4. functions

Containers

Containers store data with specific structure:

  • standard STL sequence containers : vector, string, dequeue, list
  • standard STL associative containers : set, multiset, map, multimap

  • standard non-STL containers : bitset, valarray, stack, queue, priority_queue

  • list should be used when there are frequent insertions and deletions from the middle of the sequence.
  • deque should be used when most insertions and deletions take place at the beginning or at the end of the sequence.

Contiguous-memory containers

  • Container in which more than one element is stored in the allocated chunk of memory. If an element in the chunk is inserted or deleted, the rest of the elements need to be shifted up or down in the memory.
  • Ex: vector, string, dequeue

Node-based containers

  • Containers that can allocate one element per chunk.
  • Ex: set, list

Item: Encapsulation

While writing containers try to encapsulate things:

class Widget { ... };

vector<Widget> vw;
Widget bestWidget;

vector<Widget>::iterator i =                   // find a Widget with the
  find(vw.begin(), vw.end(), bestWidget);      // same value as bestWidget

Instead of the above code, this code makes more sense:

class Widget { ... };

typedef vector<Widget> WidgetContainer;
Widget bestWidget;

WidgetContainer::iterator i =                   // find a Widget with the
  find(vw.begin(), vw.end(), bestWidget);      // same value as bestWidget

The above code is more robust to the changes made to the container late on.

Item: empty() vs size()

It seems like checking for empty and size against zero should be the same.

if (container.empty())
if (container.size() == 0)

One should always prefer empty() operation because:

  • Its generally implemented inline, which checks if size is 0.
  • It takes constant time. In case of list, the size() takes linear time.

Item: range operators

Use assign() operator to assign values to container.

To assign v2’s half content to v1:

v1.assign(v2.begin() + v2.end()/2, v2.end());

The above code does not require any loop. It takes the range from iterators as input.