View Single Post
Old 2013-04-13, 01:37   #4
Robert Holmes
 
Robert Holmes's Avatar
 
Oct 2007

2·53 Posts
Default

The reason your the original code fails is deep in the C++ standard's language. In short, when you want the compiler to deduce argument types, those types must not be dependent types. In the above case, the type vector<T>::iterator is dependent on the type of T and will not be deduced. Hence, you're forced to spell out all the specializations. There are two ways around this:

- Accept the whole vector as input, i.e., by reference
- Accept a pair of iterators as input

Here's the latter, which is the standard way of doing things on the STL:

Code:
template<typename Iterator>
void merge_sort(Iterator begin, Iterator end)
{
    static_assert( std::is_same<
                        typename std::iterator_traits<Iterator>::iterator_category, 
                        std::random_access_iterator_tag
                    >::value, "merge_sort only likes random-access iterators" );
    const auto n = std::distance(begin, end);
    const auto p = n / 2;

    if(n < 2)
        return;

    merge_sort(begin, begin + p);
    merge_sort(begin + p, end);

    std::inplace_merge(begin, begin + p, end);
}
This uses some of the newer C++11 standard stuff, like auto type deduction, static_asserts, and standard type traits for the iterators.

You can safely ignore the static_assert: it is only there to cause a compilation error when the iterator type is not random-access, since we may want, for example, to implement the merge sort differently for vectors and linked-lists, depending on whether sequential or random access exists.

Here is an example, with an added helper function that takes in arbitrary containers (including normal C arrays): https://ideone.com/fvu57s

Last fiddled with by Robert Holmes on 2013-04-13 at 01:37
Robert Holmes is offline   Reply With Quote