Implement Your Own std::vector<T> (MyVector)

A classic junior mistake when implementing vector is writing:

// FATAL JUNIOR MISTAKE:
data_ = new T[capacity_];

This fails catastrophically for three reasons:

1. Mandates Default Constructor: If T has no default constructor (e.g. struct User { User(int id); };), new T[cap] will not compile!
2. Performance Waste: Writing reserve(1'000'000) instantly invokes 1,000,000 default constructors, only for subsequent push_back calls to overwrite those values.
3. Double Destruction: delete[] expects all capacity_ objects to be valid. If only 3 elements were pushed, deleting will destroy uninitialized or overwritten objects.

A true vector allocates raw uninitialized memory with ::operator new(bytes), constructs objects in place using placement new / std::construct_at, and manually calls std::destroy_at on live elements.

Why does std::vector double its capacity ($1 → 2 → 4 → 8 …) rather than growing by a fixed constant like +10 or +100$?

If capacity grows by a constant C, inserting N elements triggers N / C reallocations. Each reallocation copies the existing i cdot C elements, resulting in:

$$\sum_{k=1}^{N/C} k \cdot C = O(N^2) total copies \implies O(N) per push_back!$$

With geometric doubling (2×), inserting N elements requires at most log_2 N reallocations. The total number of element copies across all reallocations is a convergent geometric series:

$$1 + 2 + 4 + 8 + … + N = 2N - 1 < 2N total copies$$

Dividing 2N copies by N operations yields an average of $< 2$ copies per push_back, proving amortized O(1) time complexity.

Consider the innocent-looking call:

v.push_back(v[0]);

Assume v.size() == v.capacity() == 1. When push_back(const T& val) is called, parameter val is a const reference binding directly to v.data_[0]. A naive implementation writes:

void push_back(const T& val) {
    if (size_ == capacity_) {
        reserve(capacity_ * 2); // REALLOCATES AND FREES OLD BUFFER!
    }
    std::construct_at(data_ + size_, val); // val is DANGLING! Reads freed memory!
}

The moment reserve() deallocates the old buffer, val becomes a dangling reference to dead heap memory! To prevent this, the vector must construct the new element in the newly allocated buffer before deallocating the old buffer.

push_back accepts either const T& (copy) or T&& (move), meaning an existing object must already exist before being placed into the container. For example, v.push_back(User(1, "Alice")) creates a temporary User on the stack and moves it into the vector buffer.

emplace_back(Args&&... args) uses a variadic template parameter pack and forward references (T&&). Instead of constructing a temporary object, it forwards the constructor arguments directly into placement new:

std::construct_at(data_ + size_, std::forward<Args>(args)...);

The object is constructed directly inside the vector's heap buffer with zero temporary objects and zero copy/move operations.

When reallocating a vector from capacity_ to 2 * capacity_, what happens if copying element k throws an exception (e.g. std::bad_alloc)?

If we moved elements using std::move and an exception is thrown midway, the original vector is corrupted: some elements are moved-from zombies, while others remain in the old buffer! To satisfy the Strong Exception Safety Guarantee (commit-or-rollback):

1. Use std::move_if_noexcept: If T's move constructor is marked noexcept, move the element; otherwise, make a copy.
2. Wrap the construction loop in a try/catch block. If an exception throws, destroy the newly constructed elements, deallocate the new buffer, and rethrow, leaving the original vector completely untouched.