移情别恋c++ ദ്ദി˶ｰ̀֊ｰ́ ) ——6.vector（无习题）

C++ 中的 vector 容器详细总结

1. 什么是 vector？

vector 是 C++ 标准模板库 (STL) 中的一种动态数组容器。它的底层实现是一个可以自动扩展的数组，支持随机访问和动态调整大小，是 C++ 中最常用的序列容器之一。vector 在插入、删除、遍历以及随机访问等方面有着优异的表现，尤其是在数据需要频繁随机访问且不会频繁在中间位置进行插入或删除操作的场景中表现非常出色。

1.1 动态数组的特点

vector 是动态数组，意味着它的大小在程序运行过程中可以根据需要自动扩展。当需要添加新元素且当前容量不足时，vector 会分配更大的内存空间，并将原有的数据拷贝到新的内存中。这种动态性使得 vector 在数据存储和处理上非常灵活，但也会带来一些性能上的开销。

2. vector 的特点与优缺点

2.1 vector 的特点

• 动态大小：vector 的大小可以根据需要自动扩展或缩小，用户无需手动管理内存。
• 连续内存存储：vector 使用连续的内存块存储数据，类似于数组，这使得它支持 O(1) 时间复杂度的随机访问。
• 高效的尾部操作：vector 在尾部添加或删除元素的时间复杂度为摊销 O(1)。
• 支持迭代器：vector 提供随机访问迭代器，可以方便地遍历和操作数据。

2.2 vector 的优点

• 随机访问效率高：由于 vector 的元素在内存中是连续存储的，因此可以使用下标直接访问元素，时间复杂度为 O(1)，访问效率非常高。
• 动态扩展：vector 会根据元素的增加自动扩展容量，用户无需关心内存管理问题。
• 支持 STL 算法：vector 支持与 STL 算法直接配合使用，拥有良好的可扩展性和通用性。

2.3 vector 的缺点

• 插入和删除操作的性能问题：在 vector 中间位置插入或删除元素需要移动后续所有元素，因此时间复杂度为 O(n)，效率较低。
• 内存重新分配开销：当 vector 的容量不足时，需要重新分配更大的内存并拷贝原有数据，这会带来额外的性能开销。
• 内存浪费：为了减少频繁的内存分配，vector 通常会预留比当前需要更多的内存空间，这可能会导致一定程度的内存浪费。

3. vector 的常用操作与函数

3.1 创建与初始化

vector 可以通过多种方式进行创建和初始化，以下是一些常见的方式：

#include <vector>
#include <iostream>int main() {std::vector<int> vec1;                    // 创建空的 vectorstd::vector<int> vec2(10);                 // 创建包含 10 个元素的 vector，默认值为 0std::vector<int> vec3(10, 5);              // 创建包含 10 个元素的 vector，值为 5std::vector<int> vec4 = {1, 2, 3, 4};      // 使用列表初始化std::vector<int> vec5(vec4.begin(), vec4.end()); // 使用其他容器的迭代器进行初始化return 0;
}

3.2 增加元素

• push_back(value)：在 vector 的末尾添加一个元素。

vec1.push_back(10);  // 在末尾添加 10

• emplace_back(args...)：在末尾原地构造元素，避免不必要的拷贝。

vec1.emplace_back(20);  // 原地构造 20

3.3 删除元素

• pop_back()：删除 vector 末尾的元素。

vec1.pop_back();  // 删除末尾元素

• erase(iterator)：删除指定位置的元素。

vec1.erase(vec1.begin() + 1);  // 删除第二个元素

• clear()：清空 vector 中所有元素。

vec1.clear();  // 清空容器

3.4 访问元素

• 使用下标访问：

int value = vec1[2];  // 获取第三个元素

• 使用 at(index) 方法访问，带越界检查：

int value = vec1.at(2);  // 获取第三个元素

• 获取第一个和最后一个元素：

int first = vec1.front();
int last = vec1.back();

3.5 迭代器的使用

• begin(), end()：获取指向第一个元素和末尾后一个位置的迭代器。

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

• rbegin(), rend()：获取反向迭代器，遍历元素时从尾部开始。

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

3.6 容量相关函数

• size()：获取当前元素的数量。
• capacity()：获取当前分配的存储空间，可以存储的元素数量。
• resize(new_size)：改变 vector 的大小。
• reserve(new_capacity)：预分配存储空间，减少内存重新分配的开销。
• shrink_to_fit()：将 capacity 缩小到与 size 相同，减少内存占用。

std::cout << "Size: " << vec1.size() << "\n";
std::cout << "Capacity: " << vec1.capacity() << "\n";
vec1.reserve(20);  // 预分配 20 个元素的空间

4. vector 的内部机制与性能分析

4.1 自动扩展机制

当向 vector 中添加元素时，如果当前容量不足，vector 会自动分配新的更大的内存空间。一般来说，每次扩展会使容量翻倍，以减少扩展次数，从而提高效率。这也意味着在一些场景中，尽可能使用 reserve() 方法来预分配内存，以避免频繁的内存重新分配。

4.2 内存管理与重新分配

vector 在容量不足时会分配更大的内存，并将原有的数据拷贝到新分配的内存中，这个过程称为重新分配（reallocation）。重新分配会带来以下几点开销：

• 内存分配开销：分配新的内存空间需要系统调用，可能会引入一定的开销。
• 数据拷贝开销：每次重新分配时，所有元素都需要从旧内存复制到新内存，这在数据量较大时会带来较高的性能消耗。
• 频繁分配导致的内存碎片：频繁的内存重新分配可能导致内存碎片的增加，影响内存的整体利用效率。

因此，对于已经知道大致数据量的场景，推荐使用 reserve() 来预先分配足够的空间，减少内存重新分配的次数。

4.3 随机访问的特性

