RE: Boost algorithm library (Was: [boost] New upload: algorithm.z ip 1)

From: Aleksey Gurtovoy (alexy_at_[hidden])
Date: 2001-07-29 04:02:37

David Abrahams wrote:
> I worry that even dispatching through a function template to 
> arrive at a specializable class template may be problematic:
> the point where the compiler realizes it's handling a type 
> for which the algorithm was not intended may come too late 
> (inside the dispatching function). 

So.. what are the implications of this (besides a possibly confused user of
the library)? Is it any different from what (most likely) will happen if you
try to compile the following code?

struct nothing {};
int main()
{
    // a compilation error inside of std::adjacent_find!
    std::unique(nothing(), nothing());
}

BTW, concept checking may provide a (partial?) answer to this issue.

> 
> Anyway, another technique we ought to consider is that of
> /embracing/ overload resolution instead of avoiding it. Since 
> some functions can only be called without qualification (see 
> the Barton & Nackmann technique used by the operators library), 
> it might be better to use a special tag type to indicate which 
> library's semantics are intended:
> 
> template <class S>
> typename boost::sequence_traits<S>::iterator begin(S const&, 
> boost::tag);
> 
> So instead of boost::begin(s) we're going to call begin(s, 
> boost::tag())
> 
> Of course, if you try to make that more convenient by adding:
> 
>   namespace boost {
>     template <class S>
>     typename boost::sequence_traits<S>::iterator begin(S const& s)
>     {
>         return begin(s, boost::tag);
>     }
>   }

This is _very_ interesting, Dave! I've read your proposal before, but didn't
have time to really thought about it. Now, when I did spend some time on it,
I can say that I find it quite appealing. 

A few minor problems that I see:

1) Library author(s) should always remember to use unqualified names for
dispatching functions (begin(s, boost::tag)), and qualified names for
top-level interface functions (boost::begin(s)) when they are used
internally by the library itself. Given that (at least without proper tests)
failure to do so won't result in an immediate compile-time error, chances
are that this could become a common source of subtle bugs. Also, if both
forms are "co-located", the "inconsistency" can be confusing,

template<class Sequence>
inline
bool empty(Sequence& seq, boost::tag_t)
{
    return boost::begin(seq) == boost::end(seq); // ok
}

template<class Sequence>
inline
bool empty(Sequence& seq)
{
    return empty(seq, boost::tag); // ???
}

and there is a possibility that one day someone would "fix" it. 

2) Unfortunately, Koenig lookup seems to fall into the same category of
language features as partial specialization of class templates - there are
still some popular compilers that do not implement it in full; in
particular, MSVC supports it only for operator functions. It means that if
we are going to use the technique in its original form, it would be
effectively impossible for users of such compilers to provide any
"specializations" of library's default algorithms. Of course, there are some
ways around this issue. For example, instead of 

template<class Sequence>
inline
typename boost::sequence_traits<Sequence>::iterator 
begin(Sequence& seq, boost::tag_t)
{
    return seq.begin();
}

template<class Sequence>
inline
typename boost::sequence_traits<Sequence>::iterator 
begin(Sequence& seq)
{
    return begin(seq, boost::tag);
}

one can write this:

struct begin_algorithm_tag {};

template<class Sequence>
inline
typename boost::sequence_traits<Sequence>::iterator 
operator%(Sequence& seq, boost::begin_algorithm_tag)
{
    return seq.begin();
}

template<class Sequence>
inline
typename boost::sequence_traits<Sequence>::iterator 
begin(Sequence& seq)
{
    return seq % boost::begin_algorithm_tag();
}

Given that difference between "operator%(Sequence& seq,
boost::begin_algorithm_tag)" and "begin(Sequence& seq, boost::tag_t)" can be
hidden behind a macro, it's not that bad as it might seem at first sight :)

Aleksey