C++ STL笔记04-std::vector动态数组

动手实现C++ STL容器。本节介绍std::vector的常见用法和实现。

std::vector用法

std::vector是C++标准库中的一个容器，用于动态数组的实现。std::vector的特点如下：

顺序序列：容器中的元素按照严格的线性顺序排序，可以通过元素在序列中的位置访问对应的元素；
动态数组：支持对序列中的任意元素进行快速直接访问，甚至可以通过指针算述进行该操作；提供了在序列末尾相对快速地添加/删除元素的操作；
内存分配器：可以使用一个内存分配器对象来动态地处理它的存储需求。

std::vector有非常丰富的成员函数，这里只展示一些比较常见的用法：

#include <iostream>
#include <vector>

int main()
{
    // 初始化 vector
    std::vector<int> myVector = {1, 2, 3, 4, 5};
    
    // 获取 vector 大小：
    std::cout << "Vector size: " << myVector.size() << std::endl;
    
    // 访问元素
    std::cout << "First element: " << myVector[0] << std::endl;
    
    // 迭代 vector
    for (size_t i=0; i<myVector.size(); ++i) {
        std::cout << myVector[i] << " ";
    }
    
    std::cout << std::endl;
    
    // range-based for循环
    for (int x : myVector) {
        std::cout << x << " ";
    }
    
    std::cout << std::endl;
    
    // 在末尾添加元素
    std::cout << "Add 6 to the end: ";
    myVector.push_back(6);
    
    for (int x : myVector) {
        std::cout << x << " ";
    }
    
    std::cout << std::endl;
    
    // 在指定位置插入元素
    std::cout << "Insert 10 to myVector[2]: ";
    myVector.insert(myVector.begin() + 2, 10);
    
    for (int x : myVector) {
        std::cout << x << " ";
    }
    
    std::cout << std::endl;
    
    // 删除元素
    std::cout << "Remove myVector[3]: ";
    myVector.erase(myVector.begin() + 3);
    
    for (int x : myVector) {
        std::cout << x << " ";
    }
    
    std::cout << std::endl;
    

    return 0;
}

运行上面的代码可以得到如下结果：

Vector size: 5
First element: 1
1 2 3 4 5 
1 2 3 4 5 
Add 6 to the end: 1 2 3 4 5 6 
Insert 10 to myVector[2]: 1 2 10 3 4 5 6 
Remove myVector[3]: 1 2 10 4 5 6 

std::vector的其它成员函数及其用法可以参考官方文档。

Vector实现

接下来我们从零开始实现一个类似于标准库中std::vector的动态数组Vector。

模板定义

Vector包含两个模板参数：元素类型T以及内存分配器Alloc。这里Alloc用来管理Vector持有的内存，在大多数情况下使用标准库中的std::allocator即可。除此之外，Vector还需要几个额外的成员变量：

m_data用来指向容器的起点；
m_size用来记录当前数组的大小；
m_cap用来记录容器的容量；
m_alloc用来保存内存分配器Alloc。

template <class T, class Alloc = std::allocator<T>>
struct Vector {
    T *m_data;
    size_t m_size;
    size_t m_cap;
    [[no_unique_address]] Alloc m_alloc;
}

构造函数

默认构造函数

Vector有各种不同的构造函数用来处理相应的情况。首先是默认构造函数，此时需要将数组初始化为一个空数组，即m_data为空指针并且数组的大小和容量均为0。

template <class T, class Alloc = std::allocator<T>>
struct Vector {
    ...
    Vector() noexcept {
        m_data = nullptr;
        m_size = 0;
        m_cap  = 0;
    }
}

参数化构造函数

另一种常见使用情况是将Vector初始化一个大小为n的数组，此时我们需要把数组的大小和容量都初始化为n并且对前n个元素进行默认初始化。由于我们使用了m_alloc来管理内存，申请内存的过程需要通过m_alloc来进行实现。

template <class T, class Alloc = std::allocator<T>>
struct Vector {
    ...
    explicit Vector(size_t n, Alloc const &alloc = Alloc()) : m_alloc(alloc) {
        m_data = m_alloc.allocate(n);
        m_cap = m_size = n;

        for (size_t i = 0; i != n; i++) {
            std::construct_at(&m_data[i]); // m_data[i] = 0
        }
    }
}

注意这里使用了std::construct_at来初始化m_data中的元素。此时它会调用T类型的默认构造函数来进行初始化，从而避免直接使用new来分配内存和调用构造函数时产生的不必要开销。

与之类似的一种情况是使用val来初始化数组，这里需要在调用std::construct_at时把val作为构造函数的参数传进来。

template <class T, class Alloc = std::allocator<T>>
struct Vector {
    ...
    Vector(size_t n, T const &val, Alloc const &alloc = Alloc()) : m_alloc(alloc) {
        m_data = m_alloc.allocate(n);
        m_cap = m_size = n;

        for (size_t i = 0; i != n; i++) {
            std::construct_at(&m_data[i], val); // m_data[i] = val
        }
    }
}

