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

#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位置的数据，导致pos迭代器失效。v.erase(pos);cout << *pos << endl; // 此处会导致非法访问return 0;
}

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

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

#include 
#include 
#include 
using namespace std;// 1. 扩容之后，迭代器已经失效了，程序虽然可以运行，但是运行结果已经不对了
int main()
{vector 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;
}

// 2. erase删除任意位置代码后，linux下迭代器并没有失效
// 因为空间还是原来的空间，后序元素往前搬移了，it的位置还是有效的
#inlcude 
#include 
#include 
using namespace std;int main()
{vector v{1,2,3,4,5};vector::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;
}

// 3: erase删除的迭代器如果是最后一个元素，删除之后it已经超过end
// 此时迭代器是无效的，++it导致程序崩溃
#inlcude 
#include 
#include 
using namespace std;int main()
{vector v{1,2,3,4,5};// vector v{1,2,3,4,5,6};auto it = v.begin();while(it != v.end()){if(*it % 2 == 0)v.erase(it);++it;}for(auto e : v)cout << e << " ";cout << endl;return 0;
}

• 使用第一组数据时，程序可以运行

• 使用第二组数据时，程序最终会崩溃

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

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

#include 
void TestString()
{string s("hello");auto it = s.begin();// 放开之后代码会崩溃，因为resize到20会string会进行扩容// 扩容之后，it指向之前旧空间已经被释放了，该迭代器就失效了// 后序打印时，再访问it指向的空间程序就会崩溃//s.resize(20, '!');while (it != s.end()){cout << *it;++it;}cout << endl;it = s.begin();while (it != s.end()){it = s.erase(it);// 按照下面方式写，运行时程序会崩溃，因为erase(it)之后// it位置的迭代器就失效了// s.erase(it);++it;}
}

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

💨1.2.7 vector 在OJ中的使用

链接：只出现一次的数字

• 解题思路：使用异或操作符 ^ —— 相同为 0，相异为 1

• 代码演示：

