STL：序列式容器

容器（container）

容器就是用来存放数据的，也就是数据结构，这是STL中最基础、最重要的部分。
三种容器：序列式容器、关联式容器、无序关联式容器。
所有容器底层在创建元素时，都是在堆上面的。

序列式容器

学习序列式容器的使用从以下几个方面入手：

1. 迭代器的概念。
2. 初始化。
3. 遍历。
4. 在尾部进行插入和删除。
5. 在头部进行插入和删除。
6. 原理。

学习list、vector、deque三种序列式容器。

迭代器的概念

迭代器是一个泛型指针，begin指向第一个元素，end指向最后一个元素的下一个位置。

初始化

三种容器的初始化方式有五种。

/* vector<int> number;//1.创建无参的对象 *//* vector<int> number(10)//2.count相同的元素 *//* //3.迭代器范围 *//* int array[10] = {1,2,3,4,5,6,7,8,9,0}; *//* vector<int> number(array,array + 10);//左闭右开 *//* //4.拷贝构造或者移动构造 *//* //5.使用大括号的形式 */vector<int> number = {1,3,5,7,9,2,4,6};

遍历

三种容器的遍历方式有四种。
其中vector和deque支持下标遍历、未初始化的迭代器、初始化的迭代器和增强for循环。
注意：list是不支持下标的，所以不能使用下标操作list。

//遍历//1.使用下标遍历for(size_t idx = 0;idx != number.size();idx++){cout << number[idx] << " ";}cout << endl;//2.使用未初始化的迭代器vector<int>::iterator it;//使用已初始化的迭代器for(it = number.begin();it != number.end();++it){cout << *it << " ";}cout << endl;//3.使用已初始化的迭代器auto it2 = number.begin();for(;it2 != number.end();++it2){cout << *it2 << " ";}cout << endl;//增强for循环for(auto & ele : number){cout << ele << " ";}cout << endl;

插入操作

在头部进行插入和删除

list deque支持在头部进行插入和删除，使用cotainer.push_front(num)和cotainer.pop_front()函数进行操作。
vector是不支持在头部进行插入和删除的，因为vector的_M_start指针指向位置不可以更改。

在尾部进行插入和删除

三种容器都支持在尾部进行插入和删除操作，使用container.push_back()和container.pop_back()函数。

在任意位置进行插入和删除

deque在使用insert插入时，会根据前后元素的个数进行选择性的插入。
三种容器在任意位置插入有：

//insert是在pos前插入
auto pos = container.begin();
//以在第三个位置的前面插入为例
//不支持 pos += 2;的写法
++pos;
++pos://1.直接插入一个数
container.insert(pos，5);//2.插入5个33
container.insert(pos,5,33);//3.迭代器的方式插入
verctor<int> num = {11,22,33};
container.insert(pos,num.begin(),num.end());//4.以大括号的形式插入
container.insert(pos,{111,222,333});

虽然三个容器在任意位置插入时代码完全相同，但是底层原理是不一样的。
vector存在迭代器失效问题：
vector在使用insert插入元素的时候，因为并不知道每次插入元素的个数，有可能因为插入元素过多，导致底层发生扩容，此时迭代器指向老的空间，如果还使用老的迭代器，那么后续的操作都是用的是无效的迭代器，这种现象称为迭代器失效。
解决方案：
每次使用迭代器之前，对迭代器的位置进行更新。
deque会自动计算插入位置前后的元素个数，从而选择移动前面的数据，还是后面的数据，在插入一定数量的元素后，打印pos位置的元素，可以发现变化。

删除操作

//删除一个
iterator erase(iterator pos);
iterator erase(const_iterator pos);
//删除一个范围
iterator erase(iterator first,iterator last);
iterator erase(const_iterator first,const_iterator constlast);

删除连续重复的元素：

