5 STL“容器”的使用与练习

"容器" 为什么要加引号呢～请往下看

课程内容#

模板 <类型> 名；// 自定义类型也可以，如 struct

队列与栈#

queue#

queue que;
名。方法 ()
- que.push (5); // 入队
- que.pop (); // 出队
- que.front (); // 队首元素
- que.size (); // 元素个数
- que.empty (); // 是否为空

stack#

stack sta;
名。方法 ()
- sta.push(5);
- sta.pop();
- sta.top(); // 栈顶元素，唯独与 queue 不一样的
- sta.size();
- sta.empty();

本质#

它们的底层是由deque实现的
- double-ended queue，双端队列
- 参考deque-cppreference
它们是对 deque 的封装，实际是适配器
- deque 才是正儿八经的容器

向量与优先队列#

vector#

【插：在 C 语言中，不能定义变长数组，❌不可这样定义：int n; scanf ("% d", &n); int num [n]】

vector v;
名。方法 ()
- v.push_back (5); // 在尾部添加一个元素O(1)
- v.size (); // 元素数量
- v.insert (1, 6); // 插入元素O(N)，用 push_back 更高效
vector<vector > v2; // 动态二维数组
- C++11 标准之前 "> >" 之间要有空格，否则易被误认为是右移操作
初始化，参考vector 的几种初始化及赋值方式-CSDN
cin 到 vector 需要先将 vector 初始化出空间大小

priority_queue#

priority_queue que;
- int 后可以添加排序的对象
- 参考C++ priority_queue (STL priority_queue) 用法详解-C 语言中文网
名。方法 ()
- que.push(5);
- que.pop();
- que.top(); // 堆顶元素，默认是大数在上
- que.size();
- que.empty();
自定义结构型优先队列需要重载小于号
- bool operator <(const struct 名 & 变量) {}
- 注：重载小于号，对于这个容器，在里面实现的若是
  - a) <，则从大到小排列，对应最大堆
  - b) >，则从小到大排列，对应最小堆
  - 有点绕，详细见代码演示 - priority_queue
- 注：所有需要排序的容器结构，都是重载小于号

本质#

vector 底层是用数组实现的
priority_queue 底层是用堆实现的

字符串 string#

类

string str;
名。方法 ()
- str.size () // 等同于 str.length ()
- str.find (s2, pos = 0); // 在 str 中查找 s2，默认从头 (pos = 0) 开始查找，找到返回下标
  - 底层方法实现取决于编译器
  - 判断是否找到（no position）

if (str,find(s2) != string::npos) {
  // static const size_t npos = -1;
  // 找到了
} else {
  // 未找到
}

- str.insert (x, s2); // 在下标 x 处插入 s2
- str.substr (2); // 从下标 2 截取到最后
- str.substr (2, len); // 注意第二个参数是长度
- str.replace (index, len, s2); // 同样注意第二个参数是长度
重载了很多运算符
- +
  - string a = string("123") + string("a");
  - += 慎用
    - a += string ("123") + string ("456"); // "+=" 优先级仅高于 ","
    - ❓ 想象一下定义了多少临时变量，值拷贝了多少次
- ==、>=、<=、>、<
  - 根据字典序判断
- =
  - str = "123a"
  - 可以直接赋值，不像 C 语言需要使用 strcpy

键值对 map#

映射

map<string, int> m; // "123" → 456
方法
- []
  - 赋值、访问
  - 如果访问的 key 不存在，就会自动创建一个，按类型的默认值赋值
  - 有隐式开销，因为底层是红黑树，查找效率为 O (logN)
- insert、find、erase
- count
  - 返回某个 key 多少个
  - 但 map 里没有重复的，所以只返回 0、1
  - 可用来判断 key 是否存在
底层实现是红黑树【RBTree】
- 有序的结构，map 默认升序排
- 如果 key 对应的是自定义结构体，需重载 < 号
扩展
- multimap
  - 可以有多个重复的键存在
- unordered_map ❗c++11 里出现
  - 无序
  - 底层实现是哈希表，查找、插入效率均为 O (1)
  - 自定义结构需要手动实现哈希函数
    - 参考C++ STL 无序容器自定义哈希函数和比较规则-C 语言中文网

