vector(c++)

一、概述

1. vector的作用

vector 是 C++ STL 提供的一个动态数组容器。它不仅能像普通数组一样存储和访问数据,还支持动态扩展、插入和删除操作,同时保持元素的连续存储,方便使用指针操作。

2. vector的优缺点

优点:

  1. 动态扩展:能够根据需要自动调整大小,无需手动管理内存。
  2. 连续存储:提供数组级别的性能,支持随机访问(O(1) 时间复杂度)。
  3. 多样接口:封装了丰富的操作方法,例如插入、删除、排序等。

缺点:

  1. 扩容开销:当容量不足时,vector 会重新分配更大的内存并复制原有数据,效率降低。
  2. 非尾部操作效率低:在中间插入或删除元素需要移动大量数据。

二、底层实现原理

1. 内存管理

  • vector 使用动态数组存储数据。
  • 每当元素数量超过当前容量时,会触发扩容。扩容通常以原来容量的 2 倍 为单位进行。
  • 扩容流程:
    1. 分配一块更大的内存。
    2. 将原有数据复制到新内存中。
    3. 释放旧内存。

2. 扩容性能分析

  • 触发扩容:当 size 达到 capacity 时。
  • 扩容成本:触发扩容时,所有元素都会被复制到新内存,时间复杂度为 O(n)O(n)O(n)。
  • 优化方法:提前使用 reserve() 预分配内存以避免频繁扩容。

三、常用操作及方法详细讲解

1. 构造与初始化

vector 提供多种构造方式,灵活满足不同场景需求:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <vector>
#include <iostream>

int main() {
// 默认构造:创建一个空的 vector
vector<int> vec1;

// 指定大小的构造:元素值为默认值(int类型为0)
vector<int> vec2(5); // [0, 0, 0, 0, 0]

// 指定大小和初始值
vector<int> vec3(5, 42); // [42, 42, 42, 42, 42]

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

// 复制构造
vector<int> vec5(vec4);

// 范围构造
vector<int> vec6(vec4.begin(), vec4.begin() + 3); // [1, 2, 3]
}

2. 大小与容量管理c++

方法功能
size()返回元素个数
capacity()返回当前分配的容量
resize(n, value)调整大小为 n,多出的元素初始化为 value
reserve(n)预留至少 n 个元素的存储空间,避免频繁扩容
shrink_to_fit()收缩容量,使其等于当前元素个数
empty()判断是否为空

示例:

1
2
3
4
5
6
7
8
9
10
11
vector<int> vec = {1, 2, 3};

cout << "Size: " << vec.size() << endl; // 3
cout << "Capacity: " << vec.capacity() << endl; // 4(实现细节可能不同)

vec.resize(5, 42); // 调整大小为5,后两项为42
vec.reserve(10); // 预留容量为10
vec.shrink_to_fit(); // 收缩到当前大小

cout << "Size after shrink: " << vec.size() << endl; // 5
cout << "Capacity after shrink: " << vec.capacity() << endl; // 5

3. 元素访问方法

方法功能
operator[]不进行边界检查的随机访问
at(index)带边界检查的随机访问,超出范围抛出异常 out_of_range
front()返回第一个元素
back()返回最后一个元素
data()返回底层数组的指针,允许与 C 风格数组兼容

示例:

1
2
3
4
5
6
7
8
vector<int> vec = {10, 20, 30};
cout << vec[1] << endl; // 20
cout << vec.at(2) << endl; // 30
cout << vec.front() << endl; // 10
cout << vec.back() << endl; // 30

int* arr = vec.data(); // 转换为底层数组
cout << arr[1] << endl; // 20

4. 插入和删除方法

方法功能
push_back(value)在末尾添加元素
pop_back()删除末尾元素
insert(pos, value)在指定位置 pos 插入元素
insert(pos, n, value)在指定位置 pos 插入 n 个值为 value 的元素
erase(pos)删除指定位置的元素
erase(first, last)删除范围 [first, last) 的元素
clear()清空所有元素

示例:

1
2
3
4
5
6
7
8
9
10
11
vector<int> vec = {1, 2, 3};

vec.push_back(4); // [1, 2, 3, 4]
vec.pop_back(); // [1, 2, 3]

vec.insert(vec.begin() + 1, 10); // [1, 10, 2, 3]
vec.insert(vec.end(), 2, 5); // [1, 10, 2, 3, 5, 5]

vec.erase(vec.begin() + 1); // [1, 2, 3, 5, 5]
vec.erase(vec.begin() + 2, vec.end()); // [1, 2]
vec.clear(); // 清空容器

5. 迭代器支持

