Implementing vector<T>

C++
Author

Quasar

Published

December 15, 2025

Implementing vector<T>

The problem statement

Your Task

Implement your own version of a vector with the following methods:

  • push_back – Adds an element to the back.
  • at – Retrieves an element by index.
  • getSize – Gets the size of the container.
  • getCapacity – Gets the capacity of the container.
  • shrinkToFit – Shrinks the capacity to equal the size of the container.
  • pop_back – Removes the last element in the container. Will never be called on an empty container.

Requirements

  • Do not worry about memory alignment or advanced optimizations.
  • Do not use std::vector in your dev::vector implementation.
  • Your vector’s capacity must start at 1.
  • The capacity should triple every time it is reached.

For more such C++ coding tasks, visit getcracked.io.

Writing your own vector<T> training implementation

If you know std::vector, you know half of C++.

- Bjarne Stroustrup

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-strucures 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 contigously in memory. We will put our homegrown version of vector<T> under the dev namespace.

Unit tests for vector<T>

For low-level data-structures such as the vector, let’s write the unit-tests upfront before the implementation. This will help us think through the interface and corner cases. Tests will also serve as documentation of the expected functionality.

The internal representation of a vector like type has a book-keeping node that consists of: - A pointer to the raw data (a block of memory that will hold elements of type T) - Size of the container(the number of elements in the container) - Capacity

It’s important to distinguish between size and capacity. size is the number of elements currently in the container. When size == capacity, the container becomes full and will need to grow, which means allocating more member, copying the elements from the old storage to the new storage and getting rid of the old storage.

Given this background, we assume that the vector is equipped with basic getters such as:

  • std::size_t size()
  • std::size_t capacity()
  • bool empty()
  • bool is_full()

The vector should support various constructors.

TEST(VectorTest, DefaultConstructorTest) {
    dev::vector<int> v;
    EXPECT_EQ(v.empty(), true);
}

TEST(VectorTest, InitializerListTest){
    dev::vector<int> v{1, 2, 3, 4, 5};
    EXPECT_EQ(!v.empty(), true);
    EXPECT_EQ(v.size(), 5);
    EXPECT_TRUE(v.capacity() > 0);
    for(auto i{0uz}; i < v.size(); ++i){
        EXPECT_EQ(v.at(i), i+1);
    }
}

TEST(VectorTest, ParameterizedConstructorTest){
    dev::vector v(10, 5.5);
    EXPECT_EQ(v.size(), 10);
    for(auto i{0uz}; i < v.size(); ++i){
        EXPECT_EQ(v[i], 5.5);
    }
}

TEST(VectorTest, CopyConstructorTest){
    dev::vector v1{ 1.0, 2.0, 3.0, 4.0, 5.0 };
    dev::vector v2(v1);

    EXPECT_EQ(v1.size() == v2.size(), true);

    for (int i{ 0 }; i < v1.size(); ++i)
    {
        EXPECT_EQ(v2[i], i+1);
        EXPECT_EQ(v1[i], v2[i]);
    }
}

TEST(VectorTest, MoveConstructorTest){
    dev::vector<int> v1{ 1, 2, 3 };
    dev::vector<int> v2(std::move(v1));
    EXPECT_EQ(v1.size(), 0);
    EXPECT_EQ(v1.capacity(), 0);
    EXPECT_EQ(v2.size(), 3);
    for(auto i{0uz}; i<v2.size(); ++ i)
        EXPECT_EQ(v2[i], i + 1);
}

TEST(VectorTest, CopyAssignmentTest)
{
    dev::vector<int> v1{ 1, 2, 3 };
    dev::vector<int> v2;
    v2 = v1;

    EXPECT_EQ(v1.size(), v2.size());
    EXPECT_EQ(v1.capacity(), v2.capacity());
    for (int i = 0; i < v1.size(); ++i) {
        EXPECT_EQ(v1[i], i+1);
        EXPECT_EQ(v1[i], v2[i]);
    }
}