vector<int> vec = {1,2,2,2,2,3,3,4,2,2,5};
//由于vector和deque在删除掉一个元素后，其余元素会移动，将空的位置补上，使用以下方式会存在漏删的问题。
for(auto it=vec.begin();it !=vec.end();it++){if(2 == *it){vec.erase(it);}
}
for(auto it=vec.begin();it != vec.end(); ){if(2 ==*it){vec.erase(it);}else{++it;}
}
//list中删除所有重复元素
for(auto it = list.begin();it != list.end();){if(2 ==*it){it = list.erase(it);//erase返回删除结点下一个元素的指针}else{++it;}
}

其他操作

三种序列式容器vector、deque、list都支持元素的清空clear函数以及获取元素个数的函数size；对于vector与deque而言，还有回收多余空间的函数shrink_to_fit，特别的，对于vector而言，还有记录空间的函数capacity。

resize重置元素的个数

vector中当resize小于当前size的两倍时，进行两倍扩容，当大于size的两倍时，直接扩容到resize的值。
三种序列式容器vector、deque、list都支持重置元素的个数，当重置元素的个数比上一次多，那么多的元素用默认值替代；当重置元素的个数比上一次少，那么多的元素会被删除（从后往前进行删除）。

swap

#include <vector>
#include <iostream>
using std::vector;
void printVector(std::vector<int>& vec){for(int a : vec){std::cout << a << " ";}
}int main(){vector<int> v1{1,2,3};vector<int> v2{7,8,9};cout << "v1: ";printVector(v1);std::cout << "\nv2: "printVector(v2);std::cout << "\n-- SWAP\n";v2.swap(v1);cout << "v1: ";printVector(v1);std::cout << "\nv2: "printVector(v2);
}

emplace_back

template<class... Args>
void emplace_back(Args&&... args);

emplace_back可以传入可变参数，与push_back相比较：
在不是传入左值或者右值的时候，可以使用emplace_back效率更高，不会调用拷贝构造或者移动构造函数。

list的特殊操作

merge合并两个链表
unique去除连续重复元素
sort排序：
源码：

void sort();//默认从小到大//指定排序方式,()中传入对象
template<class Compare>
void sort(Compare comp);

list<int> number = {1,3,5,8,9,7,4,3,2};
number.sort();//默认从小到大，可以可以compare
#if 0//解析number.sort();std::less<int> it;number.sort(it);number.sort(std::less<int>())number.sort(std::greater<int>())；#endif
//自定义排序规则
struct CompareList
{bool operator()(const int& lhs,const int& rhs){return lhs < rhs;}
};

reverse反转链表。
splice：可以在同一个链表中进行使用

void splice(const_iterator pos,list& other);//将链表other中的元素放到pos前面
void splice(const_iterator pos,list&& other);void splice(const_iterator pos,list& other,const_iterator it);
void splice(const_iterator pos,list&& other,const_iterator it);//将链表other it位置的元素放到pos前面void splice(const_iterator pos,list& other,const_iterator first,const_iterator last);
void splice(const_iterator pos,list&& other,const_iterator first,const_iterator last);//将other链表[first,last)范围的元素移动到调用splice的链表中

原理

vector

vector中at与operator[]一样，都可以进行随机访问，可以使用下标，但是at有范围检查，所以比下标更加安全一些。
vector动态数组头部是固定的，不能进行插入和删除，只能在尾部进行插入与删除的操作。
无论我们创建什么类型的vector对象，它的大小都是24字节，也就是三个指针的大小。
vector的底层实现有三个指针：

_M_start指向第一个元素
_M_finish指向最后一个元素的下一个位置
_M_end_of_storage指向最后一个空间的下一个位置

如何获取vector中的第一个元素的首地址呢？

vector<int> vec = {1,2,3,4,5,6};
&vec[0];//使用下标的方式
&*vec.begin();//使用迭代器
int *pdata = number.data();//使用data函数

vector的扩容原理

size() = m,capacity() = n,新插入元素的个数t;
1.t < n- m:不扩容
2.n - m < t < m：扩容到2m
3.n - m < t,m < t < n:按照t + m进行扩容
4.n - m < t,t > n：会按照t + m进行扩容

deque

deque双端队列底层有一个中控器（m_map二级指针，指向一个数组）deque是由不同片段组成的，片段内部是连续的，但是片段之间是不连续的，片段是由中控器进行控制的。deque是逻辑连续的，但是物理上是分散的
deque的iterator是由_M_start _M_finish组成。
_M_start中有_M_cur _M_first _M_last _M_node，_M_first指向片段首地址_M_last指向片段尾_M_cur指向元素，_M_node指向中控器。
_M_finish同理，但是_M_cur指向最后一个元素的下一个位置。

list

list是一个双向循环链表，首结点和尾结点之间用空结点连接起来。

总结

对于vector而言，其迭代器就是一个普通类型的指针，而对于deque而言，其迭代器不是一个普通类型的指针，是一个类，但是这个类中重载了指针的功能。

思考

Insert插入数据导致容量不够，底层是否也采用类似vector的push_back一样的两倍扩容？
push_back每次只会插入一个元素，所以可以按照统一的形式2*capacity()，但是insert的时候，插入的元素的个数是不定的，所以就不能一概而论。

假设：capacity() = n,size() = m,insert插入的元素个数为t,n一定是大于等于m的。
1.t < n - m,插入元素的个数，比剩余空间小，无需扩容
2. n - m < t < m,按照两倍去扩容，新空间是2*m;
3. n - m < t < n 且 t>m，就按照t+m去进行扩容；
4. 如果t>n时，依旧按照t+m去进行扩容。