Does std::is_sorted allow to check a sequence that it is stictly sorted?

[Vlad from Moscow]

As any sort algorithm std::is_sorted requires to specify a compare function. So you can check for example using std::less functional object that the following sequence { 1, 1, 1 } is sorted.

 

However what compare function may be used to check that this sequence is not strictly sorted that is that it  contains duplicates?

 

That to be clear here is an example

 

{ 1, 1, 1 } is not strictly sorted

{ 1, 2, 3 } is strictly sorted.

 

 

[Vlad from Moscow]

It would be better to say strictly ordered instead of strictly sorted..

 

среда, 9 октября 2013 г., 21:25:23 UTC+4 пользователь Vlad from Moscow написал:

[Daniel Krügler]

2013/10/9 Vlad from Moscow <vlad....@mail.ru>:

> As any sort algorithm std::is_sorted requires to specify a compare function.
> So you can check for example using std::less functional object that the
> following sequence { 1, 1, 1 } is sorted.

Yes, because is_sorted tests increasing versus the used relation (< in
this case).

> However what compare function may be used to check that this sequence is not
> strictly sorted that is that it contains duplicates?

I'm confused: I must assume that you mean "is strictly sorted", and
not "is not strictly sorted"?

To test for strict increasing you need the complement of the converse
of the original relation, that is, the negation when the arguments are
inversed. For

a < b

this complement of converse is

!(b < a)

In a total order (here: int) this is the same as

!(a > b)

which again is

a <= b

So you can use std::less_equal<int> in this special case, but in
general you would indeed use a composed predicate that tests !(b < a).

- Daniel

[Vlad from Moscow]

The problem is that according to the C++ Standard I may not use std::less_equal for sort algorithms.

For example MS VC++ checks the function and generate an exception if to use std::less_equal.

 

среда, 9 октября 2013 г., 22:05:25 UTC+4 пользователь Daniel Krügler написал:

[Vlad from Moscow]

So it seems that we need one more function that will be named for example as  std::is_strictly_sorted.

 

среда, 9 октября 2013 г., 22:25:04 UTC+4 пользователь Vlad from Moscow написал:

[Daniel Krügler]

2013/10/9 Vlad from Moscow <vlad....@mail.ru>:

> So it seems that we need one more function that will be named for example as
> std::is_strictly_sorted.

I disagree that there is need for this function in the standard, just
use relation composition. Albeit it might be useful to consider
relation adaptors for complement and converse. We have one of the
(not2), but not the other.

- Daniel

[Vlad from Moscow]

I have not understood what you mean saying about relation composition. Could you show how is_sorted can be used to check strictl ordering such a way that the comparison function will not contradict the standard?

среда, 9 октября 2013 г., 23:02:52 UTC+4 пользователь Daniel Krügler написал:

[Daniel Krügler]

2013/10/9 Vlad from Moscow <vlad....@mail.ru>:

> I have not understood what you mean saying about relation composition. Could
> you show how is_sorted can be used to check strictl ordering such a way that
> the comparison function will not contradict the standard?

You make a good point, is_sorted requires a strict weak ordering, but
we want a more general function that simply requires a relation to
validate. I believe that we can already construct such a function
indirectly via adjacent_find. If a sequence is strictly ordered given
some binary relation (e.g. <), then adjacent_find will always reach
the end of the sequence, if the used predicate is the negation of
original one. In other words: This is finding the first mismatch of
adjacent elements given the provided relation.

With the currently limited std::not2 composition we can write this as:

std::adjacent_find(begin, end, std::not2(std::less<X>{})) == end

But assuming we can use the more powerful negator not_fn,

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3699.html

this should also be possible via the generic std::less<void>{} predicate:

std::adjacent_find(begin, end, std::not_fn(std::less<void>{})) == end

I tend to agree that we would like to have an algorithm, e.g.
is_relation_preserving, that hides the semantics of above test. Given
is_relation_preserving applied to some weak ordering r, your strict
ordering can be found by exactly this is_relation_preserving function,
while the non-strict form results by applying it again to the
complement of the converse of the relation.

But instead of inventing new algorithms, we could also consider
whether is_sorted really requires strict weak ordering. It currently
does so, because we have added it to [alg.sorting] imposing this
requirement, but that restriction might not be needed.

