Re: [boost] Boost.Algorithms request

Subject: Re: [boost] Boost.Algorithms request
From: Lorenzo Caminiti (lorcaminiti_at_[hidden])
Date: 2011-10-09 21:23:49

On Sun, Oct 9, 2011 at 6:45 PM, Marshall Clow <mclow.lists_at_[hidden]> wrote:
> On Oct 9, 2011, at 3:11 PM, Joshua Juran wrote:
>
>> On Oct 9, 2011, at 5:28 AM, Zoltán Tóth wrote:
>>
>>> I ask to change the name of function is_ordered(). The "is_" prefix
>>> suggests that it is a boolean function which it is not. Also, there
>>> are other functions there with prefix "is_" and which are boolean
>>> functions, and this non-uniformity hurts the eye. I suggest the name
>>> "first_misordered".
>>
>> Another possible name is "first_out_of_order".  I'm not sure I like it better, but maybe someone else does.
>
> I think the consensus is that if we change the name, it should be changed to "is_sorted_until", which is what the C++11 standard uses.

Yes, as it was discussed during Boost.Algorithm review, from the C++11 standard:

// 25.4.1, sorting:

template<class ForwardIterator>
bool is_sorted(ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
bool is_sorted(ForwardIterator first, ForwardIterator last, Compare comp);

template<class ForwardIterator>
ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator
last, Compare comp);

So it would be best if this is_ordered is renamed to is_sorted_until.

To model C++11, it might make sense to also provide the version
without the comparison predicate (which uses operator< by default) and
the is_sorted boolean functions which simply return
is_sorted_until(...) == last. From the C++11 standard:

25.4.1.5 is_sorted [is.sorted]

template<class ForwardIterator>
bool is_sorted(ForwardIterator first, ForwardIterator last);

1 Returns: is_sorted_until(first, last) == last

template<class ForwardIterator, class Compare>
bool is_sorted(ForwardIterator first, ForwardIterator last, Compare comp);

2 Returns: is_sorted_until(first, last, comp) == last

template<class ForwardIterator>
ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator
last, Compare comp);

3 Returns: If distance(first, last) < 2, returns last. Otherwise,
returns the last iterator i in [first,last] for which the range
[first,i) is sorted.
4 Complexity: Linear.

--Lorenzo