Best algorithm to check whether a vector is sorted

Question

What would be the best way to check that a std::vector is sorted? Is there something faster than a loop checking that v[i]<=v[i+1]? Is it faster/cleaner with iterators? Or is it actually better to just call sort every time (though the "v is already sorted" case is quite common)?

We can safely assume the vector only contains PODs, usually floats and sometimes doubles and ints.

The size of the vector is non-trivial (usually a few thousands items) but not extreme (not gigabyte-sized).

• in some instances we'll sort the vector immediately afterwards, however there are other instances where we don't (it's an error case of our algorithm).
• we already use a flag "IsSorted" whenever possible.

Answer 1

Is there something faster than a loop checking that v[i]<=v[i+1] ?

No.

If this is something you wish to check often, you might want to make a wrapper class that keeps a "sorted" flag which starts out False, is set to False whenever an item is added, and add a member function sort() that sets the flag to True after sorting.

Answer 2

The best way is to use std::is_sorted:

is_sorted(v.begin(), v.end())

:-)