Re: [boost] Abstract STL Container Adaptors

Subject: Re: [boost] Abstract STL Container Adaptors
From: Jeffrey Lee Hellrung, Jr. (jeffrey.hellrung_at_[hidden])
Date: 2013-03-14 20:46:49

On Thu, Mar 14, 2013 at 10:20 AM, Andy Jost <Andrew.Jost_at_[hidden]>wrote:

> 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?
>

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/doc/html/boost_typeerasure/predef.html