Finding out how to implement features from the standard library can be a useful learning exercise. Quasar Chunawala explores implementing your own version of std::vector.

Implementing vector<T>

by Quasar Chunawala

From the article:

The most fundamental STL data-structure is the vector. In this article, I am going to explore writing a custom implementation of the vector data-structure. The standard library implementation std::vector is a work of art, it is extremely efficient at managing memory and has been tested ad nauseam. It is much better, in fact, than a homegrown alternative would be.

Why then write our own custom vector?

• Writing a naive implementation is challenging and rewarding. It is a lot of fun!
• Coding up these training implementations, thinking about corner cases, getting your code reviewed, revisiting your design is very effective at understanding the inner workings of STL data-structures and writing good C++ code.
• Its a good opportunity to learn about low-level memory management algorithms.

We are not aiming for an exhaustive representation or implementation, but we will write test cases for all basic functionalities expected out of a vector-like data-structure.

Informally, a std::vector<T> represents a dynamically allocated array that can grow as needed. As with any array, a std::vector<T> is a sequence of elements of type T arranged contiguously in memory. We will put our homegrown version of vector<T> under the dev namespace.