深入理解C++ STL中的 vector

前言： C++ Standard Template Library (STL) 是一个强大且灵活的库，提供了许多有用的数据结构和算法，其中vector 是最常用的容器之一。
vector是动态数组的封装，可以在运行时自动调整大小，提供了数组的效率以及更多的功能和灵活性。
在本文中，我们将深入讨论 vector的特性、使用方法、底层实现及其复杂性分析。

1. vector 的概述

vector文档的链接：http://www.cplusplus.com/reference/vector/vector/

1.1 vector 是什么？

vector 是 C++ STL 中一种顺序容器（sequence container），其底层实现基于动态数组。与普通数组不同的是，vector 可以根据需要动态扩展其大小，即它能够存储任意数量的元素，而不需要在创建时指定一个固定的大小。此外，vector 提供了丰富的成员函数，可以方便地对元素进行插入、删除、遍历、查找等操作。

1.2 vector 的优点

动态扩展：vector 能够自动调整大小，避免了固定大小数组带来的内存不足问题。
高效的随机访问：由于 vector 底层是连续的内存块，因此它可以像数组一样通过索引进行快速的随机访问。
灵活的插入和删除：vector 支持高效的尾部插入和删除操作，且提供了多种插入、删除方式。
STL 兼容性：vector 是 STL 容器，支持 STL 的算法和迭代器，可以与其他 STL 容器和算法无缝结合。

1.3 vector 的缺点

头部和中间的插入、删除效率低：由于 vector 使用连续的内存块，因此在中间或头部插入或删除元素时，需要移动大量元素，时间复杂度为 O(n)。 内存浪费：为了提高扩展效率，vector 通常会预留比实际需要更多的内存，这可能导致内存浪费。

2. vector 的基本使用

在使用 vector 时，我们需要包含头文件 。下面是一些 vector 的基本使用方法和常见操作：

2.1 vector 的定义

#include <vector>std::vector<int> vec;          // 定义一个存储整数的空vector
std::vector<int> vec(10);      // 定义一个包含10个元素的vector，元素值默认初始化为0
std::vector<int> vec(10, 5);   // 定义一个包含10个元素的vector，元素值为5
std::vector<int> vec2 = vec;   // 定义一个新vector，并通过拷贝构造函数初始化

2.2 基本操作

push_back()：在 vector 的末尾插入元素。
pop_back()：删除 vector 末尾的元素。
size()：返回 vector 中元素的数量。
capacity()：返回 vector 当前的容量，即它在不重新分配内存的情况下最多可以容纳的元素数。
clear()：清空 vector 中的所有元素。
empty()：判断 vector 是否为空。
resize()：调整 vector 的大小。
reserve()：为 vector 预留一定的容量，避免频繁的重新分配内存。

2.3 示例

#include <iostream>
#include <vector>int main() {std::vector<int> vec;// 向vector中添加元素vec.push_back(1);vec.push_back(2);vec.push_back(3);// 输出vector的元素for (int i = 0; i < vec.size(); ++i) {std::cout << vec[i] << " ";}std::cout << std::endl;// 删除最后一个元素vec.pop_back();// 检查是否为空if (!vec.empty()) {std::cout << "The vector is not empty!" << std::endl;}return 0;
}

2.4 迭代器的使用

迭代器是一种用于遍历 vector 元素的工具。vector 提供了多种迭代器，包括 begin() 和 end()。

std::vector<int> vec = {1, 2, 3, 4, 5};// 使用迭代器遍历
for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {std::cout << *it << " ";
}
std::cout << std::endl;

也可以使用 C++11 的范围 for 循环来遍历：

for (int val : vec) {std::cout << val << " ";
}

3. vector 的内部实现原理

3.1 动态数组的实现

vector 的底层实现基于动态数组。当需要插入新元素时，如果当前容量不足，vector 会自动分配更大的内存块，并将原来的元素拷贝到新的内存块中。这种动态扩展策略的时间复杂度较低，因为 vector 的容量在每次扩展时通常是当前容量的两倍。