方法功能
begin()返回指向第一个元素的迭代器
end()返回指向最后一个元素后位置的迭代器
rbegin()返回指向最后一个元素的反向迭代器
rend()返回指向第一个元素前位置的反向迭代器
cbegin()返回常量迭代器,防止修改
cend()返回常量迭代器,防止修改

示例:

1
2
3
4
5
6
7
8
9
vector<int> vec = {1, 2, 3, 4};

for (auto it = vec.begin(); it != vec.end(); ++it) {
cout << *it << " ";
}

for (auto rit = vec.rbegin(); rit != vec.rend(); ++rit) {
cout << *rit << " ";
}

6. 排序与查找

vector 可以结合 <algorithm> 的函数实现常见的排序与查找操作。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
#include <algorithm>

vector<int> vec = {5, 3, 4, 1, 2};

// 排序
sort(vec.begin(), vec.end()); // [1, 2, 3, 4, 5]

// 查找
auto it = find(vec.begin(), vec.end(), 3);
if (it != vec.end()) {
cout << "Found: " << *it << endl;
}

7. 二维 vector

示例:

1
2
3
vector<vector<int>> matrix(3, vector<int>(4, 0)); // 3x4 矩阵,初始化为0

matrix[1][2] = 10; // 修改值

四、vector的高级技巧

1. 避免不必要的拷贝

当将一个 vector 传递给函数时,为避免拷贝,建议使用 引用传递移动语义

引用传递:

1
2
3
4
5
void printVector(const vector<int>& vec) { // 使用 const 引用,避免拷贝
for (const auto& val : vec) {
cout << val << " ";
}
}

移动语义(C++11及之后):

1
2
3
4
vector<int> createVector() {
vector<int> vec = {1, 2, 3};
return vec; // 移动语义会避免深拷贝
}

2. 双缓冲技术

在需要频繁插入或删除操作时,可以使用“双缓冲”技术来避免扩容开销:

示例:

1
2
3
4
5
6
vector<int> buffer1, buffer2;
buffer1.reserve(1000); // 预留大容量
buffer2.reserve(1000);

// 将操作切换到另一个 buffer,以减少 realloc 造成的性能消耗
buffer1.swap(buffer2);

3. vectorarray的结合

在固定大小的二维数组场景下,vector可以结合array提供更高效的存储:

示例:

1
2
3
4
5
6
#include <array>

vector<array<int, 4>> matrix(3, array<int, 4>{0, 0, 0, 0});

// 访问元素
matrix[1][2] = 42;

4. move结合

当将一个vector传递到另一个地方时,可以使用move来避免拷贝。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <utility>

vector<int> createLargeVector() {
return vector<int>(1000000, 42);
}

void processVector(vector<int>&& vec) {
// vec 是右值引用,直接操作其内存
cout << "Processing vector of size: " << vec.size() << endl;
}

int main() {
processVector(move(createLargeVector()));
}

五、vector与其他容器对比

1. vector vs deque

特性vectordeque
内存布局连续存储分段存储
插入和删除末尾操作效率高,但非尾部操作效率低头部和尾部操作效率高
适用场景需要频繁随机访问需要频繁在头尾插入或删除

2. vector vs list

特性vectorlist
内存布局连续存储非连续(双向链表)
随机访问效率高(O(1))低(O(n))
插入和删除效率头尾外操作效率低任意位置操作效率高

3. vector vs array

特性vectorarray
是否支持动态大小
使用场景大小未知或动态大小固定的高效数组

六、性能优化技巧

1. 预分配内存 (reserve)

频繁插入大量元素时,使用 reserve() 提前分配内存可以显著提高性能。

示例:

1
2
3
4
5
vector<int> vec;
vec.reserve(1000); // 预分配 1000 个元素容量
for (int i = 0; i < 1000; ++i) {
vec.push_back(i);
}

2. 减少扩容开销

vector默认按2倍增长容量,但可以通过预估容量合理使用reserve


3. 使用emplace_back代替push_back

在 C++11 及之后,emplace_back 可以直接构造元素,避免额外的拷贝或移动。

示例:

1
2
vector<pair<int, string>> vec;
vec.emplace_back(1, "hello"); // 直接在容器中构造 pair

七、常见问题及解决方案

1. 频繁的扩容导致性能下降

问题:

在不断插入大量数据时,vector可能触发多次扩容操作,导致性能问题。

解决方案:

使用 reserve() 提前分配容量。


2. 访问越界问题

问题:

使用 operator[] 访问时,不会进行边界检查,可能导致未定义行为。

解决方案:

使用 at() 进行访问,确保安全。


3. 插入/删除性能低

