目录

1.vector的介绍及使用

1.1 vector的介绍

1.2 vector的使用

 1.2.1 vector的定义

 1.2.2vector itertor的使用

 1.2.3 vector空间增长问题

 1.2.3vector增删查改

1.2.4 vector 迭代器失效问题。（重点）

1.2.5 vector 在OJ中的使用。（见博客）

2.vector深度剖析及模拟实现

 2.1 使用memcpy拷贝问题

2.2 对bit::vector核心接口的测试

2.3 动态二维数组理解

1.vector的介绍及使用

1.1 vector的介绍

vector - C++ Reference

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

1.2 vector的使用

vector学习时一定要学会查看文档：vector的文档介绍vector - C++ Reference，vector在实际中非常的重要，在实际中我们熟悉常见的接口就可以，下面列出了哪些接口是要重点掌握的。

 1.2.1 vector的定义

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

 1.2.2vector itertor的使用

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

 1.2.3 vector空间增长问题

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

// vector::capacity#include #include int main(){size_t sz;std::vector foo;sz = foo.capacity();std::cout << "making foo grow:\n";for (int i = 0; i < 100; ++i) {foo.push_back(i);if (sz != foo.capacity()) {sz = foo.capacity();std::cout << "capacity changed: " << sz << '\n';}}}vs：运行结果：making foo grow :capacity changed : 1capacity changed : 2capacity changed : 3capacity changed : 4capacity changed : 6capacity changed : 9capacity changed : 13capacity changed : 19capacity changed : 28capacity changed : 42capacity changed : 63capacity changed : 94capacity changed : 141g++运行结果：making foo grow :capacity changed : 1capacity changed : 2capacity changed : 4capacity changed : 8capacity changed : 16capacity changed : 32capacity changed : 64capacity changed : 128

// vector::reserve#include #include int main(){size_t sz;std::vector foo;sz = foo.capacity();std::cout << "making foo grow:\n";for (int i = 0; i < 100; ++i) {foo.push_back(i);if (sz != foo.capacity()) {sz = foo.capacity();std::cout << "capacity changed: " << sz << '\n';}}std::vector bar;sz = bar.capacity();bar.reserve(100); // this is the only difference with foo abovestd::cout << "making bar grow:\n";for (int i = 0; i < 100; ++i) {bar.push_back(i);if (sz != bar.capacity()) {sz = bar.capacity();std::cout << "capacity changed: " << sz << '\n';}}return 0;}

// vector::resize#include #include int main(){std::vector myvector;// set some initial content:for (int i = 1; i < 10; i++)myvector.push_back(i);myvector.resize(5);myvector.resize(8, 100);myvector.resize(12);std::cout << "myvector contains:";for (int i = 0; i < myvector.size(); i++)std::cout << ' ' << myvector[i];std::cout << '\n';return 0;}

 1.2.3vector增删查改

// push_back/pop_back#include #include using namespace std;int main(){int a[] = { 1, 2, 3, 4 };vector v(a, a + sizeof(a) / sizeof(int));vector::iterator 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;return 0;}

// find / insert / erase#include #include #include using namespace std;int main(){int a[] = { 1, 2, 3, 4 };vector v(a, a + sizeof(a) / sizeof(int));// 使用find查找3所在位置的iteratorvector::iterator pos = find(v.begin(), v.end(), 3);// 在pos位置之前插入30v.insert(pos, 30);vector::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;return 0;}

// operator[]+index 和 C++11中vector的新式for+auto的遍历// vector使用这两种遍历方式是比较便捷的。#include #include using namespace std;int main(){int a[] = { 1, 2, 3, 4 };vector v(a, a + sizeof(a) / sizeof(int));// 通过[]读写第0个位置。v[0] = 10;cout << v[0] << endl;// 通过[i]的方式遍历vectorfor (size_t i = 0; i < v.size(); ++i)cout << v[i] << " ";cout << endl;vector swapv;swapv.swap(v);cout << "v data:";for (size_t i = 0; i < v.size(); ++i)cout << v[i] << " ";cout << endl;cout << "swapv data:";for (size_t i = 0; i < swapv.size(); ++i)cout << swapv[i] << " ";cout << endl;// C++11支持的新式范围for遍历for (auto x : v)cout << x << " ";cout << endl;return 0;}

1.2.4 vector 迭代器失效问题。（重点）

迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了 封装 ，比如： vector 的迭代器就是原生态指针 T* 。因此 迭代器失效，实际就是迭代器底层对应指针所指向的 空间被销毁了，而使用一块已经被释放的空间 ，造成的后果是程序崩溃 ( 即 如果继续使用已经失效的迭代器， 程序可能会崩溃 ) 。对于vector 可能会导致其迭代器失效的操作有： 1. 会引起其底层空间改变的操作，都有可能是迭代器失效 ，比如： resize 、 reserve 、 insert 、 assign 、push_back等。

