C++基础（十四）：vector

        从这一篇博客开始，我们重点学习vector，实际上，vector就是动态扩容的顺序表/数组，vector 是 C++ 标准模板库 (STL) 中的一个序列容器，用于存储同类型对象的动态数组。它提供了动态调整大小的能力，支持高效的随机访问，并允许便捷地进行元素的添加和删除操作。要使用 vector，需要包含 <vector> 头文件，并通过 std::vector 来创建对象。 vector 支持多种初始化方式，包括默认构造、指定大小的构造和使用初始值列表等，非常适用于需要灵活数组操作的场景。

目录

一、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 vector 在OJ中的使用

二、vector深度剖析及模拟实现

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

2.2 使用memcpy拷贝问题

2.3 动态二维数组理解

2.4 为什么会有List（面试题）

一、vector的介绍及使用

1.1 vector的介绍

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

使用STL的三个境界：能用，明理，能扩展 ，那么下面学习vector，我们也是按照这个方法去学习

1.2 vector的使用

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

1.2.1 vector的定义

/************************vector对象的创建*********************************/
void test_vector()
{
	vector<int> v1;            //无参构造函数，相当于定义一个整型的动态顺序表，数组尾插效率较高
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	v1.push_back(5);
	v1.push_back(6);


	vector<int> v2(v1);       //拷贝构造函数
   

	/******遍历方式和正常的数组用下标遍历方式一样（for+[下标]）********/

	for (size_t i = 0; i < v1.size(); i++)
	{
		cout << v1[i] << " ";
	}
	cout << endl;


	for (size_t i = 0; i < v2.size(); i++)
	{
		cout << v2[i] << " ";
	}
	cout << endl;
}



/***********************************************************************/

1.2.2 vector iterator 的使用

/****************************vector的三种遍历方式*********************************/

void test_vector1()
{
	vector<int> v1;            
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	v1.push_back(5);
	v1.push_back(6);


	/******遍历修改数据方式1：for循环+operator[]+size********/

	for (size_t i = 0; i < v1.size(); i++)
	{
		cout << v1[i] << " ";
	}
	cout << endl;


	/******遍历修改数据方式2：迭代器*************************/
	vector<int>::iterator it = v1.begin();
	while (it != v1.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;



    void PrintVector(const vector<int>& v)
    {
	    // const对象使用const迭代器进行遍历打印，只能读不能写
	    vector<int>::const_iterator it = v.begin();
	    while (it != v.end())
	    {
		    cout << *it << " ";
		    ++it;
	    }
	    cout << endl;
    }





	// 使用迭代器进行修改
	it = v1.begin();
	while (it != v1.end())
	{
		*it *= 2;
		++it;
	}



	// 使用反向迭代器进行遍历再打印
	// vector<int>::reverse_iterator rit = v.rbegin();
	auto rit = v1.rbegin();
	while (rit != v1.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;



	/*******遍历修改数据方式3：范围for,本质被编译器替换成迭代器方式遍历支持的*******************/
	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;

}

1.2.3 vector 空间增长问题

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

// 测试vector的默认扩容机制
void TestVectorExpand()
{
    size_t sz;
    vector<int> v;
    sz = v.capacity();
    cout << "making v grow:\n";
    for (int i = 0; i < 100; ++i) 
    {
       v.push_back(i);
       if (sz != v.capacity()) 
       {
            sz = v.capacity();
            cout << "capacity changed: " << sz << '\n';
       }
    }
}