问题:

在中间频繁插入或删除元素时,由于移动大量数据,性能可能较低。

解决方案:

  • 若需要频繁中间操作,考虑使用 dequelist
  • 若一定要用 vector,可以批量插入或使用更高效的算法。

4. 二维动态数组的初始化复杂

问题:

创建二维数组时可能需要写较复杂的代码。

解决方案:

使用嵌套初始化:

1
vector<vector<int>> matrix(5, vector<int>(5, 0));

5. 内存占用过多

问题:

当删除大量元素时,容量不会自动收缩,导致内存浪费。

解决方案:

使用 shrink_to_fit() 减少容量:

1
vec.shrink_to_fit();

八、vector的底层实现原理

1. 内存分配与扩容机制

  • 内存模型vector 使用动态数组的方式存储数据,分配的内存是连续的。
  • 扩容机制:
    • 当容量不足时,vector 会分配一块更大的内存(通常是当前容量的两倍)。
    • 扩容后,将旧数据移动到新内存区域,再释放旧内存。
    • 这就是为什么频繁扩容会造成性能问题。

示例:

1
2
3
4
5
vector<int> vec;
for (int i = 0; i < 100; ++i) {
vec.push_back(i);
cout << "Capacity: " << vec.capacity() << ", Size: " << vec.size() << endl;
}

2. 迭代器失效问题

在某些操作后,vector 的迭代器可能失效:

失效场景:

  1. 插入或删除元素
    • 插入元素时,可能触发内存重新分配,所有迭代器失效。
    • 删除元素后,指向被删除元素或后续元素的迭代器失效。
  2. **使用reserveresize**:
    • 调用 reserve() 扩容后,迭代器可能失效。

解决方案:

  • 避免直接使用失效的迭代器
  • 重新获取有效的迭代器

九、vector的特殊应用场景

1. 实现栈(stack)

vector 可以作为栈的底层实现,比 stack 更灵活:

示例:

1
2
3
4
5
vector<int> stack;
stack.push_back(10); // 入栈
stack.push_back(20);
stack.pop_back(); // 出栈
cout << "Top element: " << stack.back() << endl;

2. 实现队列(queue)

虽然 deque 更适合队列操作,但 vector 也可以实现简单的队列。

示例:

1
2
3
4
5
vector<int> queue;
queue.push_back(10); // 入队
queue.push_back(20);
queue.erase(queue.begin()); // 出队
cout << "Front element: " << queue.front() << endl;

3. 二维动态数组

通过嵌套使用 vector 实现动态二维数组:

示例:

1
2
3
4
5
6
7
8
9
vector<vector<int>> matrix(3, vector<int>(4, 0)); // 3x4 矩阵

matrix[1][2] = 42; // 修改值
for (const auto& row : matrix) {
for (int val : row) {
cout << val << " ";
}
cout << endl;
}

4. 动态缓冲区(Buffer)

在实时性要求高的场景中,vector 可以用作动态缓冲区,配合 reserve 预分配内存提升性能。


十、vector的异常安全性

1. 标准保证

vector 在以下情况下提供异常安全性:

  • 内存分配失败时,保证不会破坏已有数据。
  • 插入或删除操作失败时,不会影响其他元素。

示例:

1
2
3
4
5
6
try {
vector<int> vec;
vec.reserve(100000000000); // 故意分配超大内存
} catch (const exception& e) {
cout << "Exception: " << e.what() << endl;
}

2. 处理异常的最佳实践

当需要在 vector 中执行复杂操作时,建议在异常捕获块中处理可能的错误。


十一、vector的优化技巧

1. 自定义分配器

vector 支持自定义分配器(Allocator),用于控制内存分配策略。

示例:

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

template <typename T>
using CustomAllocator = allocator<T>;

vector<int, CustomAllocator<int>> vec;
vec.push_back(10);

2. 使用vector替代动态数组

由于 vector 具备边界检查和异常安全性,它通常是动态数组的更好选择。


十二、常见误区与注意事项

1. vector是线程不安全的

在多线程环境下同时访问同一个 vector 可能导致数据竞争。

  • 解决方法:在多线程环境下使用互斥锁(如 mutex)保护 vector

2. 避免直接删除多个元素

直接用循环删除多个元素可能导致迭代器失效。

正确方法:

1
2
vector<int> vec = {1, 2, 3, 4, 5};
vec.erase(remove(vec.begin(), vec.end(), 3), vec.end()); // 删除值为3的所有元素

3. 误用resizereserve

  • resize 会改变 vector 的大小,初始化新元素。
  • reserve 仅仅改变容量,不影响当前大小。