除此之外还可以使用迭代器来初始化Vector。对于这种情况我们需要先计算出迭代器的大小n，然后使用迭代器的元素来初始化数组。

template <class T, class Alloc = std::allocator<T>>
struct Vector {
    ...
    template <std::random_access_iterator InputIt>
    Vector(InputIt first, InputIt last, Alloc const &alloc = Alloc()) : m_alloc(alloc) {
        size_t n = last - first;
        m_data = m_alloc.allocate(n);
        m_cap = m_size = n;

        for (size_t i = 0; i != n; i++) {
            std::construct_at(&m_data[i], *first);
            ++first;
        }
    }
}

在此基础上可以通过初始化列表std::initializer_list来进行初始化。

template <class T, class Alloc = std::allocator<T>>
struct Vector {
    ...
    Vector(std::initializer_list<T> ilist, Alloc const &alloc = Alloc())
    : Vector(ilist.begin(), ilist.end(), alloc) {}
}

移动构造函数

当我们已有一个Vector对象时可以使用已有的Vector来初始化一个新的对象。这里我们先实现移动构造函数，这里需要注意在移动构造函数的最后将已有的对象清空。

template <class T, class Alloc = std::allocator<T>>
struct Vector {
    ...
    Vector(Vector &&that) noexcept : m_alloc(std::move(that.m_alloc)) {
        m_data = that.m_data;
        m_size = that.m_size;
        m_cap  = that.m_cap;

        that.m_data = nullptr;
        that.m_size = 0;
        that.m_cap  = 0;
    }

    Vector(Vector &&that, Alloc const &alloc) noexcept : m_alloc(alloc) {
        m_data = that.m_data;
        m_size = that.m_size;
        m_cap  = that.m_cap;

        that.m_data = nullptr;
        that.m_size = 0;
        that.m_cap  = 0;
    }

    Vector &operator=(Vector &&that) noexcept {
        if (&that == this) [[unlikely]] return *this;

        for (size_t i = 0; i != m_size; i++) {
            std::destroy_at(&m_data[i]);
        }

        if (m_cap != 0) {
            m_alloc.deallocate(m_data, m_cap);
        }

        m_data = that.m_data;
        m_size = that.m_size;
        m_cap  = that.m_cap;

        that.m_data = nullptr;
        that.m_size = 0;
        that.m_cap  = 0;

        return *this;
    }
}

拷贝构造函数

拷贝构造与移动构造类似，不过不需要销毁that对象。

template <class T, class Alloc = std::allocator<T>>
struct Vector {
    ...
    Vector(Vector const &that) : m_alloc(that.m_alloc) {
        m_cap = m_size = that.m_size;

        if (m_size != 0) {
            m_data = m_alloc.allocate(m_size);

            for (size_t i = 0; i != m_size; i++) {
                std::construct_at(&m_data[i], std::as_const(that.m_data[i]));
            }
        } else {
            m_data = nullptr;
        }
    }

    Vector(Vector const &that, Alloc const &alloc) : m_alloc(alloc) {
        m_cap = m_size = that.m_size;

        if (m_size != 0) {
            m_data = m_alloc.allocate(m_size);

            for (size_t i = 0; i != m_size; i++) {
                std::construct_at(&m_data[i], std::as_const(that.m_data[i]));
            }
        } else {
            m_data = nullptr;
        }
    }

    Vector &operator=(Vector const &that) {
        if (&that == this) [[unlikely]] return *this;

        reserve(that.m_size);
        m_size = that.m_size;

        for (size_t i = 0; i != m_size; i++) {
            std::construct_at(&m_data[i], std::as_const(that.m_data[i]));
        }

        return *this;
    }
}

最后我们来实现一下析构函数。Vector的析构函数比较简单，我们需要先逐个析构数组中的元素，然后利用m_alloc释放内存空间。

template <class T, class Alloc = std::allocator<T>>
struct Vector {
    ...
    ~Vector() noexcept {
        for (size_t i = 0; i != m_size; i++) {
            std::destroy_at(&m_data[i]);
        }

        if (m_cap != 0) {
            m_alloc.deallocate(m_data, m_cap);
        }
    }
}

访问元素

Vector允许通过[]运算符对数组中的元素进行访问。

template <class T, class Alloc = std::allocator<T>>
struct Vector {
    ...
    T const &operator[](size_t i) const noexcept {
        return m_data[i];
    }

    T &operator[](size_t i) noexcept {
        return m_data[i];
    }
}

当然更安全的访问方式是使用at()函数，它会在获取元素之前先判断是否越界。

template <class T, class Alloc = std::allocator<T>>
struct Vector {
    ...
    T const &at(size_t i) const {
        if (i >= m_size) [[unlikely]] throw std::out_of_range("vector::at");
        return m_data[i];
    }

    T &at(size_t i) {
        if (i >= m_size) [[unlikely]] throw std::out_of_range("vector::at");
        return m_data[i];
    }
}

除此之外，Vector还提供了front()和back()函数方便获取数组的首尾元素。