集合 set#

可用来去重、排序
底层和 map 一样，红黑树，必要时也需重载 “<”
扩展
- multiset
- unordered_set ❗c++11

对 pair#

对儿
pair<int, int>
- pair.first 前一元素
- pair.second 后一元素
make_pair可快速创建一个临时的 pair

代码演示#

queue#

两种数据类型的队列
que.empty () 和 que.size () 都是 O (1) 的，底层有一个数据域存储
默认生成构造函数

输出

stack#

与 queue 的区别：名字、头文件、top () 方法

输出

vector#

比数组更高级，在 leetcode 里常用
3 种插入方式

输出

priority_queue#

自定义结构型队列要记得重载小于号
❗重载的是小于号，但完成的是从大到小输出！

输出

第二部分里，实现了从大到小排列，但重载的是小于号，实现的也是小于号

map#

对于自定义结构，map 需重载 <，unordered_map 需定义 hash 函数
对于不存在的 key，访问时会自动创建，并赋值类型的默认值

输出

练习题#

HZOJ-383：周末舞会#

样例输入

3 5 6

样例输出

思路
- 队列
- 出队、放队尾
代码
- 队列的基本操作

HZOJ-378：字符串括号匹配 2#

样例输入

a(cc[])bbb()@

样例输出

YES

