目录

1. 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中的使用

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

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

2.2 使用memcpy拷贝问题（reserve接口扩容自定义类型时问题）

---

1. 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和引用&，是为了减少拷贝构造
{
// 三种遍历方式，operator[]、迭代器、范围for
	//for (size_t i = 0; i < v.size(); i++)
	//{
	//	cout << v[i] << " ";
	//}
	//cout << endl;

	//vector<int>::const_iterator it = v.begin();
	//while (it < v.end())
	//{
	//	cout << *it << " ";
	//	++it;
	//}
	//cout << endl;

	for (const auto& x : v)
	{
		cout << x << " ";
	}
	cout << endl;
}
void test_vector1()
{
	vector<int> v1;							// (1) 空vector
	vector<int> v2(5, 1);					// (2) 构造并初始化 5 个 1
	vector<int> v3(v2);						// (3) 拷贝构造v2
	vector<int> v4(v2.begin(), v2.end());	// (4) 用迭代器进行初始化构造
	//		第一个参数为v2迭代器的begin(),第二个为v2的end()
	Print(v1);// 打印空
	Print(v2);// 打印 5 个 1
	Print(v3);// 打印v2，同样是 5 个 1
	Print(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()返回头指针的下一个元素
	//正向迭代器：iterator
	vector<int>::iterator it1 = v1.begin();				// (1) begin + end
	while (it1 < v1.end())		//正向迭代器，从头指针指向尾指针的下一个
	{
		cout << *it1 << " ";
		++it1;
	}
	cout << endl;

	//反向迭代器：reverse_iterator
	vector<int>::reverse_iterator it2 = v1.rbegin();	// (1) rbegin + rend
	while (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的vector
	Print(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但不动size
	cout << 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,v2
	Print(v1);
	vector<int> v2(3, 200);
	cout << "v2:";
	Print(v2);

	swap(v1, v2);		// (6) 交换两个vector的数据
	cout << "v1:";//现v1,v2
	Print(v1);
	cout << "v2:";
	Print(v2);

	cout << endl;
	cout << v1[1] << endl;	//(7) operator[] 像数组一样访问vector
	cout << 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中的使用

        1. 杨辉三角

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);
            for(int j = 0; j < vv[i].size() ; ++j )
            {
                if(i == 0 || j == 0 || j == i)
                    vv[i][j] = 1;
                else
                    vv[i][j] = (vv[i-1][j-1] + vv[i-1][j]);
            }
        }
        return vv;
    }
};

        2. 删除有序数组中的重复项

        3. 只出现一次的数字 I

        4. 只出现一次的数字 II

        5. 只出现一次的数字 III

        6. 数组中出现次数超过一半的数字

        7. 电话号码的字母组合

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

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

        【免费】C++vector的模拟实现资源-CSDN文库

2.2 使用memcpy拷贝问题（reserve接口扩容自定义类型时问题）

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

问题分析：

        1. memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中。

        2. 如果拷贝的是内置类型的元素，memcpy既高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。

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