跳转至

容器适配器

栈

STL 栈(std::stack) 是一种后进先出 (Last In, First Out) 的容器适配器，仅支持查询或删除最后一个加入的元素（栈顶元素），不支持随机访问，且为了保证数据的严格有序性，不支持迭代器。

头文件

1
#include <stack>

定义

1
2
3
std::stack<TypeName> s;  // 使用默认底层容器 deque，数据类型为 TypeName
std::stack<TypeName, Container> s;  // 使用 Container 作为底层容器
std::stack<TypeName> s2(s1);        // 将 s1 复制一份用于构造 s2

成员函数

以下所有函数均为常数复杂度

  • top() 访问栈顶元素（如果栈为空，此处会出错）
  • push(x) 向栈中插入元素 x
  • pop() 删除栈顶元素
  • size() 查询容器中的元素数量
  • empty() 询问容器是否为空

简单示例

1
2
3
4
5
6
7
8
9
std::stack<int> s1;
s1.push(2);
s1.push(1);
std::stack<int> s2(s1);
s1.pop();
std::cout << s1.size() << " " << s2.size() << std::endl;  // 1 2
std::cout << s1.top() << " " << s2.top() << std::endl;    // 2 1
s1.pop();
std::cout << s1.empty() << " " << s2.empty() << std::endl;  // 1 0

队列

STL 队列(std::queue) 是一种先进先出 (First In, First Out) 的容器适配器，仅支持查询或删除第一个加入的元素（队首元素），不支持随机访问，且为了保证数据的严格有序性，不支持迭代器。

头文件

1
#include <queue>

定义

1
2
3
4
std::queue<TypeName> q;  // 使用默认底层容器 deque，数据类型为 TypeName
std::queue<TypeName, Container> q;  // 使用 Container 作为底层容器

std::queue<TypeName> q2(q1);  // 将 s1 复制一份用于构造 q2

成员函数

以下所有函数均为常数复杂度

  • front() 访问队首元素（如果队列为空，此处会出错）
  • push(x) 向队列中插入元素 x
  • pop() 删除队首元素
  • size() 查询容器中的元素数量
  • empty() 询问容器是否为空

简单示例

1
2
3
4
5
6
7
8
9
std::queue<int> q1;
q1.push(2);
q1.push(1);
std::queue<int> q2(q1);
q1.pop();
std::cout << q1.size() << " " << q2.size() << std::endl;    // 1 2
std::cout << q1.front() << " " << q2.front() << std::endl;  // 1 2
q1.pop();
std::cout << q1.empty() << " " << q2.empty() << std::endl;  // 1 0

优先队列

优先队列 std::priority_queue 是一种 堆，一般为 二叉堆。

头文件

1
#include <queue>

定义

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
std::priority_queue<TypeName> q;             // 数据类型为 TypeName
std::priority_queue<TypeName, Container> q;  // 使用 Container 作为底层容器
std::priority_queue<TypeName, Container, Compare> q;
// 使用 Container 作为底层容器，使用 Compare 作为比较类型

// 默认使用底层容器 vector
// 比较类型 less<TypeName>（此时为它的 top() 返回为最大值）
// 若希望 top() 返回最小值，可令比较类型为 greater<TypeName>
// 注意：不可跳过 Container 直接传入 Compare
std::priority_queue<TypeName> pq;             // 数据类型为 TypeName
std::priority_queue<TypeName, vector<TypeName>> pq1;  // 使用vector作为底层容器
//greater > 小根堆    less < 大根堆
std::priority_queue<TypeName, vector<TypeName>, greater<TypeName>> pq2;  


//与结构体的使用
struct point{
  int x,y,v;
  bool operator < (const point &other) const{  //重载<运算符
    return v<other.v;  // < 大根堆      > 小根堆
  }

  //结构体内声明友元函数
  friend bool operator < (const point &a,const point &b){
    return a.v<b.v;  
  } 
};

//在结构体外重载<
operator < (const point &a,const point &b){
    return a.v<b.v;  
  } 

std::priority_queue<point> pq;

// 从 C++11 开始，如果使用 lambda 函数自定义 Compare
// 则需要将其作为构造函数的参数代入，如（在标准命名空间下）：
auto cmp = [](const pair<int, int> &l, const pair<int, int> &r) {
  return l.second < r.second;
};
//在标准命名空间下
priority_queue<pair<int, int>, vector<pair<int, int>>,decltype(cmp)> pq(cmp);

成员函数

以下所有函数均为常数复杂度

  • top() 访问堆顶元素（此时优先队列不能为空）
  • empty() 询问容器是否为空
  • size() 查询容器中的元素数量

以下所有函数均为对数复杂度

  • push(x) 插入元素，并对底层容器排序
  • pop() 删除堆顶元素（此时优先队列不能为空）

简单示例

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
std::priority_queue<int> q1;
std::priority_queue<int, std::vector<int>> q2;
// C++11 后空格可省略
std::priority_queue<int, std::deque<int>, std::greater<int>> q3;
// q3 为小根堆
for (int i = 1; i <= 5; i++) q1.push(i);
// q1 中元素 :  [1, 2, 3, 4, 5]
std::cout << q1.top() << std::endl;
// 输出结果 : 5
q1.pop();
// 堆中元素 : [1, 2, 3, 4]
std::cout << q1.size() << std::endl;
// 输出结果 ：4
for (int i = 1; i <= 5; i++) q3.push(i);
// q3 中元素 :  [1, 2, 3, 4, 5]
std::cout << q3.top() << std::endl;
// 输出结果 : 1