Определение типа хранимой величины по итератору

[БалаШагаЛ]

Здравствуйте! Нужно реализовать сортировку чтобы, как в STL, в функцию передавались итераторы начала и конца. Но сортировка слиянием, так что нужно выделять дополнительную память, а для этого нужно знать тип хранимой величины. Есть ли какие-то способы узнать его?
Пробовал делать хотя бы вот такую штуку:

template <class value_type>
void mergeSort(typename vector<value_type>::iterator begin, typename vector<value_type>::iterator end);

Но при применении такой функции компилятор не может найти автоматически аргумент шаблона (если указываю явно, то всё компилируется хорошо).
Подумываю о вот такой записи:

template <class container, class value_type>
void mergeSort(typename container<value_type>::iterator begin, typename containter<value_type>::iterator end);

но это, боюсь, тоже вряд ли взлетит.

[pproger]

#include <iostream>
#include <vector>

using namespace std;

template <class Iterator>
void foo(Iterator it) {
	typename iterator_traits<Iterator>::value_type val;
	val = *it;
	cout << val << endl;
}

int main() {
	vector<int> v = { 123 };
	foo(v.begin());
	return 0;
}

[_Bers]

#include <iostream>
#include <vector>

using namespace std;

template<class Iterator> void foo(Iterator it) 
{
   typedef typename Iterator::value_type
       Element;

    const Element& val = *it;
    cout << val << endl;
}

int main() 
{
    vector<int> v = { 123 };
    foo(v.begin());
    return 0;
}

[_Bers]

а этот способ позволяет вытаскивать данные из любых итераторов, не обязательно стл-совместимых.

главное, что б умели разыменовываться:

#include <type_traits>
#include <iostream>
#include <vector>

using namespace std;

template<class Iterator> void foo(Iterator it) 
{
   typedef decltype(*it)
       Ty;
    
   typedef typename remove_reference<
               typename remove_const<Ty>::type 
           >::type 
       Element;

    const Element& val = *it;
    cout << val << endl;
}

int main() 
{
    vector<int> v = { 123 };
    foo(v.begin());
    return 0;
}