进击高手【第九期】 STL(上)

C++ 功能强大，为我们提供了标准模板库( S t a n d a r d Standard Standard T e m p l a t e Template Template L i b r a r y Library Library，简称STL)，其中封装了很多实用的容器。容器可以理解成能够实现很多功能的系统函数，或者说是一种用来存放数据的对象，我们可以根据格式直接调用，而不用去关心其内部实现的原理和具体代码，十分方便快捷！常见的容器有 v e c t o r 、 s t a c k 、 q u e u e 、 m a p 、 s e t vector、stack、queue、map、set vector、stack、queue、map、set等。

队列（queue）是一种具有先进入队列的元素一定先出队列性质的表。

	#include
	using namespace std;
 	queue name;

1. push()
   push(x) 将 x 入队，时间复杂度为 O ( 1 ) O(1) O(1).
2. front()和back()
   它们分别用来获得 队首元素 和 队尾元素 ，时间复杂度为 O ( 1 ) O(1) O(1).
3. pop()
   pop() 用来让 队首元素 出队，时间复杂度为 O ( 1 ) O(1) O(1)。
4. empty()
   empty() 用来检测 q u e u e queue queue 是否为空，返回 t r u e true true 或者 f a l s e false false ，时间复杂度为 O ( 1 ) O(1) O(1)。

需要注意，在使用 front() 和 pop() 前，必须用 empty() 来判断队列是否为空。

5. size()
   size() 返回 q u e u e queue queue 内元素的个数，时间复杂度为 O ( 1 ) O(1) O(1) 。

在优先队列（priority_queue）中，元素被赋予优先级。优先队列具有最高级先出的行为特征。通常采用堆数据结构来实现。

priority_queue q; // 数据类型为 typename
priority_queue q; // 使用 container作为底层容器
priority_queue q; // 使用 compare 作为比较类型
// 注意：不可跳过 container 直接传入 compare

大根堆优先队列的定义：    
priorty_queue q;            //默认为大顶堆优先队列
priorty_queue,less  > q;
小根堆优先队列的定义：    
priorty_queue,greater  > q;

1. push()
   push(x) 是将 x 加入优先队列，时间复杂度为 O ( l o g 2 n ) O(log_{2}n) O(log2​n)， n n n 为当前优先队列中的元素个数。加入后会自动调整 p r i o r i t y q u e u e priority_queue priorityq​ueue 的内部结构，以保证队首元素的优先级最高。
2. top()
   top() 是获取队首元素，时间复杂度为 O ( 1 ) O(1) O(1)
3. pop()
   pop() 是让队首元素出队，由于出队后要调整堆内部结构，所以时间复杂度是 O ( l o g 2 n ) O(log_{2}n) O(log2​n).

栈（stack）是一种具有后进入栈的元素一定先出栈性质的表。

	#include
	using namespace std;
  	stack name;

1. push()
   push(x) 将 x 压栈，时间复杂度为 O ( 1 ) O(1) O(1)。

2. top()
   用来获得 栈顶元素 ，时间复杂度为 O ( 1 ) O(1) O(1)

3. pop()
   pop() 用来弹出栈顶元素，时间复杂度为 O ( 1 ) O(1) O(1).

   注意pop()是删不是取。

4. empty()
   empty() 用来检测 s t a c k stack stack 是否为空，空返回 t r u e true true，非空返回 f a l s e false false，时间复杂度为 O ( 1 ) O(1) O(1)。

5. size()
   size( ) 返回 s t a c k stack stack 内元素的个数，时间复杂度为 O ( 1 ) O(1) O(1) 。

不定长数组（vector）是一个 内存连续、长度不定 的数组（亦称 列表 或 变长数组 ）数据结构，能够存放各种类型的对象。

// 以下为常数复杂度
// 1. 创建 vector
vector name;
// 2. 移动 v 到新创建的 v1，不发生拷贝，但需要 C++11(与 6 结果相同)
vector v1(std::move(v));  // 或 v1 = std::move(v);

// 以下为线性复杂度
// 3. 创建一个初始空间为 x 的 vector，其元素的默认值是 0
vector name(x);
// 4. 创建一个初始空间为 x 的 vector，其元素的默认值是 y
vector name(x, y);
// 5. 创建一个初始空间为 x 的 vector，
// 其元素的默认值是y, 并且使用 v1 的空间配置器（注：get_allocator：返回相关的分配器）
vector v(x, y, v1.get_allocator());
// 6. 创建一个 v 的拷贝 v1， 其内容元素和 v 一样（与 2 结果相同）
vector v1(v);
// 7. 创建一个 v 的拷贝 v1，其内容是{v[1], v[2]}
vector v1(v.begin() + 1, v.begin() + 3);

1. push_back()
   push_back(x) 将 x 添加到容器最后，时间复杂度为 O ( 1 ) O(1) O(1)
2. size()
   解释：如果 是一维数组 ，size() 用来获得 v e c t o r vector vector 中元素个数；如果是 二维数组 ，size() 用来获得 v e c t o r vector vector 中 第二维 的元素个数，时间复杂度为 O ( 1 ) O(1) O(1)
3. pop_back()
   用来删除 v e c t o r vector vector 中的 尾元素 。时间复杂度为 O ( 1 ) O(1) O(1)
4. clear()
   用来清空 v e c t o r vector vector 中的所有元素。时间复杂度为 O ( n ) O(n) O(n)
5. insert()
   insert(it, x) 用来向 v e c t o r vector vector任意迭代器 i t it it 处插入元素 x x x。时间复杂度为 O ( n ) O(n) O(n)
6. erase()
   erase() 用来删除 v e c t o r vector vector 中的元素，有两种用法，一是 erase(it) ，删除迭代器 i t it it 处的单个元素；二是 erase(first, last) ，删除左闭右开区间内的所有元素。