The standard itself never uses strict ordering, this is the reason why
I currently hesitate to add such a function. But it should be easy to
realize that intention. The currently blessed approach is based on
adjacent_find and the complement (negation) of the relation as shown
above.

- Daniel

> среда, 9 октября 2013 г., 23:02:52 UTC+4 пользователь Daniel Krügler
> написал:
>>
>> 2013/10/9 Vlad from Moscow <vlad....@mail.ru>:
>> > So it seems that we need one more function that will be named for
>> > example as
>> > std::is_strictly_sorted.
>>
>> I disagree that there is need for this function in the standard, just
>> use relation composition. Albeit it might be useful to consider
>> relation adaptors for complement and converse. We have one of the
>> (not2), but not the other.
>>
>> - Daniel
>

> --
>
> ---
> You received this message because you are subscribed to the Google Groups
> "ISO C++ Standard - Discussion" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to std-discussio...@isocpp.org.
> To post to this group, send email to std-dis...@isocpp.org.
> Visit this group at
> http://groups.google.com/a/isocpp.org/group/std-discussion/.

[Vlad from Moscow]

 

I wanted to give notice of that nobody refer to std::adjacent_find because it is not a good idea that the job that has to be done by std::is_sorted will be done by std::adjacent_find.

 

Nevertheless even if the restriction will be relaxed it is not a bad idea that there will be two names of the algorithm that will point out clear what ordering is checked.

четверг, 10 октября 2013 г., 0:18:38 UTC+4 пользователь Daniel Krügler написал:

[Daniel Krügler]

2013/10/9 Vlad from Moscow <vlad....@mail.ru>:
>

> I wanted to give notice of that nobody refer to std::adjacent_find because
> it is not a good idea that the job that has to be done by std::is_sorted
> will be done by std::adjacent_find.
>
> Nevertheless even if the restriction will be relaxed it is not a bad idea
> that there will be two names of the algorithm that will point out clear what
> ordering is checked.

I think it would be useful to have a function like my suggested
"is_relation_preserving" in the standard. It does not require a strict
weak ordering and it returns exactly the result that you have been
asking for in your original question, if the argument predicate is a
weak ordering.

- Daniel

[Vlad from Moscow]

It can be but word "sorted" is more natural in this context than "relation_preserved" because there is no algorithm that have word "relation" in its name.

On the other hand  is_relation_preserved gives a more freedom of its usage.

 

Do not forget to include me in the list of authors of the new algorithm.:)  

четверг, 10 октября 2013 г., 0:54:32 UTC+4 пользователь Daniel Krügler написал:

[Vlad from Moscow]

I think that as the name of the algorithm is_ordered also can be considered.

 

среда, 9 октября 2013 г., 21:25:23 UTC+4 пользователь Vlad from Moscow написал:

[Vlad from Moscow]

I think about that is_sorted should be appended with is_strictly_sorted and apart from these two algorithms there should be algorithm is_sequenced that allows to use any predicate instead of compare.

 

So I would like to propose the following set of algoritms

 

std::is_sorted - already exist but does not allow to check whether a sequence is strictly ordered

std::is_strictly_sorted - new algorithm for sorted seuence

std::is_sequenced - new algorithm with a predicate instead of compare function

четверг, 10 октября 2013 г., 18:23:01 UTC+4 пользователь Vlad from Moscow написал:

[Marshall Clow]

On Oct 26, 2013, at 2:41 AM, Vlad from Moscow <vlad....@mail.ru> wrote:

I think about that is_sorted should be appended with is_strictly_sorted and apart from these two algorithms there should be algorithm is_sequenced that allows to use any predicate instead of compare.

 

So I would like to propose the following set of algoritms

 

std::is_sorted - already exist but does not allow to check whether a sequence is strictly ordered

std::is_strictly_sorted - new algorithm for sorted seuence

std::is_sequenced - new algorithm with a predicate instead of compare function

[Coming into this discussion late.]

We already have:

template< class InputIt, class UnaryPredicate >
bool is_partitioned( InputIt first, InputIt last, UnaryPredicate p );

how would your "is_sequenced" differ from that?

-- Marshall

