C++第十弹 ---- vector的介绍及使用

前言

本文介绍了C++中的vector数据结构及其使用方法。

更多好文, 持续关注 ~ 酷酷学!!!

---

正文开始

vector的介绍及使用

1. vector是表示可变大小数组的序列容器.
2. 就像数组一样, vector也采用的连续存储空间来存储元素. 也就是意味着可以采用下标对vector的元素进行访问, 和数组一样高效. 但是又不像数组, 它的大小是可以动态改变的, 而且它的大小会被容器自动处理.
3. 本质讲, vector使用动态分配数组来存储它的元素. 当新元素插入的时候, 这个数组需要被重新分配大小为了增加存储空间, 其做法是, 分配一个新的数组, 然后讲全部元素移动到这个数组, 就时间而言, 这是一个相对代价高的任务, 因为每当一个新的元素加入到容器的时候, vector并不会每次都重新分配大小.
4. vector分配空间策略: vector会分配一些额外的空间以适应可能的增长, 因为存储空间比实际比实际需要的存储空间更大. 不同的库采用不同的策略权衡空间的使用和重新分配, 但是无论如何, 重新分配都应该是对数增长的间隔大小, 以至于在末尾插入一个元素的时候是在常数时间复杂度完成的.
5. 因此,vector占用了更多的存储空间, 为了获得管理存储空间的能力, 并且以一种有效的方式动态增长
6. 与其它动态序列容器相比(deque,list and forward_list) , vector在访问元素的时候更加高效, 在末尾添加和删除元素相对高效, 对于其他不在末尾的删除和插入操作, 效率更低, 比起list和forward_list 统一的迭代器和引用更好

使用STL的三个三个境界: 能用, 明理, 能拓展, 下面讲详细介绍STL – vector

---

1. vector的使用

我们先来查看vector的文档介绍, vector在实际中非常重要, 在实际中我们熟悉常见的接口就可以.

• 成员函数
  

1.1 vector的定义

代码演示:

int TestVector1()
{// constructors used in the same order as described above:vector<int> first;                                // empty vector of intsvector<int> second(4, 100);                       // four ints with value 100vector<int> third(second.begin(), second.end());  // iterating through secondvector<int> fourth(third);                       // a copy of third// 下面涉及迭代器初始化的部分，我们学习完迭代器再来看这部分// the iterator constructor can also be used to construct from arrays:int myints[] = { 16,2,77,29 };vector<int> fifth(myints, myints + sizeof(myints) / sizeof(int));cout << "The contents of fifth are:";for (vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)cout << ' ' << *it;cout << '\n';return 0;
}

1.2 iterator的使用

代码演示:

void PrintVector(const vector<int>& v)
{// const对象使用const迭代器进行遍历打印vector<int>::const_iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;
}void TestVector2()
{// 使用push_back插入4个数据vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);// 使用迭代器进行遍历打印vector<int>::iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;// 使用迭代器进行修改it = v.begin();while (it != v.end()){*it *= 2;++it;}// 使用反向迭代器进行遍历再打印// vector<int>::reverse_iterator rit = v.rbegin();auto rit = v.rbegin();while (rit != v.rend()){cout << *rit << " ";++rit;}cout << endl;PrintVector(v);
}

1.3 vector空间增长问题

1. capacity的代码在vs和g++下分别运行会发现, vs下capacity是按照1.5倍增长的, g++是按2倍进行增长的, 这个问题经常会考察, 不要固化的认为, vector增容都是2倍, 具体增长多少是根据具体的需求定义的, vs是PJ版本STL, g++是SGI版本STL.
2. reserve只负责开辟空间, 如果确定知道需要用多少空间, reverse可以缓解vector增容的代价缺陷问题
3. resize在开空间的同时还会进行初始化, 影响size.

可以执行下面代码在VS和g++编译器分别进行测试vector的扩容机制

// 测试vector的默认扩容机制
void TestVectorExpand()
{size_t sz;vector<int> v;sz = v.capacity();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';}}
}vs：运行结果：vs下使用的STL基本是按照1.5倍方式扩容
making foo grow :
capacity changed : 1
capacity changed : 2
capacity changed : 3
capacity changed : 4
capacity changed : 6
capacity changed : 9
capacity changed : 13
capacity changed : 19
capacity changed : 28
capacity changed : 42
capacity changed : 63
capacity changed : 94
capacity changed : 141g++运行结果：linux下使用的STL基本是按照2倍方式扩容
making foo grow :
capacity changed : 1
capacity changed : 2
capacity changed : 4
capacity changed : 8
capacity changed : 16
capacity changed : 32
capacity changed : 64
capacity changed : 128

如果已经确定好vector中要存储元素的大概个数, 可以提前将空间设置足够,就可以避免边插入边扩容导致效率低下的问题了

举个例子:

