Take the 2-minute tour ×

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

share|improve this question
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 2 '10 at 6: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 8: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 9:16
add comment

3 Answers

up vote 20 down vote accepted

Use adjacent_find in combination with less or greater functor.

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

if (pos == aVec.end()) 
    std::cout<<" sorted"<<endl;
    std::cout<<"Not sorted"<<endl;
share|improve this answer
Beat me by a second. –  GManNickG Jun 2 '10 at 5:18
Well known trick, though not so obvious. Fortunately C++0x introduces the is_sorted function for that :) –  Matthieu M. Jun 2 '10 at 8:32
add comment

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

share|improve this answer
is_sorted isn't a part of the C++ Standard Library. –  Kirill V. Lyadvinsky Jun 2 '10 at 5:00
It is in the C++0x standard - and shipping with VC++ 2010 –  corvuscorax Jun 2 '10 at 5:11
@corvuscorax, yes it is in C++0x, but it is only draft unfortunately. I wouldn't use it in a production code. –  Kirill V. Lyadvinsky Jun 2 '10 at 5:14
add comment

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.

share|improve this answer
add comment

Your Answer


