文章目录
一、vector容器
底层数据结构是动态开辟的数组，每次以原来空间大小的2倍进行扩容
使用前需要包含头文件：#include <vector>
容器中对象的构造析构，内存的开辟释放，是通过空间配置器allocator实现：allocate(内存开辟)、deallocate(内存释放)、construct(对象构造)、destroy(对象析构)
使用方法：
vector<int> vec;
增加：
vec.push_back(20);，在容器末尾增加一个元素，时间复杂度O(1)，有可能会导致容器扩容vec.insert(it, 20);，在迭代器it指向的位置增加一个元素，时间复杂度O(n)，有可能会导致容器扩容
删除：
vec.pop_back();，在容器末尾删除一个元素，时间复杂度O(1)vec.erase(it);，删除迭代器it指向的元素，时间复杂度O(n)
查询：
- 提供了
operator[]重载函数，数组下标的随机访问，例如vec[5]，时间复杂度O(1) iterator，迭代器进行遍历，一定要考虑迭代器失效问题find，for_each等泛型算法- C++11提供的语法糖
foreach，其实就是通过迭代器来实现的
注意：对容器进行连续插入或者删除操作（insert/erase），一定要更新迭代器，否则第一次insert或者erase之后，迭代器就失效了，失效问题详见这里
常用方法：
size();，返回容器底层有效元素的个数empty();，判断容器是否为空reserve();，为vector预留空间，只给容器底层开辟指定大小空间并不添加新的元素resize();，扩容，不仅给容器底层开辟指定大小空间，还会添加新的元素swap();，两个容器进行元素交换
代码示例：元素遍历
vector<int> vec;
for (int i = 0; i < 20; ++i)
vec.push_back(i);
int size = vec.size();
for (int i = 0; i < size; ++i)
cout << vec[i] << " ";
cout << endl;
auto it1 = vec.begin();
for (; it1 != vec.end(); ++it1)
cout << *it1 << " ";
cout << endl;
运行结果：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
代码示例：删除所有偶数
vector<int> vec;
for (int i = 0; i < 20; ++i)
vec.push_back(i);
auto it = vec.begin();
while (it != vec.end())
{
if (*it % 2 == 0)
it = vec.erase(it);
else
++it;
}
int size = vec.size();
for (int i = 0; i < size; ++i)
cout << vec[i] << " ";
cout << endl;
运行结果：
1 3 5 7 9 11 13 15 17 19
代码示例：所有奇数前面加一个比其小1的数
vector<int> vec;
for (int i = 0; i < 20; ++i)
vec.push_back(i);
for (auto it = vec.begin(); it != vec.end(); ++it)
{
if (*it % 2 == 1)
{
it = vec.insert(it, *it - 1);
++it;
}
}
int size = vec.size();
for (int i = 0; i < size; ++i)
cout << vec[i] << " ";
cout << endl;
运行结果：
0 0 1 2 2 3 4 4 5 6 6 7 8 8 9 10 10 11 12 12 13 14 14 15 16 16 17 18 18 19
代码示例：reserve预留空间
reserve只是预留空间，只给容器底层开辟指定大小空间并不添加新的元素
默认定义的vector底层开辟空间为0，第一次push_back插入从0变更为1，再变为2,4,8,16,32…，一直进行二倍扩容，扩容频繁，效率太低，假如开始知道问题的数据量大小，即可使用reserve预留空间
vector<int> vec;
vec.reserve(20);
cout << vec.empty() << endl;
cout << vec.size() << endl;
for (int i = 0; i < 20; ++i)
vec.push_back(i);
cout << vec.empty() << endl;
cout << vec.size() << endl;
运行结果：
1
0
0
20
代码示例：resize扩容
resize扩容，不仅给容器底层开辟指定大小空间，还会添加新的元素，没有指定添加的元素值则为0
vector<int> vec;
vec.resize(10);
cout << vec.empty() << endl;
cout << vec.size() << endl;
for (int i = 0; i < 20; ++i)
vec.push_back(i);
cout << vec.empty() << endl;
cout << vec.size() << endl;
int size = vec.size();
for (int i = 0; i < size; ++i)
cout << vec[i] << " ";
cout << endl;
运行结果：
0
10
0
30
0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
若改为vec.resize(10，3);，则运行结果为：
0
10
0
30
3 3 3 3 3 3 3 3 3 3 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
二、deque和list容器
deque：使用前需要包含头文件：#include <deque>
双端队列容器，底层数据结构为动态开辟的二维数组。 一维数组从2开始，以2倍的方式进行扩容，每次扩容后，原来第二维的数组，从新的第一维数组的下标oldsize/2开始存放（也就是扩容之后的中间），前后都预留相同的空行，方便支持双端的元素添加
随着元素增加：
如果继续增加呢？会对第一维扩容
使用方法：
deque<int> deq;
增加：
deq.push_back(20);，从末尾添加元素，时间复杂度O(1)，可能引起扩容deq.push_front(20);，从首部添加元素，时间复杂度O(1)，可能引起扩容。vector中没有该方法，需要使用vec.insert(vec.begin(), 20)，O(n)deq.insert(it, 20);，迭代器it指向的位置添加元素，时间复杂度O(n)
删除：
deq.pop_back();，从末尾删除元素，时间复杂度O(1)deq.pop_front();，从首部删除，时间复杂度O(1)deq.erase(it);，迭代器it指向的位置进行元素删除，时间复杂度O(n)
查询：
iterator，迭代器进行遍历，一定要考虑迭代器失效问题（连续的insert或erase）
常用方法：
size();，返回容器底层有效元素的个数empty();，判断容器是否为空resize();，扩容，不仅给容器底层开辟指定大小空间，还会添加新的元素swap();，两个容器进行元素交换
list：使用前需要包含头文件：#include <list>
底层数据结构为双向循环链表，结点中包括data、pre、next
与vector和deque不同，list允许高效地在任何位置插入和删除元素，但不支持随机访问
使用方法：
list<int> MyList;
增加：
MyList.push_back(20);，从末尾添加元素，时间复杂度O(1)，可能引起扩容MyList.push_front(20);，从首部添加元素，时间复杂度O(1)，可能引起扩容MyList.insert(it, 20);，迭代器it指向的位置添加元素，时间复杂度O(1)
删除：
MyList.pop_back();，从末尾删除元素，时间复杂度O(1)MyList.pop_front();，从首部删除，时间复杂度O(1)MyList.erase(it);，迭代器it指向的位置进行元素删除，时间复杂度O(1)
查询：
iterator，迭代器进行遍历，一定要考虑迭代器失效问题（连续的insert或erase）
常用方法：
size();，返回容器底层有效元素的个数empty();，判断容器是否为空resize();，扩容，不仅给容器底层开辟指定大小空间，还会添加新的元素swap();，两个容器进行元素交换