template <class T, class Alloc = std::allocator<T>>
struct Vector {
    ...
    T const &front() const noexcept {
        return *m_data;
    }

    T &front() noexcept {
        return *m_data;
    }

    T const &back() const noexcept {
        return m_data[m_size - 1];
    }

    T &back() noexcept {
        return m_data[m_size - 1];
    }
}

修改数组大小

Vector作为动态数组需要允许用户修改数组的大小。这里我们先实现一个clear()函数用来清空数组，需要注意的是clear()函数会析构数组中的元素但不会释放数组占用的内存。

template <class T, class Alloc = std::allocator<T>>
struct Vector {
    ...
    void clear() noexcept {
        for (size_t i = 0; i != m_size; i++) {
            std::destroy_at(&m_data[i]);
        }

        m_size = 0;
    }
}

如果用户想要释放掉多余的内存则可以使用shrink_to_fit()函数将容器的容量减小到与其大小相匹配。

template <class T, class Alloc = std::allocator<T>>
struct Vector {
    ...
    void shrink_to_fit() noexcept {
        auto old_data = m_data;
        auto old_cap  = m_cap;

        m_cap = m_size;
        if (m_size == 0) {
            m_data = nullptr;
        } else {
            m_data = m_alloc.allocate(m_size);
        }

        if (old_cap != 0) [[likely]] {
            for (size_t i = 0; i != m_size; i++) {
                std::construct_at(&m_data[i], std::move_if_noexcept(old_data[i])); // m_data[i] = std::move(old_data[i])
                std::destroy_at(&old_data[i]);
            }

            m_alloc.deallocate(old_data, old_cap);
        }
    }
}

另一种常见的情况是预先申请一部分内存以便后续对数组进行操作，此时则需要利用reserve()函数。它会将数组的容量扩充至n，从而预留出足够的空间。

template <class T, class Alloc = std::allocator<T>>
struct Vector {
    ...
    void reserve(size_t n) {
        if (n <= m_cap) return;
        n = std::max(n, m_cap * 2);

        auto old_data = m_data;
        auto old_cap  = m_cap;

        if (n == 0) {
            m_data = nullptr;
            m_cap  = 0;
        } else {
            m_data = m_alloc.allocate(n);
            m_cap  = n;
        }

        if (old_cap != 0) {
            for (size_t i = 0; i != m_size; i++) {
                std::construct_at(&m_data[i], std::move_if_noexcept(old_data[i]));
            }

            for (size_t i = 0; i != m_size; i++) {
                std::destroy_at(&old_data[i]);
            }

            m_alloc.deallocate(old_data, old_cap);
        }
    }
}

在此基础上我们就可以实现resize()函数，它会根据参数n的大小来修改数组。当n小于数组大小m_size时截断多出来的部分；而当n大于m_size时利用reserve()函数申请足够的空间。

template <class T, class Alloc = std::allocator<T>>
struct Vector {
    ...
    void resize(size_t n) {
        if (n < m_size) {
            for (size_t i = n; i != m_size; i++) {
                std::destroy_at(&m_data[i]);
            }
            m_size = n;
        } else if (n > m_size) {
            reserve(n);
            for (size_t i = m_size; i != n; i++) {
                std::construct_at(&m_data[i]); // m_data[i] = 0
            }
        }

        m_size = n;
    }

    void resize(size_t n, T const &val) {
        if (n < m_size) {
            for (size_t i = n; i != m_size; i++) {
                std::destroy_at(&m_data[i]);
            }
            m_size = n;
        } else if (n > m_size) {
            reserve(n);
            for (size_t i = m_size; i != n; i++) {
                std::construct_at(&m_data[i], val); // m_data[i] = val
            }
        }

        m_size = n;
    }
}

迭代器

Vector需要支持迭代器接口。这里我们参考Array中的实现来实现相关的接口。

template <class T, class Alloc = std::allocator<T>>
struct Vector {
    using value_type      = T;
    using allocator_type  = Alloc;
    using size_type       = size_t;
    using difference_type = ptrdiff_t;
    using pointer         = T *;
    using const_pointer   = T const *;
    using reference       = T &;
    using const_reference = T const &;
    using iterator        = T *;
    using const_iterator  = T const *;

    using reverse_iterator       = std::reverse_iterator<T *>;
    using const_reverse_iterator = std::reverse_iterator<T const *>;
    ...
    T *data() noexcept {
        return m_data;
    }

    T const *data() const noexcept {
        return m_data;
    }

    T const *cdata() const noexcept {
        return m_data;
    }

    T *begin() noexcept {
        return m_data;
    }

    T *end() noexcept {
        return m_data + m_size;
    }

    T const *begin() const noexcept {
        return m_data;
    }

    T const *end() const noexcept {
        return m_data + m_size;
    }

    T const *cbegin() const noexcept {
        return m_data;
    }

    T const *cend() const noexcept {
        return m_data + m_size;
    }

    std::reverse_iterator<T *> rbegin() noexcept {
        return std::make_reverse_iterator(m_data + m_size);
    }