TEST(VectorTest, MoveAssignmentTest)
{
    dev::vector<int> v1{ 1, 2, 3 };
    dev::vector<int> v2;
    v2 = std::move(v1);

    EXPECT_EQ(v1.size(), 0);
    EXPECT_EQ(v1.capacity(), 0);
    EXPECT_EQ(v2.size(), 3);
    for (int i = 0; i < v1.size(); ++i) {
        EXPECT_EQ(v2[i], i+1);
    }
}

The vector data-structure should support element access through the array subscript operator [], just like C-style arrays. The T& at(std::size_t idx) could also be used to access the element at index idx with bounds checking.

TEST(VectorTest, AtTest)
{
    dev::vector<int> v{ 1, 2, 3 };
    EXPECT_EQ(v.at(0), 1);
    EXPECT_EQ(v.at(1), 2);
    EXPECT_EQ(v.at(2), 3);

    EXPECT_THROW(v.at(3), std::out_of_range);
}

TEST(VectorTest, SubscriptOperatorTest)
{
    dev::vector<int> v{ 1, 2, 3 };
    for (int i{0uz}; i < v.size(); ++i) {
        EXPECT_EQ(v[i], i+1);
    }
}

We expect the container to perform the book-keeping of size and capacity correctly.

TEST(VectorTest, EmptyTest)
{
    dev::vector<int> v;
    EXPECT_EQ(v.empty(), true);

    v.push_back(42);
    EXPECT_EQ(v.empty(), false);
}

TEST(VectorTest, SizeAndCapacityTest)
{
    dev::vector<int> v;
    EXPECT_EQ(v.size(), 0);
    EXPECT_GE(v.capacity(), 0);

    v.push_back(42);
    EXPECT_EQ(v.size(), 1);
    EXPECT_GT(v.capacity(), 0);

    v.push_back(v.back());
    EXPECT_EQ(v.size(), 2);
    EXPECT_EQ(v[1], 42);
}

We expect the container to support the getter methods front() and back().

TEST(VectorTest, FrontAndBackTest)
{
    dev::vector<int> v{ 1, 2, 3 };
    EXPECT_EQ(v.front(), 1);
    EXPECT_EQ(v.back(), 3);
}

The container should support reserve(size_t new_capacity) and resize(size_t new_size). These are explained at length further ahead.

TEST(VectorTest, ReserveTest)
{
    dev::vector<int> v1;
    v1.reserve(10);
    EXPECT_GE(v1.capacity(), 10);
    EXPECT_EQ(v1.size(), 0);

    dev::vector<int> v2{1, 2, 3, 4, 5, 6, 7};
    size_t old_capacity = v2.capacity();
    EXPECT_GE(v2.capacity(), 7);
    EXPECT_EQ(v2.size(), 7);
    size_t new_capacity = 2 * old_capacity;
    v2.reserve(new_capacity);
    EXPECT_GE(v2.capacity(), new_capacity);
    EXPECT_EQ(v2.size(), 7);
    for(auto i{0uz}; i < v2.size(); ++i)
        EXPECT_EQ(v2[i], i + 1);
}

TEST(VectorTest, ResizeTest)
{
    dev::vector<int> v{ 1, 2, 3 };
    v.resize(5);

    EXPECT_EQ(v.size(), 5);
    for(auto i{0uz}; i<3; ++i)
        EXPECT_EQ(v[i], i + 1);

    EXPECT_EQ(v[3], 0);
    EXPECT_EQ(v[4], 0);

    v.resize(2);
    EXPECT_EQ(v.size(), 2);
    EXPECT_EQ(v[0], 1);
    EXPECT_EQ(v[1], 2);
}

The container should support appending elements or removal elements at the back.

TEST(VectorTest, PushBackTest)
{
    dev::vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);

    EXPECT_EQ(v.size(), 3);
    for(auto i{0uz}; i<v.size(); ++i)
        EXPECT_EQ(v[i], i + 1);
}

