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

Created in November 12, 2023

2023   ·   code   C++   ·   STL

std::vector用法

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

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

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



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

 
#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;
}

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



1
2
3
4
5
6
7

 
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。


1
2
3
4
5
6
7

 
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。



1
2
3
4
5
6
7
8
9

 
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来进行实现。



1
2
3
4
5
6
7
8
9
10
11
12

 
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作为构造函数的参数传进来。



1
2
3
4
5
6
7
8
9
10
11
12

 
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，然后使用迭代器的元素来初始化数组。



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

 
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来进行初始化。



1
2
3
4
5
6

 
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来初始化一个新的对象。这里我们先实现移动构造函数，这里需要注意在移动构造函数的最后将已有的对象清空。



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

 
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对象。



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

 
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释放内存空间。



1
2
3
4
5
6
7
8
9
10
11
12
13

 
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允许通过[]运算符对数组中的元素进行访问。



1
2
3
4
5
6
7
8
9
10
11

 
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()函数，它会在获取元素之前先判断是否越界。



1
2
3
4
5
6
7
8
9
10
11
12
13

 
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()函数方便获取数组的首尾元素。



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

 
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()函数会析构数组中的元素但不会释放数组占用的内存。



1
2
3
4
5
6
7
8
9
10
11

 
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()函数将容器的容量减小到与其大小相匹配。



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

 
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，从而预留出足够的空间。



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

 
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()函数申请足够的空间。



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

 
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中的实现来实现相关的接口。



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

 
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。



1
2
3
4
5
6
7
8
9
10
11
12
13

 
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);
        }
    }
}

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



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

 
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()函数会向数组的末尾添加一个新的元素。



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

 
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类型的构造参数，然后直接在数组的末尾利用这些参数构造新的元素，最后返回这个新元素的引用。这里我们使用带变长参数的函数模板来实现它。



1
2
3
4
5
6
7
8
9
10
11
12
13
14

 
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()函数会销毁数组的末尾元素。



1
2
3
4
5
6
7
8

 
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指针清除该位置上的元素，并返回数组更新后指向同一位置的指针。



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

 
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位置的指针。



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

 
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，并把后面的对象进行顺延。



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

 
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个元素。



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

 
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位置。



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

 
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类型的构造参数来直接在数组末尾构造出新的对象。



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

 
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中有很多获取内部信息的成员函数。这些成员函数的实现都比较简单，这里总结如下：



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

 
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数组内的元素。



1
2
3
4
5
6
7
8
9
10

 
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对象之间的比较我们则可以利用标准库的相关函数来实现。



1
2
3
4
5
6
7
8
9
10
11

 
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的代码可以参考如下：



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509

 
#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