Am I using C++11 features like STL and move semantics correctly?

Question

I've implemented selection sort, heap sort, insertion sort, and iterative quicksort using C++11. Am I using the correct STL data structures/algorithms? Am I using move semantics correctly in my code?

#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
#include <iterator>
#include <utility>
#include <stack>

namespace detail
{    
    template <typename It, typename Comp>
    void heapSort(It begin, It end, Comp compFunc, std::random_access_iterator_tag)
    {
        std::make_heap(begin, end, compFunc);
        std::sort_heap(begin, end, compFunc);
    }

    template <typename It, typename Comp, typename IterCat>
    void heapSort(It begin, It end, Comp compFunc, IterCat)
    {
        typedef typename It::value_type value_type;

        std::vector<value_type> randomAccessContainer(std::make_move_iterator(begin), std::make_move_iterator(end));
        heapSort(std::begin(randomAccessContainer), std::end(randomAccessContainer), compFunc, std::random_access_iterator_tag());
        std::move(std::begin(randomAccessContainer), std::end(randomAccessContainer), begin);
    }

    template <typename It>
    class QuicksortStack
    {
    private:
        typedef std::pair<It, It> IterRange;
        std::stack<IterRange> m_stack;
    public:
        void push(IterRange&& range)
        {
            if (std::distance(range.first, range.second) >= 2)
            {
                m_stack.push(std::move(range));
            }
        }

        void push(const IterRange& range)
        {
            if (std::distance(range.first, range.second) >= 2)
            {
                m_stack.push(range);
            }
        }

        void pop()
        {
            m_stack.pop();
        }

        IterRange top() const
        {
            return m_stack.top();
        }

        bool empty() const
        {
            return m_stack.empty();
        }
    };
}

template <typename It, typename Comp>
void selectionSort(It begin, It end, Comp compFunc)
{
    for (; begin != end; ++begin)
    {
        const It minElem(std::min_element(begin, end, compFunc));

        if (begin != minElem)
        {
            std::iter_swap(begin, minElem);
        }
    }
}

template <typename It>
void selectionSort(It begin, It end)
{
    selectionSort(begin, end, std::less<typename It::value_type>());
}

template <typename It, typename Comp>
void heapSort(It begin, It end, Comp compFunc)
{
    detail::heapSort(begin, end, compFunc, typename std::iterator_traits<It>::iterator_category());
}

template <typename It>
void heapSort(It begin, It end)
{
    heapSort(begin, end, std::less<typename It::value_type>());
}

template <typename It, typename Comp>
void insertionSort(It begin, It end, Comp compFunc)
{
    if (std::distance(begin, end) < 2)
    {
        return;
    }

    It elem(std::next(begin));
    It nextElem(std::next(elem));
    for (; nextElem != end; ++nextElem)
    {
        std::inplace_merge(begin, elem, nextElem, compFunc);
        elem = nextElem;
    }

    std::inplace_merge(begin, elem, nextElem, compFunc);
}

template <typename It>
void insertionSort(It begin, It end)
{
    insertionSort(begin, end, std::less<typename It::value_type>());
}

template <typename It, typename Comp>
void quickSort(It begin, It end, Comp compFunc)
{
    detail::QuicksortStack<It> ranges;
    ranges.push(std::make_pair(begin, end));

    while (!ranges.empty())
    {
        const auto current(ranges.top());
        ranges.pop();

        const It last(std::prev(current.second));
        const It pivot(std::partition(current.first, last, [=](const typename It::value_type& val){ return compFunc(val, *last); }));
        std::iter_swap(pivot, last);

        ranges.push(std::make_pair(current.first, pivot));

        if (pivot != current.second)
        {
            ranges.push(std::make_pair(std::next(pivot), current.second));
        }
    }
}

template <typename It>
void quickSort(It begin, It end)
{
    quickSort(begin, end, std::less<typename It::value_type>());
}

Edit: Updated to reflect Dave's answer, below.

#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
#include <iterator>
#include <utility>
#include <stack>
#include <iostream>

namespace detail
{    
    template <typename RandIt, typename Comparer>
    void heapSort(RandIt begin, RandIt end, Comparer compFunc, std::random_access_iterator_tag)
    {
        std::make_heap(begin, end, compFunc);
        std::sort_heap(begin, end, compFunc);
    }

    template <typename FwdIt, typename Comparer, typename IterCat>
    void heapSort(FwdIt begin, FwdIt end, Comparer compFunc, IterCat)
    {
        typedef typename std::iterator_traits<FwdIt>::value_type value_type;

        std::vector<value_type> randomAccessContainer(std::make_move_iterator(begin), std::make_move_iterator(end));
        heapSort(std::begin(randomAccessContainer), std::end(randomAccessContainer), compFunc, std::random_access_iterator_tag());
        std::move(std::begin(randomAccessContainer), std::end(randomAccessContainer), begin);
    }

