文章目录

1. vector 的概述1.1 vector 是什么？1.2 vector 的优点1.3 vector 的缺点

2. vector 的基本使用2.1 vector 的定义2.2 基本操作2.3 示例2.4 迭代器的使用

3. vector 的内部实现原理3.1 动态数组的实现3.2 内存管理3.3 内存扩展策略3.4 元素的插入与删除3.4.1 尾部插入与删除3.4.2 中间或头部插入与删除

4. vector 高级功能4.1 复制与赋值4.2 移动语义与 std::move4.3 vector 的初始化列表（C++11）4.4 emplace_back() 与 push_back() 的区别4.5 shrink_to_fit() 减少容量浪费

5. vector 的常见应用场景5.1 动态数组5.2 堆栈5.3 动态队列5.4 2D 矩阵的实现

6. vector 的复杂度分析6.1 时间复杂度6.2 空间复杂度

7. vector 的常见问题和陷阱7.1 容量浪费问题7.2 迭代器失效(最需要注意的地方)7.3 元素的析构

前言： 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 的定义

<code>#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(); // 输出10

vec.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(); // 仅删除了指针，但没有释放内存，可能导致内存泄漏

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