Resizing a std::vector

std::vector has a whole family of member functions concerned with adding and deleting elements. These member functions aren't present in std::array because std::array isn't resizable; but they are present in most of the other containers we're going to be talking about in this chapter. So it's a good idea to get familiar with them now.

Let's start with the two primitive operations specific to vector itself: .resize() and .reserve().

vec.reserve(c) updates the capacity of the vector--it "reserves" space for as many as c elements (total) in the underlying array. If c <= vec.capacity() then nothing happens; but if c > vec.capacity() then the vector will have to reallocate its underlying array. Reallocation follows an algorithm equivalent to the following:

    template<typename T>
    inline void destroy_n_elements(T *p, size_t n)
    {
      for (size_t i = 0; i < n; ++i) {
        p[i].~T();
      }
    }

    template<typename T>
    class vector {
      T *ptr_ = nullptr;
      size_t size_ = 0;
      size_t capacity_ = 0;

      public:
      // ...

      void reserve(size_t c) {
        if (capacity_ >= c) {
          // do nothing
          return;
        }

        // For now, we'll ignore the problem of
        // "What if malloc fails?"
        T *new_ptr = (T *)malloc(c * sizeof (T));

        for (size_t i=0; i < size_; ++i) {
          if constexpr (std::is_nothrow_move_constructible_v<T>) {
            // If the elements can be moved without risking
            // an exception, then we'll move the elements.
            ::new (&new_ptr[i]) T(std::move(ptr_[i]));
          } else {
            // If moving the elements might throw an exception,
            // then moving isn't safe. Make a copy of the elements
            // until we're sure that we've succeeded; then destroy
            // the old elements.
            try {
              ::new (&new_ptr[i]) T(ptr_[i]);
            } catch (...) {
              destroy_n_elements(new_ptr, i);
              free(new_ptr);
              throw;
            }
          }
        }
        // Having successfully moved or copied the elements,
        // destroy the old array and point ptr_ at the new one.
        destroy_n_elements(ptr_, size_);
        free(ptr_);
        ptr_ = new_ptr;
        capacity_ = c;
      }

      ~vector() {
        destroy_n_elements(ptr_, size_);
        free(ptr_);
      }
    };

If you've been reading this book in order, you might recognize that the crucial for-loop in this .reserve() function closely resembles the implementation of std::uninitialized_copy(a,b,c) from Chapter 3, The Iterator-Pair Algorithms. Indeed, if you were implementing .reserve() on a container that was not allocator-aware (see Chapter 8, Allocators), you might reuse that standard algorithm:

    // If the elements can be moved without risking
    // an exception, then we'll move the elements.
    std::conditional_t<
      std::is_nothrow_move_constructible_v<T>,
      std::move_iterator<T*>,
      T*
      > first(ptr_);

    try {
      // Move or copy the elements via a standard algorithm.
      std::uninitialized_copy(first, first + size_, new_ptr);
    } catch (...) {
      free(new_ptr);
      throw;
    }

    // Having successfully moved or copied the elements,
    // destroy the old array and point ptr_ at the new one.
    std::destroy(ptr_, ptr_ + size_);
    free(ptr_);
    ptr_ = new_ptr;
    capacity_ = c;

vec.resize(s) changes the size of the vector--it chops elements off the end of the vector (calling their destructors in the process), or adds additional elements to the vector (default-constructing them), until the size of the vector is equal to s. If s > vec.capacity(), then the vector will have to reallocate its underlying array, just as in the .reserve() case.

You may have noticed that when a vector reallocates its underlying array, the elements change addresses: the address of vec[0] before the reallocation is different from the address of vec[0] after the reallocation. Any pointers that pointed to the vector's old elements become "dangling pointers." And since std::vector::iterator is essentially just a pointer as well, any iterators that pointed to the vector's old elements become invalid as well. This phenomenon is called iterator invalidation, and it is a major source of bugs in C++ code. Watch out when you're dealing with iterators and resizing vectors at the same time!

Here are some classic cases of iterator invalidation:

    std::vector<int> v = {3, 1, 4};

    auto iter = v.begin();
    v.reserve(6); // iter is invalidated!

    // This might look like a way to produce the result
    // {3, 1, 4, 3, 1, 4}; but if the first insertion
    // triggers reallocation, then the next insertion
    // will be reading garbage from a dangling iterator!
    v = std::vector{3, 1, 4};
    std::copy(
      v.begin(),
      v.end(),
      std::back_inserter(v)
    );

And here's another case, familiar from many other programming languages as well, in which erasing elements from a container while iterating over it produces subtle bugs:

    auto end = v.end();
    for (auto it = v.begin(); it != end; ++it) {
      if (*it == 4) {
        v.erase(it); // WRONG!
      }
    }

    // Asking the vector for its .end() each time
    // through the loop does fix the bug...
    for (auto it = v.begin(); it != v.end(); ) {
      if (*it == 4) {
        it = v.erase(it);
      } else {
        ++it;
      }
    }

    // ...But it's much more efficient to use the
    // erase-remove idiom.
    v.erase(
      std::remove_if(v.begin(), v.end(), [](auto&& elt) {
        return elt == 4;
      }),
      v.end()
    );