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 提供多种构造方式，灵活满足不同场景需求：

#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()	判断是否为空

示例：

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 风格数组兼容

示例：

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()	清空所有元素

示例：

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()	返回常量迭代器，防止修改

示例：

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> 的函数实现常见的排序与查找操作。

示例：

#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

示例：

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

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

四、vector的高级技巧

1. 避免不必要的拷贝

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

引用传递：

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

移动语义（C++11及之后）：

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

---

2. 双缓冲技术

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

示例：

vector<int> buffer1, buffer2;
buffer1.reserve(1000); // 预留大容量
buffer2.reserve(1000);

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

---

3. vector与array的结合

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

示例：

#include <array>

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

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

---

4. 与move结合

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

示例：

#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

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

---

2. vector vs list

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

---

3. vector vs array

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

---

六、性能优化技巧

1. 预分配内存 (reserve)

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

示例：

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 可以直接构造元素，避免额外的拷贝或移动。

示例：

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

---

七、常见问题及解决方案

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

问题：

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

解决方案：

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

---

2. 访问越界问题

问题：

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

解决方案：

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

---

3. 插入/删除性能低

问题：

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

解决方案：

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

---

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

问题：

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

解决方案：

使用嵌套初始化：

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

---

5. 内存占用过多

问题：

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

解决方案：

使用 shrink_to_fit() 减少容量：

vec.shrink_to_fit();

八、vector的底层实现原理

1. 内存分配与扩容机制

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

示例：

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. **使用reserve或resize**：
   • 调用 reserve() 扩容后，迭代器可能失效。

解决方案：

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

---

九、vector的特殊应用场景

1. 实现栈（stack）

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

示例：

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

---

2. 实现队列（queue）

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

示例：

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

---

3. 二维动态数组

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

示例：

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 在以下情况下提供异常安全性：

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

示例：

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

---

2. 处理异常的最佳实践

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

---

十一、vector的优化技巧

1. 自定义分配器

vector 支持自定义分配器（Allocator），用于控制内存分配策略。

示例：

#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. 避免直接删除多个元素

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

正确方法：

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

---

3. 误用resize和reserve

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