Re: [boost] STL algorithm requirements (was Review: concept checks.)

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2000-12-03 17:56:34

On Sun, 3 Dec 2000, John E. Potter wrote:
> > What the file does is use the concept archetypes to try to determine what
> > the minimal requirements are for various STL implementations, so far SGI
> > STL (as distributed with g++) and the KAI STL (I think that's modified
> > modena?).
> 
> I think the file shows that these implementations meet the requirements
> given.  It may be very hard to get these down to the minimum that the
> algorithms actually require.

True, but I didn't follow the given or "documented" requirements. I tried
to reduce the archetypes to the minimum, though whether I succeeded is
certainly up for debate, and I certainly did not put as much effort into
minimizing every single function. This was a "first stab".

> > There were several things that surprised me, such as how
> > using the conditional operator ?: in algorithm implementations affects
> > the requirements.
> 
> The true and false types must be convertable to some common type to
> use as the result?  I would have been surprised too if I had not just
> looked at that part of the standard for other reasons.  Or did you
> have something else in mind?

Surprise surprise ;) Here's what is done:

5.16 p3

"Otherwise, if the second and third operand have different types, and
either has class type, an attempt is made to convert each of those operads
to the type of the other"

So the conversion is not to some common type, but from one to the other.
This is surprising because using an "if-else" statement would not have
requirement conversion from one to the other, but to a common type (like
the result iterator's value type).

> Some comments:
> 
> The random_shuffle and random_selection algorithms which take a ran
> did not compile with my g++ 2.95.2.  Problems with the reference
> producer getting a default_construtable when a ptrdiff_t was expected.

Hmm, that's funny, they work for me with 2.95.2. I wonder what the
difference is in our environment.

> I've hacked away at the binary_search part since that is of current
> interest to me.
> 
> >   {
> > #if defined(__KCC)
> >     // The KAI version of this uses a one-argument less-than function
> >     // object.
> 
> I would like to see this code to learn how it changes the requirements.

Here's the code. The important part is the use of __kai::default_less

// Section 25.3.3 -- Binary search

// Section 25.3.3.1 -- lower_bound

template <class ForwardIterator, class T, class Compare>
ForwardIterator __lower_bound(ForwardIterator first, ForwardIterator last,
                              const T& value, Compare comp,
forward_iterator_tag *)
{
    typedef  typename iterator_traits<ForwardIterator>::difference_type
Distance;
    Distance len =  distance(first, last);
    Distance half;
    ForwardIterator middle;

    while (len > 0) {
        half = len / 2;
        middle = first;
        advance(middle, half);
        if (comp(*middle, value)) {
            first = middle;
            ++first;
            len = len - half - 1;
        } else
            len = half;
    }
    return first;
}

template <class RandomAccessIterator, class T, class Compare>
RandomAccessIterator __lower_bound (RandomAccessIterator first,
RandomAccessIterator last,
                                    const T& value, Compare comp,
random_access_iterator_tag *)
{
    typedef  typename
iterator_traits<RandomAccessIterator>::difference_type Distance;
    Distance len = last - first;
    Distance half;
    RandomAccessIterator middle;

    while (len > 0) {
        half = len / 2;
        middle = first + half;
        if (comp(*middle, value)) {
            first = middle + 1;
            len = len - half - 1;
        } else
            len = half;
    }
    return first;
}

template <class ForwardIterator, class T>
inline ForwardIterator lower_bound(ForwardIterator first, ForwardIterator
last, const T& value)
{
    typedef  typename iterator_traits<ForwardIterator>::iterator_category
Category;
    return __lower_bound(first, last, value, __kai::default_less<T>(),
(Category *)0);
}

template <class ForwardIterator, class T, class Compare>
inline ForwardIterator lower_bound(ForwardIterator first, ForwardIterator
last, const T& value,
                            Compare comp)
{
    typedef  typename iterator_traits<ForwardIterator>::iterator_category
Category;
    return __lower_bound (first, last, value, comp, (Category *)0);
}

> >     typedef less_than_comparable_archetype<> FT;
> >     typedef convertible_to_archetype<FT> T;
> > #else
> >     typedef less_than_op_first_archetype<> FT;
> >     typedef less_than_op_second_archetype<> T;
> > #endif
> >     forward_iterator_archetype<FT> fi;
> >     T value(dummy_cons);
> >     fi = std::lower_bound(fi, fi, value);
> >   }
> 
> That is what I would expect.
> 
> >   {
> >     typedef null_archetype<int> Arg1;
> >     typedef null_archetype<char> Arg2;
> >     typedef convertible_to_archetype<Arg1> FT;
> >     typedef convertible_to_archetype<Arg2> T;
> >     forward_iterator_archetype<FT> fi;
> >     T value(dummy_cons);
> >     binary_predicate_archetype<Arg1, Arg2> comp(dummy_cons);
> >     fi = std::lower_bound(fi, fi, value, comp);
> >   }
> 
> I don't understand why the convertable_to can be used here but
> not above.

The predicate takes to arguments, Arg1 and Arg2, and the value_type and T
need to be convertible to them.

In the case of using operator<, the particular operator< is deduced from
value_type and T, there is no specified predicate object from which to
know that Arg1 and Arg2 should be.

> Does the binary_predicate_archtype test using the
> algorithm with a function pointer?

No, the binary_predicate_archetype is a function object.

> >   {
> > #if defined(__GNUC__)
> >     typedef less_than_op_first_archetype<
> >       less_than_op_second_archetype<> > FT;
> >     typedef less_than_op_second_archetype<
> >       less_than_op_first_archetype<> > T;
> 
> These requirements are way to permissive.

I was trying to encode the requirement of

T < FT
FT < T

but you are right, the archetype implementation is wrong... I'll look into
this.

> > #else
> >     typedef less_than_op_first_archetype<> FT;
> >     typedef less_than_op_second_archetype<> T;
> 
> I can't believe this conforms.  I can write one, but mine would take
> lg(N) + 2 and the standard requires lg(N) + 1.  Does it really
> compile and work as required?  Why does KAI not use a function
> object here?

Oops. That doesn't work for KAI. The following does:

    typedef less_than_comparable_archetype<> T;
    typedef convertible_to_archetype<T> FT;

I also checked if your suggestion below for g++ also works 
for KAI. It doesn't.

> > #endif
> >     forward_iterator_archetype<FT> fi;
> >     T value(dummy_cons);
> >     fi = std::upper_bound(fi, fi, value);
> >   }
> 
> Here is a version with less requirements which works for g++.  Note
> that it is just lower_bound with the types reversed.  Lower_bound
> needs *it < value and upper_bound needs value < *it.  They put the
> equality on the correct side for the algorithms.
> 
>    {
>      typedef less_than_op_first_archetype<> T;
>      typedef less_than_op_second_archetype<> FT;
>      forward_iterator_archetype<FT> fi;
>      T value(dummy_cons);
>      fi = std::upper_bound(fi, fi, value);
>    }

Ok.

> >   {
> >     typedef null_archetype<int> Arg1;
> >     typedef null_archetype<char> Arg2;
> > #if defined(__GNUC__)
> >     typedef convertible_to_archetype<Arg1,
> >       convertible_to_archetype<Arg2> > FT;
> >     typedef convertible_to_archetype<Arg2,
> >       convertible_to_archetype<Arg1> > T;
> 
> As above.
> > #else
> >     typedef convertible_to_archetype<Arg1> FT;
> >     typedef convertible_to_archetype<Arg2> T;
> 
> Again.
> 
> > #endif
> >     forward_iterator_archetype<FT> fi;
> >     T value(dummy_cons);
> >     binary_predicate_archetype<Arg1, Arg2> comp(dummy_cons);
> >     fi = std::upper_bound(fi, fi, value, comp);
> >   }
> 
> Below the stated minimum for g++.
> 
>    {
>      typedef null_archetype<int> Arg1;
>      typedef null_archetype<char> Arg2;
>      typedef convertible_to_archetype<Arg1> T;
>      typedef convertible_to_archetype<Arg2> FT;
>      forward_iterator_archetype<FT> fi;
>      T value(dummy_cons);
>      binary_predicate_archetype<Arg1, Arg2> comp(dummy_cons);
>      fi = std::upper_bound(fi, fi, value, comp);
>    }

Ok, this looks better.

> Why these are too permissive.
> 
> >     typedef less_than_op_first_archetype<
> >       less_than_op_second_archetype<> > FT;
> >     typedef less_than_op_second_archetype<
> >       less_than_op_first_archetype<> > T;
> 
> There are four possible compares:
>   *it < v
>   *it < *it
>   v < v
>   v < *it
> 
> The equal_range and binary_search algorithms require only the two
> with different types.  The above types allow all four.  I guess
> that this may be a challenge for the concept classes.  Is it
> possible to have types A and B such that A < B and B < A are
> allowed, but A < A and B < B are not?

Right, the archetypes need to be constructed differently...
Might have to do a special archetype just for this situation.

> Lest there be any doubt, I think this program is a great contribution.
> My comments are intended to be constructive.

Thanks!

Jeremy

----------------------------------------------------------------------
 Jeremy Siek                        www: http://www.lsc.nd.edu/~jsiek/
 Ph.D. Candidate                  email: jsiek_at_[hidden]
 Univ. of Notre Dame         work phone: [phone]
----------------------------------------------------------------------