[boost] Re: [range] update on ADL hooks

From: David Abrahams (dave_at_[hidden])
Date: 2005-03-25 11:17:31

David Abrahams <dave_at_[hidden]> writes:

> Things to notice:
>
> - ADL is limited to *one* name, lookup_implementation()
>
> - ADL is decoupled from the actual types being passed to algorithms
>   via their category tags
>
> - You can write generalized lookup_implementation() functions like the
>   one shown, that choose some rules by which to dispatch all
>   algorithms
>
> - You can write specific lookup_implementation functions to set
>   different rules for particular algorithms.

I should point out that the primary advantage of what we've done in
the posted code is *not* limiting semantic uncertainty and name
reservation due to ADL (though I happen to like that feature).  The
primary advantage is pluggable handling for new algorithm
implementation strategies and iterator/range concepts.

Note that where algorithms are concerned, the old adage that you
should "implement your class and the function customizations for it in
the same namespace" just doesn't apply.

If Joe implements a deque-like segmented structure and Mary implements
a circular queue (which is also segmented and subject to the same
algorithm optimizations), should each of them supply a copy of a
hierarchical copy, unique, transform, etc. implementation?  Clearly
not.

*That* is what defeats normal overloading as a viable technique for
customization.  The namespace containing the right algorithm
implementation is not neccessarily an "associated namespace" of these
ranges or iterators -- the actual arguments passed to an algorithm --
so it won't be searched by ADL.

Instead one must do dispatching via category tags associated with the
data structures, and to preserve a sane interface for callers of the
algorithms, that dispatching has to be hidden.  This is the same idea
as used by most standard library implementations, except:

  * We can add new argument concepts and implementation strategies
    into the system non-intrusively

  * The algorithm's exact return type may not be deducible without
    knowing the chosen implementation strategy.

  * The implementation strategy to use may depend on a _combination_
    of the concepts modeled by the algorithm's arguments, instead of
    just one.  We don't want to end up with combinatoric numbers of
    implementation overloads for each algorithm.  At worst we've
    limited the problem to needing a combinatoric number of
    simple lookup_implementation overloads for each implementation
    strategy.  In general there will be far more algorithm
    implementations than strategies, so this is a big win.

The fact that we can't handle cases like this without a level of
dispatching machinery in C++03 indicates one of those problems I was
referring to.

-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com