一、vector向量容器

底层数据结构：动态开辟的数组，内存是连续的，每次以原来空间大小的2倍进行扩容。

#include<vector>
vector<int> vec;

增加：
vec.push_back(20);    末尾添加元素   O(1)，会导致扩容
vec.insert(it, 20);   it迭代器指向的位置添加一个元素20   O(n)，会导致扩容

删除：
vec.pop_back();    末尾删除元素   O(1)
vec.erase(it);   删除it迭代器指向额元素   O(n)

查询：
operator[ ]  下标的随机访问vec[5]   O(1)
iterator迭代器进行遍历
find、for_each
foreach => 通过迭代器iterator实现

注意：对容器进行连续插入或删除（insert/erase），一定要更新迭代器，否则第一次insert/erase完成，迭代器就失效了。

常用方法介绍：
size( )：返回底层有效元素的个数
empty( )：判断容器是否为空
reserve(20)：vector预留空间，只给容器底层开辟指定大小的内存空间，并不会添加新的元素
resize(20)：扩容，不仅给容器底层开辟指定大小的内存空间，还会添加新的元素
swap( )：两个容器进行元素交换

#include<iostream>
#include<vector>
using namespace std;

int main()
{
	vector<int>vec;
	for (int i = 0; i < 20; i++)
	{
		vec.push_back(rand() % 100 + 1);
	}
	int size = vec.size();
	for (int i = 0; i < size; ++i)
	{
		cout << vec[i] << " ";
	}
	cout << endl;

	//删除所有偶数
	auto it2 = vec.begin();
	while (it2 != vec.end())
	{
		if (*it2 % 2 == 0)
		{
			it2 = vec.erase(it2);
		}
		else
		{
			++it2;
		}
	}
	//通过迭代器遍历vector容器
	auto it1 = vec.begin();
	for (; it1 != vec.end(); ++it1)
	{
		cout << *it1 << " ";
	}
	cout << endl;
	//给容器中所有奇数前面都添加一个小于该奇数1的偶数
	auto it3 = vec.begin();
	for (; it3 != vec.end();++it3)
	{
		if (*it3 % 2 != 0)
		{
			it3 = vec.insert(it3, *it3 - 1);
			++it3;
		}
	}
	for (it3 = vec.begin(); it3 != vec.end(); ++it3)
	{
		cout << *it3 << " ";
	}
	cout << endl;
	return 0;
}

#include<iostream>
#include<vector>
using namespace std;

int main()
{
	vector<int>vec;
	//vec.reserve(20);
	vec.resize(20);
	cout << vec.empty() << endl;  //reserve:1，resize:0
	cout << vec.size() << endl;   //reserve:0，resize:20
	for (int i = 0; i < 20; i++)
	{
		vec.push_back(rand() % 100 + 1);
	}
	cout << vec.empty() << endl;  //reserve:0，resize:0
	cout << vec.size() << endl;   //reserve:20，resize:40
    return 0;
}

二、deque双端队列容器

底层数据结构：动态开辟的二维数组，第二维是固定长度的数组空间，一堆数组从2开始，第一维的数组以2倍的方式进行扩容，每次扩容后，原来的第二维数组，从新的第一维数组的下标oldsize/2开始存放，上下 都预留相同的空行，方便支持deque的首尾元素添加。

deque底层内存是否是连续的？并不是，每一个第二维是连续的（分段连续）。

两头都可以入队、出队。

#include<deque>
deque<int> deq;

增加：
deq.push_back(20);  从末尾添加元素  O(1)
deq.push_front(20);  从首部添加元素   O(1)        //vec.insert(vec.begin(),20)    O(n)
deq.insert(it, 20);       it指向的位置添加元素   O(n)

删除：
deq.pop_back(20);  从末尾删除元素  O(1)
deq.pop_front(20);  从首部删除元素   O(1)
deq.erase(it);         从it指向的位置删除元素  O(n)

查询搜索：
iterator（连续的insert和erase一定要考虑迭代器失效的问题）

三、list链表容器

底层数据结构：双向的循环链表     （有pre、data、next）

#include<list>
list<int> mylist;

增加：
mylist.push_back(20);  从末尾添加元素  O(1)
mylist.push_front(20);  从首部添加元素   O(1)        //vec.insert(vec.begin(),20)    O(n)
mylist.insert(it, 20);       it指向的位置添加元素   O(1)   //链表中进行insert时，先进行一个query查询操作，对于链表来说，查询操作效率就比较慢

删除：
mylist.pop_back(20);  从末尾删除元素  O(1)
mylist.pop_front(20);  从首部删除元素   O(1)
mylist.erase(it);         从it指向的位置删除元素  O(1)

查询搜索：
iterator（连续的insert和erase一定要考虑迭代器失效的问题）

四、vector、deque和list对比

1.vector和deque之间的区别

• 底层数据结构：动态数组   动态的二维数组
• 前中后插入删除元素的时间复杂度：中间和末尾O(1)，前：deque O(1)，vector O(n)。
• 对于内存的使用效率：vector需要的内存空间是连续的；deque可以分块进行数据存储，不需要内存空间必须连续。
• 在中间进行insert或者erase，vector和deque的效率谁好？（vector）谁坏（deque）？：复杂度都是O(n)，由于deque的第二维内存空间不是连续的，所以在deque中间进行元素的insert或者是erase，造成元素移动的时候要比vector慢。

2.vector和list之间的区别

即区分数组和链表之间的区别：

• 底层数据结构：动态数组   双向循环链表
• 数组：增加、删除O(n)，查询O(n)，随机访问O(1)
  链表：（考虑搜索的时间）增加、删除O(1)