[boost] Abstract STL Container Adaptors

Subject: [boost] Abstract STL Container Adaptors
From: Andy Jost (Andrew.Jost_at_[hidden])
Date: 2013-03-14 13:20:55

Hi Boosters,

Is there any interest in an abstract container adaptor library (I'll describe what I mean below)?  I'm a little surprised if this has never come up in the context of Boost, but I couldn't find anything on the archives.  I did find something on stack overflow (http://stackoverflow.com/questions/5329555/abstract-wrapper-for-stl-containers), but it did not uncover an existing solution.

Motivation:

Sometimes we want to write functions that take a container as an argument.  For instance, say I have a graph object implemented in terms of ``class Node``.  I may expose an algorithm like this:

void my_algorithm(Node & root, std::set<Node const *> const & marked);

In this case, ``root`` is the root of a graph, and ``marked`` is a set of marked nodes.  The problem with this approach is that it forces a particular choice of the set implementation onto the caller.  He may, for example, prefer to use ``tr1::unordered_set``.  We could get around that limitation by using a template parameter, like this:

                template<typename Set> void my_algorithm(Node & root, Set const & marked);

The problem here is that it forces the implementer of ``my_algorithm`` to expose that code and, potentially, recompile it many times (for different Set types).

In some cases, particularly when compile times are more critical than execution times, it would be preferable to let the caller choose the set implementation without losing the advantages of separate compilation.  A simple solution is to write an adaptor that mimics the interface of ``set``.  With that, the function call would appear as shown here:

                void my_algorithm(Node & root, abstract_set<Node const *> const & marked);

Here, abstract_set<Node const *> is implicitly convertible from any type having the interface of std::set<Node const *>.  It internally holds a reference to some implementation of a suitable set-like object and mediates interactions with the outside world through virtual methods.

It seems the implementation of this would be a straightforward application of type erasure.  It seems too easy, in fact, which makes me wonder whether I'm missing something.

In any case, is this a good idea?

-Andy