TEST(VectorTest, PushBackSelfReferenceTest)
{
    // The design of push_back/insert is slightly hard to get right.
    // If the vector is full, then you reallocate(grow) the vector.
    // If the value to be added is a reference to an existing
    // vector element, then value in vec.push_back(value) may become
    // a dangling reference, if it refers to the old storage (an element of the vector
    // itself e.g. vec.back()). This test is meant for such an edge case.
    dev::vector<int> vec{ 1 };
    for (auto i{0uz}; i < 64; ++i) {
        vec.push_back(vec.back());
        EXPECT_EQ(vec.back(), 1);
    }
}

TEST(VectorTest, EmplaceBackTest)
{
    struct Point
    {
        int x, y;
        Point(int a, int b)
          : x(a)
          , y(b)
        {
        }
    };

    dev::vector<Point> v;
    v.emplace_back(1, 2);
    v.emplace_back(3, 4);

    EXPECT_EQ(v.size(), 2);
    EXPECT_EQ(v[0].x, 1);
    EXPECT_EQ(v[0].y, 2);
    EXPECT_EQ(v[1].x, 3);
    EXPECT_EQ(v[1].y, 4);
}

TEST(VectorTest, PopBackTest)
{
    dev::vector<int> v = {1, 2, 3};
    EXPECT_EQ(v.size(), 3);
    v.pop_back();
    EXPECT_EQ(v.size(), 2);
    EXPECT_EQ(v, dev::vector<int>({1, 2}));
}

The container should support a .insert method that allows us to insert elements from a source range to a specified position in the target vector. You can write a variety tests, like inserting at the beginning, middle, end of the vector, self-referential insertion etc. For brevity, I skip listing all of the tests here. The Compiler Explorer online source listing for this entire article is available in the conclusion section.

vector member data

We start with coding up the vector as a class template. It is templated by the type T of the elements stored in the container. We also define various type aliases.

namespace dev {
    template <typename T>
    class vector {
        using value_type = T;
        using size_type = std::size_t;
        using pointer = T*;
        using const_pointer = const T*;
        using reference = T&;
        using const_reference = const T&;
        using iterator = pointer;
        using const_iterator = const_pointer;
        constexpr static std::size_t initial_capacity{1};
        constexpr static unsigned short growth_factor{2};

    private:
        pointer m_data;
        size_type m_size;
        size_type m_capacity;
    };
}

C++ containers usually expose iterators as part of their interface and ours will be no exception. We define type aliases for the const and non-const iterator types, as this makes it simpler to implement alternatives.

template <typename T>
class vector {
    // ...
public:

