Boost logo

Boost :

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


Boost list run by bdawes at, gregod at, cpdaniel at, john at