Type-safe template function which takes iterators

Question

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.

Scutter

Use typename std::vector<T>::iterator. – Jeffrey

Try typename in front of std::vector<T>::iterator – Grate

Even with typename, it would be a non deducible context, and you will have to provide <T> at the call site. – Romeu

To be type-safe, you would take some kind of Range btw. – Romeu

@juanchopanza using typename here is a poor solution to the problem the OP posted. – Trihedron

Answer 1

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.

Trihedron

Answer 2

seems you are looking for something like this:

#include <iostream>
#include <vector>
#include <list>
#include <iterator>

template< typename T >
void itsort(T, T, std::bidirectional_iterator_tag)
{
    std::cout << "itsort called for bidirectional iterator\n";
}

template <typename T>
void itsort(T, T, std::random_access_iterator_tag)
{
    std::cout << "itsort called for random-access iterator\n";
}


template< typename T >
void alg(T first, T last)
{
   itsort(first, last, typename std::iterator_traits<T>::iterator_category());
}


int main()
{
    std::vector<int> v;
    alg(v.begin(), v.end());

    std::list<int> l;
    alg(l.begin(), l.end());
}

Buttonhook

Answer 3

It is possible to constraint the function with the std::enable_if type trait, which defines a valid type only if the specified type is a std::vector container iterator.

At this point, it is necessary to implement a dedicated type trait (is_vector_iterator) that allows to achieve this goal.

Example:

template <typename InIter, typename = typename std::enable_if<is_vector_iterator<InIter>::value>::type>
void itsort(InIter, InIter);

The basic idea is to create a helper type trait that accepts two different types as template parameters. It is partial-specialized for the case in which the second argument is the same as std::vector <U>::iterator, where the type U is the value_type of the iterator. Thus, the helper is specialized for only the type T. If the above type is not a std::vector container iterator, the first class is selected; otherwise, the second one is selected.

Example:

namespace detail {
    template <typename, typename>
    struct is_vector_iterator
     : std::false_type {};
    
    template <typename T>
    struct is_vector_iterator<T, typename std::vector<typename std::iterator_traits<T>::value_type>::iterator>
     : std::true_type {};
}

template <typename T>
struct is_vector_iterator
 : detail::is_vector_iterator<T, T> {};

Foreandafter