Re: [boost] [Review:Algorithms] is_ordered name

Subject: Re: [boost] [Review:Algorithms] is_ordered name
From: Brent Spillner (spillner_at_[hidden])
Date: 2011-09-24 13:08:06

On Sat, 24 Sep 2011 08:12:06 Andrew Sutton wrote:
>I'm not sure I understand the recommendation. Are you saying that if I write:
>
>auto i = is_ordered(f, l, r)
>
>Then I should have:
>
>is_increasing(f, i);

Yes, /and/ that (f, i) is the longest continuous prefix that maintains
this property.  Right now the code reads

        FI next = first;
        while ( ++next != last )
        {
            if ( !p ( *first, *next ))
                return first;
            first = next;
        }
        return last;

i.e. for the sequence { 1, 2, 3, 5, 4, ... } and comparison predicate
std::less, the loop will terminate when *first == 5 and *next == 4,
and return the iterator pointing before 5.  In other words, 5 is
considered the out-of-order element, even though { 1, 2, 3, 5 } is an
ordered sequence.  I think this is logically inconsistent with the
behavior when the entire sequence is found to be ordered (i.e. returns
past-the-end rather than an iterator pointing before the first
element.)  In other words, appending values to an ordered sequence can
cause the prefix subsequence spanned by the start iterator and the
return value of is_ordered() to shorten (i.e. if you declare int v[] =
{ 1, 2, 3, 5, 4 }, the return value of is_increasing(v, v + 5) is less
than the return value of is_increasing(v, v + 4).)  Returning the
value of 'next' instead would resolve the inconsistency and match the
behavior (as I understand it) of the new std::is_sorted_until().

There is of course a convenience counterargument, that for
ForwardIterators it's easier to compute the value of 'next' (if that's
what you really want) given the value of 'last' than it is to compute
the value of 'last' from the value of 'next', and that's probably what
Marshall had in mind.  I just happen to think that the risk of user
confusion (especially given the deviance from std::is_ordered_until())
outweighs the benefit.

>I think ordered_until is a reasonable name.

Works for me too, although I think it's best to follow the standard
where there's already a standard library function that does the same
thing.