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.
Is there something faster than a loop checking that v[i]<=v[i+1] ?
You will need to check any value to see if it's sorted, so it won't get any faster then O(n) unless you keep track of changes yourself while mutating the vector or use a datastructure that is already sorted.
Or is it actually better to just call sort every time (though the "v is already sorted" case is quite common) ?
Remember that quicksorts worst case behavior happens when the list is already sorted (and the pivot is chosen incorrectly). To avoid such behavior you might want to check out std::stable_sort as a replacement.
In order to check sorted you must check every item. So v[i]<=v[i+1] is the fastest possible check.
Is there something faster than a loop checking that v[i]<=v[i+1] ?
No.
However, if you are going to perform the check to decide whether to sort the vector, you might be better off just always sorting if you use the right sort-algorithm, i.e. std::stable_sort and not std::sort.
Of course I have no knowledge of your problem domain, so please ignore me if what I say is not relevant, but it seems to me that if I require a collection to be always be sorted whenever I access it, a naturally unsorted collection like a vector<T> may not be the best choice.
As others have noted, a predicate to determine sorted state is O(n). But from your mention of a sorted flag, I kind of wonder if you don't want something like this:
Our application's foundation libraries includes a container class which can be queried for membership. Here is a brief sketch:
class ObjList {
public:
ObjList() {};
~ObjList() {};
bool isMember(const Item *);
void add(const Item *, bool sort = false);
private:
unsigned int last_sorted_d;
bool sorted_d;
unsigned int count_d;
Item *store_d;
};
isMember() uses a binary search on the sorted range of elements, then a linear search of items after the sorted range. Insertion can trigger a sort of the items, or not, according to the programmer's choice. For instance, if you are aware that you'll be adding thousands of items in a tight loop, don't sort until the final insertion.
The above is just a sketch, and the store is more complicated than an array of pointers, but you get the idea.
If you're expecting the the list to be very close to sorted, it might be beneficial to try a modification of the insertion sort. If the list is already sorted, it just does one pass and tells you so. If the list is very nearly sorted, it will be sorted very quickly. If the list is not sorted, break out of the sort after some number of swaps and switch to a quicksort (or stable_sort).
Consider Multiple Cpu Cores
It depends on your platform and number of items in the vector. You'd have to benchmark to find what's best.
It's not possible to answer: Is there something faster than a loop checking that v[i]<=v[i+1] ?
With: No.
Because... computers now a days have multiple cpus/cores/hyperthreading. So, it may well be a lot quicker to exploit the parallism in the computer by spliting the work of checking to a number of threads, so each cpu can be checking a small range in parallel.
It's probably best to do this via a library function rather than implementing it yourself. New versions of libraries will exploit parallism. So, if you go for a std::sort you'll probably find when you build against newer implementations of STL, they'll do the operation in parallel for you without you having to worry about it. I don't know if there are readily available versions of STL that do this already, but it's worth sticking to the library functions so that when you upgrade to a version that does, this optimization is there for you without you needing to make any changes.
If when you insert items you use binary search to find the insertion point, then it's never not ordered.
std::adjacent_find(v.begin(), v.end(), std::greater<type>()) == v.end()