4、vector对象修改操作
- 使用示例：
void test_vector4() { int a1[] = { 1, 2, 3, 4 }; vector<int> v1(a1, a1 + sizeof(a1) / sizeof(int)); vector<int>::iterator it1 = v1.begin(); while (it1 != v1.end()) { cout << *it1 << " "; ++it1; } cout << endl; v1.pop_back(); v1.pop_back(); it1 = v1.begin(); while (it1 != v1.end()) { cout << *it1 << " "; ++it1; } cout << endl; int a2[] = { 1, 2, 3, 4 }; vector<int> v2(a2, a2 + sizeof(a2) / sizeof(int)); // 使用find查找3所在位置的iterator vector<int>::iterator pos = find(v2.begin(), v2.end(), 3); // 在pos位置之前插入30 v2.insert(pos, 30); vector<int>::iterator it2 = v2.begin(); while (it2 != v2.end()) { cout << *it2 << " "; ++it2; } cout << endl; pos = find(v2.begin(), v2.end(), 3); // 删除pos位置的数据 v2.erase(pos); it2 = v2.begin(); while (it2 != v2.end()) { cout << *it2 << " "; ++it2; } cout << endl; int a3[] = { 1, 2, 3, 4 }; vector<int> v3(a3, a3 + sizeof(a3) / sizeof(int)); // 通过[]读写第0个位置 v3[0] = 10; cout << v3[0] << endl; // 通过[i]的方式遍历vector for (size_t i = 0; i < v3.size(); ++i) cout << v3[i] << " "; cout << endl; vector<int> swapv; swapv.swap(v3); cout << "v data:"; for (size_t i = 0; i < v3.size(); ++i) cout << v3[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 : v3) cout << x << " "; cout << endl; }
5、vector迭代器失效问题
- 概念：
迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装（比如：vector和string 迭代器就是原生态指针T*）
因此vector迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，或者在迭代器本身指向的意义改变了，不是我们所想的那样
vector迭代器失效操作：
会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_back等
本质上：使vector发生扩容，原来动态开辟的空间被释放，但是迭代器在扩容后没有更新，再次使用会报错
示例：
#include <iostream> using namespace std; #include <vector> int main() { vector<int> 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; }
- 指定位置元素的删除或者插入操作--erase/insert
本质上：删除或者插入操作后，使原来的迭代器指向的意义发生了改变
- 示例：
void testdemo1() { int a[] = { 1, 2, 3, 4 }; vector<int> v(a, a + sizeof(a) / sizeof(int)); // 使用find查找3所在位置的iterator vector<int>::iterator pos = find(v.begin(), v.end(), 3); // 删除pos位置的数据，导致pos迭代器失效，指向的意义发生改变（pos位置的内容是4，不是3了） v.erase(pos); cout << *pos << endl; // 此处是非法访问 //解决方案：pos = v.erase(pos);//接收返回值，pos指向删除元素的后一个元素 } void testdemo2() { int a[] = { 1, 2, 3, 4 }; vector<int> v(a, a + sizeof(a) / sizeof(int)); vector<int>::iterator pos = find(v.begin(), v.end(), 3); v.insert(pos, 6);//插入后pos迭代器失效，指向的意义发生改变（pos位置的内容是6，不是3了） //解决方案：pos=v.insert(pos, 6);//接收返回值，pos指向插入的新元素 cout << *pos << endl; }
- 解释：
- erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，但是，迭代器指代的意义发生改变，vs就认为该位置迭代器失效了（对于插入操作也同理）
- 迭代器失效解决办法：在使用前，更新迭代器
三、vector剖析及模拟实现
1、vector框架及常用接口展示
- 基本框架：
- 实现常用接口展示：
template<class T> class vector { public: // Vector的迭代器是一个原生指针 typedef T* iterator; typedef const T* const_iterator; //普通迭代器和const迭代器 iterator begin(); iterator end(); const_iterator begin()const; const_iterator end()const; //无参构造函数 vector(); //n个value构造函数 vector(int n, const T& value = T()); //迭代器构造 template<class InputIterator> vector(InputIterator first, InputIterator last); //拷贝构造 vector(const vector<T>& v); //赋值重载 vector<T>& operator= (vector<T> v); //析构 ~vector(); // capacity size_t size() const; size_t capacity() const; bool empty() const; //开空间 void reserve(size_t n); //开空间+初始化 void resize(size_t n, const T& value = T()); //下标重载 T& operator[](size_t pos); const T& operator[](size_t pos)const; //尾插 void push_back(const T& x); //尾删 void pop_back(); //交换 void swap(vector<T>& v); //插入和删除 iterator insert(iterator pos, const T& x); iterator erase(iterator pos); private: iterator _start; // 指向数据块的开始 iterator _finish; // 指向有效数据的尾 iterator _endOfStorage; // 指向存储容量的尾 };
2、vector模拟常用接口具体细节
注：模拟时为了避免与C++本身提供的vector造成命名冲突，我们选择在命名空间里进行实现
- 实现代码：
namespace cole { template<class T> class vector { public: //底层是连续开辟的空间，原生指针足够完成迭代器操作 typedef T* iterator; typedef const T* const_iterator; iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin()const { return _start; } const_iterator end()const { return _finish; } //空vector vector() :_start(nullptr) , _finish(nullptr) , _endOfStorage(nullptr) {} vector(int n, const T& value = T()) :_start(nullptr) , _finish(nullptr) , _endOfStorage(nullptr) { //一定要初始化（不初始化，成员变量为随机值，调用相关接口结果会存在问题，导致reserve会出现问题） reserve(n); for (int i = 0; i < n; i++) { //对于内置类型进行赋值，对于自定义类型，调用其复制重载函数（如string） _start[i] = value; } _finish = _start + n; } //模板类中可以存在模板函数 template<class InputIterator> vector(InputIterator first, InputIterator last) :_start(nullptr) , _finish(nullptr) , _endOfStorage(nullptr) { //复用接口 reserve(last - first); while (first != last) { push_back(*first); first++; } } vector(const vector<T>& v) :_start(nullptr) , _finish(nullptr) , _endOfStorage(nullptr) { reserve(v.capacity()); for (size_t i = 0; i < v.size(); i++) { //对于内置类型进行赋值，对于自定义类型，调用其复制重载函数（如string） _start[i] = v._start[i]; } _finish = _start + v.size(); } //现代式写法 vector<T>& operator= (vector<T> v) { swap(v); return *this; } ~vector() { //释放空间以及置空 if (_start) { delete[] _start; } _start = _finish = _endOfStorage = nullptr; } // capacity size_t size() const { return _finish - _start; } size_t capacity() const { return _endOfStorage - _start; } bool empty() const { return _start == _finish; } void reserve(size_t n) { if (n > capacity()) { //扩容会重新开辟空间，导致成员变量为nullptr，这里记录下必要数据 size_t sz = size(); iterator tmp = new T[n]; if (_start) { for (size_t i = 0; i < sz; i++) { //对于内置类型进行赋值，对于自定义类型，调用其复制重载函数（如string） tmp[i] = _start[i]; } delete[] _start; } _start = tmp; _finish = _start + sz; _endOfStorage = _start + n; } } void resize(size_t n, const T& value = T()) { //分情况操作 if (n < size()) { _finish = _start + n; } else { if (n > capacity()) { reserve(n); } while (_finish != _start + n) { *_finish = value; ++_finish; } } } T& operator[](size_t pos) { //pos的合理性 assert(pos < size()); return _start[pos]; } const T& operator[](size_t pos)const { //pos的合理性 assert(pos < size()); return _start[pos]; } void push_back(const T& x) { //vector满的情况 if (_finish == _endOfStorage) { reserve(capacity() == 0 ? 4 : capacity() * 2); } *_finish = x; _finish++; } void pop_back() { //pos的合理性 assert(size() > 0); _finish--; } //算法中提供的swap涉及多次深拷贝，这里自己实现，变量交换的效率高 void swap(vector<T>& v) { ::swap(_start, v._start); ::swap(_finish, v._finish); ::swap(_endOfStorage, v._endOfStorage); } iterator insert(iterator pos, const T& x) { if (_finish == _endOfStorage) { //扩容会重新开辟空间，这里记录下必要数据 size_t len = pos - _start; reserve(capacity() == 0 ? 4 : capacity() * 2); //扩容后pos会失效，更新pos位置 pos = _start + len; } iterator end = _finish; while (end != pos) { *end = *(end - 1); end--; } *pos = x; _finish++; return pos - 1; } iterator erase(iterator pos) { iterator cur = pos + 1; while (cur != _finish) { *(cur - 1) = *cur; ++cur; } --_finish; return pos; } private: iterator _start; // 指向数据块的开始 iterator _finish; // 指向有效数据的尾 iterator _endOfStorage; // 指向存储容量的尾 }; }
3、使用memcpy拷贝问题
假设模拟实现的vector中的reserve接口中，使用memcpy进行的拷贝，以下代码会发生什么问题？
int main() { cole::vector<cole::string> v; v.push_back("1111"); v.push_back("2222"); v.push_back("3333"); return 0; }
问题分析：
memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中
如果拷贝的是自定义类型的元素，memcpy即高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝
结论：如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃
4、动态二维数组理解
- 示例：
// 以杨慧三角的前n行为例：假设n为5 void test5(size_t n) { // 使用vector定义二维数组vv，vv中的每个元素都是vector<int> cole::vector<cole::vector<int>> vv(n); // 将二维数组每一行中的vecotr<int>中的元素全部设置为1 for (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]; } } }
cole::vector<cole::vector<int>> vv(n);
- 构造一个vv动态二维数组，vv中总共有n个元素，每个元素都是vector类型的，每行没有包含任何元素，如果n为5时如下所示：
vv中元素填充完成之后，如下图所示 ：