    std::reverse_iterator<T *> rend() noexcept {
        return std::make_reverse_iterator(m_data);
    }

    std::reverse_iterator<T const *> rbegin() const noexcept {
        return std::make_reverse_iterator(m_data + m_size);
    }

    std::reverse_iterator<T const *> rend() const noexcept {
        return std::make_reverse_iterator(m_data);
    }

    std::reverse_iterator<T const *> crbegin() const noexcept {
        return std::make_reverse_iterator(m_data + m_size);
    }

    std::reverse_iterator<T const *> crend() const noexcept {
        return std::make_reverse_iterator(m_data);
    }
}

修改数组

assign()

assign()函数会首先清空数组，然后将数组的前n个元素设置为val。

template <class T, class Alloc = std::allocator<T>>
struct Vector {
    ...
    void assign(size_t n, T const &val) {
        clear();
        reserve(n);

        m_size = n;
        for (size_t i = 0; i != n; i++) {
            std::construct_at(&m_data[i], val);
        }
    }
}

类似于参数化构造函数，这里还实现了几个不同的版本以便处理迭代器和初始化列表做参数的情况。

template <class T, class Alloc = std::allocator<T>>
struct Vector {
    ...
    template <std::random_access_iterator InputIt>
    void assign(InputIt first, InputIt last) {
        clear();

        size_t n = last - first;
        reserve(n);

        m_size = n;
        for (size_t i = 0; i != n; i++) {
            std::construct_at(m_data[i], *first);
            ++first;
        }
    }

    void assign(std::initializer_list<T> ilist) {
        assign(ilist.begin(), ilist.end());
    }

    Vector &operator=(std::initializer_list<T> ilist) {
        assign(ilist.begin(), ilist.end());
    }
}

push_back()

push_back()函数会向数组的末尾添加一个新的元素。

template <class T, class Alloc = std::allocator<T>>
struct Vector {
    ...
    void push_back(T const &val) {
        if (m_size + 1 >= m_cap) [[unlikely]] reserve(m_size + 1);
        std::construct_at(&m_data[m_size], val);
        m_size = m_size + 1;
    }

    void push_back(T &&val) {
        if (m_size + 1 >= m_cap) [[unlikely]] reserve(m_size + 1);
        std::construct_at(&m_data[m_size], std::move(val));
        m_size = m_size + 1;
    }
}

emplace_back()

emplace_back()类似于push_back()同样可以向数组末尾添加元素。不过emplace_back()函数接收的是T类型的构造参数，然后直接在数组的末尾利用这些参数构造新的元素，最后返回这个新元素的引用。这里我们使用带变长参数的函数模板来实现它。

template <class T, class Alloc = std::allocator<T>>
struct Vector {
    ...
    template <class ...Args>
    T &emplace_back(Args &&...args) {
        if (m_size + 1 >= m_cap) [[unlikely]] reserve(m_size + 1);

        T *p = &m_data[m_size];
        std::construct_at(p, std::forward<Args>(args)...);
        m_size = m_size + 1;

        return *p;
    }
}

pop_back()

pop_back()函数会销毁数组的末尾元素。

template <class T, class Alloc = std::allocator<T>>
struct Vector {
    ...
    void pop_back() noexcept {
        m_size -= 1;
        std::destroy_at(&m_data[m_size]);
    }
}

erase()

erase()函数会利用it指针清除该位置上的元素，并返回数组更新后指向同一位置的指针。

template <class T, class Alloc = std::allocator<T>>
struct Vector {
    ...
    T *erase(T const *it) noexcept(std::is_nothrow_move_assignable_v<T>) {
        size_t i = it - m_data;
        for (size_t j = i + 1; j != m_size; j++) {
            m_data[j - 1] = std::move(m_data[j]);
        }

        m_size -= 1;
        std::destroy_at(&m_data[m_size]);

        return const_cast<T *>(it);
    }
}

除此之外我们还可以实现一个针对迭代器的版本，它会清除first到last之间的所有元素并返回first位置的指针。

template <class T, class Alloc = std::allocator<T>>
struct Vector {
    ...
    T *erase(T const *first, T const *last) noexcept(std::is_nothrow_move_assignable_v<T>) {
        size_t diff = last - first;
        for (size_t j = last - m_data; j != m_size; j++) {
            m_data[j - diff] = std::move(m_data[j]);
        }

        m_size -= diff;
        for (size_t j = m_size; j != m_size + diff; j++) {
            std::destroy_at(&m_data[j]);
        }

        return const_cast<T *>(first);
    }
}

insert()

insert()函数会在指针it的位置添加一个新的对象val，并把后面的对象进行顺延。

template <class T, class Alloc = std::allocator<T>>
struct Vector {
    ...
    T *insert(T const *it, T &&val) {
        size_t j = it - m_data;
        reserve(m_size + 1);
        // j ~ m_size => j + 1 ~ m_size + 1
        for (size_t i = m_size; i != j; i--) {
            std::construct_at(&m_data[i], std::move(m_data[i - 1]));
            std::destroy_at(&m_data[i - 1]);
        }

        m_size += 1;
        std::construct_at(&m_data[j], std::move(val));

        return m_data + j;
    }

