CODEWITHSUNDEEP
c++constructorstdvectorimplementation
a.tana
a.tana

Reputation: 73

Efficient implementation of std::vector-like container's constructor

std::vector has a constructor which is in the form of

template< class InputIt >
vector( InputIt first, InputIt last,
        const Allocator& alloc = Allocator() );

Then, how do you implement this constructor if the iterator is not a random-access one?
I came up with two candidates:

  1. In a loop, call push_back(*first)(assume push_back is already implemented) while first != last;
  2. Count the number of elements by std::distance(first, last),
    then allocate enough memory, then copy construct all the elements.

Obviously, the latter is not possible for an input iterator.

Which is better? Or do you have any other ideas?

Upvotes: 0

Views: 300

Answers (2)

LoS
LoS

Reputation: 1833

Provided that the iterator type is at least of the forward iterator category, the std::vector range constructor can be implemented in the following two ways:

  1. it is allocated an array, whose size is computed through an equivalent of the std::distance(f, l) function, and then all elements in the range are copy constructed;
  2. all elements in the range are copy constructed one-by-one, performing a reallocate operation each time that the array is full.

An example of implementation is the following.

// (1)
template <typename FwdIter>
vector(FwdIter f, FwdIter l, const allocator_type& a = allocator_type())
{
  this->reserve(std::distance(f, l));
  for(; f != l; ++f)
    this->push_back(*f);
}

// (2)
template <typename FwdIter>
vector(FwdIter f, FwdIter l, const allocator_type& a = allocator_type())
{
  for(; f != l; ++f)
    this->push_back(*f);
}

The first design requires to iterate through the range two times, one to compute the size and another to perform the copy construction of all elements. The overall computational cost is O(N). Conversely, the second design requires to perform only one copy construction per loop, doubling the array each time that the capacity is exhausted. This means that order logN of reallocations occur. The overall computational cost is O(N).

For simplicity, the above calculus have been made by assuming that the allocate and deallocate operations are constant-time.

The latter design has an important penalty: the need to reallocate the array more times increase the number of copy/move construct operations and then may increment the risk that an exception be thrown.

Indeed, the reallocate operation requires that the elements in the original array be move constructed into the new memory and then destroyed. This may seem a cheap operation, but it is not guaranteed. If on the one hand the value_type may have an expensive move constructor, on the other hand the move constructor may be potentially-throwing and then the implementation would be forced to adopt its copy constructor to avoid UB in case of an exception is thrown.

If the move constructor or copy constructor is potentially-throwing, the probability that an exception be thrown increases. Of course, this is the weakest issude because exceptions are generally a rare condition.

1 Design 2 Design
O(N) O(N)
N copies N copies + logN reallocations

To summarize, the first design seems to be better in terms of performance.

Upvotes: 1

Mooing Duck
Mooing Duck

Reputation: 66961

The usual implementation is something like

private:
template<class input_iterator>
std::size_t size_if_possible(input_iterator first, input_iterator last, std::input_iterator_tag) {
}
template<class input_iterator>
std::size_t size_if_possible(input_iterator first, input_iterator last, std::forward_iterator_tag) {
    return std::distance(first, last);
}

public:
template<class input_iterator>
vector(input_iterator first, input_iterator last) {
    reserve(size_if_possible(first, last, std::iterator_traits<input_iterator>::tag{}));
    while (first != last) {
        emplace_back(*first);
        first++;
    }
}

This allows it to reserve if you pass in a forward iterator, and effectively skip the reserve if you pass in a single pass input iterator, giving you the best of both worlds.

Upvotes: 1

Related Questions