Thinking In C++. Volume 2: Practical Programming

Category	Containers
Simple Sequence Containers	vector, list, deque
Container Adapters	queue, stack, priority_queue
Associative Containers	set, map, multiset, multimap

All the containers in the standard library hold objects and expand their resources as needed. The key difference between one container and another is the way the objects are stored in memory and what operations are available to the user^.

A vector, as you already know, is a linear sequence that allows rapid random access to its elements. However, it’s expensive to insert an element in the middle of a co-located sequence like a vector, just as it is with an array. A deque (double-ended-queue, pronounced "deck") also allows random access that’s nearly as fast as vector, but it’s significantly faster when it needs to allocate new storage, and you can easily add new elements at the front as well as the back of the sequence. A list is a doubly linked list, so it’s expensive to move around randomly but cheap to insert an element anywhere. Thus list, deque and vector are similar in their basic functionality (they all hold linear sequences), but different in the cost of their activities. So for your first shot at a program, you could choose any one and experiment with the others only if you’re tuning for efficiency^.

Many of the problems you set out to solve will only require a simple linear sequence such as a vector, deque, or list. All three have a member function push_back( ) that you use to insert a new element at the back of the sequence (deque and list also have push_front( )).

But now how do you retrieve those elements? With a vector or deque, it is possible to use the indexing operator[ ], but that doesn’t work with list. You can use iterators on all three sequences to access elements. Each container provides the appropriate type of iterator for accessing its elements^.

One more observation and then we’ll be ready for another example. Even though the containers hold objects by value (that is, they hold copies of whole objects), sometimes you’ll want to store pointers so that you can refer to objects from a hierarchy and therefore take advantage of the polymorphic behavior of the classes represented. Consider the classic "shape" example in which shapes have a set of common operations, and you have different types of shapes. Here’s what it looks like using the STL vector to hold pointers to various Shape types created on the heap:^.

//: C07:Stlshape.cpp

// Simple shapes w/ STL

#include

#include

using namespace std;

class Shape {

public:

  virtual void draw() = 0;

  virtual ~Shape() {};

};

class Circle : public Shape {

public:

  void draw() { cout << "Circle::draw\n"; }

  ~Circle() { cout << "~Circle\n"; }

};

class Triangle : public Shape {

public:

  void draw() { cout << "Triangle::draw\n"; }

  ~Triangle() { cout << "~Triangle\n"; }

};

class Square : public Shape {

public:

  void draw() { cout << "Square::draw\n"; }

  ~Square() { cout << "~Square\n"; }

};

typedef std::vector Container;

typedef Container::iterator Iter;

int main() {

  Container shapes;

  shapes.push_back(new Circle);

  shapes.push_back(new Square);

  shapes.push_back(new Triangle);

  for(Iter i = shapes.begin();

      i != shapes.end(); i++)

    (*i)->draw();

  // ... Sometime later:

  for(Iter j = shapes.begin();

      j != shapes.end(); j++)

    delete *j;

} ///:~

The creation of Shape, Circle, Square, and Triangle should be fairly familiar. Shape is a pure abstract base class (because of the pure specifier =0) that defines the interface for all types of shapes. The derived classes redefine the virtual function draw( ) to perform the appropriate operation. Now we’d like to create a bunch of different types of Shape objects, but where to put them? In an STL container, of course. For convenience, this typedef:

typedef std::vector Container;

creates an alias for a vector of Shape*, and this typedef:

typedef Container::iterator Iter;