STL学习笔记5 —— Container Adaptor
文章目录一、容器适配器二、stack容器1. stack的特点与使用2. stack的成员函数一、容器适配器接下来介绍 3 种容器适配器,分别是 stack、queue、priority_queue:stack:是一个封装了 deque 容器的适配器类模板,默认实现的是一个后入先出(Last-In-First-Out,LIFO)的压入栈。stack 模板定义在头文件 stack 中。queue:是
文章目录
一、容器适配器
接下来介绍 3 种容器适配器,分别是 stack
、queue
、priority_queue
:
- stack:是一个封装了 deque 容器的适配器类模板,默认实现的是一个后入先出(Last-In-First-Out,LIFO)的压入栈。stack 模板定义在头文件 stack 中。
- queue:是一个封装了 deque 容器的适配器类模板,默认实现的是一个先入先出(First-In-First-Out,LIFO)的队列。可以为它指定一个符合确定条件的基础容器。queue 模板定义在头文件 queue 中。
- priority_queue:是一个封装了 vector 容器的适配器类模板,默认实现的是一个会对元素排序,从而保证最大元素总在队列最前面的队列。priority_queue 模板定义在头文件 queue 中。
简单的理解容器适配器:将不适用的序列式容器(包括 vector、deque 和 list)变得适用
功能如下:
container addaptor | characteristic | functions |
---|---|---|
stack | LIFO | push()、pop()、top() |
queue | FIFO | push()、pop()、front()、back() |
priority_queue | first item is the greatest priority | push()、pop()、top() |
三类容器适配器均无迭代器,因此访问元素的唯一方式是遍历容器,通过不断移除访问过的元素,去访问下一个元素
二、stack容器
1. stack的特点与使用
栈中存储的元素满足“后进先出(简称LIFO)”的准则,stack 适配器也同样遵循这一准则。
由于 stack 适配器以模板类 stack<T,Container=deque<T>>
(其中 T 为存储元素的类型,Container 表示底层容器的类型)的形式位于头文件中,并定义在 std 命名空间里。第二个参数默认为 deque
,可以指定第二个参数的类型,只要该容器支持 empty()、size()、back()、push_back()、pop_back() 这 5 个成员函数即可,如:vector
、deque
和 list
:
std::stack<std::string, std::list<int>> values;
2. stack的成员函数
函数 | 功能 |
---|---|
size() | 返回元素个数 |
empty() | 若stack为空则返回true |
top() | 返回栈顶元素的引用&,栈空则报错 |
push(const T& val) | 将val压栈,利用了push_back()来实现 |
pop() | 弹栈操作 |
举例:
#include <iostream>
#include <stack>
#include <list>
using namespace std;
int main()
{
stack<int> s;
stack<int, std::list<int>> s1;
s.push(2);
s.push(5);
s.push(1);
s.push(8);
cout << s.size() << endl;
while(!s.empty()){
cout << s.top() << " ";
s.pop();
}
return 0;
}
结果:
4
8 1 5 2
三、queue容器
1. queue的特点与使用
这种存储结构最大的特点是,最先进入 queue 的元素,也可以最先从 queue 中出来,即用此容器适配器存储数据具有“先进先出(简称 “FIFO” )”的特点,因此 queue 又称为队列适配器。
queue容器包含在 <queue>
库中,定义一个queue容器可以指定基础容器(deque
或list
),底层使用的基础容器选择默认为 deque
容器
#include <queue>
#include <iostream>
using namespace std;
queue<int, deque<int>> q;
queue<int, std::list<int>> q1;
2. queue的成员函数
函数 | 功能 |
---|---|
size() | 返回元素个数 |
empty() | 若stack为空则返回true |
front() | 返回 queue 中第一个元素的引用。如果 queue 是常量,就返回一个常引用;如果 queue 为空,返回值是未定义的 |
back() | 返回 queue 中最后一个元素的引用。如果 queue 是常量,就返回一个常引用;如果 queue 为空,返回值是未定义的 |
push(const T& val) | 在 queue 的尾部添加一个元素的副本。这是通过调用底层容器的成员函数 push_back() 来完成的。 |
pop() | 删除 queue 中的第一个元素。 |
swap(queue &other_queue) | 交换两个容器(要求底层基础容器相同 |
3. queue的使用
#include <queue>
#include <iostream>
using namespace std;
int main()
{
queue<int> myque;
myque.push(5);
myque.push(2);
myque.push(2);
myque.push(3);
myque.push(6);
cout << "size: " << myque.size() << endl;
while (!myque.empty()){
cout << myque.front() << " ";
myque.pop();
}
return 0;
}
四、priority_queue容器
1. 特点
priority_queue容器遵循 “First in,Largest out”原则。直白的翻译,指的就是先进队列的元素并不一定先出队列,而是优先级最大的元素最先出队列。每个 priority_queue 容器适配器在创建时,都制定了一种排序规则。根据此规则,该容器适配器中存储的元素就有了优先级高低之分。
2. 使用
STL 中,priority_queue 容器适配器的定义如下:
template <typename T,
typename Container=std::vector<T>,
typename Compare=std::less<T> >
class priority_queue{
//......
}
- priority_queue定义在
<queue>
头文件中 - typename
T
:指定存储元素的具体类型; - typename
Container
:指定 priority_queue 底层使用的基础容器,默认使用 vector 容器。 - typename Compare:指定容器中评定元素优先级所遵循的排序规则,默认使用std::less按照元素值从大到小进行排序,还可以使用std::greater按照元素值从小到大排序,但更多情况下是使用自定义的排序规则。
作为 priority_queue 容器适配器的底层容器,其必须包含 empty()、size()、front()、push_back()、pop_back() 这几个成员函数,STL 序列式容器中只有 vector 和 deque 容器符合条件。
priority_queue的操作函数和stack的类似,包含了push()
、pop()
、top()
、empty()
和 size()
等函数。
#include <iostream>
#include <queue>
using namespace std;
class Student{
public:
string name;
int number;
Student(string str, int n):name(str), number(n){}
};
struct mycmp{
bool operator() (const Student &s1, const Student &s2){
return s1.number < s2.number; // 从大到小
}
};
int main()
{
priority_queue<Student, deque<Student>, mycmp> pq;
pq.push(Student("L", 12));
pq.push(Student("Y", 3));
pq.push(Student("U", 8));
pq.push(Student("C", 5));
cout << "Size = " << pq.size() << endl;
cout << "name" << "\t" << "number" << endl;
while(!pq.empty()){
Student stud = pq.top();
cout << stud.name << "\t" << stud.number << endl;
pq.pop();
}
return 0;
}
输出结果为:
Size = 4
name number
L 12
U 8
C 5
Y 3
参考内容:容器适配器的使用
更多推荐
所有评论(0)