vector

ZaynPei Lv6
  2025-09-23 13:00 2025-09-23 13:00 Created   2025-10-30 13:45:35 2025-10-30 13:45:35 Updated      3.2k Words  13 Mins

std::vector 是 C++ 标准模板库 (STL) 中最常用的序列容器之一。它提供了动态数组的功能，允许在运行时动态调整大小，并且支持高效的随机访问。 

1
2
#include <vector>
std::vector<T> vector_name;
- T: 存储的元素类型。

常用接口

获取元素

std::vector 提供了多种方式来获取元素： - operator[]: 通过下标访问元素，返回对元素的引用。 - at(): 通过下标访问元素，返回对元素的引用，并进行边界检查。 - front(): 返回对第一个元素的引用。 - back(): 返回对最后一个元素的引用。 - data(): 返回指向元素数组的指针。

添加元素: push_back, emplace_back

std::vector 有两个向末尾添加元素的方法：push_back 和 emplace_back。 - push_back(T&& value)：接受一个已经构造好的对象，然后将其拷贝或移动到容器的末尾。 - emplace_back(Args&&… args)：接受构造对象所需的参数，然后在容器的末尾直接构造这个对象。它避免了创建临时对象再进行拷贝或移动的开销，效率更高。

例如: 

1
2
3
std::vector<std::string> vec;
vec.push_back("Hello"); // 使用 push_back 添加字符串
vec.emplace_back("World"); // 使用 emplace_back 直接构造字符串

注意, 如果要使用这两种方法填充vector, 在声明vector时就不能指定大小, 否则会导致默认将指定大小的空间初始化, 之后再push_back或emplace_back元素到后面. 例如: 

1
2
std::vector<int> v(10); // 声明时指定大小为10, 这时v已经有10个元素了
v.push_back(1); // 这时v会变成11个元素, 不是在原有10个元素上覆盖
#### 拼接

std::vector 还提供了 insert 方法，可以将另一个 vector 或一段范围内的元素插入到指定位置。 

1
iterator insert( iterator pos, InputIt first, InputIt last );
- pos: 插入位置的迭代器。 - first, last: 要插入的元素范围。 - 返回值: 指向插入的第一个新元素的迭代器。

示例: 

1
2
3
std::vector<int> v1 = {1, 2, 3};
std::vector<int> v2 = {4, 5, 6};
v1.insert(v1.end(), v2.begin(), v2.end()); // v1 现在是 {1, 2, 3, 4, 5, 6}

删除元素

在 C++ 中，vector 的 erase 函数用于删除元素，它有两种主要的参数形式, 都是传递迭代器类型参数 

1
2
3
iterator erase(iterator position);

iterator erase(iterator first, iterator last);
第一种: 删除 position 所指向的单个元素, 返回一个迭代器，指向被删除元素之后的下一个元素。 第二种: 删除从 first 到 last（不包括 last）之间的所有元素, 返回一个迭代器，指向被删除区域之后的第一个元素。

需要十分注意的点: - 删除成功后容器的迭代器失效, 不过erase()的返回值会返回指向下一个元素的迭代器, 这在for循环中必须额外处理, 使得只有在删除失败时才it++ - 删除操作会导致后续元素前移，容器大小(size)减小，但容量(capacity)不变。

另外, erase()函数不接受反向迭代器作为参数, 只能传递正向迭代器. 为了传递反向迭代器, 需要使用 base() 方法将其转换为正向迭代器, 但要注意转换后的迭代器指向的是反向迭代器所指元素的下一个位置。

1
2
3
4
5
std::vector<int> v = {1, 2, 3, 4, 5};
auto rit = v.rbegin() ; // 指向元素 5
v.erase(rit.base() - 1); // 删除元素 5
// rit 现在无效，需要重新获取
rit = v.rbegin(); // 现在指向新的最后一个元素 4

rit.base() 返回的是当前反向迭代器指向元素的下一个位置(正向来看)，所以你需要减去 1 才能正确删除 rit 所指的元素。

同时, 由于 erase() 返回的是正向迭代器, 如果需要继续使用反向迭代器, 只能重新获取反向迭代器而不能直接重新赋值.

正向迭代器标准处理流程
1
2
3
4
5
6
7
for (auto it = lst.begin(); it != lst.end();) {
        if (*it % 2 == 0) {
            it = lst.erase(it);  // 删除后，it指向下一个元素
        } else {
            ++it;                // 未删除时手动递增
        }
    }

此外, vector 还提供了 pop_back() 方法，用于删除容器末尾的元素。这个方法不返回被删除的元素, 也不会调整容量(capacity)。

查找元素

在 C++ 中，vector 本身并没有内建的查找函数，但我们可以使用 STL 提供的算法来实现查找功能

std::find: 查找等于某个值的元素，返回找到的元素的迭代器(成功)或末尾迭代器(失败), 输入参数是迭代器(查找范围)的始末位置和要查找的值。 

1
2
auto it = std::find(v.begin(), v.end(), target);
if (it != v.end()) { /* 找到了 */ }

std::binary_search: 用于已排序的 vector，判断某个值是否存在, 但只能返回bool值代表是否存在而不能定位。 

