Containers

• Separation of contained object constructors/destructors and memory allocation/deallocation
• Parameterized with object type and allocator
• All are "direct" containers (see also the polymorphic class problem)

vector

• Vectors are composed of a single block of sequential memory, just like C vectors (see diagram).
• Memory extended in multi-object blocks.
• Memory is freed when the vector object is destroyed.
• Use when objects are inserted/removed primarily at the end.
• Inefficiency: Overflow condition can cause a complete copy.
• Type requirements for T: T(); T(const T&); ~T(); T& operator=(const T&);

#include < iostream.h >
#include < vector.h >
void print (vector < double >& vector_)
{
  for (int i = 0; i < vector_.size (); i++)
    cout << vector_[i] << " ";
  cout << endl;
}

int main ()
{
  vector < double > v1; // Empty vector of doubles.
  v1.push_back (32.1);
  v1.push_back (40.5);
  vector< double > v2; // Another empty vector of doubles.
  v2.push_back (3.56);
  cout << "v1 = ";
  print (v1);
  cout << "v2 = ";
  print (v2);
  v1.swap (v2); // Swap the vector's contents.
  cout << "v1 = ";
  print (v1);
  cout << "v2 = ";
  print (v2);
  v2 = v1; // Assign one vector to another.
  cout << "v2 = ";
  print (v2);
  return 0;
}

v1 = 32.1 40.5
v2 = 3.56
v1 = 3.56
v2 = 32.1 40.5
v2 = 3.56

• Deques are composed of fixed-size multi-object blocks of memory with a "map" block (see diagram).
• Memory is freed when the vector object is destroyed.
• Use when objects are inserted/removed primarily at the end or the beginning.
• Inefficiency: no complete copies, but operator[] is a bit slower. 0
• Type requirements for T: T(); T(const T&); ~T(); T& operator=(const T&);

#include < iostream.h >
#include < deque.h >

int main ()
{
  deque< int > d;
  d.push_back (4); // Add after end.
  d.push_back (9);
  d.push_back (16);
  d.push_front (1); // Insert at beginning.
  for (int i = 0; i < d.size (); i++)
    cout << "d[" << i << "] = " << d[i] << endl;
  cout << endl;
  d.pop_front (); // Erase first element.
  d[2] = 25; // Replace last element.
  for (i = 0; i < d.size (); i++)
    cout << "d[" << i << "] = " << d[i] << endl;
  return 0;
}

d[0] = 1
d[1] = 4
d[2] = 9
d[3] = 16

d[0] = 4
d[1] = 9
d[2] = 25

• Lists are composed prev-object-next blocks (see diagram).
• Objects are allocated from same-type static private pool. (see diagram)
• Memory isn't freed until every member of the class is destroyed.
• Use when objects are inserted/removed anywhere in the list.
• No operator[].
• Inefficiency: highest overhead.
• Type requirements for T: T(); T(const T&); ~T(); T& operator=(const T&); T* operator&(); int operator < (const T&, const T&); int operator==(const T&, const T&);

#include < iostream.h >
#include < list.h >

int array1 [] = { 9, 16, 36 };
int array2 [] = { 1, 4 };

int main ()
{
  list< int > l1 (array1, array1 + 3);
  list< int > l2 (array2, array2 + 2);
  list< int >::iterator i1 = l1.begin ();
  l1.splice (i1, l2);
  list< int >::iterator i2 = l1.begin ();
  while (i2 != l1.end ())
    cout << *i2++ << endl;
  return 0;
}

1
4
9
16
36

stack < vector < int > > a;