On Thu, Mar 14, 2013 at 10:20 AM, Andy Jost
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-containe...), 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
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
const & marked); Here, abstract_set
is implicitly convertible from any type having the interface of std::set . 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?
Despite the other comments, this has a legitimate use case: - The algorithm is code-wise large and called many times on different containers, or, say, embedded within compiled library, so either it isn't practical or isn't possible to inline it. - The dispatch overhead from the type erasure is negligible compared with other operations in the algorithm. - You want to avoid imposing unnecessary memory requirements on the caller, such as forcing them to copy their data into a specific data structure. Off the top of my head, computational geometry algorithms are sometimes of this nature. Additionally, I think this functionality is basically or entirely present in Steven Watanabe's Boost.TypeErasure library [1; warning: docs may be outdate, I just did a Google search]. - Jeff [1] http://steven_watanabe.users.sourceforge.net/type_erasure/libs/type_erasure/...