    T *insert(T const *it, T const &val) {
        size_t j = it - m_data;
        reserve(m_size + 1);
        // j ~ m_size => j + 1 ~ m_size + 1
        for (size_t i = m_size; i != j; i--) {
            std::construct_at(&m_data[i], std::move(m_data[i - 1]));
            std::destroy_at(&m_data[i - 1]);
        }

        m_size += 1;
        std::construct_at(&m_data[j], val);

        return m_data + j;
    }
}

在此基础上，我们可以再实现一个重载版本的insert()函数在it后面添加n个元素。

template <class T, class Alloc = std::allocator<T>>
struct Vector {
    ...
    T *insert(T const *it, size_t n, T const &val) {
        size_t j = it - m_data;
        if (n == 0) [[unlikely]] return const_cast<T *>(it);

        reserve(m_size + n);
        // j ~ m_size => j + n ~ m_size + n
        for (size_t i = m_size; i != j; i--) {
            std::construct_at(&m_data[i + n - 1], std::move(m_data[i - 1]));
            std::destroy_at(&m_data[i - 1]);
        }

        m_size += n;
        for (size_t i = j; i != j + n; i++) {
            std::construct_at(&m_data[i], val);
        }

        return m_data + j;
    }
}

除此之外，我们还可以实现针对迭代器的版本将first到last之间的元素插入到it位置。

template <class T, class Alloc = std::allocator<T>>
struct Vector {
    ...
    template <std::random_access_iterator InputIt>
    T *insert(T const *it, InputIt first, InputIt last) {
        size_t j = it - m_data;
        size_t n = last - first;

        if (n == 0) [[unlikely]] return const_cast<T *>(it);

        reserve(m_size + n);
        // j ~ m_size => j + n ~ m_size + n
        for (size_t i = m_size; i != j; i--) {
            std::construct_at(&m_data[i + n - 1], std::move(m_data[i - 1]));
            std::destroy_at(&m_data[i - 1]);
        }

        m_size += n;
        for (size_t i = j; i != j + n; i++) {
            std::construct_at(&m_data[i], *first);
            ++first;
        }

        return m_data + j;
    }

    T *insert(T const *it, std::initializer_list<T> ilist) {
        return insert(it, ilist.begin(), ilist.end());
    }
}

emplace()

emplace()函数会在指针it的位置添加一个新的元素。不同于insert()函数，emplace()会接收T类型的构造参数来直接在数组末尾构造出新的对象。

template <class T, class Alloc = std::allocator<T>>
struct Vector {
    ...
    template <class ...Args>
    T *emplace(T const *it, Args &&...args) {
        size_t j = it - m_data;
        reserve(m_size + 1);
        // j ~ m_size => j + 1 ~ m_size + 1
        for (size_t i = m_size; i != j; i--) {
            std::construct_at(&m_data[i], std::move(m_data[i - 1]));
            std::destroy_at(&m_data[i - 1]);
        }

        m_size += 1;
        std::construct_at(&m_data[j], std::forward<Args>(args)...);

        return m_data + j;
    }
}

其它函数

Vector中有很多获取内部信息的成员函数。这些成员函数的实现都比较简单，这里总结如下：

template <class T, class Alloc = std::allocator<T>>
struct Vector {
    ...
    size_t capacity() const noexcept {
        return m_cap;
    }

    size_t size() const noexcept {
        return m_size;
    }

    bool empty() const noexcept {
        return m_size == 0;
    }

    static constexpr size_t max_size() noexcept {
        return std::numeric_limits<size_t>::max() / sizeof(T);
    }

    Alloc get_allocator() const noexcept {
        return m_alloc;
    }
}

Vector的swap()函数可以交换两个Vector数组内的元素。

template <class T, class Alloc = std::allocator<T>>
struct Vector {
    ...
    void swap(Vector &that) noexcept {
        std::swap(m_data,  that.m_data);
        std::swap(m_size,  that.m_size);
        std::swap(m_cap,   that.m_cap);
        std::swap(m_alloc, that.m_alloc);
    }
}

不同Vector对象之间的比较我们则可以利用标准库的相关函数来实现。

template <class T, class Alloc = std::allocator<T>>
struct Vector {
    ...
    bool operator==(Vector const &that) noexcept {
        return std::equal(begin(), end(), that.begin(), that.end());
    }

    auto operator<=>(Vector const &that) noexcept {
        return std::lexicographical_compare_three_way(begin(), end(), that.begin(), that.end());
    }
}

完整实现

总结一下，整个Vector的代码可以参考如下：

#pragma once

#include <cstddef>
#include <iterator>
#include <memory>
#include <limits>
#include <stdexcept>
#include <utility>
#include <compare>
#include <initializer_list>