void TestVectorExpandOP()
{vector<int> v;size_t sz = v.capacity();v.reserve(100); // 提前将容量设置好，可以避免一遍插入一遍扩容cout << "making bar 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';}}
}

1.4 vector增删查改

代码演示:
尾插和尾删: push_back和pop_back

void TestVector4()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);auto it = v.begin();while (it != v.end()) {cout << *it << " ";++it;}cout << endl;v.pop_back();v.pop_back();it = v.begin();while (it != v.end()) {cout << *it << " ";++it;}cout << endl;
}

在任意位置插入: insert和erase, 以及查找find
注意: find不是vector自身提供的方法, 是STL提供的算法模块, 使用时需要包含< algorithm >头文件

void TestVector5()
{// 使用列表方式初始化，C++11新语法vector<int> v{ 1, 2, 3, 4 };// 在指定位置前插入值为val的元素，比如：3之前插入30,如果没有则不插入// 1. 先使用find查找3所在位置// 注意：vector没有提供find方法，如果要查找只能使用STL提供的全局findauto pos = find(v.begin(), v.end(), 3);if (pos != v.end()){// 2. 在pos位置之前插入30v.insert(pos, 30);}vector<int>::iterator it = v.begin();while (it != v.end()) {cout << *it << " ";++it;}cout << endl;pos = find(v.begin(), v.end(), 3);// 删除pos位置的数据v.erase(pos);it = v.begin();while (it != v.end()) {cout << *it << " ";++it;}cout << endl;
}

operator[]+index 和 C++11中vector的新式for+auto的遍历
vector使用这两种遍历方式是比较便捷的

void TestVector6()
{vector<int> v{ 1, 2, 3, 4 };// 通过[]读写第0个位置。v[0] = 10;cout << v[0] << endl;// 1. 使用for+[]小标方式遍历for (size_t i = 0; i < v.size(); ++i)cout << v[i] << " ";cout << endl;vector<int> swapv;swapv.swap(v);cout << "v data:";for (size_t i = 0; i < v.size(); ++i)cout << v[i] << " ";cout << endl;// 2. 使用迭代器遍历cout << "swapv data:";auto it = swapv.begin();while (it != swapv.end()){cout << *it << " ";++it;}// 3. 使用范围for遍历for (auto x : v)cout << x << " ";cout << endl;
}

2. vector迭代器失效问题(重点)

迭代器的主要作用就是让算法能够不用关心底层的数据结构, 其底层实际就是一个指针, 或者是对指针进行了封装, 比如: vector的迭代器就是原生态指针T* , 因此迭代器失效, 实际就是迭代器底层对应指针所指向的空间被销毁了, 而使用的一块已经被释放的空间, 造成的后果是程序崩溃, 即如果继续使用已经失效的迭代器, 程序可能会崩溃.

对于vector可能会导致其迭代器失效的操作有:

1. 会引起其底层空间改变的操作, 都有可能是迭代器失效, 如: resize, reserve, insert, assign, push_back等.

出错原因: 以下操作, 都有可能会导致vector扩容, 也就是说vector底层原理旧空间被释放掉, 而在打印的时候, it还使用的是释放之前的就空间, 在对it迭代器操作时, 实际操作的是一块被释放的空间, 而引起代码运行时崩溃.

int main()
{vector<int> v{ 1,2,3,4,5,6 };auto it = v.begin();v.resize(100, 8);//将有效元素个数增加到100个,多出的位置使用8填充,操作期间底层会扩容,其it不可以在使用v.reserve(100);//reserve的作用就是改变扩容大小但不改变有效元素个数,操作期间会引起底层容量改变,其it不可以在使用v.insert(v.begin(), 0);v.push_back(8);//插入元素期间,可能会引起扩容, 而导致原空间被释放,it不可以在使用v.assign(100, 8);//给vector重新赋值,可能会引起底层容量改变, 其it不可在使用while (it != v.end()){cout << *it << " ";++it;}cout << endl;return 0;
}

解决方式: 在以上操作完成之后, 如果想要继续通过迭代器操作vector中的元素, 只需给it重新赋值即可.

可以看到insert这里返回值为一个迭代器, 迭代器的位置位插入元素之后的下一个新位置, 我们可以用来接受新的迭代器

2. 指定位置元素的删除操作 – erase

int main()
{int a[] = { 1,2,3,4 };vector<int> v(a, a + sizeof(a) / sizeof(int));//使用find查找3所在位置的iteratorvector<int>::iterator pos = find(v.begin(), v.end(), 3);//删除pos位置的数据,导致pos迭代器失效v.erase(pos);cout << *pos << endl;return 0;
}

原因: erase删除pos位置元素后, pos位置之后的元素会往前挪动, 没有导致底层空间的改变, 理论上讲迭代器不应该改变, 但是: 如果pos位置刚好是最后一个位置, 删完之后pos刚好就是end的位置, 而end位置是没有元素的, 那么pos就失效了, 因此删除vector中任意位置上元素时, vs就认为该位置迭代器失效了.

