文章目录
- 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::move
- 4.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 的定义
#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(); // 仅删除了指针,但没有释放内存,可能导致内存泄漏
解决方案是在删除元素之前手动释放内存,或者使用智能指针。