2022年8月学习记录 - STL

系统学习

建议搭配 2022 年 8 月学习记录 - 队列、栈及其应用 一起使用。

我的学习资料

BiliBili：清华算协暑期培训 第二讲 STL & 基础数据结构

栈（Stack）

特征：先进后出/后进先出

// STL 实现
#include<stack>
std::stack<T> s;
s.push(x);		//插入元素
s.pop();		//弹出元素
s.top();		//查询头元素

// 数组实现
const int N = 10;		//栈的大小
T stack[N];
int top=0;
// 判断栈是否为空
bool empty(int top){
    return top==0;
}
// 判断栈是否已满
bool full(int top){
    return top==n;
}
// 插入一个元素
bool push(T stack[],T x){
    if(full){
        return 0;
    }
    stack[top++]=x;
    return 1;
}
// 弹出一个元素
bool pop(T stack[],T *x){
    if(empty){
        return 0;
    }
    x=stack[--top];
    return 1;
}
// 查询头元素
bool top(T stack[],T *x){
    if(sempty){
        return 0;
    }
    x=stack[top];
    return 1;
}

卡特兰数(Catalan)

应用：括号序列、三角剖分、二叉树计算

队列（Queue）

特性：先进先出。

// STL实现
#include<queue>
std::queue<T> q;
q.push(x);		//插入元素
q.pop();		//弹出元素
q.front();		//查询头元素
q.back();		//查询尾元素

// 数组实现
const int N = 10;		//队列的大小
T queue[N];
int head=0,tail=0;
// 返回队列大小
bool size(T queue[]){
	return tail-head;   
}
// 判断队列是否为空
bool empty(){
    return head==tail;
}
// 插入元素
bool push(T queue[],T x){
    if(){
        return 0;
    }
    queue[tail++]=x;
    return 1;
}
// 弹出元素
bool pop(T queue[],T *x){
    if(empty){
        return 0;
    }
    x=queue[head++];
    return 1;
}
// 查询头元素
bool front(int *x){
    if(empty){
        return 0;
    }
    x=queue[head];
    return 0;
}
// 查询尾元素
bool back(int *x){
    if(empty){
        return 0;
    }
    x=queue[tail];
    return 0;
}

向量（Vector）

一句话概括：不定长的数组。

// STL实现
#include<vertor>
std::vector<T> v;
v.insert(iter,x);		//在iter处插入元素
v.push_back();			//在末尾插入元素
v.erase(iter);			//弹出iter处的元素
v.pop_back();			//弹出尾元素

// 数组实现
int *a = new int [N];

列表（List）与链表（linked list）

// STL实现
#include<list>
std::list<T> l;
l.front();				//查询头元素
l.back();				//查询尾元素
l.insert(iter,x);		//在iter处插入元素
l.push_back();			//在末尾插入元素
l.push_front();			//在开头插入元素
l.erase(iter);			//弹出iter处的元素
l.pop_back();			//弹出尾元素
l.pop_front();			//弹出头元素

链表的结构

哨兵节点：

头元素和尾元素的处理：可以不用考虑边界情况

• use it or 特判

单向链表：

struct Node {
    int val;
    Node *next;
};
std::forward_list (C++11)

基本操作 - 插入

Node* insert(Node *pos,int value){
    Node *n = new Node(value);
    n->next = pos->next;
    post->next = n;
    return n;
}
// 注：代码中的语句顺序不能调换

基本操作 - 删除

void erase(Node *pos){
    Node *tmp = pos->next;
    pos->next = pos->next->next;
    delete tmp;
}

翻转 - reverse()

将一个链表整体翻转

std::forward_list::reverse()

双向链表：

struct Node{
    int val;
    Node *prev,*next;
};

基本操作 - 插入

Node* insert(Node *pos,int value){
    Node *n = new Node(value);
    n->next = pos->next;
    n->prev = pos;
    pos->next->prev = n;
    pos->next = n;
    return n;
}
// 注：代码中的语句顺序不能调换

基本操作 - 删除

void erase(Node *pos){
    pos->prev->next = pos->next;
    pos->next->prev = pos->prev;
    delete pos;
}
// 注：代码中的语句顺序可以调换
//	   STL 的 erase 方法会返回删除之后的原子之后的迭代器，这里为了简化代码就仅返回了 void

翻转 - reverse()

将一个链表整体翻转

std::list::reverse()

交换 prev 和 next （首尾特别处理）

通用

基本操作 - 遍历

for (Node* x = head->next; x != tail; x = x->next);

一些技巧

生产环境中请不要随意使用

内存池

优化 new 和 delete 的时间复杂度

Node pool[MAXN];
int top;
Node* newnode(){
    return &pool[top++];
}

数组下标模拟指针

struct Node{
    int val,next;
} pool[MAXN];
int top;
int newnode(){
    return top++;
}

优先队列（Priority Queue）

特征：“优先级”大的先离开

#include<queue>
std::priority_queue<T> pq;
pq.push(x);		//插入一个元素
pq.pop();		//弹出最大的元素
pq.top();		//查询最大的元素

std:greater<T>	//反向使用

实现：二叉树

其他 STL

容器类

1. set/map

2. deque

算法类

#include<algorithm>

1. sort：排序

2. lower_bound：二分查找（大于等于）

3. upper_bound：二分查找（大于）

4. merge：归并

更多资料

一些应用

单调栈 单调队列

• 例题给出 $n$ 天的气温情况，对于每一天，求出前k天的气温最大值。

• 关键的观察：如果存在两个数满足 $ i<j∧a_i<a_j $ ,那么在$a$被纳入考察之后，$a$ 就不可能成为最大值了。（如果有人比你年轻还比你强）

• 那么我们需要考虑的可能值是单调递减的。

• 从左到右扫描，每加入一个数，可以排除最末尾的一段数的可能性。

• 同时我们只需要维护前k天的情况，因此过期的数据也可排除。

• 我们需要实现 push_back,pop_back,pop_front。

表达式求值

• 为了简化问题，假设我们只有 $ + $ $ - $ $ * $ $ / $ $ () $ 这几种运算。

• 观察：$1+2*3$ 和 $1*2+3$ 。我们什么时候可以确定计算顺序？

• 第一个等式需要到最末尾，第二个等式在扫描到 $+$ 的时候就发现可以计算前面的内容。

• 无法判断的式子优先级大小递增。

• 类似单调队列的单调栈。同时需要维护没有计算的数。

• 将括号也纳入优先级比较的范围，或者每遇到一层括号，括号内优先级增加一档。