template <class T, class Alloc = std::allocator<T>>
struct Vector {
    using value_type = T;
    using allocator_type = Alloc;
    using size_type = size_t;
    using difference_type = ptrdiff_t;
    using pointer = T *;
    using const_pointer = T const *;
    using reference = T &;
    using const_reference = T const &;
    using iterator = T *;
    using const_iterator = T const *;
    using reverse_iterator = std::reverse_iterator<T *>;
    using const_reverse_iterator = std::reverse_iterator<T const *>;

    T *m_data;
    size_t m_size;
    size_t m_cap;
    [[no_unique_address]] Alloc m_alloc;

    Vector() noexcept {
        m_data = nullptr;
        m_size = 0;
        m_cap = 0;
    }

    Vector(std::initializer_list<T> ilist, Alloc const &alloc = Alloc())
    : Vector(ilist.begin(), ilist.end(), alloc) {}

    explicit Vector(size_t n, Alloc const &alloc = Alloc()) : m_alloc(alloc) {
        m_data = m_alloc.allocate(n);
        m_cap = m_size = n;
        for (size_t i = 0; i != n; i++) {
            std::construct_at(&m_data[i]); // m_data[i] = 0
        }
    }

    Vector(size_t n, T const &val, Alloc const &alloc = Alloc()) : m_alloc(alloc) {
        m_data = m_alloc.allocate(n);
        m_cap = m_size = n;
        for (size_t i = 0; i != n; i++) {
            std::construct_at(&m_data[i], val); // m_data[i] = val
        }
    }

    template <std::random_access_iterator InputIt>
    Vector(InputIt first, InputIt last, Alloc const &alloc = Alloc()) : m_alloc(alloc) {
        size_t n = last - first;
        m_data = m_alloc.allocate(n);
        m_cap = m_size = n;
        for (size_t i = 0; i != n; i++) {
            std::construct_at(&m_data[i], *first);
            ++first;
        }
    }

    void clear() noexcept {
        for (size_t i = 0; i != m_size; i++) {
            std::destroy_at(&m_data[i]);
        }
        m_size = 0;
    }

    void resize(size_t n) {
        if (n < m_size) {
            for (size_t i = n; i != m_size; i++) {
                std::destroy_at(&m_data[i]);
            }
            m_size = n;
        } else if (n > m_size) {
            reserve(n);
            for (size_t i = m_size; i != n; i++) {
                std::construct_at(&m_data[i]); // m_data[i] = 0
            }
        }
        m_size = n;
    }

    void resize(size_t n, T const &val) {
        if (n < m_size) {
            for (size_t i = n; i != m_size; i++) {
                std::destroy_at(&m_data[i]);
            }
            m_size = n;
        } else if (n > m_size) {
            reserve(n);
            for (size_t i = m_size; i != n; i++) {
                std::construct_at(&m_data[i], val); // m_data[i] = val
            }
        }
        m_size = n;
    }

    void shrink_to_fit() noexcept {
        auto old_data = m_data;
        auto old_cap = m_cap;
        m_cap = m_size;
        if (m_size == 0) {
            m_data = nullptr;
        } else {
            m_data = m_alloc.allocate(m_size);
        }
        if (old_cap != 0) [[likely]] {
            for (size_t i = 0; i != m_size; i++) {
                std::construct_at(&m_data[i], std::move_if_noexcept(old_data[i])); // m_data[i] = std::move(old_data[i])
                std::destroy_at(&old_data[i]);
            }
            m_alloc.deallocate(old_data, old_cap);
        }
    }

    void reserve(size_t n) {
        if (n <= m_cap) return;
        n = std::max(n, m_cap * 2);
        /* printf("grow from %zd to %zd\n", m_cap, n); */
        auto old_data = m_data;
        auto old_cap = m_cap;
        if (n == 0) {
            m_data = nullptr;
            m_cap = 0;
        } else {
            m_data = m_alloc.allocate(n);
            m_cap = n;
        }
        if (old_cap != 0) {
            for (size_t i = 0; i != m_size; i++) {
                std::construct_at(&m_data[i], std::move_if_noexcept(old_data[i]));
            }
            for (size_t i = 0; i != m_size; i++) {
                std::destroy_at(&old_data[i]);
            }
            m_alloc.deallocate(old_data, old_cap);
        }
    }

    size_t capacity() const noexcept {
        return m_cap;
    }

    size_t size() const noexcept {
        return m_size;
    }

    bool empty() const noexcept {
        return m_size == 0;
    }

    static constexpr size_t max_size() noexcept {
        return std::numeric_limits<size_t>::max() / sizeof(T);
    }

    T const &operator[](size_t i) const noexcept {
        return m_data[i];
    }

    T &operator[](size_t i) noexcept {
        return m_data[i];
    }

    T const &at(size_t i) const {
        if (i >= m_size) [[unlikely]] throw std::out_of_range("vector::at");
        return m_data[i];
    }

    T &at(size_t i) {
        if (i >= m_size) [[unlikely]] throw std::out_of_range("vector::at");
        return m_data[i];
    }

