C++11 Quicksort any container

Question

As the title says, simple quicksort to help myself get used to C++ templates and iterators. Main concern is whether there's a better way to template so that you can have a simple function (e.g. quicksort) that accepts any container type (specifically should I have some kind of assert or more complicated template to make sure the arguments are in fact iterators?) Also note that it is inclusive of the end value, so to sort a whole container the call is qsort(c.begin(), c.end()-1).

template <typename Iter> Iter partition(Iter start, Iter end){
 Iter pivot = start;
 Iter cur = start;
 while (cur < end) {
 if(*cur <= *end){
 std::swap(*cur,*pivot);
 pivot++;
 }
 cur++;
 }
 std::swap(*pivot, *end);
 return pivot;
}
template <typename Iter> void qsort(Iter start, Iter end){
 if(end > start) {
 Iter p = partition(start, end);
 qsort(start, p - 1);
 qsort(p + 1, end);
 } 
}

• sjrowlinson: Note that comparison of iterators using operator< and similar only works for containers which use forward iterators. A more "portable" solution is to use operator!= - e.g: while(cur != end) instead of while(cur < end).
• Adam Martin: @ArchbishopOfBanterbury Are there some links/examples I can see (kinda curious, I'm guessing something like map)? And would there be a problem with using incrementing in those cases as well (not sure how else I would use the iterator though, so I guess that should be well defined).
• sjrowlinson: Yes std::map is an example of a STL container to which this applies, as far as I am aware you can find which iterators are defined for each container on the cppreference website. Also, yes all iterators used by STL containers have operator++ defined so that should be fine.
• Adam Martin: This is v useful thanks! Thinking it through though, in this scenario it probably makes more sense to exclude those types of containers (you can't/shouldn't sort a map, since it's already sorted). Is there a way to use assert or something to make the function only accept forward iterators, or does that not make sense?
• sjrowlinson: You could do some template SFINAE to check that the iterator passed is forward iterator using std::enable_if_t and iterator tags. There's a similar question here which could be applied: forward iterator checking.

Answer 1

If you make restriction only for ForwardIterators you can't call c.end()-1 from your question. It would be probably difficult to sort the whole container.

• 200_success: Actually, I do consider this to be an answer, as it mentions a valid concern: not all iterators are bidirectional. Accepting an inclusive-exclusive range would be more idiomatic and technically superior. (Even though this issue was mentioned in a comment, it deserves to be made into an answer.)