    template <typename InIt>
    class QuicksortStack
    {
    private:
        typedef std::pair<InIt, InIt> IterRange;
        std::stack<IterRange> m_stack;
    public:
        void push(IterRange&& range)
        {
            if (std::distance(range.first, range.second) >= 2)
            {
                m_stack.push(std::move(range));
            }
        }

        void push(const IterRange& range)
        {
            if (std::distance(range.first, range.second) >= 2)
            {
                m_stack.push(range);
            }
        }

        void pop()
        {
            m_stack.pop();
        }

        IterRange top() const
        {
            return m_stack.top();
        }

        bool empty() const
        {
            return m_stack.empty();
        }
    };
}

template <typename FwdIt, typename Comparer>
void selectionSort(FwdIt begin, FwdIt end, Comparer compFunc)
{
    for (; begin != end; ++begin)
    {
        const auto minElem(std::min_element(begin, end, compFunc));

        if (begin != minElem)
        {
            std::iter_swap(begin, minElem);
        }
    }
}

template <typename FwdIt>
void selectionSort(FwdIt begin, FwdIt end)
{
    selectionSort(begin, end, std::less<typename std::iterator_traits<FwdIt>::value_type>());
}

template <typename FwdIt, typename Comparer>
void heapSort(FwdIt begin, FwdIt end, Comparer compFunc)
{
    detail::heapSort(begin, end, compFunc, typename std::iterator_traits<FwdIt>::iterator_category());
}

template <typename FwdIt>
void heapSort(FwdIt begin, FwdIt end)
{
    heapSort(begin, end, std::less<typename std::iterator_traits<FwdIt>::value_type>());
}

template <typename FwdIt, typename Comparer>
void insertionSort(FwdIt begin, FwdIt end, Comparer compFunc)
{
    for (auto elem = begin; elem != end; ++elem)
    {
        const auto current(std::move(*elem));
        const auto sortPosition(std::upper_bound(begin, elem, current, compFunc));

        std::move_backward(sortPosition, elem, std::next(elem));

        *sortPosition = std::move(current);
    }
}

template <typename FwdIt>
void insertionSort(FwdIt begin, FwdIt end)
{
    insertionSort(begin, end, std::less<typename std::iterator_traits<FwdIt>::value_type>());
}

template <typename BiDirIt, typename Comparer>
void quickSort(BiDirIt begin, BiDirIt end, Comparer compFunc)
{
    detail::QuicksortStack<BiDirIt> ranges;
    ranges.push(std::make_pair(begin, end));

    while (!ranges.empty())
    {
        const auto current(ranges.top());
        ranges.pop();

        const auto last(std::prev(current.second));
        const auto pivot(std::partition(current.first, last, [=](const typename std::iterator_traits<BiDirIt>::value_type& val){ return compFunc(val, *last); }));
        std::iter_swap(pivot, last);

        ranges.push(std::make_pair(current.first, pivot));

        if (pivot != current.second)
        {
            ranges.push(std::make_pair(std::next(pivot), current.second));
        }
    }
}

template <typename BiDirIt>
void quickSort(BiDirIt begin, BiDirIt end)
{
    quickSort(begin, end, std::less<typename std::iterator_traits<BiDirIt>::value_type>());
}

Answer 1

Your code looks good, I don't see any major problems.

Here's what I would consider changing:

• Name your iterator template arguments by the iterator concept they are required to meet. For example: template<typename ForwardIt>
• I would prefer not to see early returns from functions if possible. I think it's clearer to do if(blah){ do stuff } then to do if(!blah){ return; } do stuff
• I didn't look closely at all of them, but you can use STL to make a much prettier insertion sort:

....

template<typename ForwardIt, typename Compare>
void InsertionSort(ForwardIt first, ForwardIt last, Compare comp)
{
    for(auto i = first; i != last; ++i)
    {
        std::rotate(std::upper_bound(first, i, *i, comp), i, std::next(i));
    }
}

Edit: In hindsight, that insertion sort is sub optimal. Yours will be quite bad too. Here's a much faster one, with different STL use:

template<typename BiDirIt, typename Compare>
void InsertionSort(BiDirIt first, BiDirIt last, Compare comp)
{
    for(auto i = first; i != last; ++i)
    {
        auto current = std::move(*i);
        auto start   = std::upper_bound(first, i, current, comp);
        std::move_backward(start, i, std::next(i));
        *start       = std::move(current);
    }
}

Edit2: Your forwarding functions (the functions that fill in a default compare function) don't allow for raw pointer iterators. The STL algorithms do. The problem is that you're using typename FwdIt::value_type. Obviously a raw pointer doesn't have a member typedef called value_type. The way to solve this is to use iterator_traits:

template <typename FwdIt>
void selectionSort(FwdIt begin, FwdIt end)
{
    selectionSort(begin, end, std::less<typename std::iterator_traits<FwdIt>::value_type>());
}