    Vector(Vector &&that) noexcept : m_alloc(std::move(that.m_alloc)) {
        m_data = that.m_data;
        m_size = that.m_size;
        m_cap = that.m_cap;
        that.m_data = nullptr;
        that.m_size = 0;
        that.m_cap = 0;
    }

    Vector(Vector &&that, Alloc const &alloc) noexcept : m_alloc(alloc) {
        m_data = that.m_data;
        m_size = that.m_size;
        m_cap = that.m_cap;
        that.m_data = nullptr;
        that.m_size = 0;
        that.m_cap = 0;
    }

    Vector &operator=(Vector &&that) noexcept {
        if (&that == this) [[unlikely]] return *this;
        for (size_t i = 0; i != m_size; i++) {
            std::destroy_at(&m_data[i]);
        }
        if (m_cap != 0) {
            m_alloc.deallocate(m_data, m_cap);
        }
        m_data = that.m_data;
        m_size = that.m_size;
        m_cap = that.m_cap;
        that.m_data = nullptr;
        that.m_size = 0;
        that.m_cap = 0;
        return *this;
    }

    void swap(Vector &that) noexcept {
        std::swap(m_data, that.m_data);
        std::swap(m_size, that.m_size);
        std::swap(m_cap, that.m_cap);
        std::swap(m_alloc, that.m_alloc);
    }

    Vector(Vector const &that) : m_alloc(that.m_alloc) {
        m_cap = m_size = that.m_size;
        if (m_size != 0) {
            m_data = m_alloc.allocate(m_size);
            for (size_t i = 0; i != m_size; i++) {
                std::construct_at(&m_data[i], std::as_const(that.m_data[i]));
            }
        } else {
            m_data = nullptr;
        }
    }

    Vector(Vector const &that, Alloc const &alloc) : m_alloc(alloc) {
        m_cap = m_size = that.m_size;
        if (m_size != 0) {
            m_data = m_alloc.allocate(m_size);
            for (size_t i = 0; i != m_size; i++) {
                std::construct_at(&m_data[i], std::as_const(that.m_data[i]));
            }
        } else {
            m_data = nullptr;
        }
    }

    Vector &operator=(Vector const &that) {
        if (&that == this) [[unlikely]] return *this;
        reserve(that.m_size);
        m_size = that.m_size;
        for (size_t i = 0; i != m_size; i++) {
            std::construct_at(&m_data[i], std::as_const(that.m_data[i]));
        }
        return *this;
    }

    T const &front() const noexcept {
        return *m_data;
    }

    T &front() noexcept {
        return *m_data;
    }

    T const &back() const noexcept {
        return m_data[m_size - 1];
    }

    T &back() noexcept {
        return m_data[m_size - 1];
    }

    void push_back(T const &val) {
        if (m_size + 1 >= m_cap) [[unlikely]] reserve(m_size + 1);
        std::construct_at(&m_data[m_size], val);
        m_size = m_size + 1;
    }

    void push_back(T &&val) {
        if (m_size + 1 >= m_cap) [[unlikely]] reserve(m_size + 1);
        std::construct_at(&m_data[m_size], std::move(val));
        m_size = m_size + 1;
    }

    template <class ...Args>
    T &emplace_back(Args &&...args) {
        if (m_size + 1 >= m_cap) [[unlikely]] reserve(m_size + 1);
        T *p = &m_data[m_size];
        std::construct_at(p, std::forward<Args>(args)...);
        m_size = m_size + 1;
        return *p;
    }

    T *data() noexcept {
        return m_data;
    }

    T const *data() const noexcept {
        return m_data;
    }

    T const *cdata() const noexcept {
        return m_data;
    }

    T *begin() noexcept {
        return m_data;
    }

    T *end() noexcept {
        return m_data + m_size;
    }

    T const *begin() const noexcept {
        return m_data;
    }

    T const *end() const noexcept {
        return m_data + m_size;
    }

    T const *cbegin() const noexcept {
        return m_data;
    }

    T const *cend() const noexcept {
        return m_data + m_size;
    }

    std::reverse_iterator<T *> rbegin() noexcept {
        return std::make_reverse_iterator(m_data + m_size);
    }

    std::reverse_iterator<T *> rend() noexcept {
        return std::make_reverse_iterator(m_data);
    }

    std::reverse_iterator<T const *> rbegin() const noexcept {
        return std::make_reverse_iterator(m_data + m_size);
    }

    std::reverse_iterator<T const *> rend() const noexcept {
        return std::make_reverse_iterator(m_data);
    }

    std::reverse_iterator<T const *> crbegin() const noexcept {
        return std::make_reverse_iterator(m_data + m_size);
    }

    std::reverse_iterator<T const *> crend() const noexcept {
        return std::make_reverse_iterator(m_data);
    }

    void pop_back() noexcept {
        m_size -= 1;
        std::destroy_at(&m_data[m_size]);
    }

