目录
一.vector的介绍及使用
1.1 vector的介绍
1.2 vector的使用
1.2.1 vector的定义
1.2.2 vector iterator 迭代器的使用
1.2.3 vector 空间增长问题
1.2.4 vector 增删查改
1.2.5 vector 迭代器失效问题。（重点）
1.2.6 vecotr<自定义类型>（vector、vector>）
1.2.7 vector 在OJ中的使用
二.vector深度剖析及模拟实现
2.1 std::vector的核心框架接口的模拟实现csdn::vector
2.2 使用memcpy拷贝问题
一.vector的介绍及使用
1.1 vector的介绍
vector的文档介绍
使用STL的三个境界：能用，明理，能扩展 ，那么下面学习vector，我们也是按照这个方法去学习。
1.2 vector的使用
vector学习时一定要学会查看文档：vector的文档介绍，vector在实际中非常的重要，在实际中我们熟悉常见的接口就可以，下面列出了哪些接口是要重点掌握的。
1.2.1 vector的定义
| constructor 构造函数 | 接口说明 | |
| (1) | vector();（重点） | 无参构造 |
| (2) | vector（size_type n, const value_type& val = value_type()); | 构造并初始化n个val |
| (3) | vector (const vector& x); （重点） | 拷贝构造 |
| (4) | vector (InputIterator first, InputIterator last); | 使用迭代器进行初始化构造 |
vertor的定义用的类模板，而类模板的实例化只能显示实例化，即在使用vector时必须指名类型。
示例：(1)、(2)、(3)、(4)
#include<iostream>
#include<vector>
using namespace std;//vector没有重载 <<流插入和>>流提取运算符，打印vector可以直接用范围for
void Print(const vector<int>& v) //用const和引用&，是为了减少拷贝构造
{for (const auto& x : v) {cout << x << " ";}cout << endl;
}
void test_vector1()
{vector<int> v1; // (1) 空vectorvector<int> v2(5, 1); // (2) 构造并初始化 5 个 1vector<int> v3(v2); // (3) 拷贝构造v2vector<int> v4(v2.begin(), v2.end()); // (4) 用迭代器进行初始化构造// 第一个参数为v2迭代器的begin(),第二个为v2的end()Print(v1);// 打印空Print(v2);// 打印 5 个 1Print(v3);// 打印v2，同样是 5 个 1Print(v4);// 打印v2，同样是 5 个 1// 迭代器构造函数也可用于从数组进行构造： int myints[] = { 16,2,77,29 };int len = sizeof(myints) / sizeof(myints[0]);vector<int> v5(myints, myints + len); // (5) 用数组构造，第一个参数是数组头指针，第二个是尾指针Print(v5);
}
int main()
{test_vector1();return 0;
}1.2.2 vector iterator 迭代器的使用
| iterator迭代器的使用 | 接口说明 | |
| (1) | begin+end（重点） | 获取第一个数据位置的iterator/const_iterator， 获取最后一个数据的下一个位置的iterator/const_iterator |
| (2) | rbegin+rend | 获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的reverse_iterator |
迭代器分为正向迭代器iterator和反向迭代器reverse_iterator，还有conse迭代器
iterator //正向迭代器
const_iterator //const正向迭代器
reverse_iterator //反向迭代器
const_reverse_iterator //const反向迭代器迭代器的使用，以正向迭代器为例
容器类型::iterator it = 容器.begin();
//it是迭代器名，可以赋予begin(),end(),rbegin(),rend()举例：
string s1("abcd");
string::iterator its = s1.begin();vector<int> v1;
string::iterator itv = v1.begin();示例：iterator的使用，(1)、(2)
#include<iostream>
#include<vector>
using namespace std;//vector没有重载 <<流插入和>>流提取运算符，打印vector可以直接用范围for
void Print(const vector<int>& v) //用const和引用&，是为了减少拷贝构造
{for (const auto& x : v){cout << x << " ";}cout << endl;
}
void test_vector2()
{int array_int[] = { 1,2,3,4,5 };int len = sizeof(array_int) / sizeof(array_int[0]);vector<int> v1(array_int, array_int + len); //定义一个{1,2,3,4,5}的vector// 可以把迭代器想成指针，begin()返回头指针，end()返回尾指针的下一个元素// ，rbegin()返回尾指针，rend()返回头指针的下一个元素//正向迭代器：iteratorvector<int>::iterator it1 = v1.begin(); // (1) begin + endwhile (it1 < v1.end()) //正向迭代器，从头指针指向尾指针的下一个{cout << *it1 << " ";++it1;}cout << endl;//反向迭代器：reverse_iteratorvector<int>::reverse_iterator it2 = v1.rbegin(); // (1) rbegin + rendwhile (it2 < v1.rend()) //反向迭代器，从尾指针指向头指针的前一个{cout << *it2 << " ";++it2; //从begin到end都是用++}cout << endl;
}
int main()
{test_vector2();return 0;
}1.2.3 vector 空间增长问题
| 容量管理 | 接口管理 | |
| (1) | size | 获取数据个数 |
| (2) | capacity | 获取容量大小 |
| (3) | empty | 判断是否为空 |
| (4) | resize（重点） | 改变vector的size，减小size不缩容，增大size可扩容 |
| (5) | reserve（重点） | 改变vector的capacity |
capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。
reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。
resize在开空间的同时还会进行初始化，影响size。
示例：(1)、(2)、(3)、(4)、(5)
#include<iostream>
#include<vector>
using namespace std;//vector没有重载 <<流插入和>>流提取运算符，打印vector可以直接用范围for
void Print(const vector<int>& v) //用const和引用&，是为了减少拷贝构造
{for (const auto& x : v){cout << x << " ";}cout << endl;
}
void test_vector3()
{vector<int> v1(10,1); //定义一个10个1的vectorPrint(v1); // (1) (2) (3) cout << v1.size() << " " << v1.capacity() << " " << v1.empty() << endl << endl;v1.resize(5); // (4) resize减小size，但不缩容Print(v1);cout << v1.size() << " " << v1.capacity() << " " << v1.empty() << endl << endl;v1.resize(15,5);// resize增大size, 给多出来的size放5(不给第二个值则放默认值)Print(v1);cout << v1.size() << " " << v1.capacity() << " " << v1.empty() << endl << endl;vector<int> v;v.reserve(20); // reverse改变capacity但不动sizecout << v.size() << " " << v.capacity() << " " << v.empty() << endl << endl;
}
int main()
{test_vector3();return 0;
}1.2.4 vector 增删查改
| vector增删查改 | 接口说明 | |
| (1) | push_back（重点） | 尾插 |
| (2) | pop_back（重点） | 尾删 |
| (3) | find | 查找。（注意这个是算法模块实现，不是vector的成员接口）find找不到则返回end() |
| (4) | insert | 在position之前插入val |
| (5) | erase | 删除position迭代器位置的数据 |
| (6) | swap | 交换两个vector的数据空间 |
| (7) | operator[]（重点） | 像数组一样访问 |
注意：find并不是vector容器的成员接口，find可以用于数组和vector，用法见（示例2）
示例1：(1)尾插、(2)尾删
#include<iostream>
#include<vector>
using namespace std;//vector没有重载 <<流插入和>>流提取运算符，打印vector可以直接用范围for
void Print(const vector<int>& v) //用const和引用&，是为了减少拷贝构造
{for (const auto& x : v){cout << x << " ";}cout << endl;
}
void test_vector4()
{vector<int> v1(5, 1); Print(v1);v1.push_back(3);v1.push_back(4); // (1) push_back尾插v1.push_back(5);Print(v1);v1.pop_back(); // (2) pop_back尾删Print(v1);
}
int main()
{test_vector4();return 0;
}示例2：（3）find的使用
#include<iostream>
#include<vector>
using namespace std;void test_vector3()
{int array[] = { 0,1,2,3,4 };int len = sizeof(array) / sizeof(array[0]);int* pf;pf = find(array, array + len, 3); // find在数组中使用，参数为(数组头指针，数组尾指针，查找的数字)cout << "数字3的地址：" << &array[3] << endl; // 找到后返回找到的第一个对应数字的地址cout << "find查找的数字3的地址：" << pf << endl;vector<int> v1(array, array + len);vector<int>::iterator itv;itv = find(v1.begin(), v1.end(),2); // find在vector中要配合迭代器使用，第三个参数是要查找的数字cout << *itv << endl; // 找到后返回第一个对应数字的迭代器// 注意，迭代器并不是指针，只是类似指针
}
int main()
{test_vector3();return 0;
}示例3：(4) insert
#include<iostream>
#include<vector>
using namespace std;//vector没有重载 <<流插入和>>流提取运算符，打印vector可以直接用范围for
void Print(const vector<int>& v) //用const和引用&，是为了减少拷贝构造
{for (const auto& x : v){cout << x << " ";}cout << endl;
}
void test_vector3()
{vector<int> v1(3, 100);vector<int>::iterator itv = v1.begin();itv = v1.insert(itv, 200); // (1) iterator insert(迭代器, 插入值) Print(v1); // 返回值为指向第一个新插入元素的新迭代器。必须有迭代器接受返回值cout << *itv << endl;itv.v1.insert(itv, 2, 300); // (2) void insert(迭代器, 插入数量，插入值)// v1.insert(itv, 2, 300); // 不能这样写，此处要扩容，扩容之后itv就失效了，为野指针，会报错Print(v1);itv = v1.begin(); // 此前迭代器指向200，是一个新的迭代器，不指向v1里，现修改为指向v1.begin内容的迭代器vector<int> v2(2, 400); // (3) void insert(iterator position,v2迭代器的begin(), v2迭代器的end());v1.insert(itv + 2, v2.begin(), v2.end());// 在迭代器往后两个位置插入Print(v1);int myarray[] = { 501,502,503 };v1.insert(v1.begin(), myarray, myarray + 3); // (4) 也可插入数组Print(v1);
}
int main()
{test_vector3();return 0;
}示例4：(5)、(6)、(7)
#include<iostream>
#include<vector>
using namespace std;//vector没有重载 <<流插入和>>流提取运算符，打印vector可以直接用范围for
void Print(const vector<int>& v) //用const和引用&，是为了减少拷贝构造
{for (const auto& x : v){cout << x << " ";}cout << endl;
}
void test_vector6()
{vector<int> v1(3, 100);vector<int>::iterator itv = v1.begin();int myarray[] = { 501,502,503 };v1.insert(v1.begin(), myarray, myarray + 3); //插入数组Print(v1);itv = v1.begin();itv = v1.erase(itv + 1); // (5) 删除迭代器指向的数据Print(v1);cout << endl;cout << "v1:";//原v1,v2Print(v1);vector<int> v2(3, 200);cout << "v2:";Print(v2);swap(v1, v2); // (6) 交换两个vector的数据cout << "v1:";//现v1,v2Print(v1);cout << "v2:";Print(v2);cout << endl;cout << v1[1] << endl; //(7) operator[] 像数组一样访问vectorcout << v2[1] << endl;
}
int main()
{test_vector6();return 0;
}1.2.5 vector 迭代器失效问题。（重点）
迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就是原生态指针T* 。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)。
对于vector可能会导致其迭代器失效的操作有：
1. 会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_back等。 类似野指针
（1）由于扩容引起的野指针，解决：insert()函数的修改
（2）由于扩容，主函数中调用修改后的迭代器形成的野指针，再次修改insert()函数
（3）如果不扩容，使用p指针，VS检查的比较严格，也会报错；linux的g++不会报错。但都十分不安全。
2. 指定位置元素的删除操作--erase
以下代码的功能是删除vector中所有的偶数的例子
erase删除 it 位置元素后， it 位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：如果 it 刚好是最后一个元素，删完之后 it 刚好是end的位置，而end位置是没有元素的，那么 it 就失效了。因此删除vector中任意位置上元素时，vs就认为该位置迭代器失效了。
在使用erase的时候也要注意，it 调用了erase函数之后，会间接的+1，需要加else条件屏蔽这个问题。
3. 注意：Linux下，g++编译器对迭代器失效的检测并不是非常严格，处理也没有vs下极端。
// 1. 扩容之后，迭代器已经失效了，程序虽然可以运行，但是运行结果已经不对了
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
// 2. erase删除任意位置代码后，linux下迭代器并没有失效
// 因为空间还是原来的空间，后序元素往前搬移了，it的位置还是有效的
#include <vector>
#include <algorithm>
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
// 3: 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);++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范围内，肯定会崩溃的。
4. 与vector类似，string在插入+扩容操作+erase之后，迭代器也会失效
#include <string>
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.6 vecotr<自定义类型>（vector<string>、vector<vector<int>>）
vector<vector<int>>类似二维数组，但是二维数组是静态的，不能改变大小，vector可以进行增删查改等操作
#include<iostream>
#include<vector>
using namespace std;void test_vector7()
{vector<string> v1; // (1) vector<string>string s1("xxxx");v1.push_back(s1);v1.push_back("yyyyy");for (const auto& e : v1){cout << e << " ";}cout << endl;vector<int> v(5, 1);vector<vector<int>> vv(10, v); // (2) vector<vector<int>>vv[2][1] = 2; // 类似二维数组，但二维数组直接用下标，这里其实是调用的下面一行的两个函数// vv.operator[](2).operator[](1) = 2;for (size_t i = 0; i < vv.size(); i++){for (size_t j = 0; j < vv[i].size(); ++j){cout << vv[i][j] << " ";}cout << endl;}cout << endl;
}// vv[2][1] = 2;
// vv.operator[](2).operator[](1) = 2;
// 这里把[]写成oerator[]比较好理解，第一个[]是调用的 T=vector<int>的[], 第二个[]是调用的T=int的[]
// 因为模板是编译器根据给的T类型，自动实例化出不同的类
//template<typename T>vector<int> T=int
//class vector
//{
//public:
// int& operator[](int i)
// {
// assert(i < _size);
// return _a[i];
// }
//private:
// int* _a;
// size_t _size;
// size_t _capacity;
//};
//
//template<typename T>vector<vector<int>> T=vector<int>
//class vector
//{
//public:
// vector<int>& operator[](int i)
// {
// assert(i < _size);
// return _a[i];
// }
//private:
// vector<int>* _a;
// size_t _size;
// size_t _capacity;
//};
int main()
{test_vector7();return 0;
}1.2.7 vector 在OJ中的使用
C++的杨辉三角实现，可见相比于C语言，C++的实现要简单的多。
class Solution {
public:vector<vector<int>> generate(int numRows) {vector<vector<int>> yh(numRows);for(int i = 0; i < numRows; ++i){yh[i].resize(i+1,1);}for(int j = 2; j < numRows; j++){ for(int i = 1; i < j; i++){yh[j][i] = yh[j-1][i-1] + yh[j-1][i];}}return yh;}
};二.vector深度剖析及模拟实现
2.1 std::vector的核心框架接口的模拟实现csdn::vector
【免费】C++vector的模拟实现资源-CSDN文库
2.2 使用memcpy拷贝问题
假设模拟实现的vector中的reserve接口中，使用memcpy进行的拷贝，以下代码会发生什么问题？
问题分析：
1. memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中。
2. 如果拷贝的是内置类型的元素，memcpy既高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。
结论：如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。
