How does a compiler distinguish between two variations of "vector::insert"?

Question

I'm implementing a simple std::vector. There are two insert functions:

template <typename T, typename Allocator>
typename Vector<T, Allocator>::iterator
Vector<T, Allocator>::insert(const_iterator pos, size_type count, const T& value)
{
    checkIterator(pos);
    auto p = const_cast<iterator>(pos);
    if (count == 0) {
        return p;
    }
    for (size_type i = 0; i < count; ++i) {
        p = insert(p, value);
    }
    return p;
}

template <typename T, typename Allocator>
template <typename InputIt>
typename Vector<T, Allocator>::iterator
Vector<T, Allocator>::insert(const_iterator pos, InputIt first, InputIt last)
{
    checkIterator(pos);
    auto p = const_cast<iterator>(pos);
    if (first == last) {
        return p;
    }
    for (auto iter = first; iter != last; ++iter) {
        p = insert(p, *iter);
        ++p;
    }
    return p - (last-first);
}

But when I want to use first insert function, the compiler invokes the second one:

Vector<int> vi = {1, 2, 3};
vi.insert(vi.begin(), 3, 4); // get compile error, using insert(const_iterator pos, InputIt first, InputIt last).

Why compiler chooses the second function, and how to modify my code to make it right?

Answer 1

Unfortunately, doing this fully correctly is a problem. However, you can do something that is reasonable (and will work in this case). Basically, you need to conditionally enable the second overload dependent on whether the deduced type InputIt actually meets the requirements for input iterator. There's a whole list of input iterator requirements: http://en.cppreference.com/w/cpp/concept/InputIterator. However, we'll just focus on one that will solve this situation and most common cases for us. Namely, we'll verify that the type InputIt actually has a correct operator*. We use the void_t trick to build a trait for this:

template <class ... T> using void_t = void;

template <class T, class = void>
struct has_iterator_deref : std::false_type {};

template <class T>
struct has_iterator_deref<T, std::enable_if_t<
    std::is_same<typename std::iterator_traits<T>::reference,
                 decltype(*std::declval<T>())>::value>> : std::true_type {};

The long and short of it is, that this struct will ensure that an instance of T can be dereferenced with * and yields the same type as iterator_traits<T>::reference. Having done that, we now use this to sfinae the second overload:

template <typename T, typename Allocator>
template <typename InputIt, class = enable_if_t<has_iterator_deref<T>::value>>
typename Vector<T, Allocator>::iterator
Vector<T, Allocator>::insert(const_iterator pos, InputIt first, InputIt last)
...

If you are feeling frisky, you can in fact go through the entire list of Input Iterator requirements, and as far as I can see, build a trait that detects if each one is present, and then finally take the conjunction to do exactly correct detection to ensure that InputIt meets the Input Iterator concept. It's rather a pain though.

Answer 2

A fairly simple way to do this is to rely on iterator_traits::iterator_category from <iterator>

It could look something like this:

#include <iterator>

template<typename It>
using iterator_category_t = typename std::iterator_traits<It>::iterator_category;

template<typename T>
class container
{
public:
    template <typename InputIt, typename ItCat = iterator_category_t<InputIt>>
    iterator insert(const_iterator pos, InputIt first, InputIt last);
    // the rest

This will SFINAE away things like int, since they don't fulfill any iterator category.

This has the added benefit that you can dispatch on ItCat{} inside the implementation, if you have different algorithms for different iterator categorys.