Let's examine a few of the ways you can use existing Standard C++ Library containers to create your own containers. For example, say you want to implement a set container that enforces unique values that are not inherently sorted. You also want a group of algorithms to operate on that set. The container is certainly a sequence, but not an associative container, since an associative container is, by definition, sorted. The algorithms will presumably work on other sequences, assuming those sequences provide appropriate iterator types, since the iterator required by a set of algorithms determines the range of containers those algorithms can be applied to. The algorithms will be universally available if they only require forward iterators. On the other hand, they'll be most restrictive if they require random access iterators.
Simple implementations of this set container could make use existing Standard Library containers for much of their mechanics. Three possible ways of achieving this code re-use are:
Inheritance;
Generic inheritance;
Generic composition.
Let's take a look at each of these approaches.
The new container could derive from an existing standard container, then override certain functions to get the desired behavior. One approach would be to derive from the vector container, as shown here:
#include <vector>
// note the use of a namespace to avoid conflicts with standard // or global names
namespace my_namespace {
template <class T, class Allocator = std::allocator>
class set : public std::vector<T,Allocator>
{
public:
// override functions such as insert
iterator insert (iterator position, const T& x)
{
if (find(begin(),end(),x) == end())
return vector<T,Allocator>::insert(position,x);
else
return end(); // This value already present!
}
_
};
} // End of my_namespace
A second approach is to create a generic adaptor, rather than specifying vector. You do this by providing the underlying container through a template parameter:
namespace my_namespace {
template <class T, class Container = std::vector<T> >
class set : public Container
{
public:
// Provide typedefs (iterator only for illustration)
typedef typename Container::iterator iterator;
// override functions such as insert
iterator insert (iterator position, const T& x)
{
if (find(begin(),end(),x) == end())
return Container::insert(position,x);
else
return end(); // This value already present!
}
_
};
} // End of my_namespace
If you use generic inheritance through an adaptor, the adaptor and users of the adaptor cannot expect more than default capabilities and behavior from any container used to instantiate it. If the adaptor or its users expect functionality beyond what is required of a basic container, the documentation must specify precisely what is expected.
The third approach uses composition rather than inheritance. (You can see the spirit of this approach in the Standard adaptors queue, priority_queue and stack. ) When you use generic composition, you have to implement all of the desired interface. This option is most useful when you want to limit the behavior of an adaptor by providing only a subset of the interface provided by the container.
namespace my_namespace {
template <class T, class Container = std::vector<T> >
class set
{
protected:
Container c;
public:
// Provide needed typedefs
typedef typename Container::iterator iterator;
// provide all necessary functions such as insert
iterator insert (iterator position, const T& x)
{
if (find(c.begin(),c.end(),x) == c.end())
return c.insert(position,x);
else
return c.end(); // This value already present!
}
_
};
} // End of my_namespace
The advantages of adapting existing containers are numerous. For instance, you get to reuse the implementation and reuse the specifications of the container that you're adapting.