    T *erase(T const *it) noexcept(std::is_nothrow_move_assignable_v<T>) {
        size_t i = it - m_data;
        for (size_t j = i + 1; j != m_size; j++) {
            m_data[j - 1] = std::move(m_data[j]);
        }
        m_size -= 1;
        std::destroy_at(&m_data[m_size]);
        return const_cast<T *>(it);
    }

    T *erase(T const *first, T const *last) noexcept(std::is_nothrow_move_assignable_v<T>) {
        size_t diff = last - first;
        for (size_t j = last - m_data; j != m_size; j++) {
            m_data[j - diff] = std::move(m_data[j]);
        }
        m_size -= diff;
        for (size_t j = m_size; j != m_size + diff; j++) {
            std::destroy_at(&m_data[j]);
        }
        return const_cast<T *>(first);
    }

    void assign(size_t n, T const &val) {
        clear();
        reserve(n);
        m_size = n;
        for (size_t i = 0; i != n; i++) {
            std::construct_at(&m_data[i], val);
        }
    }

    template <std::random_access_iterator InputIt>
    void assign(InputIt first, InputIt last) {
        clear();
        size_t n = last - first;
        reserve(n);
        m_size = n;
        for (size_t i = 0; i != n; i++) {
            std::construct_at(m_data[i], *first);
            ++first;
        }
    }

    void assign(std::initializer_list<T> ilist) {
        assign(ilist.begin(), ilist.end());
    }

    Vector &operator=(std::initializer_list<T> ilist) {
        assign(ilist.begin(), ilist.end());
    }

    template <class ...Args>
    T *emplace(T const *it, Args &&...args) {
        size_t j = it - m_data;
        reserve(m_size + 1);
        // j ~ m_size => j + 1 ~ m_size + 1
        for (size_t i = m_size; i != j; i--) {
            std::construct_at(&m_data[i], std::move(m_data[i - 1]));
            std::destroy_at(&m_data[i - 1]);
        }
        m_size += 1;
        std::construct_at(&m_data[j], std::forward<Args>(args)...);
        return m_data + j;
    }

    T *insert(T const *it, T &&val) {
        size_t j = it - m_data;
        reserve(m_size + 1);
        // j ~ m_size => j + 1 ~ m_size + 1
        for (size_t i = m_size; i != j; i--) {
            std::construct_at(&m_data[i], std::move(m_data[i - 1]));
            std::destroy_at(&m_data[i - 1]);
        }
        m_size += 1;
        std::construct_at(&m_data[j], std::move(val));
        return m_data + j;
    }

    T *insert(T const *it, T const &val) {
        size_t j = it - m_data;
        reserve(m_size + 1);
        // j ~ m_size => j + 1 ~ m_size + 1
        for (size_t i = m_size; i != j; i--) {
            std::construct_at(&m_data[i], std::move(m_data[i - 1]));
            std::destroy_at(&m_data[i - 1]);
        }
        m_size += 1;
        std::construct_at(&m_data[j], val);
        return m_data + j;
    }

    T *insert(T const *it, size_t n, T const &val) {
        size_t j = it - m_data;
        if (n == 0) [[unlikely]] return const_cast<T *>(it);
        reserve(m_size + n);
        // j ~ m_size => j + n ~ m_size + n
        for (size_t i = m_size; i != j; i--) {
            std::construct_at(&m_data[i + n - 1], std::move(m_data[i - 1]));
            std::destroy_at(&m_data[i - 1]);
        }
        m_size += n;
        for (size_t i = j; i != j + n; i++) {
            std::construct_at(&m_data[i], val);
        }
        return m_data + j;
    }

    template <std::random_access_iterator InputIt>
    T *insert(T const *it, InputIt first, InputIt last) {
        size_t j = it - m_data;
        size_t n = last - first;
        if (n == 0) [[unlikely]] return const_cast<T *>(it);
        reserve(m_size + n);
        // j ~ m_size => j + n ~ m_size + n
        for (size_t i = m_size; i != j; i--) {
            std::construct_at(&m_data[i + n - 1], std::move(m_data[i - 1]));
            std::destroy_at(&m_data[i - 1]);
        }
        m_size += n;
        for (size_t i = j; i != j + n; i++) {
            std::construct_at(&m_data[i], *first);
            ++first;
        }
        return m_data + j;
    }

    T *insert(T const *it, std::initializer_list<T> ilist) {
        return insert(it, ilist.begin(), ilist.end());
    }

    ~Vector() noexcept {
        for (size_t i = 0; i != m_size; i++) {
            std::destroy_at(&m_data[i]);
        }
        if (m_cap != 0) {
            m_alloc.deallocate(m_data, m_cap);
        }
    }

    Alloc get_allocator() const noexcept {
        return m_alloc;
    }

    bool operator==(Vector const &that) noexcept {
        return std::equal(begin(), end(), that.begin(), that.end());
    }

    auto operator<=>(Vector const &that) noexcept {
        return std::lexicographical_compare_three_way(begin(), end(), that.begin(), that.end());
    }
};

Reference

PREVIOUSstd::array

NEXTstd::list