STL 算法

STL标准库（一）：序列式容器

Avatar photo By froyoisle

STL 简介

STL 标准模板库从广义上讲分为 算法（Algorithm）、容器（Container）及 迭代器（Iterator）3 类。

容器（Container）

容器是用来管理某一类对象的集合。

C++ 提供了各种不同类型的容器，如 vector、stack、queue、list、set、map 等。

迭代器（Iterator）

迭代器（Iterator）用来访问和检查 STL 容器中元素的对象，它的行为模式和指针类似，可以看作是一个数据指针。除此之外还封装了一些有效性检查，并提供了统一的访问格式。

迭代器主要支持两个运算符：

  1. 自增 (++) ：移动迭代器；
  2. 解引用（单目 * 运算符）：获取或修改迭代器指向的元素；

常用容器

向量 vector

vector 译为向量，更通俗易懂的说法是“变长数组”，它是 C++ 标准库中的一个动态数组容器，可以在运行时根据需要动态改变容器长度，自动管理内存大小。

定义

#include <vector> // 使用 vector 导入该头文件
#include <iostream>
using namespace std; // 在标准命名空间下

int main(){
        vector<int> v; // 定义一个存放 int 型数组的变长数组 v
        int x, n;
        cin >> n;
        for(int i = 1; i <= n; i++){
                cin >> x;
                v.push_back(x); // 在 v 后面添加元素 x
        }
        // 迭代器不支持 it < v.end() 的写法，结束条件用 it != v.end()
        for(vector<int>::iterator it = v.begin(); it != v.end(); it++) // 使用迭代器遍历
                cout << *it << " "; // *it 表示取 it 指向的元素值
        cout << "\n";
        for(int i = 0; i < n; i++) // 使用数组下标遍历
                cout << v[i] << " "; // v[i] 等价于 (v.begin()+i)        cout << "\n";
*        /* C++11 后引入了 auto 遍历
        for(auto i: v) // auto: 自动遍历获取容器 v 中的元素 i
                cout << i << " ";
        cout << "\n";
        for(int i: v) // 指定元素类型为 int 遍历 v 中的元素 i
                cout << i << " ";
        cout << "\n";
        */
        return 0;
}

常用操作

  1. push_back()：插入元素

v.push_back(x); // 在 v 后面添加元素 x

  1. pop_back()：删除尾元素

v.pop_back(); // 删除 v 的尾元素

  1. size()：获取长度
        for(int i = 0; i < v.size(); i++) // size(): 获取 v 的元素个数
                cout << v[i] << " ";
  1. insert(it，ｘ)：在迭代器 it 处插入元素 x
        v.insert(v.begin() + 2, 66); // 将 66 插入 v[2] 的位置
        for(int i = 0; i < v.size(); i++) // size(): 获取 v 的元素个数
                cout << v[i] << " "; // 容器元素变成: 8 3 66 4 6
  1. erase()：删除元素
    1. erase(it)：删除迭代器 it 处的单个元素
    v.erase(v.begin() + 2); // 将 v[2] 的元素删除
        for(int i = 0; i < v.size(); i++) // size(): 获取 v 的元素个数
                cout << v[i] << " "; // 容器元素变成: 8 3 4 6
  1. erase(start, end)：删除 [start, end) 区间中所有元素
        v.erase(v.begin() + 1, v.begin() + 3); // 将 v[1] ~ v[2] 的元素删除
        for(int i = 0; i < v.size(); i++)
                cout << v[i] << " "; // 容器元素变成: 8 6
  1. clear()：清空容器
        v.clear(); // 清空 v 中所有元素
        cout << "size: " << v.size() << "\n"; // 输出 0

字符串 string

C++ 在 STL 中引入的 string 类型对字符串常用的功能进行了封装，使得字符串的操作更方便。使用 string 需要加入头文件 <string>。

定义

#include <string>
#include <iostream>
using namespace std;

int main(){
        string a, b;
        cin >> a >> b;
        a += b; // += 会将 b 拼在 a 的后面
        cout << a << "\n";
        for(int i = 0; i < a.size(); i++) // 遍历字符串                cout << a[i];
        cout << "\n";
        for(string::iterator it = a.begin(); it != a.end(); it++) // 使用迭代器遍历 a
                cout << *it;        cout << "\n";
        return 0;
}

常用操作

  1. += 拼接
        a += b; // += 会将 b 拼在 a 的后面
  1. ==、>=、<=、>、<：比较字符串字典序大小
        string x = "ab", y = "abc";
        cout << (x < y) << "\n";  // 1
        cout << (x > y) << "\n";  // 0
        cout << (x == y) << "\n";  // 0
  1. length()/size()：获取长度/大小（元素个数）
  for(int i = 0; i < a.size(); i++) // 遍历字符串                cout << a[i];