    iterator begin(){ return m_data; }
    const_iterator begin() const{ return m_data; }
    iterator end(){ return begin() + m_size; }
    const_iterator end() const{ return begin() + m_size; }
// ...

vector constructors

vector()
: m_data{allocate_helper(initial_capacity)},
m_size{0},
m_capacity{initial_capacity} {}

vector(size_t n, const T& initial_value)
: m_data{static_cast<T*>(operator new(sizeof(T) * n))},
m_size{0},
m_capacity{n} {
    try {
        std::uninitialized_fill_n(m_data, n, initial_value);
        m_size = n;
    } catch (std::exception& ex) {
        operator delete(m_data);
        m_capacity = 0;
    }
}

// Constructs a vector with count default-inserted 
// objects of T. No copies are made.
vector(size_t n)
: m_data{ allocate_helper(n) },
m_size{0},
m_capacity{n}{
    try {
        std::uninitialized_default_construct(m_data, m_data + n);
        m_size = n;
    } catch (std::exception& ex) {
        operator delete(m_data);
        m_capacity = 0;
    }
}

vector(std::initializer_list<T> list)
: m_data{allocate_helper(list.size())},
m_size{list.size()},
m_capacity{list.size()} {
    try {
        if constexpr (std::is_nothrow_move_constructible_v<T>) {
            std::uninitialized_move(list.begin(), list.end(), m_data);
        } else {
            std::uninitialized_copy(list.begin(), list.end(), m_data);
        }
    } catch (std::exception& ex) {
        operator delete(m_data);
        m_size = 0;
        m_capacity = 0;
    }
}

vector(const vector& other)
: m_data{ allocate_helper(other.size()) },
m_size{other.size()},
m_capacity{other.capacity()} {
    try {
        // Perform a deep-copy of all the Ts
        std::uninitialized_copy(other.m_data, other.m_data + other.m_size,
                                m_data);
    } catch (std::exception& ex) {
        operator delete(m_data);
        std::string error_msg =
            std::format("Error while copying in copy ctor {}", ex.what());
        throw std::logic_error(error_msg);
    }
}

vector(vector&& other) noexcept
: m_data{std::exchange(other.m_data, nullptr)},
m_size{std::exchange(other.m_size, 0)},
m_capacity{std::exchange(other.m_capacity, 0)} 
{}

void swap(vector& other) noexcept {
    std::swap(this->m_data, other.m_data);
    std::swap(this->m_size, other.m_size);
    std::swap(this->m_capacity, other.m_capacity);
}

vector& operator=(const vector& other) {
    vector(other).swap(*this);
    return *this;
}

vector& operator=(vector&& other) {
    vector(std::move(other)).swap(*this);
    return *this;
}

Basic services of a vector-like class

Implementing front(), back() and operator[](size_t idx)

There is more to writing a convenient dynamic array type. For example, member functions that let you access the elements at front or rear-end of the vector are to be expected. Similarly, an implementation of operator[] to access the element at a specific index in the array is also expected.

// ...
reference operator[](size_type idx){
    return m_data[idx];
}

const_reference operator[](size_type idx) const{
    return m_data[idx];
}

// precondition: !empty()
reference front(){ return (*this)[0]; }
const_reference front() const { return (*this)[0]; }
reference back(){ return (*this)[m_size - 1]; }
const_reference back() const{ return (*this)[m_size - 1]; }

Comparing two vector<T> objects for equivalence or lack thereof is a relatively easy matter if we use algorithms:

//...
bool operator==(const vector& other){
    return size() == other.size() && 
        std::equal(begin(), end(), other.begin());
}

Implementing reserve()

reserve(size_type new_capacity) increases the capacity of the vector(the total number of elements that the vector can hold without requiring reallocation) to a value that’s greater or equal to new_capacity. If new_capacity is greater than the current capacity(), new storage is allocated, otherwise the function does nothing.

We introduce the helper functions allocate_helper and copy_old_storage_to_new.

// Dynamically allocates a chunk of uninitialized memory on the heap
// that can hold `new_capacity` number of elements.
// Allocation excepts are propogated to the caller.
pointer allocate_helper(size_type new_capacity){
    return static_cast<pointer>(operator new(sizeof(value_type) * new_capacity));
}

void deallocate_helper(pointer ptr){
    operator delete(ptr);
}

// Copies elements from old storage to new
// If T's copy/move ctor throws, the objects already constructed are
// destroyed and the exception is propagated to the caller.
void copy_old_storage_to_new(pointer source_first, size_t num_elements, pointer destination_first){
    if constexpr(std::is_nothrow_move_constructible_v<T>){
        std::uninitialized_move(source_first, source_first + num_elements, destination_first);
    }
    else{
        try{
            std::uninitialized_copy(source_first, source_first + num_elements, destination_first);
        }catch(std::exception& ex){
            throw ex;
        }
    }
}

void reserve(size_type new_capacity){
    if(new_capacity <= capacity())
        return;
    
    auto ptr_new_blk = allocate_helper(new_capacity);
    try{
        copy_old_storage_to_new(m_data, m_size, ptr_new_blk);
    }catch(std::exception& ex){
        deallocate_helper(ptr_new_blk);
        throw ex;   // rethrow
    }
    
    std::destroy(m_data, m_data + m_size);
    deallocate_helper(m_data);
    m_data = ptr_new_blk;
    m_capacity = new_capacity;    
}

If new_capacity > capacity(), we must:

