STL_序列式容器
> 所谓序列容器，即以线性排列（类似普通数组的存储方式）来存储某一指定类型（例如 int、double 等）的数据，需要特殊说明的是，该类容器并不会自动对存储的元素按照值的大小进行排序。
序列容器大致包含以下几类容器：
- array< T,N >（数组容器）：表示可以存储 N 个 T 类型的元素，是 C++本身提供的一种容器。此类容器一旦建立，其长度就是固定不变的，这意味着不能增加或删除元素，只能改变某个元素的值；
- vector< T >（向量容器）：用来存放 T 类型的元素，是一个长度可变的序列容器，即在存储空间不足时，会自动申请更多的内存。使用此容器，在尾部增加或删除元素的效率最高（时间复杂度为 O(1) 常数阶），在其它位置插入或删除元素效率较差（时间复杂度为 O(n) 线性阶，其中 n 为容器中元素的个数）；
- deque< T >（双端队列容器）：和 vector 非常相似，区别在于使用该容器不仅尾部插入和删除元素高效，在头部插入或删除元素也同样高效，时间复杂度都是 O(1) 常数阶，但是在容器中某一位置处插入或删除元素，时间复杂度为 O(n) 线性阶；
- list< T >（链表容器）：是一个长度可变的、由 T 类型元素组成的序列，它以双向链表的形式组织元素，在这个序列的任何地方都可以高效地增加或删除元素（时间复杂度都为常数阶 O(1)），但访问容器中任意元素的速度要比前三种容器慢，这是因为 list
必须从第一个元素或最后一个元素开始访问，需要沿着链表移动，直到到达想要的元素。 - forward_list< T >（正向链表容器）：和 list 容器非常类似，只不过它以单链表的形式组织元素，它内部的元素只能从第一个元素开始访问，是一类比链表容器快、更节省内存的容器。
重点了解vector、deque、list。以vector为例：
初始化
三种序列式容器vector、deque、list完全支持五种初始化的方式
/*--------------初始化--------------*/
// 5种初始化方式
// 1.创建空对象
vector<int> vec1;
// 2.创建count个value
vector<int> vec2(10,6);
// 3.迭代器范围
int arr[10] = {1,2,3,4,5,6,7,8,9,10};
vector<int> vec3(arr,arr + 10); // 左闭右开
// 4.拷贝构造函数与移动构造函数
vector<int> vec4(vec2);
vector<int> vec5(vector<int>(10,7));
// 5.初始化列表（大括号）
vector<int> vec6 = {1,3,5,7,9};
遍历
三种遍历方式也都支持，但是list（它是双向链表）不支持下标访问的操作。用at也可以进行访问，且at更安全，因为它有范围检查，而下标访问是没有的。
/*--------------遍历--------------*/
// 1.使用下标访问
cout << "使用下标访问" << endl;
for(size_t idx = 0;idx != vec6.size();++idx)
{
cout << "vec6[" << idx << "] = " << vec6[idx] << " ";
}
cout << endl;
// 2.使用迭代器访问
cout << "使用迭代器访问" << endl;
vector<int>::iterator it; // 未初始化
// vector<int>::iterator it = vec6.begin(); // 初始化
for(it = vec6.begin();it != vec6.end();++it)
{
cout << *it << " ";
}
cout << endl;
// 3.使用for与auto
cout << "使用for与auto" << endl;
for(auto& elem : vec6)
{
cout << elem << " ";
}
cout << endl;
在尾部插入和删除
三种容器在尾部进行插入与删除的使用是完全一样的。
/*--------------在尾部插入和删除--------------*/
cout << "在尾部插入和删除" << endl;
vec6.push_back(66);
vec6.push_back(77);
display(vec6);
vec6.pop_back();
display(vec6);
在头部插入和删除
deque与list支持在头部进行插入与删除，但是vector不支持在头部进行插入与删除的操作。
Q：vector为什么不支持在头部进行插入和删除操作？
A：vector中的元素是连续的，如果在头部删除（插入）一个元素，那么后面的所有元素都需要前移（后移），这样操作的时间复杂度是O(N)。
/*--------------在头部插入和删除--------------*/
cout << "在头部插入和删除" << endl;
list<int> lis1= {1,5,9,3,10};
display(lis1);
lis1.push_front(100);
lis1.push_front(200);
display(lis1);
lis1.pop_front();
display(lis1);
在任意位置插入和删除
插入
对list而言，直接插入即可。
对vector而言，每次在操作迭代器时候，最好提前更新迭代器的位置，让迭代器指向新的空间的位置，这样才能保证不会出错。
对deque而言，去进行insert操作的时候，也有可能迭代器失效，所以最好还是可以每次使用迭代器的时候，像vector一样，将迭代器的位置进行更新，指向新的空间的位置。
/*--------------在任意位置插入和删除--------------*/
cout << "在list的任意位置插入元素" << endl;
list<int> number = {1,6,9,7,4,2,3,5,0};
list<int>::iterator ite = number.begin();
++ite;
++ite;
cout << "*ite = " << *ite << endl;
// 1.找一个位置，插入一个元素
number.insert(ite,100);
display(number);
cout << "*ite = " << *ite << endl;
cout << endl;
// 2.找一个位置，插入count个相同元素
number.insert(ite,3,200);
display(number);
cout << "*ite = " << *ite << endl;
cout << endl;
// 3.找一个位置，插入迭代器范围的元素
vector<int> num = {77,99,33,55};
number.insert(ite,num.begin(),num.end());
display(number);
cout << "*ite = " << *ite << endl;
cout << endl;
// 4.找一个位置，插入一个大括号范围的元素
number.insert(ite,{111,222,333,444,666});
display(number);
cout << "*ite = " << *ite << endl;
cout << endl;
删除
cout << "在list任意位置删除" << endl;
// 1.删除一个元素
list<int>::iterator ite1 = number.begin();
++ite1;
++ite1;
cout << "删除前" << endl;
display(number);
cout << "*ite1 = " << *ite1 << endl;
ite1 = number.erase(ite1);
cout << "删除后" << endl;
display(number);
cout << "*ite1 = " << *ite1 << endl;
// 2.删除一段元素
list<int>::iterator ite2 = number.begin();
list<int>::iterator ite3 = number.begin();
++ite3;
++ite3;
++ite3;
++ite3;
cout << "删除前" << endl;
display(number);
number.erase(ite2,ite3); // 注意，此时是删除到ite3的前一个元素
cout << "删除后" << endl;
display(number);
此处，要注意vector在删除重复元素时可能出现的问题：
void test()
{
vector<int> number = {1, 3, 6, 6, 6, 6, 7, 5};
display(number);
//这种方式不能删除连续重复元素
for(auto it = number.begin(); it != number.end(); ++it)
{
if(6 == *it)
{
number.erase(it);
}
}
display(number);
}
void test2()
{
vector<int> number = {1, 3, 6, 6, 6, 6, 7, 5};
display(number);
for(auto it = number.begin(); it != number.end(); )
{
if(6 == *it)
{
//不用更新迭代器的位置
number.erase(it);
}
else
{
++it;
}
}
display(number);
}
vector的删除是将后面的元素向前移动，此时，如果我们同时又将迭代器指针向后移动，就会漏删元素。
元素的清空
对于vector和deque，clear()函数只是将元素清空了但是没有进行内存的回收，还需要调用shrink_to_fit()函数才会将剩余的空间进行回收。
对于list而言，元素删除了也会将结点删除，不存在shrink_to_fit()这种空间回收函数了。
shrink_to_fit()会请求删除未使用的空间，调用成功后，所有的迭代器（即使是发生了重新分配，前一个迭代器也会失效）以及引用都会失效。deque类似（但注意deque没有容量这一说法）。
// list中，clear的底层源码
template <class _tp,="" class="" _alloc="">
void
_List_base<_Tp,_Alloc>::clear()
{
_List_node<_Tp>* __cur = (_List_node<_Tp>*) _M_node->_M_next;
while (__cur != _M_node) {
_List_node<_Tp>* __tmp = __cur;
__cur = (_List_node<_Tp>*) __cur->_M_next;
_Destroy(&__tmp->_M_data);
_M_put_node(__tmp);
}
_M_node->_M_next = _M_node;
_M_node->_M_prev = _M_node;
}
// vector中，clear的底层源码
void clear()
{
erase(begin(), end());
}
#include <iostream>
#include <vector>
#include <deque>
#include <list>
using std::cout;
using std::cin;
using std::endl;
using std::vector;
using std::deque;
using std::list;
void test()
{
cout << "vector:" << endl;
vector<int> number = {1,2,3,4,5,6,7,8,9};
number.clear();
cout << "number.size() = " << number.size() << endl;
cout << "number.capacity() = " << number.capacity() << endl;
number.shrink_to_fit();
cout << "number.size() = " << number.size() << endl;
cout << "number.capacity() = " << number.capacity() << endl;
}
void test1()
{
cout << endl << "deque:" << endl;
deque<int> number = {1,2,3,4,5,6,7,8,9};
cout << "number.size() = " << number.size() << endl;
number.clear();
cout << "number.size() = " << number.size() << endl;
//cout << "number[0] = " << number[0] << endl;
number.shrink_to_fit();
//cout << "number[0] = " << number[0] << endl;
cout << "number.size() = " << number.size() << endl;
}
void test2()
{
cout << endl << "list:" << endl;
list<int> number = {1,2,3,4,5,6,7,8,9};
cout << "number.size() = " << number.size() << endl;
number.clear();
cout << "number.size() = " << number.size() << endl;
}
int main()
{
test();
test1();
test2();
return 0;
}
emplace_back的使用
该函数是 C++11 新增加的，其功能和 push_back() 相同，都是在 vector 容器的尾部添加一个元素。
emplace_back() 和 push_back() 的区别，就在于底层实现的机制不同。push_back() 向容器尾部添加元素时，首先会创建这个元素，然后再将这个元素拷贝或者移动到容器中（如果是拷贝的话，事后会自行销毁先前创建的这个元素）；而 emplace_back() 在实现时，则是直接在容器尾部创建这个元素，省去了拷贝或移动元素的过程。
#include <vector>
#include <iostream>
using namespace std;
class testDemo
{
public:
testDemo(int num):num(num){
std::cout << "调用构造函数" << endl;
}
testDemo(const testDemo& other) :num(other.num) {
std::cout << "调用拷贝构造函数" << endl;
}
testDemo(testDemo&& other) :num(other.num) {
std::cout << "调用移动构造函数" << endl;
}
private:
int num;
};
int main()
{
cout << "emplace_back:" << endl;
std::vector<testdemo> demo1;
demo1.emplace_back(2);
cout << "push_back:" << endl;
std::vector<testdemo> demo2;
demo2.push_back(2);
}
运行结果：
emplace_back:
调用构造函数
push_back:
调用构造函数
调用移动构造函数
显然完成同样的操作，push_back() 的底层实现过程比 emplace_back() 更繁琐，换句话说，emplace_back() 的执行效率比 push_back() 高。因此，在实际使用时，建议大家优先选用 emplace_back()。
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::vector;
class Point
{
friend std::ostream& operator<<(std::ostream& os,const Point& rhs);
public:
Point(int ix = 0, int iy = 0)
: _ix(ix)
, _iy(iy)
{
cout << "调用构造函数";
print();
}
Point(const Point& other)
: _ix(other._ix)
, _iy(other._iy)
{
cout << "调用拷贝构造函数";
print();
}
Point(Point&& other)
: _ix(other._ix)
, _iy(other._iy)
{
cout << "调用移动构造函数" << endl;
}
void print() const
{
cout << "(" << _ix
<< ", " << _iy
<< ")" << endl;
}
private:
int _ix;
int _iy;
};
std::ostream& operator<<(std::ostream& os,const Point& rhs)
{
os << "(" << rhs._ix
<< "," << rhs._iy
<< ")";
return os;
}
template <typename container="">
void display(const Container& con)
{
for(auto& elem : con)
{
cout << elem << " ";
}
cout << endl;
}
void test()
{
vector<point> number;
vector<point> number1;
/* Point pt(1,2); */
cout << "push_back: " << endl;
number.push_back(Point(1,2));
/* number.push_back({1,2}); */
/* number.push_back(pt); */
cout << endl << endl << "emplace_back: "<< endl;
cout << "number1.size() = " << number1.size() << endl;
cout << "number1.capacity() = " << number1.capacity() << endl;
number1.emplace_back(3,4);
cout << "number1.size() = " << number1.size() << endl;
cout << "number1.capacity() = " << number1.capacity() << endl;
number1.emplace_back(5,6);
cout << "number1.size() = " << number1.size() << endl;
cout << "number1.capacity() = " << number1.capacity() << endl;
number1.emplace_back(7,8);
cout << "number1.size() = " << number1.size() << endl;
cout << "number1.capacity() = " << number1.capacity() << endl;
number1.emplace_back(9,0);
cout << "number1.size() = " << number1.size() << endl;
cout << "number1.capacity() = " << number1.capacity() << endl;
display(number);
display(number1);
}
int main()
{
test();
return 0;
}
运行结果：
刚开始没有把size和capacity打印出来，会发现使用emplace_back仍然会有拷贝构造函数的调用，比较困惑。后来才想到，这中间会有扩容的操作，而扩容就需要调用拷贝构造函数。