четверг, 10 октября 2013 г., 18:23:01 UTC+4 пользователь Vlad from Moscow написал:

I think that as the name of the algorithm is_ordered also can be considered.

 

среда, 9 октября 2013 г., 21:25:23 UTC+4 пользователь Vlad from Moscow написал:

As any sort algorithm std::is_sorted requires to specify a compare function. So you can check for example using std::less functional object that the following sequence { 1, 1, 1 } is sorted.

 

However what compare function may be used to check that this sequence is not strictly sorted that is that it  contains duplicates?

 

That to be clear here is an example

 

{ 1, 1, 1 } is not strictly sorted

{ 1, 2, 3 } is strictly sorted.

 

 

--
 
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussio...@isocpp.org.
To post to this group, send email to std-dis...@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-discussion/.

-- Marshall

Marshall Clow     Idio Software   <mailto:mclow...@gmail.com>

A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait).
        -- Yu Suzuki

[Vlad from Moscow]

std::is_partitioned and std::is_sequenced are two different algorithms. They have different semantic. std::is_partitioned cjhecks at front there are elements that satisfy the predicate and after them there are alements that do not satisfy the predicate.

std::is_sequenced checks that any two adjacent elements satisfy the predicate.

суббота, 26 октября 2013 г., 18:56:10 UTC+4 пользователь Marshall написал:

-- Marshall

Marshall Clow     Idio Software   <mailto:mc...@gmail.com>

[Vlad from Moscow]

It would be better to demonstrate the difference by an example

 

[code]

std::vector<int> v = { 1, 4, 3, 2, 7, 6, 5, 8 };

 

std::cout << std::boolalpha << std::is_sequenced( v.begin(), v.end(),

                                                                                []( int x, int y ) { return ( x % 2 != y % 2 ); } )

               << std::endl;

[/code]

 

суббота, 26 октября 2013 г., 18:56:10 UTC+4 пользователь Marshall написал:

On Oct 26, 2013, at 2:41 AM, Vlad from Moscow <vlad....@mail.ru> wrote:

-- Marshall

Marshall Clow     Idio Software   <mailto:mc...@gmail.com>

[Marshall Clow]

On Oct 26, 2013, at 8:22 AM, Vlad from Moscow <vlad....@mail.ru> wrote:

It would be better to demonstrate the difference by an example

 

[code]

std::vector<int> v = { 1, 4, 3, 2, 7, 6, 5, 8 };

 

std::cout << std::boolalpha << std::is_sequenced( v.begin(), v.end(),

                                                                                []( int x, int y ) { return ( x % 2 != y % 2 ); } )

               << std::endl;

[/code]

Thanks for the example.

That makes more sense, but I would write that as:

std::cout << std::boolalpha << 

( v.end() == std::adjacent_find( v.begin(), v.end(),

[]( int x, int y ) { return ( x % 2 == y % 2 ); } ))

<< std::endl;

[ i.e, find me the first pair of elements that do not satisfy the condition. If end, then the sequence is "sequenced" ]

-- Marshall

-- Marshall

Marshall Clow     Idio Software   <mailto:mclow...@gmail.com>

[Vlad from Moscow]

Moreover for example std::all_of can be substituted for std::find_if. And std::fill and std::generate can be substituted for std::for_each. For example

 

[code]

int a[10];

 

std::generate( std::begin( a ), std::end( a ), [] { return ( std::rand() % 10 ); } );

[/code]

 

[code]

int a[10];

 

std::for_each( std::begin( a ), std::end( a ), []( int &x ) { x = std::rand() % 10; } );

[/code]

 

Nevertheless I think that std::is_sequenced has more clear semanric than std::adjacent_find the same way as std::all_of  compared with std::find_if.

 

Also take into account that if there is algorithm std::is_sorted for sorted sequences then it would be logically consistent to have a similar algorithm for non-sorted sequences. And such algorithm is std::is_sequenced.:)

 

 

 

 

 

суббота, 26 октября 2013 г., 19:46:28 UTC+4 пользователь Marshall написал:

[Vlad from Moscow]

 

By the way std::is_sorted can be also substituted for std:;adjacent_find.:)

суббота, 26 октября 2013 г., 19:46:28 UTC+4 пользователь Marshall написал: