【2022.1.21】STL学习笔记（优先队列，deque，map，stack，pair，list）

本文主要是介绍【2022.1.21】STL学习笔记（优先队列，deque，map，stack，pair，list），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

priority_queue优先队列

优先队列，具有队列的所有特性和基本操作，只是在这基础上添加了内部的一个排序，它本质是由堆实现

头文件#include<queue>

数据结构

队首元素一定是优先级最高的一个

声明

priority_queue<int> a默认为大顶堆，降序

访问

只能通过a.top() 访问队顶元素

优先级设置

priority_queue<typename, container, functional>完整的定义方式

container容器默认为vector，functional默认为less<int>

1. 基本数据类型的优先级

less<int>表示数字大的优先级越大，即降序排列，大顶堆

greater<int>表示数字小的优先级越大，即升序排列，小顶堆

2. 结构体的优先级

需要用到重载运算符（

操作

和queue队列操作基本相同

a.top() 访问队头元素，无a.front()，a.back()

a.push(x)将x进行入队（时间复杂度为O(log n))

a.pop()令队首元素出队（时间复杂度为O(log n))

应用

贪心

queue

头文件#include<queue>

数据结构

先进先出，queue容器允许从一端新增元素，从另一端移除元素。

queue无迭代器。

声明

queue<int> a;新建一个queue容器

访问

只能通过a.front()，a.back()来访问队首，队尾元素

操作

a.push(x)将x进行入队（时间复杂度为O(1))

a.pop()令队首元素出队

a.front()获取队首元素

a.back()获取队尾元素

应用

广搜

map

头文件include<map>

我们可以把array数组理解为int到int的映射

map可以将任意数据类型(包括STL)映射到任意数据类型(包括STL)

声明

map<typename1,typename2> atypename1和typename2分别为键值，实值

map<string,int> a字符串到整型的映射，必须使用string，不能用char

访问

1. 通过键值访问：

比如当建立了map<char,int> a的map时，可以直接使用a['c']这样的方式来访问它对应的int

注意：map中的键值是唯一的。

2. 通过迭代器访问：

map<key,value>::iterator it1;
it1 -> first; //访问当前映射的键值
it1 -> second; //访问当前映射的实值

迭代器

map<key,value>::iterator it1;双向访问迭代器，解引用后得到一个二元组pair

数据结构

map会按照键值的字典序由小到大自动排序，这是因为map内部是用红黑树实现的

操作

a.find(key)返回键值为key的映射的迭代器，O(log n)

a.erase(it) 删除单个元素，it为需要删除元素的迭代器，O(1)

a.erase(key) 删除单个元素，key为所需要删除元素的键值，O(log n)

a.erase(l,r)删除一个区间内的所有元素，l为区间的起始迭代器，r为区间末尾迭代器的下一个地址

a.size()获取map内映射的对数

a.clear()以下同set

a.begin()

a.end()

a.empty()

应用

处理大整数或其他类型数据的题目

需要建立字符或字符串到整数的映射

multimap

Multimap和map的操作类似，唯一区别multimap键值可重复。

Map和multimap都是以红黑树为底层实现机制。

stack

头文件include<stack>

后进后出的容器。

无迭代器，不能遍历。

声明

stack<int> a

访问

只能通过top()来访问栈顶元素

操作

a.push(x)将x入栈

a.top()获取栈顶元素

a.pop()弹出栈顶元素

a.empty()

a.size()

数据结构

后进后出

应用

实现某些递归

pair

头文件#include<map>或#include<utility>

<map>中包含<utility>

pair可以把两个元素绑在一起作为一个合成元素

pair可以看作一个内部有两个元素的结构体

声明

pair<typename1,typename2> a其中typename1，typename2可以是任意基本数据类型或容器

pair<typename1,typename2> a(value1,value2)声明并进行初始化

a = pair<string,int>("asd",123)在代码中临时构建一个pair

a = make_pair("asd",123)使用自带函数在代码中临时构建一个pair

访问

按结构体的方式访问

a.first访问第一个元素

a.second访问第二个元素

操作

两个pair类型数据可以直接使用==，!= ，<，<=，>，>=比较大小，规则是先以first的大小为标准，若first相等再判断second

pair<int,int> a(10,10);
pair<int,int> b(5,5);
a>b;

应用

代替二元结构体

作为map的键值进行插入：

map<string,int> a;
a.insert(make_pair("c",123));

list

头文件#include<list>

数据结构

• list容器为双向链表

• 链表是一种在物理内存空间中非连续，非顺序的存储结构

• 元素的逻辑顺序通过链表中的指针链接次序实现

• 链表中的元素称为节点，一个节点包括两部分：数据域(存数据)和指针域(存下个节点的地址)

• 链表为动态内存分配，每次插入或者删除一个元素，就会配置或者释放一个元素的空间

• 链表灵活，但是空间和时间额外耗费较大，随机访问较慢

迭代器

• list为双向迭代器,不支持随机访问

• 插入和删除操作都不会造成原有list迭代器的失效。

声明

list<int> a

访问

1. 使用迭代器

list<int> a;
for(list<int>::iterator it = a.begin(); it != a.end(); it++)
    {
      cout<<*it;
    }

2. 通过函数

front() 和 back()

操作

a.push_back(x) 在容器尾部加入一个元素x

a.push_front(x) 在容器开头插入一个元素x

a.pop_back() 删除容器中最后一个元素

a.pop_front()移除容器中第一个元素

a.remove(x) 删除容器中所有与x值匹配的元素

a.assign(l,r) 将[l,r)中的数据赋值给本身

a.swap(c) 将c与本身的元素互换

a.front()返回第一个元素

a.back() 返回最后一个元素

a.insert()，a.erase()，a.clear()，a.size() ，a.empty()

和其他容器的用法相同

这篇关于【2022.1.21】STL学习笔记（优先队列，deque，map，stack，pair，list）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！