#include using namespace std;#include int main(){vector v{ 1,2,3,4,5,6 };auto it = v.begin();// 将有效元素个数增加到100个，多出的位置使用8填充，操作期间底层会扩容// v.resize(100, 8);// reserve的作用就是改变扩容大小但不改变有效元素个数，操作期间可能会引起底层容量改变// v.reserve(100);// 插入元素期间，可能会引起扩容，而导致原空间被释放// v.insert(v.begin(), 0);    // v.push_back(8); // 给vector重新赋值，可能会引起底层容量改变v.assign(100, 8);/*出错原因：以上操作，都有可能会导致vector扩容，也就是说vector底层原理旧空间被释放掉，   而在打印时，it还使用的是释放之间的旧空间，在对it迭代器操作时，实际操作的是一块已经被释放的   空间，而引起代码运行时崩溃。解决方式：在以上操作完成之后，如果想要继续通过迭代器操作vector中的元素，只需给it重新   赋值即可。*/while (it != v.end()){cout << *it << " ";++it;}cout << endl;return 0;}

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

#include using namespace std;#include int main(){int a[] = { 1, 2, 3, 4 };vector v(a, a + sizeof(a) / sizeof(int));// 使用find查找3所在位置的iteratorvector::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 就认为该位置迭代器失效了。 以下代码的功能是删除 vector 中所有的偶数，请问那个代码是正确的，为什么？

#include using namespace std;#include int main(){vector 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 v{ 1, 2, 3, 4 };auto it = v.begin();while (it != v.end()){if (*it % 2 == 0)it = v.erase(it);else++it;}return 0;}

迭代器失效解决办法：在使用前，对迭代器重新赋值即可。

1.2.5 vector 在OJ中的使用。（见博客）

2.vector深度剖析及模拟实现

2.1 std::vector的核心框架接口的模拟实现 bit::vector  

#include using namespace std;#include // 注意这里namespace大家下去就不要取名为bit了，否则出去容易翻车。^^namespace bit{templateclass vector{public:// Vector的迭代器是一个原生指针typedef T* iterator;typedef const T* const_iterator;iterator begin() { return _start; }iterator end() { return _finish; }const_iterator cbegin() const { return _start; }const_iterator cend() const { return _finish; }// construct and destroyvector(): _start(nullptr), _finish(nullptr), _endOfStorage(nullptr){}vector(int n, const T& value = T()): _start(nullptr), _finish(nullptr), _endOfStorage(nullptr){reserve(n);while (n--){push_back(value);}}// 若使用iterator做迭代器，会导致初始化的迭代器区间[first,last)只能是vector的迭代器// 重新声明迭代器，迭代器区间[first,last)可以是任意容器的迭代器templatevector(InputIterator first, InputIterator last){reserve(last - first);while (first != last){push_back(*first);++first;}}vector(const vector& v): _start(nullptr), _finish(nullptr), _endOfStorage(nullptr){reserve(v.capacity());iterator it = begin();const_iterator vit = v.cbegin();while (vit != v.cend()){*it++ = *vit++;}}vector& operator=(vector v){swap(v);return *this;}~vector(){delete[] _start;_start = _finish = _endOfStorage = nullptr;}// capacitysize_t size() const { return _finish - _start; }size_t capacity() const { return _endOfStorage - _start; }bool empty() const { return _first == _finish; }void reserve(size_t n){if (n > capacity()){size_t oldSize = size();T* tmp = new T[n];// 这里直接使用memcpy?//if (_start)// memcpy(tmp, _start, sizeof(T)*size);if (_start){for (size_t i = 0; i < oldSize; ++i)tmp[i] = _start[i];}_start = tmp;_finish = _start + oldSize;_endOfStorage = _start + n;}}void resize(size_t n, const T& value = T()){// 1.如果n小于当前的size，则数据个数缩小到nif (n  capacity())reserve(n);// 3.将size扩大到niterator it = _finish;_finish = _start + n;while (it != _finish){*it = value;++it;}}///access///T& operator[](size_t pos) { return _start[pos]; }const T& operator[](size_t pos)const { return _start[pos]; }///modify/void push_back(const T& x) { insert(end(), x); }void pop_back() { erase(--end()); }void swap(vector& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endOfStorage, v._endOfStorage);}iterator insert(iterator pos, const T& x){assert(pos = pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;}// 返回删除数据的下一个数据 // 方便解决:一边遍历一边删除的迭代器失效问题iterator erase(iterator pos){// 挪动数据进行删除iterator begin = pos + 1;while (begin != _finish) {*(begin - 1) = *begin;++begin;}--_finish;return pos;}private:iterator _start; // 指向数据块的开始iterator _finish; // 指向有效数据的尾iterator _endOfStorage; // 指向存储容量的尾};}

 swap接口

 2.1使用memcpy拷贝问题

