How to differentiate fill constructor and range constructor in C++11?

Question

I suspect the prototypes of fill constructor and range constructor of std::vector (and many other STL types) given in this webpage are not right, so I implement a NaiveVector to mimic these two prototypes.

My code is:

#include <iostream>
#include <vector>
using namespace std;

template <typename T>
struct NaiveVector {
  vector<T> v;
  NaiveVector(size_t num, const T &val) : v(num, val) { // fill
    cout << "(int num, const T &val)" << endl;
  }

  template <typename InputIterator>
  NaiveVector(InputIterator first, InputIterator last) : v(first, last) { // range
    cout << "(InputIterator first, InputIterator last)" << endl;
  }

  size_t size() const { return v.size(); }
};

int main() {
  NaiveVector<int> myVec1(5,1);                   // A
  cout << "size = " << myVec1.size() << endl;
  for (auto n : myVec1.v) { cout << n << " "; }
  cout << endl;

  cout << "-----" << endl;

  vector<int> vec({1,2,3,4,5});               
  NaiveVector<int> myVec2(vec.begin(), vec.end());// B
  cout << "size = " << myVec2.size() << endl;
  for (auto n : myVec2.v) { cout << n << " "; }
  cout << endl;
}

And the output is:

$ g++ overload.cc -o overload -std=c++11
$ ./overload
(InputIterator first, InputIterator last) // should be: (int num, const T &val)
size = 5
1 1 1 1 1
-----
(InputIterator first, InputIterator last)
size = 5
1 2 3 4 5

As I suspected from the beginning, the compiler cannot differentiate the two constructors properly. Then my question is: how does std::vector's fill constructor and range constructor differentiate from each other?

Rephrase: how to implement the two constructors of this NaiveVector?

This question seems to be a duplicate of this question but the answer is not satisfying. Additionally, C++11 itself doesn't provide a is_iterator<>.. (MSVC has lots of hacks).

Edit: it is allowed to bind an rvalue to a constant lvalue reference, so the first constructor of NaiveVector is valid for A.

Answer 1

C++03

[lib.sequence.reqmts]/9

For every sequence defined in this clause and in clause 21:

• the constructor

  template <class InputIterator>
  X(InputIterator f, InputIterator l, const Allocator& a = Allocator())
  

  shall have the same effect as:

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

  if InputIterator is an integral type.

...

[lib.sequence.reqmts]/11

One way that sequence implementors can satisfy this requirement is to specialize the member template for every integral type. Less cumbersome implementation techniques also exist.

In other words, the standard says that if the range constructor gets selected by overload resolution but the "iterator" type is actually an integral type, it has to delegate to the fill constructor by casting its argument types to force the latter to be an exact match.

C++11/C++14

[sequence.reqmts]/14

For every sequence container defined in this clause and in clause 21:

• If the constructor

  template <class InputIterator>
  X(InputIterator first, InputIterator last,
    const allocator_type& alloc = allocator_type())
  

  is called with a type InputIterator that does not qualify as an input iterator, then the constructor shall not participate in overload resolution. ...

[sequence.reqmts]/15

The extent to which an implementation determines that a type cannot be an input iterator is unspecified, except that as a minimum integral types shall not qualify as input iterators.

This is more or less the way the standard hints to you to use SFINAE (which works reliably in C++11 as opposed to C++03).

C++17

The wording is similar, except that the paragraph about integral types not being iterators has been moved to [container.requirements.general]/17.

Conclusion

You can write your range constructor to look something like this:

template <typename InputIterator,
          typename = std::enable_if<is_likely_iterator<InputIterator>>::type>
NaiveVector(InputIterator first, InputIterator last)

The is_iterator helper template might simply disqualify integral types and accept all other types, or it might do something more sophisticated such as checking whether there is an std::iterator_traits specialization that indicates that the type is an input iterator (or stricter). See libstdc++ source, libc++ source

Both approaches are consistent with the standard's mandated behaviour of std::vector in C++11 and later. The latter approach is recommended (and will be consistent with what the real std::vector is likely to do on typical implementations), because if you pass arguments that are implicitly convertible to the types expected by the fill constructor, you would hope that the class would "do the right thing" and not select the range constructor only to have it fail to compile. (Although I suspect this is fairly uncommon.) Relative to the C++03 std::vector, it is a "conforming extension" since in that case the constructor call would not compile.

Answer 2

If you read the documentation at http://en.cppreference.com/w/cpp/container/vector/vector carefully, you will notice the following (emphasis mine):

4) Constructs the container with the contents of the range [first, last).

This constructor has the same effect as vector(static_cast<size_type>(first), static_cast<value_type>(last), a) if InputIt is an integral type. (until C++11)

This overload only participates in overload resolution if InputIt satisfies InputIterator, to avoid ambiguity with the overload (2).

The confusion is not with the std::vector but your expectation of which of your constructors gets called. Your code doesn't have the checks to make sure that the second constructor gets called only if the above condition of std::vector is met.

In your case, when you use

NaiveVector<int> myVec1(5,1);

the second constructor can be called by using int as the template parameter without requiring any conversion. The compiler needs to convert an int to a size_t in order to be able to call the first constructor. Hence, the second constructor is a better fit.

Answer 3

You can try adding some type trait check to verify that arguments of second constructor are iterators over T elements:

template
<
    typename InputIterator
,   typename = typename ::std::enable_if
    <
        ::std::is_same
        <
            T &
        ,   typename ::std::remove_const
            <
                decltype(*(::std::declval< InputIterator >()))
            >::type
        >::value
    ,  void
    >::type
>
NaiveVector(InputIterator first, InputIterator last) : v(first, last)
{
    cout << "(InputIterator first, InputIterator last)" << endl;
}

Run this code online