4. c_str()：将string类型字符串转为 C 中的字符数组表示，可以使用 %s 输出

        pritnf("%s", a); // 错误写法：string 类型字符串只能 cin、cout        
        printf("%s\n", a.c_str()); // 正确写法：把 a 转成字符数组可以用 %s 输出

5. a.insert(p, b)：在 a[p] 处插入字符串 b

        string x = "ab", y = "abc";
        y.insert(2, x); // y[2] 出插入字符串 x
        cout << "y: " << y << "\n"; // y: ababc

6. erase()：删除元素

  1. erase(it)：删除迭代器 it 处的单个元素
  2. erase(start, end)：删除 [start, end) 区间中所有元素
  3. s.erase(p, len)：删除 s[p] 开始的 len 个元素
        string z = "marco polo";
        z.erase(z.begin() + 5); // "marcopolo"
        cout << z << "\n";
        z.erase(z.begin() + 5, z.end()); // "marco"
        cout << z << "\n";
        z.erase(3, 2); // "mar"
        cout << z << "\n";

7. clear()：清空字符串

        z.clear();
        cout << "size of z: " << z.size() << "\n"; // size of z: 0

8. s.substr(p, len)：获取从 s[p] 开始长度为 len 的子串

        string z = "marco polo";
        cout << z.substr(6, 4) << "\n"; // "polo"
        cout << z.substr(0, 5) << "\n"; // "marco"

9. find()：查找子串，查找成功返回子串第一次出现的位置，失败返回 string::npos。

  1. x.find(y)：在 x 中查找子串 y
string z = "marco polo";
cout << z.find("o") << "\n"; // 返回子串 "o" 第一次出现的位置
cout << (z.find("k") == string::npos ? 1 : 0) << "\n"; // 查找子串 "k" 失败，返回 string::npos

2. x.find(y, p)：在 x 中从位置 p 处的 x[p]开始匹配

 cout << z.find("o", 5) << "\n"; // 返回 7

10. replace(): 替换

  1. s.replace(p, len, s1)：把 s 从 s[p] 开始长度为 len 的子串替换为 s1
  2. s.replace(it1, it2, s1)：把 s 迭代器 [it1, it2) 范围内的子串替换为 s1
        string z = "marco polo";
        z.replace(3, 2, "coco"); // 把 z[3] ~ z[4]替换成 coco
        cout << z << "\n"; // marcoco polo
        z.replace(z.begin(), z.begin() + 7, "marco");
        cout << z << "\n"; // marco polo

双端队列 deque

deque 在头文件 <deque> 中声明，它是一种双向开口的连续线性空间，可以高效地在头、尾两端插入和删除元素。它的操作时间复杂度为 O(1)，考虑容器元素的内存分配策略和操作性能时，deque 比 vector 有优势（vector 头部操作效率极低）。

定义及常见操作示例

#include <deque>
#include <iostream>
using namespace std;

int main(){
        deque<int> dq;
        dq.push_back(3); // 尾部插入 3，序列 3        dq.push_back(5); // 尾部插入 5，序列 3 5
        dq.push_front(8); // 头部插入 8，序列 8 3 5
        cout << dq.front() << "\n"; // front() 取首元素
        cout << dq.back() << "\n"; // back() 取尾元素
        dq.pop_back(); // 删除尾元素，序列 8 3
        dq.pop_front(); // 删除首元素，序列 3
        for(int i = 0; i < dq.size(); i++)
                cout << dq[i] << " ";
        return 0;
}

双向链表 list

list 双向链表容器在头文件 <list> 中声明，它对任一位置元素的查找、插入及删除都具有高效的常数阶算法时间复杂度。它的结构示意如图所示。

定义及常见操作示例

#include <list>
#include <iostream>
using namespace std;

int main(){
        list<int> l;
        l.push_back(5); // 5
        l.push_back(4); // 5 4
        l.push_front(8); // 8 5 4
        l.push_front(3); // 3 8 5 4
        cout << l.front() << "\n"; // 3
        cout << l.back() << "\n"; // 4
        l.push_front(5); // 5 3 8 5 4
        l.sort(); //  升序排序：3 4 5 5 8
        l.unique(); // 去重：3 4 5 8
        for(list<int>::iterator it = l.begin(); it != l.end(); it++)
                cout << *it << " "; // 遍历输出：3 4 5 8
        return 0;
}

栈 stack

C++语言 STL 的stack堆栈容器不设最大容量，提供入栈、出栈、栈顶元素访问及判断是否为空的基本操作，其在头文件<stack>中定义，对于栈中元素的访问只能通过 top() 访问栈顶元素。

定义及常见操作示例