思路
- 字符栈
- 匹配：YES，如 ([] )
- 不匹配：NO
  - 括号错开了，如 ([) ]
  - 碰见右括号时，栈为空，如 ())
  - 字符串结束了，栈还不为空，如 (( {} )
- 注意：不能使用三个变量单纯记录个数，因为括号有顺序问题，比如 ([)]
代码
- 注意三种不匹配情况
- 匹配时将左括号出栈

HZOJ-376：机器翻译#

样例输入

3 7
1 2 1 5 4 4 1

样例输出

思路
- 队列
- 用标记数组记录单词
  - mark[x] = 1、0
  - 数据不大（文章长度不超过 1000），没必要用 map、set 之类的
代码
- 关键在存单词的队列和标记单词的数组
- 注意内存已满的情况

HZOJ-379：仓库日志#

样例输入

13 0 1 0 2 2 0 4 0 2 2 1 2 1 1 2 1 2

样例输出

思路
- 0、1、2：入库、出库、查询
- 先进后出：需要一个货物栈
- 查询功能（输出最大值）：还需要一个记录最大值的栈 **【关键】**
- 注意：每次的货物均不同，所以题目被简单化了
代码
- 共两个栈！
  - 对于本题，货物栈可以不用，只是助于理解
  - 因为本题不需要管出栈的货物是什么，而最大栈每次入库都记录最大值，会重复记！

HZOJ-382：报数#

样例输入

7 3

样例输出

思路
- 约瑟夫环问题
- 【精髓】队列：安全的人扔队尾，不安全的人弹出去
- 结束条件：当队列的 size 为 1 时
代码
- push 的 i 是编号
- pop 没有返回值吗？
  - 这里提到的容器里，pop、push 都没有返回值
  - 详见pop-cppreference

HZOJ-384：敲七#

样例输入

4 3 6

样例输出

思路
- 与上题如出一辙，注意细节
- 区别在于
  - 输入：第 x 个人从 t 开始报
  - 判断条件：含 7 或者 7 的倍数
  - 报数不重置，一直 + 1
代码

HZOJ-385：海港#

样例输入

4
1 4 1 2 2 3
3 2 2 3
86401 2 3 4
86402 1 5

样例输出

思路
- 输入：到达时间、人数、每个人的国籍
- 队列 +【标记数组 /map】+ 国家数量的变量
  - 队列存船或人都可以
    - 因为船里的人不固定，存人更方便
  - 先根据时间减人，再加人
  - 国家数量：如果新来一个，+1；如果走了最后一个，-1
代码
- 关键在用到的队列、标记数组和统计国家数量的变量
- 有点像滑动窗口？略像，但一般滑动窗口，其数据是早就固定好的
- 直接复制数据输入，输出格式有点奇怪？应该是换行符的问题
- 33 行快速定义结构体：(struct 名){..., ...}
  - 不加圆括号 () 也没问题，但是加括号可能更清晰

HZOJ-569：溶液模拟器#

样例输入

样例输出

200 50.00000
100 100.00000

思路
- 撤销操作：用栈！存每一次操作后的质量和浓度 [或者] 盐的质量和总质量
- 化学知识回顾
  - 溶液组成：盐 + 水
  - 浓度：盐 / (盐 + 水)
  - 质量：盐 + 水
代码
- 存盐的质量和总质量便于理解计算
  - 都存为 double 类型，输出时注意转换
- 撤销操作：先减再弹

LC-232：用栈实现队列#

思路
- 两个栈实现队列
- 心中有这样一个过程👇
代码

class MyQueue {
public:
    // 在此处声明栈，否则不好调用
    stack<int> s1, s2;
    /** Initialize your data structure here. */
    MyQueue() {
        // 不用管
    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
        s1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        // 先把s1栈的元素全倒到s2栈
        while (!s1.empty()) {
            // 先push再pop，顺序不能反
            s2.push(s1.top());
            s1.pop();
        }
        int t = s2.top();  // 此时取出要pop的值
        s2.pop();          // 出栈
        // 倒回来
        while (!s2.empty()) {
            s1.push(s2.top());
            s2.pop();
        }
        return t;
    }
    
    /** Get the front element. */
    int peek() {
        // 折腾到s2
        while (!s1.empty()) {
            s2.push(s1.top());
            s1.pop();
        }
        int t = s2.top();  // 临时变量t存值，还得放回来再return
        // 折腾回来
        while (!s2.empty()) {
            s1.push(s2.top());
            s2.pop();
        }
        return t;
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        return s1.empty();  // 直接判断s1即可
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

- 每次操作完，值一直是存放在 s1 里
- 栈的声明位置：放在类的全局里，才能被其他函数访问
  - 放在初始化函数 MyQueue () 里是否可以用 this 调用到？
  - ❌不行，this 指的是整个大类，之后学习类的时候注意
- 【进阶】你能否实现每个操作均摊时间复杂度为 O (1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O (n) ，即使其中一个操作可能花费较长时间。
  - 关键在于：pop 把元素从 s1 倒腾到 s2 的时候，不倒腾回来了
  - 这样 s2 的顺序就是队列出队的顺序
  - 每次 pop 只有 s2 为空时，才把 s1 的元素倒腾过来，否则直接 pop s2 即可
  - 参考用栈实现队列 - 官方解答- 方法二

LC-225：用队列实现栈#

思路
- 其实只需要一个队列
  - 转移元素时，放队尾即可
    - ①可以在 push 的时候调整顺序
    - ②也可以在 pop 的时候操作
  - 通过 queue.size () 控制转移的边界
代码

class MyStack {
public:
    queue<int> que;
    /** Initialize your data structure here. */
    MyStack() {
    }
    
    /** Push element x onto stack. */
    void push(int x) {
        que.push(x);
        // 将前面的所有元素依次放到后面
        for (int i = 1; i < que.size(); i++) {
            que.push(que.front());
            que.pop();
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int t = que.front();
        que.pop();
        return t;
    }
    
    /** Get the top element. */
    int top() {
        return que.front();
    }
    
    /** Returns whether the stack is empty. */
    bool empty() {
        return que.empty();
    }
};
/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

Bo2SS

5 STL“容器”的使用与练习

课程内容#

队列与栈#

queue#

stack#

本质#

向量与优先队列#

vector#

priority_queue#

本质#

字符串 string#

键值对 map#

集合 set#

对 pair#

代码演示#

queue#

stack#

vector#

priority_queue#

map#

练习题#

HZOJ-383：周末舞会#

HZOJ-378：字符串括号匹配 2#

HZOJ-376：机器翻译#

HZOJ-379：仓库日志#

HZOJ-382：报数#

HZOJ-384：敲七#

HZOJ-385：海港#

HZOJ-569：溶液模拟器#

LC-232：用栈实现队列#

LC-225：用队列实现栈#

附加知识点#

思考点#

Tips#

课程速记#