class Solution {
public:int singleNumber(vector& nums) {int ret = 0;//1、operator[]/*for(size_t i = 0; i < nums.size(); ++i){ret ^= nums[i];}*///2、迭代器/*vector::iterator it = nums.begin();while(it != nums.end()){ret ^= *it;++it;}*///3、范围forfor(auto e : nums){ret ^= e;}return ret;}
};

链接：杨辉三角

• 解题思路：需要先生成一个杨辉三角，每行的第一个和最后一个是 1，其余设置为 0，如果是 0，则需要计算。这里可以发现规律：1 = 1 + (1 - 1)，这里以第一个要计算的值为例，且这里的数字代表的下标 —— 第 3 行以 1 为下标位置的值是等于第 2 行以 1 为下标的值加上第 2 行以 1 - 1 为下标的值

• 代码演示：

class Solution {
public://vector>就是一个二维数组vector> generate(int numRows) {vector> vv;vv.resize(numRows);//生成for(size_t i = 0; i < vv.size(); ++i){//每行有多少个,并初始化为0vv[i].resize(i + 1, 0);//每一行的第一个和最后一个赋值为1/*vv[i].front() = 1;vv[i].back() = 1;*/vv[i][0] = 1;vv[i][vv[i].size() - 1] = 1; }//遍历for(size_t i = 0; i < vv.size(); ++i){for(size_t j = 0; j < vv[i].size(); ++j){if(vv[i][j] == 0)//需要处理{vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];}}}return vv;}
};

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

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

//
//  main.cpp
//  模拟实现vector
//
//  Created by 卜绎皓 on 2022/10/20.
//#include
#include
#include
#include
#include
using namespace std;#pragma oncenamespace byh
{templateclass vector{public:// Vector的迭代器是一个原生指针typedef T* iterator;typedef const T* const_iterator;// 迭代器相关iterator begin(){return _start;}const_iterator begin() const{return _start;}iterator end(){return _finish;}const_iterator end() const{return _finish;}// 构造和销毁vector(): _start(nullptr), _finish(nullptr), _endofstorage(nullptr){}//类模板的成员函数还可以再定义模板参数,这样写的好处是first/last可以是list等其它容器的迭代器,只要它解引用后的类型与T匹配templatevector(InputIterator first, InputIterator last): _start(nullptr), _finish(nullptr), _endofstorage(nullptr){//reserve(?)这个构造函数里传的是一段迭代器区间,只有对象才知道你有多少个容量while(first != last){push_back(*first);++first;}}//v2(v1)//1、传统写法/*vector(const vector& v){_start = new T[v.capacity()];memcpy(_start, v._start, sizeof(T) * v.size());_finish = _start + v.size();_endofstorage = _start + v.capacity();}*///2、传统写法————复用当前的一些接口,本质还是自己开空间,这里相对于现代写法更推荐第二种传统写法,因为它这里提前把空间开好了,并利用/*vector(const vector& v): _start(nullptr), _finish(nullptr), _endofstorage(nullptr){reserve(v.capacity());//一次性开好空间for(const auto& e : v)//引用的作用是为了防止T是string等{push_back(e);}}*///3、现代写法,sring那我们是取_str来构造一个临时对象再交换,但是这里怎么取所有的数据来构造并交换呢,没有法子//这里有个法子：vector的构造函数里还提供了一个显示的迭代器(它可以传其它容器或原生指针做迭代器,但是原生指针必须要求指向的空间是连续的)//所以这里还需要构造一个函数,这里的现代写法对比上面的传统写法并没有讨到便宜()vector(const vector& v): _start(nullptr), _finish(nullptr), _endofstorage(nullptr){//现代写法里提前开空间没有意义,因为现代写法的空间是tmp去搞的,tmp没办法自己开,因为它不知道有多少个数据,那有人说用last－first,不敢减,因为比如list是不支持减的,它不是一段连续的空间vector tmp(v.begin(), v.end());swap(tmp);}void swap(vector& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}//v1 = v4;//1、传统写法————不推荐(如果你能掌握现代写法,任何容器的深拷贝都推荐现代写法,尤其是赋值操作)/*vector& operator=(const vector& v){if(this != &v){delete[]_start;_start = _finish = _endofstorage = nullptr;reserve(v.capacity());for(const auto& e : v){push_back(e);}}return *this;}*///2、现代写法,v就是去深拷贝的v4vector& operator=(vector v){//v是v1想要的,所以v1和v交换swap(v);return *this;}~vector(){delete[] _start;_start = _finish = _endofstorage = nullptr;}size_t size() const{return _finish - _start;}size_t capacity() const{return _endofstorage - _start;}T& operator[](size_t i){assert(i < size());return _start[i];}const T& operator[](size_t i) const{assert(i < size());return _start[i];}void reserve(size_t n){if(n > capacity()){//备份一份size_t sz = size();T* tmp = new T[n];if(_start){//对于string,memcpy会引发更深层次的浅拷贝问题,具体如下说明//memcpy(tmp, _start, sizeof(T) * size());for(size_t i = 0; i < size(); ++i){//如果T是string,它会调用string的operator=完成深拷贝tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;//_finish = _start + size();err,size去计算时,_finish还是旧空间的_finish,而_start却是新空间的_start了,所以_finish-_start就是一个负值,再加_start就是0_endofstorage = _start + n;}}//如果没有给值,就用默认值,如果T是int,那就是int的匿名对象。T是string,那就是stirng的匿名对象。它会调用对应的默认构造函数————int是0,double是0.0,指针就是空指针//所以一般写一个类型,一定要提供一个不用参数就可以调的函数void resize(size_t n, const T& val = T()){if(n <= size()){_finish = _start + n;}else{if(n > capacity()){reserve(n);}while(_finish < _start + n){*_finish = val;++_finish;}}}void push_back(const T& x){/*if(_finish == _endofstorage){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}//这里不用像源码中一样使用定位new,因为使用定位new的原因是finish指向的空间没有初始化,所以使用定位new把对象构造上去。但是我们这里的对象是new出来的,所以这里直接赋值即可*_finish = x;++_finish;*/insert(end(), x);}void pop_back(){/*//一般情况下--finish就行了,但是特殊情况vector为空时就不好//所以一般需要assertassert(!empty());--_finish;*/erase(--end());}iterator insert(iterator pos, const T& x){//可以=_finish,因为它相当于尾插assert(pos >= _start && pos <= _finish);if(_finish == _endofstorage){size_t len = pos - _start;size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;//reserve里会更新那三个成员变量,insert返回新插入的那个元素的地址,所以这里的pos需要先备份一下旧空间里与_start之间的长度,然后再在新空间里重新赋值reserve(newcapacity);pos = _start + len;}iterator end = _finish - 1;while(end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;}iterator erase(iterator pos){assert(pos >= _start && pos < _finish);iterator it = pos + 1;while(it != _finish){*(it - 1) = *it;++it;}--_finish;return pos;}private:iterator _start;iterator _finish;iterator _endofstorage;};void print(const vector& v){vector::const_iterator it = v.begin();while(it != v.end()){cout << *it << " ";++it;}cout << endl;for(auto e : v){cout << e << " ";}cout << endl;for(size_t i = 0; i < v.size(); ++i){cout << v[i] << " ";}cout << endl;}void test_vector1(){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;for(auto e : v){cout << e << " ";}cout << endl;for(size_t i = 0; i < v.size(); ++i){cout << v[i] << " ";}cout << endl;print(v);}void test_vector2(){vector v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);for(auto e : v){cout << e << " ";}cout << endl;v.resize(2);for(auto e : v){cout << e << " ";}cout << endl;v.resize(4);for(auto e : v){cout << e << " ";}cout << endl;v.resize(10, 5);for(auto e : v){cout << e << " ";}cout << endl;}void test_vector3(){vector v;string s("hello");v.push_back(s);v.push_back(string("hello"));v.push_back("hello");v.push_back("hello");v.push_back("hello");v.push_back("hello");for(auto e : v){cout << e << " ";}cout << endl;}void test_vector4(){vector v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);vector::iterator pos = find(v.begin(), v.end(), 2);if(pos != v.end()){pos = v.insert(pos, 20);}cout << *pos << endl;*pos = 100;++pos;for(auto e : v){cout << e << " ";}cout << endl;}void test_vector5(){vector v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);vector::iterator pos = find(v.begin(), v.end(), 2);if(pos != v.end()){v.erase(pos);}//这段代码在VS下是会崩溃的,但是在Linux下没有崩,所以这块我们就按Linux下实现cout << *pos << endl;*pos = 100;}void test_vector6(){vector v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);//删除v中所有偶数vector::iterator it = v.begin();while(it != v.end()){if(*it % 2 == 0){it = v.erase(it);}else{++it;}}for(auto e : v){cout << e << " ";}cout << endl;}void test_vector7(){vector v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);vector v2(v1);for(auto e : v2){cout << e << " ";}cout << endl;//为什么现代写法里的构造函数的实现还需要再定义模板,而不使用T*或iterator//因为如果是T*的话就写死了,你是其它容器的迭代器就不行了string s("abcde");vector v3(v1.begin(), v1.end());vector v4(s.begin(), s.end());//赋值v1 = v4;for(auto e : v1){cout << e << " ";}cout << endl;}
}int main()
{byh::test_vector1();cout << "-----------------------next-----------------------" << endl;byh::test_vector2();cout << "-----------------------next-----------------------" << endl;byh::test_vector3();cout << "-----------------------next-----------------------" << endl;byh::test_vector4();cout << "-----------------------next-----------------------" << endl;byh::test_vector5();cout << "-----------------------next-----------------------" << endl;byh::test_vector6();cout << "-----------------------next-----------------------" << endl;byh::test_vector7();return 0;
}

🎵 2.2 使用memcpy拷贝问题

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

vector v;v.push_back(1111);v.push_back(2222);v.push_back(3333);return 0;

• 问题分析：

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

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

🎵 2.3 动态二维数组理解

//以杨辉三角的前n行为例:假设n为5
void test5(size_t n) 
{//使用vector定义二维数组vv,vv中的每个元素都是vectorvector> 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];}}
}

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

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

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