Generic Container Idioms

Intent

To create generic container classes (vector, list, stack) that impose minimal requirements on their value types. The requirements being only a copy-constructor and a non-throwing destructor.

Motivation

Developing generic containers in C++ can become complex if truly generic containers (like STL) are desired. Relaxing the requirements on type T is the key behind developing truly generic containers. There are a few C++ idioms to actually achieve the "lowest denominator" possible with requirements on type T.

Lets take an example of a Stack.

template<class T>
class Stack
{
  int size_;
  T * array_;
  int top_;
 public:
  Stack (int size=10)
   : size_(size),
    array_ (new T [size]), // T must support default construction
    top_(0)
  { }
  void push (const T & value)
  {
   array_[top_++] = value; // T must support assignment operator.
  }
  T pop ()
  {
   return array_[--top_]; // T must support copy-construction. No destructor is called here
  }
  ~Stack () throw() { delete [] array_; } // T must support non-throwing destructor
};

Other than some array bounds problem, above implementation looks pretty obvious. But it is quite naive. It has more requirements on type T than there needs to be. The above implementation requires following operations defined on type T:

A default constructor for T
A copy constructor for T
A non-throwing destructor for T
A copy assignment operator for T

A stack ideally, should not construct more objects in it than number of push operations performed on it. Similarly, after every pop operation, an object from stack should be popped out and destroyed. Above implementation does none of that. One of the reasons is that it uses a default constructor of type T, which is totally unnecessary.

Actually, the requirements on type T can be reduced to the following using construct and destroy generic container idioms.

A copy constructor
A non-throwing destructor.

Solution and Sample Code

To achieve this, a generic container should be able to allocate uninitialized memory and invoke constructor(s) only once on each element while "initializing" them. This is possible using the following three generic container idioms:

#include <algorithm>
// construct helper using placement new:
template <class T1, class T2>
void construct (T1 &p, const T2 &value)
{
 new (&p) T1(value); // T must support copy-constructor
}

// destroy helper to invoke destructor explicitly.
template <class T>
void destroy (T const &t) throw ()
{
 t.~T(); // T must support non-throwing destructor
}

template<class T>
class Stack
{
  int size_;
  T * array_;
  int top_;
 public:
  Stack (int size=10)
   : size_(size),
    array_ (static_cast <T *>(::operator new (sizeof (T) * size))), // T need not support default construction
    top_(0)
  { }
  void push (const T & value)
  {
   construct (array_[top_++], value); // T need not support assignment operator.
  }
  T top ()
  {
    return array_[top_ - 1]; // T should support copy construction
  }
  void pop()
  {
   destroy (array_[--top_]);   // T destroyed
  }
  ~Stack () throw()
  {
   std::for_each(array_, array_ + top_, destroy<T>);
   ::operator delete(array_); // Global scope operator delete.
  }
};
class X
{
 public:
  X (int) {} // No default constructor for X.
 private:
  X & operator = (const X &); // assignment operator is private
};
int main (void)
{
 Stack <X> s; // X works with Stack!

 return 0;
}

operator new allocates uninitialized memory. It is a fancy way of calling malloc. The construct helper template function invokes placement new and in turn invokes a copy constructor on the initialized memory. The pointer p is supposed to be one of the uninitialized memory chunks allocated using operator new. If end is an iterator pointing at an element one past the last initialized element of the container, then pointers in the range end to end_of_allocation should not point to objects of type T, but to uninitialized memory. When an element is removed from the container, destructor should be invoked on them. A destroy helper function can be helpful here as shown. Similarly, to delete a range, another overloaded destroy function which takes two iterators could be useful. It essentially invokes first destroy helper on each element in the sequence.

Known Uses

All STL containers employ similar techniques. They have minimal possible requirements on the template parameter types. On the other hand, some popular C++ libraries have stricter requirements on parameterizable types than necessary.

Related Idioms

There are several other generic container idioms.

References

Designing Exception Safe Generic Containers -- Herb Sutter