How does overloaded template function selection (pattern matching) work in std::vector insert?

Question

Consider the following declarations of a std::vector (taken from cplusplus - EASTL has the same declarations)

    iterator insert ( iterator position, const T& x );
    void insert ( iterator position, size_type n, const T& x );
template <class InputIterator>
    void insert ( iterator position, InputIterator first, InputIterator last );

If I type

someVector.insert(someVector.begin(), 10, 90);

how is that not confused (by the compiler) with the last overload, where 10 and 90 are ints and InputIterator's type is taken as int instead of the alternative which is to take 10 as size_type and 20 as a const int&?

Now I say "not" because I am implementing a vector container (learning purposes) and in my case with the above mentioned call, the third overload is selected by the compiler rather than the second overload and consequently fails to compile. If I remove the third overload then things seem fine.

Does it have something to do with what the last overload is calling (overloaded functions with iterator traits)? If so, then if I were to assume that all iterators are raw pointers (although in my case I am using the same declaration, that means that I have overload #3 with a template that expects an iterator... although expects is the wrong word here because in the end it can be anything and in this case, it is interpreted as int for me and fails to compile) how will I make sure the compiler selects the proper function?

Answer 1

Out of curiosity, I had a look at the GCC sources:

  template<typename _InputIterator>
    void
    insert(iterator __position, _InputIterator __first,
           _InputIterator __last)
    {
      // Check whether it's an integral type.  If so, it's not an iterator.
      typedef typename std::__is_integer<_InputIterator>::__type _Integral;
      _M_insert_dispatch(__position, __first, __last, _Integral());
    }

Later...

  // _GLIBCXX_RESOLVE_LIB_DEFECTS
  // 438. Ambiguity in the "do the right thing" clause
  template<typename _Integer>
    void
    _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
                       __true_type)
    { _M_fill_insert(__pos, __n, __val); }

  // Called by the range insert to implement [23.1.1]/9
  template<typename _InputIterator>
    void
    _M_insert_dispatch(iterator __pos, _InputIterator __first,
                       _InputIterator __last, __false_type)
    {
      typedef typename std::iterator_traits<_InputIterator>::
        iterator_category _IterCategory;
      _M_range_insert(__pos, __first, __last, _IterCategory());
    }

It seems that they were indeed worried that an ambiguity could arise, so an explicit use of typetraits and overloading is used to check whether the template matched an integral type or not.

Answer 2

The implementation likely applies SFINAE, which in some cases is Standard-mandated, to ensure that InputIterator is actually an iterator. Further to that, the compiler will only instantiate the template version if it can't make a call to any non-templates.

Answer 3

23.1.1/9 dictates that it must pick the "integral type/value" constructor instead of the "iterator/iterator" constructor and the compiler must make sure that it's able to make that determination.

[Standard text]:

the member functions in the forms:

template <class InputIterator> // such as insert()
rt fx1(iterator p, InputIterator f, InputIterator l);

template <class InputIterator> // such as append(), assign()
rt fx2(InputIterator f, InputIterator l);

template <class InputIterator> // such as replace()
rt fx3(iterator i1, iteraror i2, InputIterator f, InputIterator l);

shall have the same effect, respectively, as:

fx1(p, static_cast<typename X::size_type>(f),
static_cast<typename X::value_type>(l));

fx2(static_cast<typename X::size_type>(f),
static_cast<typename X::value_type>(l));

fx3(i1, i2, static_cast<typename X::size_type>(f),
static_cast<typename X::value_type>(l));

if InputIterator is an integral type.

Answer 4

In your case, the insert does match the template better that the non-template, as long as your parameters are int and int.

The standard requires that it should work like if the non-template was selected anyway!

— the member functions in the forms:

template <class InputIterator> // such as insert()
rt fx1(iterator p, InputIterator f, InputIterator l);

template <class InputIterator> // such as append(), assign()
rt fx2(InputIterator f, InputIterator l);

template <class InputIterator> // such as replace()
rt fx3(iterator i1, iteraror i2, InputIterator f, InputIterator l);

shall have the same effect, respectively, as:

fx1(p,
    static_cast<typename X::size_type>(f),
    static_cast<typename X::value_type>(l));
fx2(static_cast<typename X::size_type>(f),
    static_cast<typename X::value_type>(l));
fx3(i1, i2,
    static_cast<typename X::size_type>(f),
    static_cast<typename X::value_type>(l));

if InputIterator is an integral type.

So there has to be some meta magic to resolve this.

If you change your call to someVector.insert(someVector.begin(), 10u, 90);, the non-template will might be the better match, depending on what size_type is.