#include <stack>
#include <iostream>
using namespace std;
int main(){
        stack<int> s;
        int n, x;
        cin >> n;
        for(int i = 1; i <= n; i++){
                cin >> x;
                s.push(x); // push(): 入栈操作
        }
        if(!s.empty()) // 栈非空
                s.pop(); // 弹出栈顶元素
        cout << s.size() << "\n"; // size(): 获取元素个数
        cout << s.top() << "\n"; // top(): 获取栈顶元素值
        return 0;
}

队列 queue

queue队列容器是一个线性存储表，在头文件<queue>中声明。与后进先出的堆栈不同，元素数据的插入在表的一端进行，元素数据的删除在表的另一端进行，从而构成了一个“先进先出”（First In First Out） 表。插入一端称为队尾，删除一端称为队首。对于队列中元素的访问可以通过 front() 访问队首元素或 back() 访问队尾元素。

定义及常见操作示例

#include <queue>
#include <iostream>
using namespace std;

int main(){
        queue<char> q;
        char c;
        int n;
        cin >> n;
        for(int i = 1; i <= n; i++){
                cin >> c;
                q.push(c); // push(x): x 入队(队尾)
        }
        cout << "队首是: " << q.front() << "\n"; // front(): 取队首元素
        cout << "队尾是: " << q.back() << "\n"; // back(): 取队尾元素
        if(!q.empty()) // empty(): 判断队列是否为空
                q.pop(); // 队首元素出队
        cout << q.size() << "\n"; // size(): 队列长度
        return 0;
}

经典例题

寄包柜

思路

本题数据规模如果用普通数组需要开 10^5 * 10 ^5 的 int 数组（约 40 G），内存会炸，可以使用二维动态数组解决这个问题。需要注意的是，若定义时未指定数组大小，初始容器是个容量为 0 的空容器，因此定义时可以先初始化一维长度 (n + 1), 当需要在 v[i][j] 存入 物品 k 时，需要判断 v[i].size() 够不够取到下标 j，不够需要调用 resize() 重分配容器空间大小。

v.resize(n, m): 重新调整数组大小为 n，若 n 比原来小，则删除多余信息，否则，则将数组容量增加到 n，且新增部分都初始化为 m（m 可省略）。

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, q;
    scanf("%d %d", &n, &q);
    vector< vector<int> > v(n + 1); // 定义二维 int 型 vector
    int op, i, j , k;
    while(q--){
        scanf("%d %d %d", &op, &i, &j);
        if(op == 1){
            scanf("%d", &k);
            if(v[i].size() < j + 1){
                v[i].resize(j + 1); // 第 i 个柜子不够大，重新分配容量
            }
            v[i][j] = k;
        }
        else{
            printf("%d\n", v[i][j]);
        }
    }
    return 0;
}

Phone List

思路

将输入的字符串由小到大排列，然后到下一个字符串中查找上一个字符串，如果下一个字符串的最前面的子串是上一个字符串，就终止。注意本题的输出，找到有前缀，输出“NO”，否则，输出“YES”。

代码

#include <bits/stdc++.h>
using namespace std;

vector<string> v;
int main(){
    int t, n;
    scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        v.clear(); // 清空容器
        bool f = 0; // 初始化查找标记为 0
        char x[15] = "";
        while(n--){
            scanf("%s", x);
            v.push_back(string(x)); // x 放入容器 v
        }
        sort(v.begin(), v.end()); // 对容器排序
        for(int i = 0; i < v.size() - 1; i++){ // 遍历所有前串
            if(v[i+1].find(v[i]) == 0){ // 判断前串是否是后串前缀
                f = 1;
                break;
            }
        }
        printf("%s\n", f ? "NO" : "YES");
    }
    return 0;
}

表达式括号匹配

思路

用一个栈存储读入的左括号，每读入一个右括号（不存），就出栈一个左括号（出栈操作前必须先判断栈非空！）。最后读入完成后，检查栈是否已空，若左右括号是完全匹配的，栈最后应该全空了。否则表示还有多出的左括号，也是不匹配的。

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    stack<char> s;
    char x;
    while(cin >> x && x != '@'){
        if(x == '(')
            s.push(x);
        if(x == ')'){
            if(!s.empty()){ // 栈非空
                s.pop(); // 出栈一个右括号
            }
            else{ // 栈空读入到 ) 非法
                cout << "NO";
                return 0;
            }
        }    }
    if(s.empty()) cout << "YES";
    else  cout << "NO";
    return 0;
}

平衡的括号

思路

注意输入字符串可能会有空格。

代码

#include <bits/stdc++.h>
using namespace std;


