Type-safe template function which takes iterators

I'm writing different sort functions, which take two iterators and sort sequence. I would like to implement them for any kind of vector and make them typesafe, like this:

template <typename T>
void itsort(std::vector<T>::iterator begin, std::vector<T>::iterator end)
{
    // code
}

But due to errors I'm only able to implement something type-unsafe:

template <typename T>
void itsort(T begin, T end)
{
    // code
}

How to implement type-safe template function, which takes two vector iterators?

PS: Currently there is no need in comparator, all sorts work with different types of numbers.

Determining if something is an iterator of a vector is hard, and mostly pointless.

The type of vector iterators are extremely free under the standard. They can even be naked pointers in some implementations.

What more, the type of the vector that produces the iterator might not be deducible from the iterator. As an example, a std::vector<int, some_allocator>::iterator might be a different, or the same type, as a std::vector<int>::iterator. They could both be int*, or they could be some class wrapped around a pointer. They could be the same type, or different types. (The technique of using the same type for different container types is called SCARY iterators if you want to find discussion about it).

In general, you cannot determine if a given iterator is a vector iterator.

You can write code that will fail if the given iterator is not a random-access iterator, and deduce the type T. First, a bit of boilerplate to make the access to iterator_traits a bit less verbose:

namespace iterators {
  template<class It>
  using iterator_category =
    typename std::iterator_traits<It>::iterator_category;

  template<class It>
  using value_type =
    typename std::iterator_traits<It>::value_type;
}

now we do this:

template<class It>
void itsort(It begin, It end)
{
  using T = iterator::value_type<It>;
  using category = iterator::iterator_category<It>;
  static_assert(
    std::is_base_of<std::random_access_iterator_tag, category>::value, "This function only supports random-access iterators"
  );
}

this "fails late", in that the error does not occur at the time of overload resolution (SFINAE), but it does check your types for you.

You also have access to the underlying value type of your iterators.

Doing this in a SFINAE friendly way is difficult, because iterator_traits is not mandated to be SFINAE friendly, and iterator_traits is the mandated way to determine the traits of an iterator. As a concrete example, void* often matches the empty iterator_traits for pointers, but then it fails because it isn't an iterator.