STL implementation of quicksort

Question

The code is generic, trying to support both STL iterators and normal C pointer arithmetic.

#include <cstdio>
#include <vector>

template<typename I>
void quick_sort_step(const I left, const I right)
{
    auto pivot = *(left + (right - left) / 2);
    auto l = left;
    auto r = right;

    while (l <= r) {
        while (*l < pivot)
            ++l;

        while (*r > pivot)
            --r;

        if (l <= r)
            std::swap(*l++, *r--);
    }

    if (left < r)
        quick_sort_step(left, r);
    if (l < right)
        quick_sort_step(l, right);
}

template<typename I>
void quick_sort(const I begin, const I end)
{
    if (end - begin > 1)
        quick_sort_step(begin, std::prev(end));
}

int main()
{
    typedef std::vector<int> list;

    list l { 5, 0, 2, 4, 1, 3, 9, 8, 7, 6 };

    quick_sort(l.begin(), l.end());

    for (auto i : l) {
        printf("%i ", i);
    }

    return 0;
}

Answer 1

You need to somehow check or restrict your templates to iterators only.

The way you have it written, I can perform the following:

int main(void)
{
  const char a = '5';
  const char b = '$';
  sort(a,b);

  const int five = 5;
  const int zero = 0;
  sort(five, 0);

  return EXIT_FAILURE;
}

Also, you may want to clarify that your arguments, when they are pointers, are constant pointers to mutable data.

Answer 2

• For generic template types, it's more common to use T. This would help take out the guesswork if one isn't already aware of the template statement.

• Your typedef is superfluous since it's only used once in main(), so just remove it. The new name itself doesn't add anything to the context anyway.

• Sure, you can still use C-style print functions in C++ if you'd like, but it still makes your code look less like C++. I would've expected it to be done with something more complex that doesn't look as great with std::cout, but such a print statement will still look the same with std::cout.