bool jg(string a){
        stack<char> s; // 重新初始化 s
        for(int i = 0; i < a.size(); i++){
                if(a[i] == ' ') continue;
                if(a[i] == '(' || a[i] == '[')
                        s.push(a[i]);
                else{ // ) 和 ] 的情况
                        if(s.empty()) return 0;
                        if(a[i] == ')' && s.top() == '(' || a[i] == ']' && s.top() == '['){
                                s.pop();
                        }
                        else return 0;
                }        }
        if(s.empty()) return 1;
        else return 0;
}
int main(){
    int n;
    cin >> n;
    getchar(); // 跳过空格
    string a;
    while(n--){
            getline(cin, a); // 字符串中可能有空格                
            cout << (jg(a) ? "Yes" : "No") << "\n";
    }
    return 0;
}

[NOIP2013 普及组] 表达式求值

思路

用一个栈存储所有需要相加的结果，过程中就要及时进行 % 操作。

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    stack<int> s;
    int x;
    char op;
    cin >> x;
    s.push(x); // 第一个数入栈
    while(cin >> op >> x){ // 读入下一个数和操作符
        if(op == '*'){
            x *= s.top(); // 取栈顶相乘
            s.pop(); // 弹出栈顶值
            x %= 10000; // 保留 4 位数
            s.push(x); // 压入新乘积
        }
        else{ // 把要加的数依次压入栈中
            s.push(x); // 压入 x
        }
    }
    int ans = 0;
    while(!s.empty()){ // 遍历栈求元素和
        ans = (ans + s.top()) % 10000;
        s.pop(); // 弹出栈顶
    }
    cout << ans;
    return 0;
}

约瑟夫问题

思路

首先让 n 个人依次入队。然后遍历队列，只要队列还非空，就取出前 (m-1) 个人循环接到队尾，并在第 m 个人的时候让第 m 个人出队（先取队首输出再出队）。直到队列已空，人都出完，程序结束。

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    queue<int> q;
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        q.push(i);
    while(!q.empty()){
        for(int j = 1; j <= m - 1; j++){ // 前 m-1 个人依次取出放队尾
            q.push(q.front());  // 取队首元素放队尾            q.pop(); // 弹出队首
        }
        cout << q.front() << " "; // 第 m 个人输出
        q.pop(); // 第 m 个人出队
    }
    return 0;
}

小熊的果篮

思路

模拟双向链表记录每个水果左右两边的水果地址，对于“每块水果（连续相同的）”，再用一个 vector 动态记录块首地址，每轮遍历 vector 中的块首地址输出并在对应链表中删除输出了的元素。

删除元素后，还要考虑新的块首地址的变化，若删除元素后面的元素和前面的一样，则前面这个元素地址就是新的块首地址，每轮边删除边更新维护一个新块首的 vector，再在一轮遍历结束后用新块首的 vector 替代原有的，直到块首地址容器为空，表示已无元素未输出。

注意要将表首元素前和尾元素后都标记为不会出现的特殊值，便于边界的统一处理。

代码

#include <bits/stdc++.h>
#define maxn 200005
using namespace std;

int n, a[maxn], r[maxn], l[maxn];
vector<int> v; // 存每块水果的开头
int main() {
    scanf("%d", &n);
    a[0] = -1; // 首位前标记为特殊值便于记录连续水果块
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        r[i] = i + 1, l[i] = i - 1;
        if(a[i] != a[i - 1]){ // 和前面不一样 -> 是个新块
            v.push_back(i); // i 是新块开头的地址（下标）
        }
    }
    a[n + 1] = -1;  // 末位后标记为特殊值便于记录连续水果块
    while(v.size()){ // 还有块
        vector<int> t; // 存更新后的块首地址
        for(int i = 0; i < v.size(); i++){
            printf("%d ", v[i]); // 取出第 i 个
            r[l[v[i]]] = r[v[i]],  l[r[v[i]]] = l[v[i]]; // l[v[i]] v[i] r[v[i]]  删除中间的 v[i]
            if(a[r[v[i]]] == a[v[i]] && a[l[v[i]]] != a[v[i]]){ // y x(删掉的 a[i]) x(a[r[i]]) x
                t.push_back(r[v[i]]); // r[v[i]] 是新块起点
            }
        }
        printf("\n");
        v = t;
    }
    return 0;
}

拓展学习资料

  1. OI Wiki – C++ 标准库
  2. 晴问算法-第 6 章 C++标准模板库（STL）介绍
Avatar photo

By froyoisle

Related Post

并查集 算法

并查集

Avatar photofroyoisle
STL 算法

STL标准库（三）：算法篇

Avatar photofroyoisle
STL 算法

STL标准库（二）：关联式容器

Avatar photofroyoisle

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

You Missed

心理 生活 读书

《隐藏的自我》读书笔记

并查集 算法

并查集

NOIP/CSP 普及组 复赛 真题

2002-NOIP-普及组：复赛真题及解析

反思 生活 读书

《幸福超越完美》读书笔记