【本节目标】
- 1.vector的介绍及使用
- 2.vector深度剖析及模拟实现
1.vector的介绍及使用
1.1 vector的介绍
- 1. vector是表示可变大小数组的序列容器。
- 2. 就像数组一样，vector也采用连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
- 3. 本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。
- 4. vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
- 5. 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
- 6. 与其它动态序列容器相比（deque, list and forward_list）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起list和forward_list 统一的迭代器和引用更好。
1.2 vector的使用
vector学习时一定要学会查看文档：vector的文档介绍，vector在实际中非常的重要，在实际中我们熟悉常 见的接口就可以，下面列出了哪些接口是要重点掌握的。
1.2.1 vector的定义
我们先来看一下vector文档中的构造函数
我们先来直接看看第二个构造函数的使用：创建一个包含n个元素的容器。每个元素都是val的副本
void test1() { vector<int> v(10, 1); for (auto e : v) { cout << e << " "; } cout << endl; }
运行结果：
我们再来看看第三个构造函数：创建一个包含与范围 [first, last) 中的元素数量相同的容器，每个元素都是从该范围中对应元素构造而来的，顺序相同。
void test2() { vector<int> v1(10, 1); vector<int> v2(v1.begin(), v1.end()); vector<int>::iterator it1 = v2.begin(); while (it1 != v2.end()) { cout << *it1 << " "; ++it1; } cout << endl; }
运行结果：
我们这里的迭代器区间能不能是其他容器，比如string。
void test3() { string str("hello world"); //vector<int> v2(str.begin(), str.end()); //string是char类型，这里模板参数需要转为char //如果为int则会输出字符对应的ASCII码值 vector<char> v2(str.begin(), str.end()); for (size_t i = 0; i < v2.size(); i++) { cout << v2[i] << " "; } cout << endl; }
那在这里就要提出一个问题了，能不能用vector替代string呢？
肯定不可以，虽然string的有些功能可以通过vector实现，但是string中还提供了插入一个字符串的功能，vector只能插入单个字符。同时有些库函数或接口可能期望传递的是以 null 结尾的 C 风格字符串，而 vector 不会在末尾添加 null 终止字符。在这种情况下，使用 string 更方便，因为它保证末尾有 null 终止字符。
1.2.2 vector iterator 的使用
void test4() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); vector<int>::iterator it1 = v.begin(); while (it1 != v.end()) { cout << *it1 << " "; ++it1; } cout << endl; vector<int>::reverse_iterator it2 = v.rbegin(); while (it2 != v.rend()) { cout << *it2 << " "; ++it2; } cout << endl; }
运行结果：
1.2.3 vector 空间增长问题
capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。 这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义 的。vs是PJ版本STL，g++是SGI版本STL。
// 测试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倍方式扩容
linux下的情况是怎么样的呢？我们去验证一下
结论：g++运行结果：linux下使用的STL基本是按照2倍方式扩容
为了解决上面多次开辟空间造成的消耗，我们可以提前开辟空间，我们是用reserve还是resize呢？
reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。而resize在开空间的同时还会进行初始化，影响size。
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'; } } }
vs上一般是不会缩容的，如果我们想要缩容呢？我们就可以使用C++11提供的缩容函数。
void test6() { vector<int> v; for (int i = 0; i < 100; ++i) { v.push_back(i); } cout << v.size() << endl; cout << v.capacity() << endl; v.resize(10);//不缩容 cout << v.size() << endl; cout << v.capacity() << endl; v.shrink_to_fit(); cout << v.size() << endl; cout << v.capacity() << endl; }
运行结果：
1.2.4 vector 增删查改
相比string容器的insert，这里vector容器提供的insert就简洁了很多。
我们知道string都是使用的下标，而这里的vector都是使用的迭代区间。
void test7() { vector<int> v; //尾插 v.push_back(2); v.push_back(3); v.push_back(4); for (auto e : v) { cout << e << " "; } cout << endl; //头插 v.insert(v.begin(), 1); for (auto e : v) { cout << e << " "; } cout << endl; }
运行结果：
如果我们想在元素3的位置之前插入一个30呢？可以使用find函数找到元素3的下标，但是我们在vector里面没有找到find函数！！！
注意：find这个函数是算法模块实现，不是vector的成员接口。
问题：为什么string容器要单独写一个find函数，而不直接像vector一样直接使用算法里面的find呢？
string容器除了查找字符，有时候还会查找字符串，使用算法模块的find函数不太方便，同时string类返回下标才能和其他函数接口更好匹配，而算法模块里面的find函数返回的是迭代器。
void test7() { vector<int> v; //尾插 v.push_back(2); v.push_back(3); v.push_back(4); for (auto e : v) { cout << e << " "; } cout << endl; //头插 v.insert(v.begin(), 1); for (auto e : v) { cout << e << " "; } cout << endl; vector<int>::iterator it = find(v.begin(), v.end(), 3); //中间插入,如果找不到就不插入 if(it != v.end()) { v.insert(it, 30); } for (auto e : v) { cout << e << " "; } cout << endl; }
运行结果：
注意：对于 vector 来说，它本身不提供流插入和流提取运算符的重载（<< 和 >>），因为这些运算符的行为和预期对于一系列同类型元素的容器并不明确。
- 输出操作的歧义性： vector 可能包含大量元素，直接使用流插入操作符 << 输出整个容器可能会导致输出过于庞大，不方便进行控制。
- 输入操作的难以解释性： 对于流提取运算符 >>，尝试从流中提取元素并放入 std::vector 时可能需要解决一些语义上的歧义问题。比如，应该如何确定输入流的结束以停止提取？如果元素类型没有默认构造函数，又该如何处理？
我们一般通过下面的方式去遍历访问。
//下标 + [] for (size_t i = 0; i < v.size(); i++) { cout << v[i] << " "; } cout << endl; //迭代器 vector<int>::iterator it1 = v.begin(); while (it1 != v.end()) { cout << *it1 << " "; ++it1; } cout << endl; //范围for for (auto e : v) { cout << e << " "; } cout << endl;
1.2.5 vector 在OJ中的使用
class Solution{ public: int singleNumber(vector<int>&nums) { int value = 0; for (auto e : nums) { value ^= e; } return value; } };
我们先来介绍一个这个返回值类型是怎么个事儿。
// 涉及resize / operator[] // 核心思想：找出杨辉三角的规律，发现每一行头尾都是1，中间第[j]个数等于上一行[j-1]+[j] class Solution { public: vector<vector<int>> generate(int numRows) { vector<vector<int>> vv(numRows); for (int i = 0; i < numRows; ++i) { vv[i].resize(i + 1, 1); } for (int i = 2; i < numRows; ++i) { for (int j = 1; j < i; ++j) { vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1]; } } return vv; } };
【探索C++容器：vector的使用和模拟实现】（二）：https://developer.aliyun.com/article/1425781
