one line assert to test if STL container is sorted

Question

Is there a way to write a one line condition that would return true if STL container is sorted? The container in question is std::vector

I intend to use it in an assert

You shouldn't be putting this sort of thing in an assert. Assertions are for things that could NEVER possibly happen. Throwing an exception is very likely to be more appropriate. If being passed an un-sorted vector violates a method or objects operating contract then it should throw not assert. Exceptions provide great advantages over assertions and should be used in preference in most cases. — radman, Jun 02 '10 at 06:20
@radman: If they could never possibly happen, why would you assert them? You need to define context! For example: assert class invariants, but throw when interface preconditions or postconditions are violated. — ltjax, Nov 14 '12 at 10:46
@ltjax Your right that was a little terse. Assertions are primarily to catch programmer mistakes, exceptions are for bad inputs or unavoidable runtime problems. I think class invariants are a good example of assertions used correctly. Fundamentally assertions provide a guarantee for the code following them so that invasive error handling is minimised and programmer errors are caught early and loudly. — radman, Jan 22 '13 at 08:53
This seems like a good use of an assert to me. If you wanted to write something like binary_search then that requires a sorted container to work. Having an assert in there to check that it actually is sorted seems like the kind of thing assert is for. Although of course it's a very expensive test ... — jcoder, Sep 16 '13 at 09:16

score 24 · Accepted Answer · edited Sep 16 '13 at 08:22

Use adjacent_find in combination with less or greater functor.

Restriction:
You should know whether the container is sorted in ascending or descending.

If the vector is supposed to be sorted in ascending order:

//Checks the first element where adjacent value where elem > nextElem
//returns end if the vector is sorted!
//Complexity is O(n)
vector<int>::iterator pos =  std::adjacent_find (aVec.begin(), aVec.end(),   // range
                                     std::greater<int>());               


if (pos == aVec.end()) 
{
    std::cout<<" sorted"<<endl;
}
else
{
    std::cout<<"Not sorted"<<endl;
}

Well known trick, though not so obvious. Fortunately C++0x introduces the `is_sorted` function for that :) — Matthieu M., Jun 02 '10 at 08:32

score 9 · Answer 2 · edited Oct 08 '18 at 21:26

9

You can use std::is_sorted(vec.begin(),vec.end()) to test if it is sorted. Note, though, that this is O(n).

edited Oct 08 '18 at 21:26

Alexis Wilke

19,179
10
84
156

answered Jun 02 '10 at 04:59

Michael Aaron Safyan

93,612
16
138
200

6

`is_sorted` isn't a part of the C++ Standard Library. – Kirill V. Lyadvinsky Jun 02 '10 at 05:00
4

It is in the C++0x standard - and shipping with VC++ 2010 – corvuscorax Jun 02 '10 at 05:11
@corvuscorax, yes it is in C++0x, but it is only draft unfortunately. [I wouldn't use it in a production code.](http://stackoverflow.com/questions/1754397/how-are-you-using-c0x-today) – Kirill V. Lyadvinsky Jun 02 '10 at 05:14
@KirillV.Lyadvinsky Only now it's officially part of STL making this answer the best one. :-) – Alexis Wilke Oct 08 '18 at 21:19

score 0 · Answer 3 · answered Jun 02 '10 at 05:03

0

It depends what STL data type you want to use.

A map is already sorted by the key provided the key has overloaded compare operators. You're good to go here.

A list requires that you explicitly call the sort function. You will need to keep track of whether or not you sorted it yet.

Hope this helps.

answered Jun 02 '10 at 05:03

Ben Burnett

1,554
10
17

You cannot `std::sort()` on a an `std::list` container. – Alexis Wilke Oct 08 '18 at 21:20

one line assert to test if STL container is sorted

3 Answers3

Linked