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

From: Vesa Karvonen (vesa.karvonen_at_[hidden])
Date: 2001-07-25 16:55:53

From: "Fernando Cacciola" <fcacciola_at_[hidden]>
> From: <helmut.zeisel_at_[hidden]>
> > --- In boost_at_y..., "Fernando Cacciola" <fcacciola_at_g...> wrote:
[...]
> > I do not know what to do to provide
> > both version of the algorithms in a cheap way,
> > I think, however, that the most common usage
> > should be honored in some way.
> >
> I'm not sure if this should be provided by the library.
> It is very common for library users to add all sorts of wrappers and
> shortcuts, so this one in particular might be just something else that a
> particular user can do upon the library.

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).

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. (I have been delighted to find out that I'm not the only
one to have realized this problem. Barton & Nackman handle this issue in
Scientific and Engineering C++, when they design their famous algebraic
gategory templates.)

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);

Before continuing, I'd like to emhasize, that the above function does not use
partial specialization. This kind of overloading seems to be confused with
partial specialization quite often.

The container<base> layer can be (almost) completely abstract. In particular,
it needs to support passing parameters through to the base object. Example:

    template<class base>
    struct container : base
    {
    // ...
    protected:
      container() {}
      template<class p0t>
      container(p0t& p0) : base(p0) {}
    // ..
    };

A bit more difficult is to make it so that it is easy and safe to write such
overloaded functions. Consider the following code:

    template<class base, class t, class bin_op>
    t accumulate(const container<base>& c, t x, bin_op op)
    //                               ^^^
    { return std::accumulate(c.begin(), c.end(), x, op);
    //                       ^^^^^^^^^^^^^^^^^^
    }

First of all, container<base> should not be (publicly) constructible, because
it would then be possible to slice containers. Second, all the member
functions of the container, including the assignment operators, should be
accessible from container<base>.

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)

A container is then composed out of these layers using inheritance:

        body layers+
            A
            |
      concept layers+
            A
            |
     constructor layer

There is a particular unfortunate thing that comes to play with this style of
overloading support. I call it type-slicing. Namely, when you "pattern match"
the minimum concept that you need, you possibly slice out concepts that might
be useful for other algorithms. This can be avoided by explicitly inferring
the most derived type of a pattern matched parameter:

    template<class base>
    ... foo(container<base>& concept_c)
    { typename base::most_derived_type& c = infer(concept_c);
      ...
      bar(c);
      ...
    }

This is most unfortunate, but fortunately such explicit type inference is not
always needed, and the benefit that can be reaped from overloading is
generally much higher than the cost of explicit type inference.

Function templates whose all parameters are of pure template parameter type
are evil. (Perhaps an overstatement.)

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.