Levels of implementing std::vector

WIP! Last updated Oct 26 2025 while I am still updating my site

There’s a saying I’ve heard: if you know std::vector, you know half of C++. And as it turns out, I don’t really know std::vector, so in my journey of being an actual competent C++ dev, I’m going to fix that.

As it turns out, this general problem is quite open-ended depending on what constraints and requirements are given. Surprisingly, I wasn’t able to find a satisfying, comprehensive explanation of what you’ll need to consider for every level.

Let’s start out with the very basics; a vector is a list that stores things of the same type, and can grow and shrink dynamically.

Ok, so we will need templates to handle the type of the elements stored, and some way to handle memory size. As part of the assignment is to handle memory ourselves, we must also take care to not leak any memory.

Level 1: Generic types, simple objects.

template <typename T> class vector {
  T *a_;
  size_t n_;
  size_t mx_;

  void setToSize(int sz) {
    T *a = new T[sz];
    for (size_t i = 0; i < n_; i++) {
      a[i] = a_[i];
    }
    delete[] a_;
    a_ = a;
    mx_ = sz;
  }
  void expandSize() {
    setToSize(mx_ == 0 ? 1 : 2 * mx_);
  }

public:
  vector() : a_(nullptr), n_(0), mx_(0) {}
  vector(int n) : n_(n), mx_(n) { a_ = new T[n]; }
  ~vector() { delete[] a_; }

  void push_back(T x) {
    if (n_ == mx_) {
      expandSize();
    }
    a_[n_++] = x;
  }
  const T at(size_t i) {
    if(i < 0 || i >= n_) throw std::runtime_error("out of bounds");
    return a_[i];
  }
  size_t getSize() {
    return n_;
  }
  size_t getCapacity() {
    return mx_;
  }
  void shrink_to_fit() {
    setToSize(n_);
  }
  void pop_back() {
    if(n_ == 0) throw std::runtime_error("nothing to pop back");
    n_--;
  }

  void print() {
    std::cout << "size: " << n_ << ", capacity: " << mx_ << "\n";
    std::cout << "array: ";
    for (size_t i = 0; i < n_; i++) {
      std::cout << a_[i] << " ";
    }
    std::cout << "\n";
  }
};

And just a quick test:

int main() {
  ricky::vector<int> v;
  v.print();
  v.push_back(2);
  v.push_back(3);
  v.print();
  v.pop_back();
  v.push_back(5);
  v.push_back(10000);
  v.print();
}

[ricky@surface2 cpp_playground]$ g++ implementVector.cpp -o main
[ricky@surface2 cpp_playground]$ ./main
size: 0, capacity: 0
array:
size: 2, capacity: 2
array: 2 3
size: 3, capacity: 4
array: 2 5 10000

Alright, that looks as expected. So all we really need is a pointer to a memory block that holds our data (a), a current size (n), and a capacity (sz). Our underlying management is with new() and delete(), and some reasonable logic to adjust the size and capacity. We need to be careful about increasing the size: to keep the memory block continuous, we must allocate a new memory block with a larger size, migrate our data over, then delete and replace the old block.

What can be improved with this, though? While we don’t have a precise goal, adhering closer to the C++ standard is ideal. Let’s not go over all the requirements of std::vector, but try this vector on some other objects to see if there are any differences with what we would expect:

struct complexObject {
  int *a;
  std::string b;
  complexObject(int x, std::string y) {
    a = new int(x);
    b = y;
  }
  friend std::ostream &operator<<(std::ostream &os, const complexObject &o) {
    return os << *o.a << ", " << o.b;
  }
};

int main() {
  ricky::vector<complexObject> v;
  v.print();
  v.push_back(complexObject(1, "a"));
  v.push_back(complexObject(1, "b"));
  v.print();
  v.pop_back();
  v.push_back(complexObject(2, "a"));
  complexObject c(2, "c");
  v.push_back(c);
  v.print();
}

We now get:
    T *a = new T[sz];
Diagnostics:
No matching constructor for initialization of 'complexObject[]' [ovl_no_viable_function_in_init]

Hm, so why is this? Let’s take a closer look. new T[sz] invokes the new-expression (not the new-allocation); after some digging on cppreference, we can see that if this “new-initializer” thing is absent, the object is default initialized. Aha, and so our error is that we don’t provide any complexObject() default.

But…we don’t want to be default constructing complexObject. Our intuition of vector is that an empty declaration starts out empty, and then we “push_back” elements for the first time. So, in fact, our class is doing extra unintended work. This may also inspire us to look at deletions; thankfully, delete[] does delete each element before deallocating, but if we cannot use new[], then naturally we must find a different way while keeping this in mind.

So, we need to ensure that we are allocating memory without doing any work of constructing objects. Upon search, there are many ways, but discarding unideal ones for this use case (OS, fixed size buffers, C malloc/free), there are two that remain: global allocator functions and std::allocator/std::allocator_traits.

The simpler of these is global allocator functions, so we will use them for level 2. Instead of new[] expression, we instead get void* from new-allocation of ::operator new(bits allocated). Likewise, instead of expression delete[] we use ::operator delete. Note the primary difference is that the expressions handle both allocation and construction (managing object’s lifetime), whereas these allocators only handle allocation.

