Reimplementing a standard library type is one of those exercises that sounds like a beginner task but turns out to reveal layers you did not know existed. Quasar Chunawala’s walkthrough of a custom vector implementation is a good starting point, but the interesting parts come when you ask why each design decision exists, and what happens if you get one wrong.
Three Pointers, Not Two
The natural first instinct is to store a pointer and a size. That works for a fixed-size array wrapper, but a growable container needs to track allocated capacity separately from constructed size. Both libc++ and libstdc++ represent a vector’s state with three pointers:
begin_: points to the first elementend_: points one past the last constructed elementend_of_capacity_: points one past the last allocated byte
size() is end_ - begin_. capacity() is end_of_capacity_ - begin_. The region between end_ and end_of_capacity_ is raw, allocated memory containing no live objects.
template <typename T>
class vector {
T* begin_;
T* end_;
T* end_of_capacity_;
};This distinction between allocated-but-uninitialized and allocated-and-constructed is the foundation of everything else. reserve(n) extends end_of_capacity_ without changing end_. push_back constructs an element at end_ and advances it. pop_back destroys the element at end_ - 1 and retreats the pointer, without touching the allocation.
Why Not Just Use new and delete
A homegrown vector that uses new T[n] to allocate has an immediate problem: new T[n] default-constructs all n elements. The entire point of separating capacity from size is that the capacity region is uninitialized storage, not a row of default-constructed objects waiting to be overwritten.
The correct approach is raw allocation followed by placement new:
// Allocate raw memory -- no construction
T* buf = static_cast<T*>(::operator new(n * sizeof(T)));
// Construct at a specific address
::new(static_cast<void*>(buf + i)) T(value);
// Destroy without deallocating
buf[i].~T();
// Deallocate without destroying
::operator delete(buf);The standard library wraps this protocol in std::allocator_traits<A>, which provides allocate, construct, destroy, and deallocate. By routing through allocator_traits instead of calling placement new directly, your vector becomes compatible with custom allocators: pool allocators, arena allocators, or anything else that satisfies the allocator concept. This is the correct architecture even for a learning implementation, because it shapes how you think about construction and allocation as separate concerns.
libc++ takes this further with an empty base optimization: the allocator is stored in a __compressed_pair<pointer, allocator_type>, so a stateless allocator like std::allocator contributes zero bytes to the vector’s size. Without this, a naive struct { T* ptr; Alloc alloc; } would waste padding bytes even when the allocator has no state.
The Growth Factor Problem
When push_back is called and size equals capacity, the vector allocates a larger buffer and moves everything into it. The question of how much larger has a less obvious answer than it appears.
The most common choice is 2x: double the capacity on each reallocation. libstdc++ uses this. libc++ uses this. The amortized O(1) guarantee holds for any factor greater than 1, so 2x is not wrong, but it has a memory reuse problem.
Consider the allocation sequence with 2x growth: 1, 2, 4, 8, 16, 32. Each new allocation is larger than the sum of all previous allocations combined. This means a smart allocator can never reuse the freed memory from prior allocations to satisfy the next one. You always need a completely fresh region.
A growth factor below the golden ratio (approximately 1.618) avoids this. With 1.5x, the cumulative freed memory eventually exceeds the next required allocation size, allowing the allocator to recycle prior blocks. Facebook’s folly::fbvector documents this reasoning and uses 1.5x explicitly. MSVC’s standard library switched to 1.5x (new_capacity = old + old / 2). Howard Hinnant’s widely-cited Stack Overflow answer gives the mathematical argument.
For short-lived vectors in local scope, this distinction rarely matters. For programs that allocate millions of vectors over their lifetime, the heap fragmentation difference is measurable.
The noexcept Dance
This is the subtlety most homegrown implementations miss, and it has silent performance consequences.
When vector reallocates, it transfers all existing elements from the old buffer to the new one. It would prefer to use move construction, which is fast. But if a move constructor throws mid-transfer, the vector is in trouble: some elements in the old buffer have been moved-from (destroyed), and the new buffer is partially constructed. There is no way to recover the original state. The strong exception safety guarantee, which says the vector is unchanged if an operation throws, cannot be maintained.
The resolution is std::move_if_noexcept. If T’s move constructor is marked noexcept, the vector uses moves. If not, and if T is copy constructible, it falls back to copies. A copy that throws leaves the original element intact in the old buffer.
// During reallocation:
if constexpr (std::is_nothrow_move_constructible_v<T>) {
std::uninitialized_move(begin_, end_, new_buf);
} else {
std::uninitialized_copy(begin_, end_, new_buf);
}The practical consequence: if your type T has a move constructor that is not noexcept, every vector<T> reallocation copies all your objects. This is checked at compile time and produces no warning. The copies happen silently, at whatever cost copying T carries. Marking your move constructors noexcept when they cannot throw is not optional boilerplate; it controls which code path vector uses on every growth event. Scott Meyers covers this in Effective Modern C++, Item 14.
Exception Safety in Practice
Implementing the strong guarantee for push_back requires a specific sequence:
- If no reallocation is needed, construct the new element in place at
end_. If construction throws,end_has not moved, the vector is unchanged. - If reallocation is needed, allocate the new buffer, move or copy existing elements (using the noexcept dance), then construct the new element at the end of the new buffer, then update all three pointers atomically. If any step throws, deallocate the new buffer and leave the original intact.
The insert-into-the-middle case provides only the basic guarantee when shifting elements is involved: the vector remains valid but its contents may be in an unspecified state if an exception occurs. This is documented behavior in the standard, not an implementation shortcut.
pop_back, clear, and erase provide the nothrow guarantee. This is only valid because destructors should not throw. If a destructor throws, vector’s nothrow guarantees break, and you are in undefined behavior territory regardless of what vector does.
What Production Implementations Add
A correct homegrown implementation still differs from std::vector in several ways that matter in practice.
libc++ annotates vector’s capacity region for AddressSanitizer: the bytes between end_ and end_of_capacity_ are marked as inaccessible by ASan, so an out-of-bounds write that lands within the allocated capacity region is caught immediately rather than silently corrupting future elements. This is transparent to normal builds but invaluable under sanitizers.
LLVM’s SmallVector embeds N elements of aligned storage directly inside the vector object, avoiding heap allocation entirely when the contents fit. The isSmall() check is a pointer comparison: if BeginX == &InlineStorage[0], no heap has been used. On overflow past N, it falls back to heap allocation and moves the inline elements out. LLVM uses this throughout its internals for lists that are usually short: instruction operands, basic block successors, worklist entries.
Rust’s Vec<T> covers the same problem from a different direction. Its internal representation is a pointer, a length, and a capacity (NonNull<T> plus two usize fields) rather than three raw pointers. The growth factor is 2x in the current alloc/src/raw_vec.rs implementation. The structural difference is that Rust’s borrow checker enforces iterator invalidation at compile time: you cannot hold a reference into a Vec across a reallocation. In C++, iterator invalidation rules are a runtime contract you maintain manually; violations are undefined behavior with no guaranteed diagnostic.
What the Exercise Is Actually For
The result of implementing your own vector<T> will not beat std::vector. That is not the point. The point is that vector concentrates an unusual number of C++ memory management concepts into one data structure: the three-pointer layout, the allocator protocol, growth factor mathematics, placement new, the noexcept dance, and the layered exception safety hierarchy. Working through them in sequence builds a mental model that makes reading the real implementation productive rather than opaque. And the real implementation, in libc++ or libstdc++, is worth reading.