1
2
std::sort(v.begin(), v.end());
bool found = std::binary_search(v.begin(), v.end(), target);
### 迭代器遍历

反向迭代器: 指的是从容器的末尾向前遍历元素的迭代器。C++ STL 提供了 rbegin() 和 rend() 成员函数来获取反向迭代器, 它们分别指向容器的最后一个元素和第一个元素之前的位置。 

1
2
3
for (auto rit = v.rbegin(); rit != v.rend(); ++rit) {
    std::cout << *rit << " ";
}

元素去重

使用 std::unique

C++ STL 提供了 std::unique 算法来移除相邻的重复元素。它需要先对 vector 进行排序，然后使用 std::unique 来将重复元素移动到容器的末尾，最后使用 erase 删除这些重复元素。

1
2
3
4
5
6
7
#include <algorithm>
#include <vector>

std::vector<int> v = {1, 2, 2, 3, 4, 4, 5};
std::sort(v.begin(), v.end());
auto last = std::unique(v.begin(), v.end());
v.erase(last, v.end());

这里的 std::unique 原型为: 

1
2
template< class ForwardIt >
ForwardIt unique( ForwardIt first, ForwardIt last );
其作用是重新排列范围[first, last)中的元素，使得每个元素只出现一次，并返回一个指向新逻辑结尾的迭代器。而其他重复的元素会被移动到范围的末尾, 因此需要使用 erase 方法将这些多余的元素删除。

需要注意的是，std::unique 只会移除相邻的重复元素，因此在使用之前通常需要先对容器进行排序。

使用 std::set

另一种去重的方法是使用 std::set，它是一个自动排序且不允许重复元素的容器。可以将 vector 的元素插入到 set 中，然后再将 set 的元素复制回 vector。

1
2
3
4
5
#include <set>
#include <vector>
std::vector<int> v = {1, 2, 2, 3, 4, 4, 5};
std::set<int> s(v.begin(), v.end()); // 利用 set 去重
v.assign(s.begin(), s.end());        // 复制回 vector

需要注意的是，使用 std::set 会改变元素的顺序，因为 set 会对元素进行排序。

这里的std::assign函数原型为: 

1
2
template< class InputIt >
void assign( InputIt first, InputIt last );
它的作用是将范围[first, last)内的元素复制到容器中，替换掉原有的所有元素。

而另一个类似的函数std::copy则是将元素复制到指定位置, 例如: 

1
2
template< class InputIt, class OutputIt >
OutputIt copy( InputIt first, InputIt last, OutputIt d_first );

例如, 将set中的元素复制到vector的开头: 

1
std::copy(s.begin(), s.end(), std::back_inserter(v));

这里的std::back_inserter是一个适配器，用于将元素插入到容器的开头。可能有人会问, 为什么不使用std::vector的begin()作为输出迭代器? 因为std::back_inserter 是一个特殊的输出迭代器，它不会直接进行赋值，而是每次写入时都调用目标容器的 push_back() 方法。这会动态地为 std::vector 分配内存并添加元素。如果直接使用 begin() 作为输出迭代器, 那么在复制过程中如果目标容器的大小不足以容纳所有元素, 就会导致未定义行为。

底层实现

std::vector 底层通常是通过一个动态分配的数组来实现的。它维护了三个关键属性： - **_start: 指向数组的起始位置。 - _finish: 指向当前最后一个元素的下一个位置。 - _end_of_storage**: 指向分配的内存的末尾。

下面是一个简化版的 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
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
#include <cstddef>   // for size_t
#include <memory>    // for std::allocator, std::uninitialized_copy, etc. (高级实现)
#include <utility>   // for std::move
#include <stdexcept> // for std::out_of_range
#include <iostream>  // for debugging output

template <typename T>
class MyVector {
public:
    // --- 1. 构造函数, 析构函数, 和赋值运算符 (Rule of Five) ---

    // 默认构造函数
    MyVector() noexcept : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {
        std::cout << "[Default Constructor]\n";
    }

    // 拷贝构造函数
    MyVector(const MyVector& other) {
        std::cout << "[Copy Constructor]\n";
        // 分配足够大的新空间
        _start = new T[other.size()];
        // 逐个拷贝元素
        std::uninitialized_copy(other._start, other._finish, _start);
        _finish = _start + other.size();
        _end_of_storage = _finish; // 容量等于大小
    }

    // 移动构造函数
    MyVector(MyVector&& other) noexcept
        : _start(other._start), _finish(other._finish), _end_of_storage(other._end_of_storage) {
        std::cout << "[Move Constructor]\n";
        // “窃取”资源后，将源对象置为空状态，防止其析构函数释放我们刚窃取的内存
        other._start = other._finish = other._end_of_storage = nullptr;
    }

    // 拷贝赋值运算符 (使用 copy-and-swap 惯用法)
    MyVector& operator=(const MyVector& other) {
        std::cout << "[Copy Assignment Operator]\n";
        if (this != &other) {
            MyVector temp(other); // 调用拷贝构造函数
            swap(*this, temp);   // 交换内部指针
        }
        return *this;
    }

