C++的容器

STL具有容器概念和容器类型

容器概念是具有名称（如容器，序列容器，关联容器等）的通用类别

容器类型是可用于创建具体容器对象的模板

目录

1.容器概念

2.序列

3.容器类型

4.forward_list

5.queue(包含头文件queue)

6.priority_queue(包含头文件queue)

7.stack(包含头文件stack)

---

1.容器概念

没有与基本容器概念对应的类型，但概念描述了所有容器类通用的元素。它是一个概念化的抽象基类。容器概念指定了所有STL容器类都必须满足的一系列要求。

容器是存储其他对象的对象。背存储的对象必须是同一种类型，它们可以是OOP意义上的对象，也可以是内置类型值。

存储再容器中的数据为容器所有，这意味着当容器过期时，存储再容器中的数据也将过期。

不能将任何类型的对象存储在容器中，类型必须是可复制构造和可赋值的。

所有的容器都提供某些特征和操作我们先来看一些基本的容器特征

这里面复制操作保留源对象，而移动操作可修改源对象，还可能转让所有权，而不做任何复制

X:容器类型

T：存储再容器中的对象类型

a,b：类型为X的值

r:类型为X&的值

u:类型为X的标识符（如果X表示vector<int>,则u是一个vector<int>对象）

rv:表示类型为X的非常量右值

而复杂度从块到慢依次为 编译时间 > 固定时间 > 线性时间

编译时间:操作将再编译时执行，执行时间为0

固定时间:操作发生在运行阶段，但独立于对象中的元素数目

线性时间：操作时间于数据数目成正比

2.序列

我们可以通过添加要求来改进基本的容器概念。序列是一种重要的改进。序列概念增加了迭代器至少是正向迭代器这样的要求，着保证了元素将按特定顺序排列，而不会再两次迭代之间发生变化

序列要求其他元素严格按照线性顺序排列，即存在第一个元素，最后一个元素，除第一个元素和最后一个元素之外，每个元素前后都分别有一个元素

序列的要求

序列的可选要求

a[n]和at[t]的却别在于后者会执行边界检擦，并引发out_of_range异常

3.容器类型

vector:vector是数组的一种类表示，它提供了自动内存管理功能，可以动态地改变vector对象的长度，并随着元素的添加和删除而增大和缩小。它提供了对元素对的随机访问。在尾部添加和删除元素的时间是固定的，但在头部或中间插入和删除元素的复杂度为线性时间。并且vector还是可反转容器概念的模型

deque(包含头文件deque):双端队列。支持随机访问，从deque对象的开始位置插入和删除元素的时间是固定的。

虽然vector和deque提供了对元素的随机访问和在序列中部执行线性时间的插入和删除操作，但vector容器执行这些操作时速度要快些。

list(包含头文件list):双向链表，除第一个和最后一个元素外，每个元素都与前后的元素相链接，所以list属于双向遍历链表。

list在链表中任一位置进行插入和删除的时间都是固定的。list也属于可反转容器。但vector不支持数组表示法和随机访问。与矢量迭代器(vector)不同，从容器中插入或删除元素之后，链表迭代器指向元素将不变。

除了序列和可反转容器的函数外，list模板类还包含了链表专用的成员函数

#include <iostream>
#include <list>
#include <iterator>
#include <algorithm>
using namespace std;

void outint(int n) { cout << n << " "; }

int main()
{
	list<int> one(5, 2);
	int stuff[5] = { 1,2,4,8,6 };

	list<int> two;

	two.insert(two.begin(), stuff, stuff + 5);	//将数组stuff的值插入到two容器中
	int more[6] = { 6,4,2,4,6,5 };
	
	list<int> three(two);	//新创建了three容器值和two一样
	three.insert(three.end(), more, more + 6);	//从three容器末尾插入more数组的值

	cout << "List one: ";
	for_each(one.begin(), one.end(), outint);

	cout << endl << "List two: ";
	for_each(two.begin(), two.end(), outint);

	cout << endl << "List three: ";
	for_each(three.begin(), three.end(), outint);

	three.remove(2);		//从three容器中删除2

	cout << endl << "List three minus 2s: ";
	for_each(three.begin(), three.end(), outint);

	three.splice(three.begin(), one);	//将one链表容器内容插入到three容器当中，此时one容器为空
	cout << endl << "List three after splice: ";
	for_each(three.begin(), three.end(), outint);

	cout << endl << "List one: ";
	for_each(one.begin(), one.end(), outint);

	three.unique();		//将连续的相同元素压缩为单个元素
	cout << endl << "List three after unique: ";
	for_each(three.begin(), three.end(), outint);

	three.sort();	//重新排序
	three.unique();

	cout << endl << "List three after sort& unique: ";
	for_each(three.begin(), three.end(), outint);
	two.sort();
	three.merge(two);	//将two容器内容插入到three容器中，合并后经过排序的链表保存在调用链表中

	cout << endl << "Sorted two merged into three: ";
	for_each(three.begin(), three.end(), outint);
	cout << endl;

	return 0;
}

4.forward_list

它实现了单链表。在这种链表中，每个节点都只链接到下一个节点，而没有链接到前一个节点。

forward_list只需要正向迭代器，而不需要双向迭代器。forward_list是不可逆得容器。

5.queue(包含头文件queue)

queue模板类是一个适配器类。queue模板让底层类展示典型的队列接口。

它不仅不允许随机访问队列元素，甚至不允许遍历队列。

6.priority_queue(包含头文件queue)

一个适配器类，它支持的操作与queue相同。不同的是，在priority_queue中，最大的元素被移到队首。

内部的区别在于，默认的底层类是vector。

7.stack(包含头文件stack)

stack也是一个适配器，它给底层类提供了典型的栈接口

stack模板的限制比vector更多。它不仅不允许随机访问栈元素，甚至不允许遍历栈。它把使用限制在定义栈的基本操作上，即可以将压入推到栈顶，从栈顶弹出元素，查看栈顶的值，检查元素数目和测试栈是否为空