Does range constructor of std::vector reserve required capacity before filling?

Viewed 29

Which of 2 implementation is more close to the specification?

#1

template <typename Iter>
vector::vector(Iter first, Iter last)
{
    reserve(std::distance(first, last));
    for (auto it = first; it != last; it++)
        { push_back(*it); }
}

#2

template <typename Iter>
vector::vector(Iter first, Iter last)
{
    for (auto it = first; it != last; it++)
        { push_back(*it); }
}

The reserving implementation (#1) runs two times through the range if Iter is a not random access iterator. The first time is in std::distance to determine vector size, the second time is in the constructor itself for filling the vector with elements.

The reserve-less implementation (#2) is always single-pass. But if the vector is out of capacity, then reallocations happen which involve additional "pass through the range" actions. So in generate the #1 implementation has better performance.

Therefore I'm almost sure that the correct answer is #1. Also GNU C++ standard library does it this way. But I'm still curious.

The question may be more relevant to corresponding assign method that takes range as a parameter, because, when doing assign, the vector may have enough capacity, and so doing reserve before assign is redundant. Therefore it is unclear if vector assign reserves required capacity before filling.

0 Answers
Related