假设模拟实现的vector中的reserve接口中，使用memcpy进行的拷贝，以下代码会发生什么问题？

int main(){ bite::vector v; v.push_back("1111"); v.push_back("2222"); v.push_back("3333"); return 0; }

问题分析： 1. memcpy 是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中 2. 如果拷贝的是自定义类型的元素， memcpy 即高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy 的拷贝实际是浅拷贝。

 结论：如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。

2.2 对bit::vector核心接口的测试

// constructing vectorsvoid TestVector1(){// constructors used in the same order as described above:bite::vector first; // empty vector ofintsbite::vector second(4, 100); // four ints with value 100bite::vector third(second.Begin(), second.End()); // iterating through secondbite::vector fourth(third); // a copy of third// the iterator constructor can also be used to construct from arrays:int myints[] = { 16, 2, 77, 29 };bit::vector fifth(myints, myints + sizeof(myints) / sizeof(int));std::cout << "The contents of fifth are:";for (bit::vector::iterator it = fifth.begin(); it != fifth.end(); ++it)std::cout << *it << " ";std::cout << endl;// 测试T是string时，拷贝问题bit::vector strV;strV.PushBack("1111");strV.PushBack("2222");strV.PushBack("3333");strV.PushBack("4444");for (size_t i = 0; i < strV.size(); ++i){cout << strV[i] << " ";}cout << endl;}//vector iterator的使用void PrintVector(const bite::vector& v) {// 使用const迭代器进行遍历打印bit::vector::const_iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;}void TestVector2(){// 使用push_back插入4个数据bite::vector v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);PrintVector(v);// 使用迭代器进行修改auto it = v.begin();while (it != v.end()){*it *= 2;++it;}PrintVector(v);// 这里可以看出C++11支持iterator及接口，就支持范围forfor (auto e : v)cout << e << " ";}// find / insert / erasevoid TestVector3(){int a[] = { 1, 2, 3, 4 };bite::vector v(a, a + sizeof(a) / sizeof(a[0]));// 使用find查找3所在位置的iteratorauto pos = find(v.begin(), v.end(), 3);// 在pos位置之前插入30v.insert(pos, 30);PrintVector(v);// 删除pos位置的数据pos = find(v.begin(), v.end(), 3);v.Erase(pos);PrintVector(v);}// iterator失效问题void TestVector4(){int a[] = { 1, 2, 3, 4 };bite::vector v(a, a + sizeof(a) / sizeof(a[0]));// 删除pos位置的数据，导致pos迭代器失效auto pos = find(v.begin(), v.end(), 3);v.erase(pos);cout << *pos << endl; // 此处会导致非法访问// 在pos位置插入数据，导致pos迭代器失效。// insert会导致迭代器失效，是因为insert可// 能会导致增容，增容后pos还指向原来的空间，而原来的空间已经释放了。pos = find(v.begin(), v.end(), 3);v.insert(pos, 30);cout << *pos << endl; // 此处会导致非法访问// 实现删除v中的所有偶数// 下面的程序会崩溃掉，如果是偶数，erase导致it失效 // 对失效的迭代器进行++it，会导致程序崩溃auto it = v.begin();while (it != v.end()){if (*it % 2 == 0)v.erase(it);++it;}// 以上程序要改成下面这样，erase会返回删除位置的下一个位置it = v.begin();while (it != v.end()){if (*it % 2 == 0)it = v.erase(it);else++it;}}

2.3 动态二维数组理解

// 以杨慧三角的前n行为例：假设n为5void test5(size_t n) {// 使用vector定义二维数组vv，vv中的每个元素都是vectorbit::vector<bit::vector> vv(n);// 将二维数组每一行中的vecotr中的元素全部设置为1for (size_t i = 0; i < n; ++i)vv[i].resize(i + 1, 1);// 给杨慧三角出第一列和对角线的所有元素赋值for (int i = 2; i < n; ++i){for (int j = 1; j < i; ++j){vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];}}}

bit::vector<bit::vector> vv(n);

vv(n) ; 构造一个 vv 动态二维数组， vv 中总共有 n 个元素，每个元素都是 vector 类 型的，每行没有包含任何元素，如果 n 为 5 时如下所示：

 vv中元素填充完成之后，如下图所示：

 使用标准库中vector构建动态二维数组时与上图实际是一致的。