std::vector<int> vec;
vec.push_back(1);  // 第一次插入，分配内存
vec.push_back(2);  // 插入，内存足够，不需要重新分配
vec.push_back(3);  // 插入，内存足够，不需要重新分配
// 当容量不足时，vector 会重新分配内存，通常是原来容量的两倍。

3.2 内存管理

vector 通过 capacity 来控制当前分配的内存大小，而 size 表示实际存储的元素数量。capacity 总是大于或等于 size。当 size 超过 capacity 时，vector 会重新分配内存，并将所有现有元素拷贝到新的内存地址。

std::vector<int> vec;
vec.reserve(10);  // 预先分配10个元素的内存
vec.push_back(1); // 不会触发内存重新分配
vec.push_back(2); // 不会触发内存重新分配

通过使用 reserve()，可以避免多次内存重新分配，从而提高效率。

3.3 内存扩展策略

当 vector 的容量不足时，它通常会以指数倍（通常是 2 倍）的方式扩展。每次扩展都会重新分配一块新的内存，并将旧的元素拷贝到新的位置。这种方式虽然在内存重新分配时会有较大的开销，但由于扩展的频率较低，总体上这种策略是高效的。

3.4 元素的插入与删除

3.4.1 尾部插入与删除

vector 尾部的插入和删除操作是最为高效的，时间复杂度为 O(1)，因为它们不需要移动其他元素。使用 push_back() 和 pop_back() 可以高效地操作 vector 末尾的元素。

3.4.2 中间或头部插入与删除

在 vector 中间或头部插入和删除元素时，需要将插入位置之后的所有元素向后移动，这样才能为新元素腾出空间。这使得这些操作的时间复杂度为 O(n)。

vec.insert(vec.begin() + 1, 10);  // 在第二个位置插入10，后面的元素都需要向后移动
vec.erase(vec.begin() + 2);       // 删除第三个元素，后面的元素都需要向前移动

4. vector 高级功能

4.1 复制与赋值

当一个 vector 被赋值或复制时，会创建一个新对象，并将所有元素进行深拷贝。这意味着修改新对象不会影响原来的 vector。

std::vector<int> vec1 = {1, 2, 3};
std::vector<int> vec2 = vec1;   // 深拷贝
vec2[0] = 10;
std::cout << vec1[0];  // 输出1，vec1不受影响

4.2 移动语义与 std::move

C++11 引入了移动语义，允许将 vector 的资源直接转移到另一个对象，而不需要进行深拷贝。这可以极大地提高性能，尤其是在处理大型对象时。

std::vector<int> vec1 = {1, 2, 3};
std::vector<int> vec2 = std::move(vec1);  // 使用std::move，vec1的资源转移给vec2

在上面的例子中，std::move 将 vec1 的所有资源（如内存和元素）直接转移到 vec2 中，而不需要进行深拷贝。这种操作后，vec1 将处于“空”状态，不再拥有原来的数据，size() 将返回0。

4.3 vector 的初始化列表（C++11）

C++11 引入了初始化列表，可以直接通过大括号初始化 vector：

std::vector<int> vec = {1, 2, 3, 4, 5};  // 初始化列表

这种方式非常方便，不需要手动调用 push_back() 来插入每个元素。

4.4 emplace_back() 与 push_back() 的区别

emplace_back() 是 C++11 新增的功能，它允许直接在容器的末尾构造对象，而无需先构造对象再拷贝到 vector。相比之下，push_back() 会进行额外的拷贝操作，因此在某些情况下，emplace_back() 会比 push_back() 更高效。

class Person {
public:Person(const std::string& name, int age) : name(name), age(age) {}
private:std::string name;int age;
};// 使用push_back
std::vector<Person> people;
people.push_back(Person("John", 30));  // 先构造Person对象，然后拷贝到vector中// 使用emplace_back
people.emplace_back("Jane", 25);  // 直接在vector内部构造Person对象，避免拷贝

使用 emplace_back() 时，参数直接传递给对象的构造函数，从而减少了不必要的拷贝或移动操作。

4.5 shrink_to_fit() 减少容量浪费

由于 vector 通常会预留比实际所需更多的内存空间（capacity()），可能会造成内存浪费。shrink_to_fit() 函数用于释放未使用的内存，使得 vector 的容量等于其大小。

