3
\$\begingroup\$

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);
    }   
}
\$\endgroup\$
  • 1
    \$\begingroup\$ 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). \$\endgroup\$ – sjrowlinson Jun 5 '16 at 22:02
  • \$\begingroup\$ @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). \$\endgroup\$ – Adam Martin Jun 6 '16 at 14:26
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – sjrowlinson Jun 6 '16 at 19:39
  • \$\begingroup\$ 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? \$\endgroup\$ – Adam Martin Jun 6 '16 at 19:43
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – sjrowlinson Jun 6 '16 at 19:49
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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.) \$\endgroup\$ – 200_success Jun 9 '16 at 22:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.