一.vector的介绍及使用文档参考https://cplusplus.com/reference/vector/vector/vector是一个可以动态增长、支持下标访问的连续数组容器。它和数组一样元素在内存中连续存放所以支持[]下标访问效率 O(1)。但它不像数组那样大小固定可以自动增长不需要手动管理容量。vector内部用三个指针管理内存_start指向数组开头_finish指向最后一个元素的下一个位置_end_of_storage指向容量末尾的下一个位置。元素个数size就是_finish - _start总容量capacity就是_end_of_storage - _start。当size等于capacity时空间已满vector会触发扩容新开一块更大的内存通常是原容量的 1.5 或 2 倍把旧元素拷贝或移动到新空间释放旧内存最后调整三个指针指向新位置。扩容有开销但不是每次插入都触发所以尾部插入的均摊时间仍然是 O(1)。vector用额外占用的空间换取了尾部操作的效率。优点是下标访问快O(1)尾部增删快均摊 O(1)内存连续对缓存友好。缺点是中间插入删除需要移动元素O(n)效率低扩容时有拷贝开销可能占用比实际需要更多的内存。和其他容器相比vector比list访问更快但中间插入删除更慢和deque比vector的尾部操作更稳定但头部操作不如deque。常见操作复杂度下标访问[]是 O(1)push_back和pop_back均摊 O(1)中间插入insert和删除erase是 O(n)查找find是 O(n)。使用STL的三个境界能用明理能扩展 那么下面学习vector我也是按照这个方法去学习二.vector的使用2.1 vector的定义default(1) —— 空间配置器allocvector(const allocator_type alloc allocator_type());alloc是缺省参数绝大多数情况下不需要手动传入它是STL 六大组件中的空间配置器负责底层内存的分配与释放简单点说就是allocnew/delete的封装版本允许用户自定义内存管理策略日常使用完全可以忽略它直接用默认值即可vectorint v; // 等价于 vectorint, allocatorint v;fill(2) ——value_type和\0的问题vector(size_type n, const value_type val value_type());value_type就是vector的模板参数类型好比vectorint中value_type就是int这里的\0是 char 类型的缺省值vectorchar v1(5); // 5 个 \0缺省值 vectorchar v2(5, a); // 5 个 a vectorint v3(5); // 5 个 0int 的缺省值 vectorstring v4(3); // 3 个空字符串更正缺省值不是固定的\0而是该类型的默认构造值value_type()。对于char来说正好是\0。range(3) —— 迭代器是函数模板template class InputIterator vector(InputIterator first, InputIterator last);这里的迭代器不一定是vector::iterator它可以是任意满足输入迭代器要求的类型比如可以用数组指针、其他容器的迭代器、istream_iterator// 用数组指针初始化 int arr[] {1, 2, 3, 4, 5}; vectorint v1(arr, arr 5); // 用 list 的迭代器初始化 listint lst {10, 20, 30}; vectorint v2(lst.begin(), lst.end()); // 用另一个 vector 的迭代器部分区间 vectorint v3(v1.begin() 1, v1.end() - 1); // 用 istream_iterator 从输入流读取 vectorint v4((istream_iteratorint(cin)), istream_iteratorint());copy(4)—— 拷贝构造函数vector (const vector x);只有一个参数另一个同类型的 vector 对象。作用用已有的 vector 对象 x 构造一个新的 vector新对象是 x 的独立副本深拷贝。特点 参数类型 const vector常量引用只读 深拷贝新对象有独立的内存修改 v2 不会影响 v11. 无参构造vector()vectorint v1; // 创建一个空的 vector2. 构造并初始化 n 个 valvectorint v2(5, 10); // 创建包含 5 个 10 的 vector // v2: [10, 10, 10, 10, 10] vectorstring v3(3, hello); // 创建包含 3 个 hello 的 vector // v3: [hello, hello, hello]3. 拷贝构造vectorint v4(5, 10); // [10, 10, 10, 10, 10] vectorint v5(v4); // 用 v4 拷贝构造 v5 // v5: [10, 10, 10, 10, 10]独立4. 使用迭代器区间初始化vectorint v6(5, 10); // [10, 10, 10, 10, 10] vectorint v7(v6.begin(), v6.end()); // 用迭代器拷贝整个 v6 int arr[] {1, 2, 3, 4, 5}; vectorint v8(arr, arr 5); // 用数组区间初始化 // v8: [1, 2, 3, 4, 5] vectorint v9(v6.begin() 1, v6.end() - 1); // 部分区间 // v9: [10, 10, 10]去掉首尾2.2 vector iterator 的使用//正向迭代器 iterator begin(); // 返回第一个元素的迭代器 const_iterator begin() const; // const 对象调用只能读 iterator end(); // 返回最后一个元素后面的位置不能解引用 const_iterator end() const; // const 对象调用 //反向迭代器 reverse_iterator rbegin(); // 返回最后一个元素的迭代器反向遍历起点 const_reverse_iterator rbegin() const; reverse_iterator rend(); // 返回第一个元素**前面**的位置反向遍历终点 const_reverse_iterator rend() const;1.begin()和end()begin()返回指向第一个元素的迭代器end()返回指向最后一个元素后面一个位置的迭代器。vectorint v {1, 2, 3, 4, 5}; // 正向遍历 for (auto it v.begin(); it ! v.end(); it) { cout *it ; // 输出1 2 3 4 5 } cout endl; // 修改元素 for (auto it v.begin(); it ! v.end(); it) { *it 10; // 每个元素加 10 } 输出11, 12, 13, 14, 15 // const 版本只读 const vectorint v2 {1, 2, 3}; auto cit v2.begin(); // 返回 const_iterator不能修改 *cit 100; 报错2.rbegin()和rend()rbegin()返回指向最后一个元素的反向迭代器rend()返回指向第一个元素前面一个位置的反向迭代器。vectorint v {1, 2, 3, 4, 5}; // 反向遍历从后往前 for (auto it v.rbegin(); it ! v.rend(); it) { cout *it ; // 输出5 4 3 2 1 } cout endl; // 修改元素 for (auto it v.rbegin(); it ! v.rend(); it) { *it 10; // 每个元素加 10 } 输出11, 12, 13, 14, 152.3 vector 空间增长问题// 获取数据个数 size_t size() const; // 获取容量大小 size_t capacity() const; // 判断是否为空 bool empty() const; // 改变 vector 的 size void resize(size_t n, const T val T()); // 改变 vector 的 capacity void reserve(size_t n);size()—— 获取元素个数vectorint v {1, 2, 3, 4, 5}; cout v.size() endl; // 输出5 v.push_back(6); cout v.size() endl; // 输出6 v.pop_back(); cout v.size() endl; // 输出5empty()—— 判断是否为空vectorint v1; cout v1.empty() endl; // 输出1 vectorint v2 {1, 2, 3}; cout v2.empty() endl; // 输出0 if (!v2.empty()) { cout vector 不为空 endl; }resize()—— 改变 size重点new_size size发生截断会删除多余元素new_size size发生扩容 size会新增元素用默认值或指定值填充reserve()—— 改变 capacity重点只改变容量不改变元素个数n capacity无效果n capacity扩容到至少 nvectorint v(10, 1); // size10, capacity1010个1 v.reserve(20); // 扩容到 20 cout v.size() endl; // 10不变 cout v.capacity() endl; // 20 v.reserve(15); // 15 ≤ 20不缩容 cout v.size() endl; // 10不变 cout v.capacity() endl; // 20不变 v.reserve(5); // 5 ≤ 20不缩容 cout v.size() endl; // 10不变 cout v.capacity() endl; // 20不变结论reserve只能扩大容量不能缩小且不改变size。vectorint v(10, 1); // size10, capacity10 v.reserve(20); // 先扩容到 20 cout v.size() endl; // 10 cout v.capacity() endl; // 20 v.resize(15, 2); // 扩大到 15 个元素多出的填 2 cout v.size() endl; // 15 cout v.capacity() endl; // 20容量够不变 v.resize(25, 3); // 扩大到 25 个元素容量不够 cout v.size() endl; // 25 cout v.capacity() endl; // 可能 30 或 40自动扩容 v.resize(5); // 缩小到 5 个元素 cout v.size() endl; // 5 cout v.capacity() endl; // 不变还是之前的容量resize改变size可能改变capacity小结一下二者的区别reserve只改容量只能扩大不改元素个数resize改元素个数可扩大可缩小容量不够时会自动扩容但缩小 size 不会缩容量。capacity()—— 获取当前容量大小void TestVectorExpand() { size_t sz; vectorint v; //v.reserve(100); sz v.capacity(); cout capacity changed: sz \n; cout making v grow:\n; for (int i 0; i 100; i) { v.push_back(i); if (sz ! v.capacity()) { sz v.capacity(); cout capacity changed: sz \n; } } }在Linux下运行结果capacity的代码在vs和g下分别运行会发现vs下capacity是按1.5倍增长的g是按2倍增长的。这个问题经常会考察不要固化的认为vector增容都是2倍具体增长多少是根据具体的需求定义的。vs是PJ版本STLg是SGI版本STL。reserve只负责开辟空间如果确定知道需要用多少空间reserve可以缓解vector增容的代价缺陷问题。resize在开空间的同时还会进行初始化影响size。2.4vector 增删查改// 尾插 void push_back(const T val); // 尾删 void pop_back(); // 查找算法不是 vector 成员 template class InputIterator, class T InputIterator find(InputIterator first, InputIterator last, const T val); // 在 position 之前插入 val iterator insert(iterator position, const T val); // 在 position 之前插入 n 个 val void insert(iterator position, size_type n, const T val); // 在 position 之前插入迭代器区间 [first, last) template class InputIterator void insert(iterator position, InputIterator first, InputIterator last); // 删除 position 位置的元素 iterator erase(iterator position); // 删除 [first, last) 区间内的元素 iterator erase(iterator first, iterator last); // 交换两个 vector void swap(vector x); // 下标访问不检查边界 reference operator[](size_type n); const_reference operator[](size_type n) const; // 下标访问检查边界越界抛异常 reference at(size_type n); const_reference at(size_type n) const; // 第一个元素 reference front(); const_reference front() const; // 最后一个元素 reference back(); const_reference back() const; // 返回底层数组指针 T* data(); const T* data() const;T是模板参数表示这个vector存储的元素类型value_type是 STL 标准中对“容器元素类型”的统一定义名称所以T就是value_typepush_back—— 尾插作用:在vector末尾添加一个元素vectorint v; v.push_back(10); // v: [10] v.push_back(20); // v: [10, 20] v.push_back(30); // v: [10, 20, 30]底层原理检查当前size是否等于capacity;如果容量够直接把元素放到_finish位置然后_finish;如果容量不够先扩容新容量 ≈ 1.5 倍或 2 倍再添加元素.扩容时 O(n)需要拷贝所有元素pop_back—— 尾删作用:删除vector末尾的一个元素vectorint v {10, 20, 30, 40}; v.pop_back(); // v: [10, 20, 30] v.pop_back(); // v: [10, 20]底层原理检查是否非空不能对空 vector 执行pop_back_finish--只是指针前移不释放内存元素个数减 1容量不变O(1)只是指针移动不需要拷贝find是 算法在algorithm中不是vector的成员函数。它用于在容器中查找值。template class InputIterator, class T InputIterator find(InputIterator first, InputIterator last, const T val);first 查找范围的起始迭代器last 查找范围的结束迭代器不包含val 要查找的值返回值找到返回指向该元素的迭代器找不到返回 last。vectorint v {10, 20, 30, 40}; auto it find(v.begin(), v.end(), 30); if (it ! v.end()) cout *it endl;底层实现templateclass InputIterator, class T InputIterator find(InputIterator first, InputIterator last, const T val) { while (first ! last) { if (*first val) // 用 比较 return first; first; } return last; }std::find 是算法用迭代器范围 [first, last) 查找值返回迭代器找到返回位置找不到返回 last。vector 本身没有 find 成员函数。insert—— 在 pos 前插入容量不足则扩容将[pos, _finish)往后挪一位然后构造新元素。iterator insert(iterator position, const T val);vectorint v {10, 20, 40}; auto it v.begin() 2; v.insert(it, 30); // 输出v: [10, 20, 30, 40]erase—— 删除 pos 位置的数据将[pos1, _finish)往前挪一位覆盖被删除元素然后_finish--。iterator erase(iterator position);vectorint v {10, 20, 30, 40}; auto it v.begin() 2; v.erase(it); // v: [10, 20, 40]swap—— 交换两个 vector 的数据空间只交换三个指针_start、_finish、_end_of_storage不拷贝元素。void swap(vector x);vectorint v1 {1, 2, 3}; vectorint v2 {4, 5, 6}; v1.swap(v2); //输出 v1: [4, 5, 6], v2: [1, 2, 3]operator[]—— 下标访问return _start[n]直接指针偏移不检查越界。reference operator[](size_type n); const_reference operator[](size_type n) const;vectorint v {10, 20, 30}; cout v[0] endl; // 10 v[1] 100; // 进行修改 // v: [10, 100, 30]2.4 vector 迭代器失效问题重点迭代器的主要作用就是让算法能够不用关心底层数据结构其底层实际就是一个指针或者是对指针进行了封装比如vector的迭代器就是原生态指针T* 。因此迭代器失效实际就是迭代器底层对应指针所指向的空间被销毁了而使用一块已经被释放的空间造成的后果是程序崩溃(即如果继续使用已经失效的迭代器程序可能会崩溃)。对于vector可能会导致其迭代器失效的操作有会引起其底层空间改变的操作都有可能是迭代器失效比如resize、reserve、insert、assign、push_back等。1.insert第一种插入操作导致的内存重新分配扩容void TestInsert1() { // 迭代器失效问题 -- 类似野指针问题 vectorint v; v.push_back(1); v.push_back(2); v.push_back(3); vectorint::iterator pos find(v.begin(), v.end(), 2); if (pos ! v.end()) { // 第一种扩容导致失效 // 当 v.capacity() v.size() 1 时vector 重新分配内存 // 所有迭代器包括 pos指向已释放的旧内存 v.insert(pos, 20); // pos 已失效不能使用 // cout *pos endl; // 解决方法重新赋值 // pos v.insert(pos, 20); } }当size() 1 capacity()时vector 会重新分配更大内存;所有迭代器包括 pos都失效指向已释放的旧内存图解第二种插入操作导致的位置移动即使不扩容void TestInsert2() { // 迭代器失效问题 -- 类似野指针问题 vectorint v; v.reserve(10); // 预留足够空间避免扩容 v.push_back(1); v.push_back(2); v.push_back(3); vectorint::iterator pos find(v.begin(), v.end(), 2); if (pos ! v.end()) { // 虽然没扩容但 insert 导致 pos 之后的所有元素后移 // pos 仍然指向原位置但该位置现在放的是新插入的 20 // 原本的 2 已经被后移pos 的语义改变了 v.insert(pos, 20); // pos 现在指向 20而不是原来的 2 // cout *pos endl; // 输出 20不是 2 // 解决方法重新赋值 // pos v.insert(pos, 20); // pos 指向新插入的 20 } }pos 仍指向原位置但该位置现在是新插入的元素;pos 原本指向的元素已经被后移所以 pos 语义改变图解insert 操作导致迭代器失效的两种场景扩容导致的失效当插入元素时发生扩容vector 会重新分配内存空间将旧数据迁移到新空间后释放旧空间。此时迭代器 pos 仍然指向已被释放的旧空间变成了野指针无法再使用。不扩容但语义改变导致的失效当插入元素时没有发生扩容vector 会将 pos 位置及其之后的元素向后移动为插入腾出空间。此时 pos 仍然指向原来的内存位置但该位置已经被新插入的元素占据pos 不再指向原来的值其语义发生了改变。补充发生扩容时当前迭代器和之后所有迭代器都会失效无论哪种场景迭代器失效后都不能再进行访问读取、写入、比较等操作解决方法使用 insert 函数返回的新迭代器指向新插入元素重新赋值不同平台的表现VS2019/VS2022Debug 模式程序崩溃触发迭代器失效断言VS2019/VS2022Release 模式可能不会立即崩溃但属于未定义行为LinuxGCC/Clang通常不会崩溃但迭代器确实已失效2.erase// erase 操作导致迭代器失效演示 void TestEraseDemo() { vectorint v{ 10, 20, 30, 40, 50 }; // 查找值为30的元素 vectorint::iterator it find(v.begin(), v.end(), 30); if (it ! v.end()) { // 删除it指向的元素值为30 v.erase(it); // 此时it已失效因为it后面的元素4050都向前移动了 // it指向的位置现在存放的是40不再是原来的30 // 错误访问已失效的迭代器 // cout *it endl; // 虽然可能输出40但这是未定义行为 // *it 100; // 危险操作 // 正确使用erase返回值更新迭代器 // it v.erase(it); // it指向被删除元素的下一个位置也就是40 } // 删除后it及其之后的所有迭代器都失效了 // 不能再用it去访问vector中的元素 }erase 导致迭代器失效的原因erase 删除元素时pos 位置之后的元素会向前移动填补空缺。pos 仍然指向原来的内存位置但该位置的数据已经被覆盖或删除因此 pos 不再指向原来的值迭代器失效。不同平台的表现VS2019/VS2022Debug 模式程序崩溃触发迭代器失效断言VS2019/VS2022Release 模式可能不会立即崩溃但属于未定义行为LinuxGCC/Clang通常不会崩溃但迭代器确实已失效图解erase 导致迭代器失效的两种场景缩容引发失效比如 vector 当前有 100 个容量且存满 100 个数据删除操作后有效数据只剩 30 个这时编译器可能会触发缩容重新开辟一块 50 个容量的新空间把数据搬过去后释放原来的 100 个容量空间。之前保存的迭代器 pos 还指着被释放的旧空间就成了野指针。元素搬移导致意义改变删除 pos 位置的数据后pos 后面的所有元素会依次前移填补空缺。pos 还是指向原来那个内存地址但里面的数据已经不是原来的值了迭代器的含义发生了变化。如果 pos 正好指向最后一个元素删除后 pos 就变成了 end 位置end 位置没有有效数据去访问它也是非法的。补充缩容并不是 C 标准规定的行为不同的 STL 实现可能不同有的编译器会缩容有的不会但无论缩容与否erase 之后的迭代器都应该认为是失效的因为即使没有缩容迭代器指向的位置意义也已经发生了改变VS 系列Debug 模式做了非常严格的检查即使迭代器仅仅是意义改变并非野指针也会被检测出来并触发断言导致程序崩溃GLinux检查相对宽松即使迭代器已经失效访问时可能也不会报错能正常输出结果但这不代表迭代器是有效的迭代器失效小结vector 插入或删除操作对迭代器的影响插入或删除元素会导致当前迭代器及其之后所有元素的迭代器失效。这是因为插入时元素后移或扩容搬移数据迭代器指向的位置或内存发生变化删除时元素前移填补空缺迭代器指向的数据或语义发生改变解决办法在使用迭代器之前重新赋值即可。对于insertpos v.insert(pos, value);获取指向新插入元素的迭代器对于erasepos v.erase(pos);获取指向被删除元素下一个位置的迭代器重点就是进行插入或删除操作后原有的迭代器不再可靠。如果后续还需要通过迭代器操作 vector 中的元素必须用函数返回值对迭代器重新赋值获取新的有效迭代器。