There is a subtle error here that helps cement our understanding of object lifetimes:

  void push_back(T x) {
    if (n_ == mx_) {
      expandSize();
    }
    a_[n_++] = x;
  }

  ricky::vector2<complexObject> v;
  v.print();
  v.push_back(complexObject(1, "a"));
  v.push_back(complexObject(1, "b"));
  v.print();
  v.pop_back();
  v.push_back(complexObject(2, "a"));
  complexObject c(2, "c");
  v.push_back(c);
  v.print();

[ricky@surface2 cpp_playground]$ ./main
size: 0, capacity: 0
array:
size: 2, capacity: 2
array: 1, a 1, b
size: 3, capacity: 4
array: 1, a 97, a 2, c

Our statement of a*[n*++] = x is incorrect, and is in fact undefined behavior. Because a*[n] is not yet, it does not really “exist”, so we cannot assign x to it. Instead, we must call std::construct_at(a* + n_, x).

At this stage, we must also address and come to recognize move semantics. Let’s say we were to call construct_at with some x. If we don’t need the existing contents of x, such as if we are moving the objects during a size transition, it would be much more efficient to just move the objects directly rather than constructing from a created copy. This is naturally move semantics. If you are unfamiliar, I highly recommend getting a basic understnding of the differences in value types (lvalues, xvalues, prvalues) before moving on.

Consider the different ways we might push back:

  void push_back(const T &x) {
    if (n_ == mx_) expandSize();
    std::construct_at(a_ + n_, x);
    ++n_;
  }
  void push_back(T &&x) {
    if (n_ == mx_) expandSize();
    std::construct_at(a_ + n_, std::move(x));
    ++n_;
  }
...
int main() {
  vector<Obj> v;
  Obj o(...);
  v.push_back(o);        // Calls the T&
  v.push_back(Obj(...)); // Calls the T&&
}

Because we are initializing the Obj(…) in place in the last line, the move optimizes it so that it is if we are just creating that right in the correct place of the vector, no middle man needed.

  vector2 &operator=(vector2 &&o) noexcept {
    if (this != &o) {
      for (size_t i = 0; i < n_; ++i) {
        std::destroy_at(a_ + i);
      }
      ::operator delete(a_);
      a_ = o.a_;
      n_ = o.n_;
      mx_ = o.mx_;
      o.a_ = nullptr;
      o.n_ = o.mx_ = 0;
    }
    return *this;
  }

Similarly, if we are assigning to an expiring vector, we can optimize by directly assigning contents. This is similar to the underlying O(1) pointer swap done by std::swap. There is also deep copy implementation to complete the rule of 5, but since that is not the focus of this blog I leave them to do.

template <typename T> class vector2 {
  T *a_;
  size_t n_;
  size_t mx_;

  void setToSize(size_t sz) {
    T *a = static_cast<T *>(::operator new(sizeof(T) * sz));
    size_t i = 0;
    for (; i < n_; ++i){
      std::construct_at(a + i, std::move(a_[i]));
    }
    for (size_t j = 0; j < n_; ++j) {
      std::destroy_at(a_ + j);
    }
    ::operator delete(a_);
    a_ = a;
    mx_ = sz;
  }

  void expandSize() { setToSize(mx_ == 0 ? 1 : 2 * mx_); }

public:
  vector2() : a_(nullptr), n_(0), mx_(0) {}

  vector2(int n) : a_(nullptr), n_(0), mx_(0) {
    a_ = static_cast<T *>(::operator new(sizeof(T) * static_cast<size_t>(n)));
    for (; n_ < static_cast<size_t>(n); ++n_) {
      std::construct_at(a_ + n_);
    }
    mx_ = static_cast<size_t>(n);
  }

  ~vector2() {
    for (size_t i = 0; i < n_; ++i) {
      std::destroy_at(a_ + i);
    }
    ::operator delete(a_);
  }

  // TODO: write a deep copy
  // vector2(const vector2 &) = delete;
  // vector2 &operator=(const vector2 &) = delete;

  vector2(vector2 &&o) noexcept : a_(o.a_), n_(o.n_), mx_(o.mx_) {
    o.a_ = nullptr;
    o.n_ = o.mx_ = 0;
  }
  vector2 &operator=(vector2 &&o) noexcept {
    if (this != &o) {
      for (size_t i = 0; i < n_; ++i) {
        std::destroy_at(a_ + i);
      }
      ::operator delete(a_);
      a_ = o.a_;
      n_ = o.n_;
      mx_ = o.mx_;
      o.a_ = nullptr;
      o.n_ = o.mx_ = 0;
    }
    return *this;
  }

  void push_back(const T &x) {
    if (n_ == mx_) expandSize();
    std::construct_at(a_ + n_, x);
    ++n_;
  }
  void push_back(T &&x) {
    if (n_ == mx_) expandSize();
    std::construct_at(a_ + n_, std::move(x));
    ++n_;
  }

  // Also const variant
  T &at(size_t i) {
    if (i >= n_) throw std::runtime_error("out of bounds");
    return a_[i];
  }

  size_t getSize() { return n_; }
  size_t getCapacity() { return mx_; }
  void shrink_to_fit() { setToSize(n_); }

  void pop_back() {
    if (n_ == 0) throw std::runtime_error("nothing to pop back");
    --n_;
    std::destroy_at(a_ + n_);
  }

  void print() {
    std::cout << "size: " << n_ << ", capacity: " << mx_ << "\n";
    std::cout << "array: ";
    for (size_t i = 0; i < n_; i++) std::cout << a_[i] << " ";
    std::cout << "\n";
  }
};

// TODO: Fill level 3 of allocate/allocator_traits, level 4 with basic iterators