vector iterator parameter as template C++ [duplicate]

Question

template<typename T>
void Merge_Sort(vector<T>::iterator begin, vector<T>::iterator end) {

size_t length = end - begin;
if (1 >= length) return;

size_t mid = length/2;

Merge_Sort(begin, begin + mid);
Merge_Sort(begin + mid, end);
inplace_merge(begin, begin + mid, end);
}

I am trying to template-ize the function but getting the error that I am missing the typename prior to vector::iterator. Could anybody have an idea about making this function template?

To sum, I am trying to make iterator parameter as template.

Answer 1

You should use std::distance, std::next (or std::advance in c++03) to do the calculations.

Also, hardcoding vector is quite the opposite of making it generic, IYAM

template<typename It>
void Merge_Sort(It begin, It end) {
    size_t length = std::distance(begin, end);
    if (1 >= length) return;

    size_t mid = length/2;

    auto pivot = std::next(begin, mid);

    Merge_Sort(begin, pivot);
    Merge_Sort(pivot, end);
    inplace_merge(begin, pivot, end);
}

For completeness, here's one that integrates the Comparison predicate and sorts in descending order live on Coliru

#include <algorithm>
#include <vector>
#include <iterator>

template<typename It, 
    typename Cmp = typename std::less<typename std::iterator_traits<It>::value_type> >
void Merge_Sort(It begin, It end, Cmp cmp = Cmp()) {
    size_t length = std::distance(begin, end);
    if (length<2) return;

    size_t mid = length/2;

    auto pivot = std::next(begin, mid);

    Merge_Sort(begin, pivot, cmp);
    Merge_Sort(pivot, end, cmp);
    std::inplace_merge(begin, pivot, end, cmp);
}

#include <iostream>

int main()
{
    std::vector<int> v { 1,3,7,-3,4,99,-13 };

    Merge_Sort(begin(v), end(v), std::greater<int>());

    for(auto i : v)
        std::cout << i << " ";
}