    // 移动赋值运算符
    MyVector& operator=(MyVector&& other) noexcept {
        std::cout << "[Move Assignment Operator]\n";
        if (this != &other) {
            free(); // 释放当前对象的资源
            // 窃取源对象的资源
            _start = other._start;
            _finish = other._finish;
            _end_of_storage = other._end_of_storage;
            // 将源对象置空
            other._start = other._finish = other._end_of_storage = nullptr;
        }
        return *this;
    }

    // 析构函数
    ~MyVector() {
        std::cout << "[Destructor] Cleaning up " << size() << " elements.\n";
        free();
    }

    // --- 2. 容量相关 ---
    size_t size() const noexcept { return _finish - _start; }
    size_t capacity() const noexcept { return _end_of_storage - _start; }
    bool empty() const noexcept { return _start == _finish; }

    // --- 3. 元素访问 ---
    T& operator[](size_t n) { return _start[n]; }
    const T& operator[](size_t n) const { return _start[n]; }

    // --- 4. 修改器 ---
    void push_back(const T& value) { // 拷贝版本
        std::cout << "push_back (copy)\n";
        if (_finish == _end_of_storage) {
            reallocate();
        }
        // 使用 placement new 在已分配的原始内存上构造对象
        new (_finish) T(value);
        ++_finish;
    }

    void push_back(T&& value) { // 移动版本
        std::cout << "push_back (move)\n";
        if (_finish == _end_of_storage) {
            reallocate();
        }
        // 使用 placement new 并通过 std::move 转发，调用移动构造函数
        new (_finish) T(std::move(value));
        ++_finish;
    }

    // --- 5. 迭代器 (简化版，仅为指针) ---
    T* begin() noexcept { return _start; }
    T* end() noexcept { return _finish; }
    const T* begin() const noexcept { return _start; }
    const T* end() const noexcept { return _finish; }


private:
    // --- 6. 私有辅助函数 ---
    void free() {
        if (_start) {
            // 必须先手动调用析构函数
            for (T* p = _start; p != _finish; ++p) {
                p->~T();
            }
            // 再释放原始内存
            delete[] reinterpret_cast<char*>(_start);
        }
    }

    void reallocate() {
        // 策略：容量为0时分配1，否则加倍, 这里是两倍的策略
        size_t new_capacity = size() == 0 ? 1 : 2 * capacity();
        size_t old_size = size();
        
        // 分配原始内存，注意这里用 char* 是为了避免调用T的默认构造
        T* new_start = reinterpret_cast<T*>(new char[new_capacity * sizeof(T)]);
        
        // 移动旧元素到新内存
        // 使用 std::uninitialized_move 来处理移动并构造，更安全高效
        for(size_t i = 0; i < old_size; ++i) {
            new (new_start + i) T(std::move(_start[i]));
        }

        // 释放旧内存
        free();

        // 更新指针
        _start = new_start;
        _finish = _start + old_size;
        _end_of_storage = _start + new_capacity;
    }

    // 友元函数，用于 copy-and-swap
    friend void swap(MyVector& first, MyVector& second) noexcept {
        using std::swap;
        swap(first._start, second._start);
        swap(first._finish, second._finish);
        swap(first._end_of_storage, second._end_of_storage);
    }

    T* _start;  // 指向数据的起始位置
    T* _finish;  // 指向当前最后一个元素的下一个位置
    T* _end_of_storage;  // 指向分配的内存的末尾
};

这里的std::uninitialized_copy和std::uninitialized_move是C++标准库中的两个函数模板，分别用于在未初始化的内存区域中拷贝和移动对象。它们通常用于容器类的实现中，以便在分配新内存后正确地构造对象。

底层实现的关键：size vs capacity

要深入理解 std::vector，就必须明白它内部的内存管理机制，这涉及到两个核心概念：大小 (size) 和 容量 (capacity)。

  • 大小 (Size)：指容器中当前实际存储的元素数量。你可以通过 size() 成员函数获取。
  • 容量 (Capacity)：指在不重新分配内存的情况下，容器最多可以容纳的元素数量。你可以通过 capacity() 成员函数获取。

可以在上述实现中看到, size 是通过 _finish - _start 计算得到的, 而 capacity 是通过 _end_of_storage - _start 计算得到的。

当你向 vector 添加元素时（例如通过 push_back），如果当前的 size 达到了 capacity，vector 会调用 reallocate() 函数来分配一块更大的内存区域，通常是当前容量的两倍。然后，它会将旧元素移动到新内存中，并释放旧内存。

这个过程是昂贵的，因为它涉及内存分配和所有元素的移动。但是，由于每次扩容都是指数级增长，这种昂贵的操作不会频繁发生。因此，push_back 的平均时间复杂度（摊还时间复杂度）依然是 O(1)。

On this page
vector
  1. 常用接口
    1. 获取元素
    2. 添加元素: push_back, emplace_back
    3. 删除元素
    4. 查找元素
    5. 元素去重
      1. 使用 std::unique
      2. 使用 std::set
  2. 底层实现
    1. 底层实现的关键：size vs capacity