  • Allocate a chunk new_capacity * sizeof(T) bytes large on the heap dynamically.
  • Copy the existing container elements from the old storage area to the new block of memory.
  • Destruct the elements in the old storage and deallocate the memory occupied.
  • Update the vector’s m_data pointer and m_capacity field.

In general, we must separate allocation from construction. operator new(size_t count) and operator new[](size_t count). operator new(size_t count) attempt to allocate count bytes on the heap. The newly allocated memory is uninitialized. This is different from the new expression, new T(Args) or new T[]() which performs both allocation and zero initialization (invokes the default constructor T()).

After the allocation, we want to copy the elements in the range m_data[0...m_size-1] to ptr_new_blk. copy_old_storage_to_new is a helper function to copy num_elements from the memory location source_first to destination_first.

C++17 introduced std::uninitialized_copy and std::uninitialized_move algorithms. std::uninitialized_copy(first, last, d_first) accepts a source range [first,last) and copies the elements from the source range to an uninitialized memory area beginning at d_first. The std::uninitialized_move algorithm uses move semantics.

The beauty of these uninitialized memory algorithms are that they are exception safe. If one of the T(const T&) constructors invoked by uninitialized_copy ends up throwing, then the objects it managed to create before the exception was thrown will be destroyed in the reverse order of construction, before the exception leaves the function.

The type-trait std::is_move_constructible_v<T> is meta-function that returns true, if the argument T is move constructible.

There’s a general trick that you would have seen in all of this. Do not modify your object until you know, you can safely do. Try to do the potentially throwing operations first, then do the operations until you can mutate your object. You will sleep better, and the risks of object corruption will be alleviated.

Implementing resize()

The distinction between resize() and reserve() is that reserve() only affects the capacity of the container, whereas resize() modifies the size and capacity both.

The resize(size_type new_size) method resizes the container to contain count elements:

