Is std::vector(InputIterator first, InputIterator last) linear time complexity?
boost, c++, constructor, stdvector, time-complexity
Solution
Is `std::vector(InputIterator first, InputIterator last)` linear time complexity?
In a nutshell, yes.
The standard guarantees the following for `vector(InputIterator, InputIterator)` in §23.3.6.2:
Complexity: Makes only N calls to the copy constructor of T (where N is the distance between first and last) and no reallocations if iterators first and last are of forward, bidirectional, or random access categories. It makes order N calls to the copy constructor of T and order log(N) reallocations if they are just input iterators.
Basically, for forward, bidirectional, or random access iterators you shouldn't be expecting to see any performance gain from using `reserve()` as in your second example; the constructor will automatically do this for you.
For plain input iterators, `reserve()` would speed things up, but not more than by a constant factor. The `log(n)` reallocations would still be done in `O(n)` total time, so the total time of constructing the vector will also be `O(n)`.
Problem
I'd like to use the C++ `std::vector` input iterator constructor to build an array of consecutive integers like this: ``` std::vector<unsigned> indexes(boost::counting_iterator<unsigned>(0U), boost::counting_iterator<unsigned>(10000U)); ``` However, I'm wondering if it will have time complexity proportional to the distance between the iterators or whether it could have an additional logarithmic component due to repeated resizing to grow the vector? In other words, does the constructor look at the distance between the two iterators? Since the constructor arguments are not random access iterators, I'm not sure the distance can be computed? If it would resize repeatedly, is there a better solution than this to avoid that: ``` std::vector<unsigned> indexes; indexes.reserve(10000U); for (unsigned idx = 0; idx < 10000U; ++idx) { indexes.push_back(idx); } ```