Generic container idioms

Developing generic containers in C++ can become complex if you want to develope truly generic containers (as much as they can get). Relaxing the requirements on type T is the key behind developing truly generic containers. There a few C++ idioms to actually achieve the "lowest denominator" possible with requirements on type T.

It is easy to come up with a generic stack which requires following operations defiend on type T: a default constructor, a copy constructor, a non-throwing destructor and a copy assignment operator. But thats too much!

The requirements can be reduced to the folloing list: a copy constructor and a non-throwing destructor.

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 following two techniques:

1. operator new:
void * mem = operator new (sizeof (T) * NUMBER_OF_ELEMENTS);

2. construct helper using placement new:
template <class T1, class T2>
void construct (T1 *p, const T2 &value) {
new (p) T1(value);
}

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.

Moreover, pointers in the range [end, end_of_allocated_range) should not point to objects of type T, but to uninitialized memory. (end can be considered an iterator pointing at an element one past the last initialized element of the container)

When an element is removed from the container, destructot should be invoked on them. A destroy helper function can be helpful here as shown.

template <class T>
void destroy (T *p) {
p->~T();
}

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.

Please see More C++ gems for elaborate articles on this topic. (authors Hurb Sutter and Matthew H. Austern)