std::vector<int> vec = {1, 2, 3};
vec.reserve(10);   // 预留10个元素的空间
std::cout << vec.capacity();  // 输出10vec.shrink_to_fit();
std::cout << vec.capacity();  // 输出3，容量被调整为实际使用的大小

需要注意的是，shrink_to_fit() 并不保证一定会减少容量，但在支持该操作的系统上可以显著减少内存占用。

5. vector 的常见应用场景

5.1 动态数组

vector 最常见的应用场景就是作为动态数组使用。当程序中需要动态调整数组大小时，vector 提供了极大的方便。

std::vector<int> vec;
int n;
std::cin >> n;
for (int i = 0; i < n; ++i) {int x;std::cin >> x;vec.push_back(x);  // 动态添加元素
}

5.2 堆栈

vector 可以模拟堆栈的功能，因为它提供了高效的尾部插入（push_back()）和删除（pop_back()）操作。虽然 C++ STL 中已经有 stack 容器，但使用 vector 实现堆栈也是完全可行的。

std::vector<int> stack;
stack.push_back(1);  // 入栈
stack.push_back(2);
stack.pop_back();    // 出栈

5.3 动态队列

虽然 C++ STL 提供了 queue 容器，但 vector 同样可以用来实现队列。通过在 vector 的末尾插入元素并从头部移除元素，我们可以模拟队列的行为。

std::vector<int> queue;
queue.push_back(1);  // 入队
queue.push_back(2);
queue.erase(queue.begin());  // 出队，删除第一个元素

5.4 2D 矩阵的实现

vector 可以轻松实现二维或多维数组。通过将 vector 嵌套使用，可以构建动态调整大小的二维数组或矩阵。

std::vector<std::vector<int>> matrix(3, std::vector<int>(3));  // 创建3x3的矩阵
matrix[0][0] = 1;
matrix[1][1] = 2;
matrix[2][2] = 3;

这个方法可以处理动态大小的矩阵，使得二维数组的尺寸不需要在编译时确定。

6. vector 的复杂度分析

6.1 时间复杂度

随机访问：由于 vector 是连续的内存块，随机访问某个元素的时间复杂度为 O(1)。
尾部插入和删除：尾部插入（push_back()）和尾部删除（pop_back()）的平均时间复杂度为 O(1)，但在某些情况下（如扩容时）插入操作的复杂度可能会暂时达到 O(n)。
中间或头部插入和删除：由于插入或删除会导致大量元素的移动，因此这些操作的时间复杂度为 O(n)。

6.2 空间复杂度

vector 使用连续的内存块来存储元素，其空间复杂度与存储的元素个数成正比，即 O(n)。由于 vector 会在扩展时预留更多的内存，因此有时它的实际内存使用量会超过其存储的元素量。

为了减少内存浪费，可以使用 shrink_to_fit() 来回收未使用的空间。

7. vector 的常见问题和陷阱

7.1 容量浪费问题

如前所述，vector 的容量通常大于其实际存储的元素数量。如果程序中频繁进行插入操作且对内存使用敏感，可以使用 shrink_to_fit() 来减少浪费。

7.2 迭代器失效(最需要注意的地方)

在 vector 中进行插入或删除操作时，所有指向 vector 元素的迭代器、指针或引用可能会失效。这是因为插入或删除操作可能导致 vector 重新分配内存，从而改变所有元素的地址。

std::vector<int> vec = {1, 2, 3};
auto it = vec.begin();
vec.push_back(4);  // 可能导致内存重新分配
std::cout << *it;  // 迭代器可能失效，行为未定义

解决方法是，在插入或删除操作后，尽量避免使用之前的迭代器或指针。

7.3 元素的析构

当 vector 中的对象被删除时，会调用对象的析构函数。因此，如果 vector 存储的是指针类型，在删除 vector 或清空元素时需要特别小心，确保不会引发内存泄漏。

std::vector<int*> vec;
vec.push_back(new int(10));
vec.clear();  // 仅删除了指针，但没有释放内存，可能导致内存泄漏

解决方案是在删除元素之前手动释放内存，或者使用智能指针。