大连哪个企业想做网站,烟台软件优化网站,深圳市宝安区邮政编码多少,seo外链推广ps#xff1a;部分内容使用“AI”查询
一、入门
1、什么是vector
动态数组容器#xff0c;支持自动扩容、随机访问和连续内存存储。
2、怎么创建-初始化vector
std::vectorint v; // 创建空vectorstd::vectorint v {1, 2, 3}; // 直接初始化std::vec…ps部分内容使用“AI”查询
一、入门
1、什么是vector
动态数组容器支持自动扩容、随机访问和连续内存存储。
2、怎么创建-初始化vector
std::vectorint v; // 创建空vectorstd::vectorint v {1, 2, 3}; // 直接初始化std::vectorint v(5, 0); // 指定大小和值5个0
3、访问方式
operator[]无边界检查 int v vec[6];at()有边界检查: vec.at(6) 8;
4、size()和capacity()的区别
size()当前元素数量。—— 实际的比如下课时间班里只有10个人capacity()当前分配的内存可容纳的元素数量capacity size—— resize改变的是capacity比如下课时间班里只有10个人但是班级里座位能容纳50个学生
5、vector 在堆上
二、进阶
1、扩容机制
当size capacity时容器会分配一块更大的连续内存块新容量通常是当前容量的 1.5~2倍具体倍数因实现而异例如 GCC 默认采用 1.5 倍而 MSVC 常用 2 倍。 容器将旧内存中的所有元素 复制 或 移动 到新内存中。 复制适用于不支持移动语义的类型如 std::array。移动适用于支持移动语义的类型如 std::string、自定义类可避免深拷贝开销 释放旧内存被释放容器内部指针更新为新内存地址 均摊时间复杂度push_back 的均摊时间复杂度为 O(1)但每次扩容操作需 O(n)时间n 为当前元素数量。若频繁触发扩容如循环中不断 push_back总时间复杂度可能退化为 O(n²)显著影响性能
代价 时间复杂度O(n)可能影响性能
2、如何避免频繁扩容
使用reserve(n)预分配内存
3、迭代器失效的场景
vector内存布局[1, 2, 3, 4, 5]迭代器it指向元素2元素2被删除后续元素3,4,5前移填补空缺。vector内存布局变为[1, 3, 4, 5]。it迭代器失效指向原位置2但该位置已被覆盖。erase()返回新迭代器new_it指向原it的下一个元素3
// 正确更新迭代器例子
it vec.erase(it); // it 现在指向 3
插入/删除元素尤其是非尾部操作可能导致迭代器失效。 比如扩容时会导致复制 或 移动 内容到新内存中同时释放原始内存容器内部指针更新为新内存地址 。原有迭代器指向的旧内存空间被释放导致迭代器失效。 std::vectorint vec {1,2,3};
auto it vec.begin(); // 指向1
vec.insert(it, 0); // 可能扩容it失效
删除元素时后续元素会向前移动填补空位导致被删除元素及其后的迭代器失效
在中间或开头插入/删除元素时操作点之后的所有迭代器均失效
解决方法
a、重新获取迭代器或使用范围for循环b、insert和erase等函数返回指向新有效位置的迭代器可直接更新迭代器
it vec.insert(it, 0); // 插入后返回新迭代器
it vec.erase(it); // 删除后返回下一个有效迭代器
c、范围for循环推荐
// 此方法仅适用于删除第一个符合条件的元素。若需删除多个元素必须采用其他方法如erase-remove惯用法或反向遍历
for (auto elem : vec) {if (elem % 2 0) {vec.erase(std::find(vec.begin(), vec.end(), elem));break; // 循环迭代器未再被使用避免了后续可能的失效访问。}
}
d、反向遍历从后向前删除元素避免影响未遍历的迭代器。
std::vectorint vec {1, 2, 3, 4, 5};
for (auto rit vec.rbegin(); rit ! vec.rend(); ) {if (*rit % 2 0) {rit decltype(rit)(vec.erase(std::next(rit).base()));} else {rit;}
}
// 反向迭代器遍历通过rbegin()和rend()获取反向迭代器范围实现从末尾向开头的遍历
// std::next(it).base()将反向迭代器转换为对应的正向迭代器指向当前元素的前一个元素
// 调用vec.erase()删除该元素并返回下一个有效正向迭代器
反向迭代器rit初始化为vec.rbegin()指向5
rit指向4偶数执行vec.erase(std::next(rit).base())
4被删除5前移填补空缺
rit更新为vec.rend()循环结束
e、 erase-remove std::remove将待删除元素移到容器末尾并返回新逻辑末尾的迭代器erase根据该迭代器真正删除元素。 remove_if标记待删除元素将不需要删除的元素移到vector前端返回“新逻辑末尾”迭代器new_end。 通过new_end和vec.end()范围删除剩余元素 std::vectorint vec {1, 2, 3, 4, 5};
auto new_end std::remove_if(vec.begin(), vec.end(), [](int n) {return n % 2 0; // 删除偶数
});
vec.erase(new_end, vec.end()); // 删除 2,4
4、push_back与emplace_back的区别
push_back与emplace_back的区别主要体现在对象构造方式和性能效率上
push_back需要先构造一个完整的对象临时对象或已有对象再通过拷贝/移动构造函数将其添加到容器中emplace_back直接在容器的内存空间中调用对象的构造函数无需临时对象避免拷贝/移动
性能差异
简单类型如int两者性能几乎无差异因为int的构造/拷贝成本极低自定义复杂类型emplace_back通过避免临时对象和拷贝操作显著提升性能 struct Complex { Complex(int, double); }; // 高成本构造函数
vec.emplace_back(42, 3.14); // 直接构造效率高
vec.push_back(Complex(42, 3.14)); // 需先构造临时对象再拷贝
5、vectorbool 使用的是bit不能取地址
三、高阶
1、如何快速释放vector的内存
shrink_to_fit(); //请求容量等于大小非强制std::vectorint(vec).swap(vec); // 强制释放多余内存
shrink_to_fit() 的实现与效果内存地址改变原容器的迭代器、指针、引用可能失效
目标释放 vector 未使用的内存即 capacity size 的部分使 capacity 尽可能接近 size。
创建临时容器生成一个空的临时 vector使用与原容器相同的分配器。预分配精确内存临时容器调用 reserve(size)使其容量恰好等于原容器的当前元素数量size。复制元素将原容器的所有元素复制到临时容器中。内存交换通过 swap 交换两个容器的内部指针指向数据内存、size 和 capacity 的指针。销毁临时容器临时容器析构时释放原容器之前占用的多余内存。 std::vectorint(vec).swap(vec) 的实现与效果
目标通过构造临时对象并交换内存强制将 capacity 缩减到 size。
构造临时对象std::vectorint(vec) 调用复制构造函数生成一个临时 vector。**新容器的 capacity 等于原容器的 size**因为复制构造函数仅复制元素不保留多余容量交换内存通过 swap(vec) 交换临时容器与原容器的内部指针。销毁临时对象临时对象析构时释放原容器的旧内存此时临时对象持有原容器的旧内存。结果原容器的 capacity 变为临时对象的 size即精确匹配当前元素数量。 2、vector与list的核心差异
vector支持O(1)随机访问插入/删除非尾部元素代价高
list插入/删除任意位置高效无法随机访问
3、移动语义在vector中的应用
std::vectorstd::string v1 {a, b};
std::vectorstd::string v2 std::move(v1); // v1变为空v2接管资源
4、自定义分配器如何与vector结合
通过模板参数指定分配器类型
std::vectorint, MyAllocatorint v; // 使用自定义分配器
5、vector里面的内存 总是连续的吗
std::vector 的内存布局始终是连续的。std::deque 虽支持高效随机访问但其内存布局为分段连续通过多个独立块实现
