【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>表示数字小的优先级越大,即升序排列,小顶堆

  1. 结构体的优先级

需要用到重载运算符(

操作

和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中的键值是唯一的。

  1. 通过迭代器访问:
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;
    }
  1. 通过函数

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()

和其他容器的用法相同

上一篇:用.bat批处理搞一个简易对拍器


下一篇:day15 - centos7部署nagios(服务端目录、配置语法)(ob16)