  • If the new_size is equal to the current size, do nothing.
  • If the current size is greater than the new_size, the container is reduced to its first new_size elements.
  • If the current size is less than new_size, then:
    • Additional default-constructed elements are appended.
void resize(size_type new_size){
    size_type current_size = m_size;
    if(new_size == current_size)
        return;

    if(new_size < current_size)
    {
        // Reduce the container to count elements
        std::destroy(m_data + new_size, m_data + m_size);
    }

    if(new_size > current_size)
    {
        reserve(new_size);

        // Default construct elements at indicates
        // [current_size,...,new_size-1]
        std::uninitialized_fill(m_data + size(), m_data + capacity(), value_type{});
    }
    m_size = new_size;
}

How to think about adding elements to our container?

We will code up a push_back(T&&) member function that accepts a universal reference T&&. If T is move constructible, then the value will be moved. If T is copy constructible then the value will be copied.

The emplace_back(Args...) will take a variadic pack of constructor arguments, and then perfectly forward them to the constructor of a T object, that will be placed at the end of the container. A reference to the newly constructed object is returned by emplace_back(), for convenience, in case the user-code would like to use it right away.

We would like to first check whether the container is full. We have a dichotomy. If the container is full, we take the so-called slow path, else we take the fast lane.

push_back_slow_path(value)

In this case, we would like to grow our container; we allocate more memory, than what the container currently holds. We leave the memory uninitialized. Memory allocation, can of course, fail.

We then add the new value at the index m_size. Appending the new element may fail.

We copy/move construct the existing elements of the container from the old storage to the new block of storage.

If all three steps were successful, we deallocate the old storage and return it back before replacing the values in the member variables m_data, m_size and m_capacity.

If either of the last couple of steps fail, we free the newly obtained block of storage.

push_back_fast_path(value)

In this case, we simply copy/move construct value at the end of the container and update the size of the container.

Edge-case

Consider the following edge-case, where the value to be added is an element of the vector itself. If there is a reallocation, then the elements of the container are relocated to a new region. So, value might become a dangling reference.

dev::vector<int> vec{ 1 };
for (int i = 0; i < 10; ++i) {
    vec.push_back(vec.back());
    EXPECT_EQ(vec.back(), 1);
}

Our design takes care of this edge case.

template<typename U>
void push_back_slow_path(U&& value){
    // allocate more memory
    size_type offset = size();
    size_type new_size = m_size + 1;
    size_type new_capacity = growth_factor * capacity();
    auto ptr_new_blk = allocate_helper(new_capacity);

    try{
        // Copy-construct the new value at the index m_size
        std::construct_at(ptr_new_blk + m_size, value);
    }catch(std::exception& ex){
        deallocate_helper(ptr_new_blk);
        throw ex;   // rethrow                
    }
    
    try{
        // copy/move construct the existing elements 
        // of the container from the old storage 
        // to the new block of storage.
        copy_old_storage_to_new(m_data, m_size, ptr_new_blk);
    }catch(std::exception& ex){
        std::destroy_at(ptr_new_blk + m_size);
        deallocate_helper(ptr_new_blk);
        throw ex;   // rethrow
    }

    // deallocate the old storage, if we are here
    deallocate_helper(m_data);

    m_data = ptr_new_blk;
    ++m_size;
    m_capacity = new_capacity;
}

template<typename U>
void push_back_fast_path(U&& value){
    std::construct_at(m_data + m_size, value);
    ++m_size;
}        

template<typename U>
void push_back(U&& value)
{
    if(is_full())
    {
        push_back_slow_path(std::forward<U>(value));
    }
    else{
        push_back_fast_path(std::forward<U>(value));
    }
}

Coding up emplace_back

Again we have a fork - emplace_back_slow_path and emplace_back_fast_path.

template<typename... Args>
reference emplace_back_slow_path(Args... args){
    // allocate more memory
    size_type offset = size();
    size_type new_size = m_size + 1;
    size_type new_capacity = growth_factor * capacity();
    auto ptr_new_blk = allocate_helper(new_capacity);

    try{
        // copy/move construct the existing elements 
        // of the container from the old storage 
        // to the new block of storage.
        copy_old_storage_to_new(m_data, m_size, ptr_new_blk);
    }catch(std::exception& ex){
        deallocate_helper(ptr_new_blk);
        throw ex;   // rethrow
    }

    std::construct_at(ptr_new_blk + m_size, std::forward<Args>(args)...);
    deallocate_helper(m_data);
    m_data = ptr_new_blk;
    ++m_size;
    return back();
}

template<typename... Args>
reference emplace_back_fast_path(Args... args){
    std::construct_at(m_data + m_size, std::forward<Args>(args)...);
    ++m_size;
    return back();
}

template<typename... Args>
reference emplace_back(Args... args){
    if(is_full())
        return emplace_back_slow_path(std::forward<Args>(args)...);
    else
        return emplace_back_fast_path(std::forward<Args>(args)...);
}

Implementing pop_back()

pop_back() should call the destructor of the element at index m_size - 1. std::destroy_at(T* p) calls the destructor of the object pointed to by p. It is equivalent to p->~T(). We must not forget to decrement the size of the container.

void pop_back() {
    T* ptr_to_last = m_data + m_size - 1;
    std::destroy_at(ptr_to_last);
    --m_size;
}

Implementing insert(const_iterator position, It first, It last)

The insert function inserts the given value into the vector before the specified position, possibly using move-semantics. Note that, this kind of operation could be expensive for a vector, and if it is frequently used, it can trigger reallocation.

Our insert function will be generic enough with the following interface:

template<class It>
iterator insert(const_iterator pos, It first, It last)

It inserts the range [first,last) at position pos (immediately prior to element currently at pos).

I spent some time thinking about .insert, and drawing some quick diagrams helped me generalize the algorithm.

Step 1. We first determine if the elements in the range [first,last) can fit into the remaining_capacity = capacity() - size(). If n exceeds the remaining_capacity, the excess_capacity_reqd we require is std::max(n - remaining_capacity,0). So, we invoke reserve(capacity() + excess_capacity_reqd).

Step 2. Assume that we have sufficient room for the range [first,last).

How many elements should be copied from the [begin(), end()) sequqence to the raw memory block at the end of the container?

Consider the scenario, where the range [first,last) is smaller than [pos,end).

In this scenario, the elements [end()-n, end()) need to be copied or moved to the uninitialized memory.

If there are elements to copy or move from [pos,end()) sequence as a replacement to existing objects in the container(there could be none), how many should be there? Looking at the figure below, the subsequence [pos, end() - n) will be mapped to [pos + n, end()) upon insertion.

Consider the scenario, where the range [first,last) is larger than [pos,end).

In this case, let’s define num_tail as the trailing number of elements from the source range [first,last) that would be copied/moved to uninitialized memory. Clearly, num_tail = std::max(n - end() + pos,0). So, the tail [last-num_tail,last) will be mapped to [end(),end()+num_tail) upon insertion.

To make room for the insertion, the elements [pos,end()) will have to be moved to [end() + num_tail, end() + num_tail + end() - pos).

Here is a possible implementation based on our ideas above:

template<typename It>
iterator insert(const_iterator pos, It first, It last){
    auto pos_ = const_cast<iterator>(pos);
    auto first_ = first;
    auto last_ = last;

    if(first != last)
    {
        size_type offset = std::distance(begin(), pos_);
        size_type n = std::distance(first, last);
        size_type num_elems_to_shift = std::distance(pos_, end());
        size_type remaining_capacity = capacity() - size();
        
        dev::vector<T> temp;
        // handle self-referential insertion
        if((first_ >= begin() && first_ < end()) 
        && last_ > begin() && last_ <= end())
        {
            for(auto it{first_}; it!=last_; ++it)
                temp.push_back(*it);

            first_ = temp.begin();
            last_ = temp.end();
        }

        if(n > remaining_capacity)
        {
            size_type excess_capacity_reqd = std::max(n - remaining_capacity, 0uz);
            reserve(capacity() + excess_capacity_reqd);
            // The iterator pos is invalidated. Update it.
            pos_ = std::next(begin(), offset);
        }

        // objects to displace (move or copy) from the 
        // [begin, end()] sequence into raw uninitialized
        // memory 
        if(n < num_elems_to_shift)
        {
            if constexpr(std::is_nothrow_move_constructible_v<T>)
            {
                std::uninitialized_move(end() - n, end(), end());
            }
            else
            {
                std::uninitialized_copy(end() - n, end(), end());
            }

        }else{
            size_type num_tail = std::max(n - num_elems_to_shift, 0uz);
            if constexpr(std::is_nothrow_move_constructible_v<T>)
            {
                std::uninitialized_move(pos_, end(), end() + num_tail);
            }
            else
            {
                std::uninitialized_copy(pos_, end(), end() + num_tail);
            }
        }

        // objects to displace (copy or move) from [pos,end()]
        // to the end of the container
        if(n < num_elems_to_shift)
        {
            if constexpr(std::is_nothrow_move_constructible_v<T>)
            {
                std::move_backward(pos_, end() - n, end());
            }
            else
            {
                std::copy_backward(pos_, end() - n, end());
            }
        }

        // objects from [first,last) to insert into raw
        // uninitialized memory
        const size_type num_tail = std::max(n - num_elems_to_shift, 0uz);
        if(n >= num_elems_to_shift)
        {
            if constexpr(std::is_nothrow_move_constructible_v<T>)
            {
                std::uninitialized_move(last_ - num_tail, last_, end());
            }
            else
            {
                std::uninitialized_copy(last_ - num_tail, last_, end());
            }
        }
        
        // objects to copy from [first,last) to pos
        if(n < num_elems_to_shift)
        {
            std::copy(first_, last_, pos_);
        }
        else{
            std::copy(first_, first_ + n - num_tail, pos_);
        }

        m_size += n;
    }
    return pos_;
}

Conclusion

Implementing a custom vector<T> from scratch is a rewarding exercise that deepens understanding of C++ fundamentals.

The standard library implementation handles additional complexities I haven’t addressed: custom allocator support, small object optimizations, and numerous other edge cases discovered through decades of production use.

However, the journey of building this container teaches invaluable lessons. You learn to think carefully about exception safety, understand the tradeoffs between copy and move operations, appreciate the elegance of algorithms like std::uninitialized_copy, and recognize why seemingly simple operations like insert() require careful reasoning about memory layout and iterator invalidation.

If you enjoyed this deep dive, I recommend exploring deque, std::inplace_vector, or the more complex associative containers. Each presents unique challenges and design decisions that will further sharpen your C++ skills.

You can find the complete source listing and unit tests online at https://compiler-explorer.com/z/Tvbs5Wc73.

References