---

当然, vs也给出了解决方案, 如果还想访问it则编译器会将新的it作为函数返回值

一个指向函数调用后最后被删除元素的下一个位置的迭代器。如果操作删除了序列中的最后一个元素，那么就是容器的末尾。

错误写法

int main()
{vector<int> v{ 1,2,3,4 };auto it = v.begin();while (it != v.end()){if (*it % 2 == 0){v.erase(it);}++it;}return 0;
}

正确写法:

int main()
{vector<int> v{ 1,2,3,4 };auto it = v.begin();while (it != v.end()){if (*it % 2 == 0){it = v.erase(it);}++it;}return 0;
}

3. 注意: Linux下,g++编译器对迭代器失效的检测并不是非常严格, 处理也没有vs下极端.

下面来看看Linux下的迭代器

• 扩容之后, 迭代器已经失效了, 程序虽然可以运行, 但是运行结果已经不对了

int main()
{vector<int> v{1,2,3,4,5};for(size_t i = 0; i < v.size(); ++i)cout << v[i] << " ";cout << endl;auto it = v.begin();cout << "扩容之前，vector的容量为: " << v.capacity() << endl;// 通过reserve将底层空间设置为100，目的是为了让vector的迭代器失效 v.reserve(100);cout << "扩容之后，vector的容量为: " << v.capacity() << endl;// 经过上述reserve之后，it迭代器肯定会失效，在vs下程序就直接崩溃了，但是linux下不会// 虽然可能运行，但是输出的结果是不对的while(it != v.end()){cout << *it << " ";++it;}cout << endl;return 0;
}程序输出：
1 2 3 4 5 
扩容之前，vector的容量为: 5
扩容之后，vector的容量为: 100
0 2 3 4 5 409 1 2 3 4 5

• erase删除任意位置代码后, linux下迭代器并没有失效, 因为空间还是原来的空间, 后序元素往前搬移了, it的位置还是有效的

int main()
{vector<int> v{ 1,2,3,4,5 };vector<int>::iterator it = find(v.begin(), v.end(), 3);v.erase(it);cout << *it << endl;while (it != v.end()){cout << *it << " ";++it;}cout << endl;return 0;
}程序可以正常运行，并打印：
4
4 5

但是, erase删除的迭代器如果是最后一个元素, 删除之后it已经超过end, 此时迭代器是无效的, ++it导致程序崩溃

int main()
{vector<int> v{1,2,3,4,5};// vector<int> v{1,2,3,4,5,6};auto it = v.begin();while(it != v.end()){if(*it % 2 == 0)v.erase(it)}for(auto e : v)cout << e << " ";cout << endl;return 0;
}========================================================
// 使用第一组数据时，程序可以运行
[sly@VM-0-3-centos 20220114]$ g++ testVector.cpp -std=c++11
[sly@VM-0-3-centos 20220114]$ ./a.out
1 3 5 
=========================================================
// 使用第二组数据时，程序最终会崩溃
[sly@VM-0-3-centos 20220114]$ vim testVector.cpp 
[sly@VM-0-3-centos 20220114]$ g++ testVector.cpp -std=c++11
[sly@VM-0-3-centos 20220114]$ ./a.out
Segmentation fault

从上述三个例子中可以看到: SGI STL中, 迭代器失效后, 代码并不一定会崩溃, 但是运行结果肯定不对, 如果it不在begin和end范围内, 肯定会崩溃的.

---

• 与vector类似, string在插入+扩容操作+erase之后, 迭代器也会失效

这里代码放开后会崩溃, 因为resize到20, string会进行扩容, 扩容之后, it指向之前的旧空间就已经被释放了, 该迭代器就失效了, 后续打印时, 在访问it指向的空间程序就会崩溃.

int main()
{string s("hello");auto it = s.begin();//s.resize(20, '!');while (it != s.end()){cout << *it;++it;}cout << endl;return 0;
}

erase也是如此

int main()
{string s("hello");auto it = s.begin();while (it != s.end()){s.erase(it);//错误写法it = s.erase(it);//++it;}return 0;
}

总结一下: 迭代器的解决办法, 在使用之前, 对迭代器重新赋值即可.

总结

vector是可变大小的数组，能够动态调整其存储容量。
通过下标访问vector中元素的效率与数组相同，但其大小由容器自动管理。
在扩容时，vector会分配额外的空间，从而提高末尾插入元素的效率。
vector支持通过迭代器高效访问元素，但在增删操作中迭代器可能失效。
调用reserve可以提前分配空间，减少扩容的性能损失。
vector中的元素可以通过多种方式插入和删除，包括在中间位置插入以及尾部的增删。
在操作vector时，若要继续使用迭代器，需重新赋值以避免失效。

---

完