Re: [boost] Abstract STL Container Adaptors

Jeffrey Lee Hellrung, Jr. wrote:

On Thu, Mar 14, 2013 at 10:20 AM, Andy Jost 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-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].

There are also some algorithms of a nature that are large with many variations and performance critical enough that you can't really afford to instantiate all variations in code with templates and you can't afford the overhead of internal runtime dispatch. A good example of this would be a complex software renderer. There are configurable paths but the path is known at the start of the algorithm and will not change for a given set of data. For example the properties of a vertex that must be interpolated over the face of a triangle in addition to position there may be any/all/none of texture coordinates, normals, colors, etc. You can't really afford any dispatch in code that is in such an inner loop but instantiating all possible options and compile time would lead to a huge code bloat, especially when most of the configurations would never be used in practice. A solution to these types of problems is essentially jit compiling the algorithm to run by fitting together prefabricated blocks depending on all the configuration as if you were doing template instantiation at runtime. I think it would be an interesting area of exploration. http://tinyurl.com/optimizing-pixomatic1 http://tinyurl.com/optimizing-pixomatic2 http://tinyurl.com/optimizing-pixomatic3