In the STL the containers are actually factory classes. They manage object lifespans,and memory allocation. This makes them behave rather strangely as abstract data types (ADT, e.g. stack, list, array, deque). For instance: you might think that you could create a reference to an object within an STL container, but unfortunately the object can be easily moved invalidating your reference silently. This kind of behaviour is frustrating at first, but logical when you consider that an STL collection has to grow/shrink to accomodate insertion/deletion.

In order to deal with this I apply the principle of separation of concerns: I create separate classes for my objects: an object lifetime manager, and an ADT. Usually the object manager is implemented as a linked list of arrays. I then create the appropriate ADT (e.g. tree, linked list, heap) which my algorithms operate on. To quote David Wheeler out of context:

"Any problem in computer science can be solved with another layer of indirection."

struct fubar { };
fubar x;
std::vector<fubar> v;
v.push_back(x); // the vector makes an internal copy of the object, therefore it is a factory.

> struct fubar { };
> fubar x;
> std::vector<fubar> v;
> v.push_back(x); // the vector makes an internal copy of
> the object, therefore it is a factory.
>