由于 vector 的底层实现是一个连续数组，因此它支持 O(1) 时间复杂度的随机访问。这一点使得 vector 相较于其他序列容器（如 list）在需要频繁随机访问时更加高效。尤其是在需要通过下标快速定位特定元素的场景下，vector 是一个非常好的选择。

4.4 vector 的增长策略

C++ 标准中并未规定 vector 的具体增长策略，但大多数实现中，vector 会在容量不足时将容量翻倍。这种指数级增长的策略可以确保在插入元素时具有摊销的常数时间复杂度，从而在大多数情况下提供良好的性能。

5. vector 的高级操作

5.1 插入与删除

• insert(iterator, value)：在指定位置插入一个元素。

vec1.insert(vec1.begin() + 2, 15);  // 在第三个位置插入 15

• insert(iterator, count, value)：在指定位置插入多个相同的元素。

vec1.insert(vec1.begin(), 3, 5);  // 在开头插入三个值为 5 的元素

• erase(iterator)：删除指定位置的元素。

vec1.erase(vec1.begin() + 1);  // 删除第二个元素

• erase(iterator_first, iterator_last)：删除指定范围内的元素。

vec1.erase(vec1.begin(), vec1.begin() + 3);  // 删除前三个元素

5.2 交换与赋值

• swap(other_vector)：交换两个 vector 的内容。

std::vector<int> vec2 = {10, 20, 30};
vec1.swap(vec2);  // 交换 vec1 和 vec2 的内容

• assign(count, value)：将 vector 的内容替换为指定数量的相同元素。

vec1.assign(5, 100);  // 用 5 个值为 100 的元素替换原内容

• assign(iterator_first, iterator_last)：使用指定范围内的元素替换 vector 的内容。

vec1.assign(vec2.begin(), vec2.end());  // 用 vec2 的所有元素替换 vec1 的内容

6. vector 的应用场景与性能优化

6.1 适用场景

• 频繁随机访问：vector 支持 O(1) 的随机访问，因此适合需要频繁通过下标访问元素的场景。
• 数据量动态变化：vector 的大小可以动态扩展，适用于数据量不固定且需要动态添加元素的场景。
• 相对较少的插入和删除操作：如果主要在末尾进行插入和删除，vector 的性能非常好，但在中间位置频繁插入或删除元素时，性能较差。

6.2 性能优化建议

• 预分配内存：如果知道大致的数据量，可以使用 reserve() 预先分配内存，以减少扩展带来的重新分配开销。
• 减少不必要的复制：在添加元素时，尽量使用 emplace_back() 而不是 push_back()，这样可以避免不必要的对象复制。
• 使用移动语义：当元素支持移动语义时，vector 会优先使用移动操作来减少复制开销，尽量使用支持移动语义的类型。

7. vector 与其他容器的对比

7.1 与 list 的对比

• 存储结构：vector 使用连续内存存储，支持 O(1) 时间复杂度的随机访问；list 使用链表存储，不支持随机访问。
• 插入和删除操作：vector 在末尾插入和删除的效率较高，但在中间位置插入和删除需要移动大量元素，时间复杂度为 O(n)。list 的插入和删除操作在任何位置都是 O(1)。
• 内存使用：vector 的内存使用更加紧凑，而 list 由于存储了前驱和后继指针，内存占用更大。
• 遍历性能：vector 的连续内存使得遍历性能更好，能够更好地利用 CPU 缓存，而 list 的遍历性能相对较差。

7.2 与 deque 的对比

• 存储结构：deque（双端队列）由多个连续内存块组成，支持快速的头尾插入和删除操作，而 vector 是单个连续内存块。
• 访问性能：vector 支持 O(1) 时间复杂度的随机访问，deque 也支持随机访问，但性能稍逊于 vector。
• 插入和删除操作：deque 在头尾的插入和删除效率高，而 vector 只在尾部插入和删除效率较高。

7.3 与 array 的对比

• 大小固定：array 是大小固定的容器，在编译时确定大小，vector 是动态大小的容器，能够根据需要自动扩展。
• 性能比较：array 的性能优于 vector，因为它没有动态扩展的开销。对于大小固定且不需要动态调整的场景，array 是更好的选择。

8. 示例代码

下面是一个完整的示例代码，展示了 vector 的常用操作以及高级功能：

#include <iostream>
#include <vector>int main() {// 创建 vector 并初始化std::vector<int> vec = {1, 2, 3, 4, 5};// 添加元素vec.push_back(6);   // 在末尾添加元素vec.emplace_back(7);  // 原地构造元素// 遍历 vectorstd::cout << "Elements: ";for (int val : vec) {std::cout << val << " ";}std::cout << std::endl;// 删除元素vec.pop_back();    // 删除末尾元素vec.erase(vec.begin() + 1);  // 删除第二个元素// 查看大小和容量std::cout << "Size: " << vec.size() << ", Capacity: " << vec.capacity() << std::endl;// 预分配空间vec.reserve(20);std::cout << "Capacity after reserve: " << vec.capacity() << std::endl;// 清空 vectorvec.clear();std::cout << "Size after clear: " << vec.size() << std::endl;return 0;
}

9. 总结

vector 是 C++ 中非常强大且常用的容器，适用于需要动态大小且具有随机访问需求的场景。它提供了丰富的操作接口，并且通过连续的内存布局提供了较高的访问效率。然而，在涉及频繁插入和删除操作时，特别是在中间位置的操作，vector 的性能可能会受到限制。合理选择合适的容器以匹配具体的应用场景非常重要，例如在需要频繁插入和删除的场景中可以选择 list，在需要快速访问头尾元素的场景中可以选择 deque。对于大多数应用场景，vector 是一个高效且灵活的选择，能够满足大多数序列数据的处理需求。