Re: Boost algorithm library (Was: [boost] New upload: algorithm.zip 1)

From: Vladimir Prus (ghost_at_[hidden])
Date: 2001-07-26 05:34:40

On Thursday 26 July 2001 01:55, Vesa Karvonen wrote:

> I think that the essential question is: What support should a container
> library provide for extending the library?
>
> My opinion is that a generic C++ container library should provide means for
> writing generic overloaded functions on containers, and STL specifically
> does not provide such support. This means that in order to write overloaded
> algorithm wrappers for standard containers, you need to repeat the wrappers
> for each container (10x work) or change the names of the algorithm
> functions (ugly).

Or just reimplement all the STL algorithms in namespace boost with 
appropriate changes.

> Before continuing, I'd like to emphasize that we really need overloading
> support. The problem is that without such support, you end up writing
> overly generic functions for containers. An overly generic function
> partially or completely defeats the compile-time type checking and
> overloading capabilities of the C++ language. 

Right.

> Providing generic overloading support is not difficult. Basically, all you
> need to do is to make sure that a container is-a instance of a class
> template with a single template parameter, so that you can write an
> algorithm on the template, that basically uses "pattern matching" to enable
> overloading:
>
>     template<class base, class t, class bin_op>
>     t accumulate(const container<base>& c, t x, bin_op op);

I have tried something similar some time ago. In my case class 
Container<base>, derived from class Concept, simply had reference to base 
object. Other component was function metaclass, which accessed compile time 
list containing all the concepts class implements and created object derived 
from all concepts, for example:
        class A {};
        class B {};

        void find_c(const SortedContainer<B>&,  const T&);
        void find_c(const Container<B>&, const T&);

        void find_c(const T1& t1, const T2& t2)
        {
                // Supposing that T1=B and B is declared as model of SortedContainer and
                // FunnyConcept then metaclass will return metaclass_t<B> object which 
                // will be derived from SortedContainer<B> and FunnyConcept<B>
                find_c(metaclass(t1), t2);
        }
The biggest problem was creating those compile-time lists of concepts, and I 
don't have a good solution.	

> [snip]

> It is not too difficult to construct containers like that. For example, you
> can use 3 type of layers:
> - body layers (these implement the container)
> - concept layers (these describe the type of the container for overloading)
> - constructor layer (this layer contains all the constructors appropriate
> for the container type)

OK, this is reasonable. In fact, all is needed is to write wrappers for all 
containers in namespace boost. It is also possible to create something like
'container_traits', write algorithm wrappers and use traditional despatch 
methods.

> In order to avoid type-slicing, a language should support constrained
> genericity and the type constraints should be considered at overloading
> time, so that the most "specialized" function whose type constraints pass
> is called.

It really should. But nobody can be sure that even 'typeof' will appear in 
next revision of the standard, not to say about constrained genericity and 
similar things.

-- 
Regards,
Vladimir