Introduction

In interviews, you might be asked how to implement a vector. This requires understanding the underlying implementation of vector. Before that, you need to learn about dynamic memory management, especially allocators, which are explained in the C++ Primer book.

Basic Contents to Implement

On the cplusplus website, common usages are as follows: Member functions (Constructor) Construct vector (public member function) (Destructor) Vector destructor (public member function)

Iterators: begin Return iterator to beginning (public member function) end Return iterator to end (public member function)

Capacity: size Return size (public member function)

Element access: operator[] Access element (public member function) at Access element (public member function)

Modifiers: push_back Add element at the end (public member function) pop_back Delete last element (public member function)

Main Structure of a Basic Vector

#include <cstddef>
#include <stdexcept>
#include <memory>
#include <iterator>

template <typename T>
class vector
{
  public:
    using value_type = T;
    using iterator = value_type *;
    using size_type = std::size_t;

  public:
    vector() = default;
    ~vector();
    iterator begin() const;
    iterator end() const;
    size_type size() const;
    value_type &operator[](size_type i) const;
    value_type &at(size_type i) const;
    void push_back(const value_type &new_elem);
    void pop_back();

  private:
    iterator startptr = nullptr;
    iterator endptr = nullptr;
    iterator capptr = nullptr;
    std::allocator<value_type> alloc;

  private:
    void check_cap();
    void free();
};

In our class, we’ve simply implemented iterators, push_back, pop_back, as well as the [] operator, at function, and size function. To implement memory management, we also need to implement constructors, destructors, and capacity checking functions.

Internal Implementation of Basic Functions

template <typename T>
typename vector<T>::iterator vector<T>::begin() const
{
    return startptr;
}

template <typename T>
typename vector<T>::iterator vector<T>::end() const
{
    return endptr;
}

template <typename T>
typename vector<T>::size_type vector<T>::size() const
{
    return endptr - startptr;
}

template <typename T>
typename vector<T>::value_type &vector<T>::operator[](size_type i) const
{
    return *(startptr + i);
}

template <typename T>
typename vector<T>::value_type &vector<T>::at(size_type i) const
{
    if (startptr + i >= endptr)
    {
        throw std::runtime_error("out of range!");
    }
    return *(startptr + i);
}

template <typename T>
vector<T>::~vector()
{
    free();
}

The above are implementations of simple functions. They simply retrieve internal data.

template <typename T>
void vector<T>::free()
{
    if (startptr)
    {
        for (auto p = startptr; p != endptr; p++)
        {
            alloc.destroy(p);
        }
        alloc.deallocate(startptr, endptr - startptr);
    }
}

template <typename T>
void vector<T>::check_cap()
{
    if (endptr == capptr)
    {
        int newsize = size() ? size() << 1 : 1;
        auto newstartptr = alloc.allocate(newsize);
        auto newendptr = uninitialized_copy(std::make_move_iterator(startptr), std::make_move_iterator(endptr), newstartptr);
        free();
        startptr = newstartptr;
        endptr = newendptr;
        capptr = newstartptr + newsize;
    }
}

template <typename T>
void vector<T>::push_back(const value_type &new_elem)
{
    check_cap();
    alloc.construct(endptr, new_elem);
    endptr++;
}

template <typename T> 
void vector<T>::pop_back()
{
    if(endptr-startptr>0){
        alloc.destroy(endptr);
        endptr--;
    }
}

This part deals with memory and uses allocator to manage memory. The constructor separates the allocation of space and construction, dividing the process into allocating space, reclaiming space, destruction, and construction. The capacity check involves these four scenarios: first allocate new space, then construct new elements in the new position, then destruct old elements, and release old space. The free function is used to destruct old elements and release old space. Here, uninitialized_copy function and make_move_iterator, move iterators, and uninitialized copy functions are used to construct new elements in new positions, aiming to speed up the construction of new elements.

Advanced Functions and Implementation

erase

Next, let’s implement some additional functions. Let’s start with erase. Erase deletes all content from the specified position to the specified position. The function prototype is as follows:

  public:
    iterator erase(const_iterator position);
    iterator erase(const_iterator first, const_iterator last);

The first function can also be seen as simply calling the second function. We implement the second function as follows:

template <typename T>
typename vector<T>::iterator vector<T>::erase(const_iterator first, const_iterator last)
{
    if(last >= endptr || first < startptr) throw std::runtime_error("out of range!");
    iterator newendptr = std::copy(last, static_cast<const_iterator>(endptr), first);
    while(newendptr < endptr){
        alloc.destroy(--endptr);
    }
    return endptr;
}

First, perform a validity check. Then, use std::copy to copy the later content to the part to be deleted. Note that the copy will automatically call the assignment function for the part being overwritten, and the assignment function should call the destructor internally. Then, if there is still content that needs to be destructed (this occurs only when the moved content is not as long as the deleted content), destruct that content. Then return the end pointer.

The other overloaded function is relatively simple to implement:

template<typename T>
typename vector<T>::iterator vector<T>::erase(const_iterator position)
{
    return erase(position, position+1);
}