joomla网站模板,一个人做网站的swot,商城网站建设需求文档,sw网站建设C 中的 vector 容器详细总结
1. 什么是 vector#xff1f;
vector 是 C 标准模板库 (STL) 中的一种动态数组容器。它的底层实现是一个可以自动扩展的数组#xff0c;支持随机访问和动态调整大小#xff0c;是 C 中最常用的序列容器之一。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 iostreamint main() {std::vectorint vec1; // 创建空的 vectorstd::vectorint vec2(10); // 创建包含 10 个元素的 vector默认值为 0std::vectorint vec3(10, 5); // 创建包含 10 个元素的 vector值为 5std::vectorint vec4 {1, 2, 3, 4}; // 使用列表初始化std::vectorint vec5(vec4.begin(), vec4.end()); // 使用其他容器的迭代器进行初始化return 0;
}3.2 增加元素
push_back(value)在 vector 的末尾添加一个元素。
vec1.push_back(10); // 在末尾添加 10emplace_back(args...)在末尾原地构造元素避免不必要的拷贝。
vec1.emplace_back(20); // 原地构造 203.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); // 在第三个位置插入 15insert(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::vectorint 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 vectorint main() {// 创建 vector 并初始化std::vectorint 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 是一个高效且灵活的选择能够满足大多数序列数据的处理需求。
