【知识点】深入浅出STL标准模板库

stl · 浏览次数 : 0

小编点评

**集合操作算法** * **set_union** 函数用于将两个集合合并并存储在容器的末尾。 * **set_intersection** 函数用于计算两个集合的交集并存储在容器中。 **反转算法** * **reverse** 函数用于反转一个容器的顺序。 **去重算法** * **unique** 函数用于移除容器中相邻的重复元素并返回一个指针，指向重复元素的所在区间的末尾。 * **erase** 函数用于删除容器中指定区间的元素。 **查找算法** * **lower_bound** 和 **upper_bound** 函数用于在有序范围内查找元素。

正文

前几天谈论了许多关于数论和数据结构的东西，这些内容可能对初学者而言比较晦涩难懂（毕竟是属于初高等算法/数据结构的范畴了）。今天打算来讲一些简单的内容 - STL 标准模板库。

STL 标准模板库

C++ 标准模板库 (Standard Template Library, STL)，是 C++ 语言非常重要的一个构成部分。它提供了一组通用的类和函数，用于实现一些数据结构和算法。STL 主要包含以下五个部分：

  1. 容器 (Containers)：STL 提供了不同的容器来供开发者根据所需要维护数据来选择存储。
  2. 算法 (Algorithms)：STL 提供了许多通用算法，用于排序、搜索、复制、修改等操作。
  3. 迭代器 (Iterators)：STL 迭代器的作用是遍历容器元素的对象。
  4. 函数对象 (Function Objects)：这是一种行为类似于函数的对象（由于不太常见，因此本篇文章将不会详细讲解 STL 中的函数对象）。
  5. 适配器 (Adapters)：STL 的适配器用于修改容器、迭代器或函数对象的接口。为方便起见，容器适配器将会与容器部分一同讲解。

综上所述，本文将会主要围绕 容器、算法和迭代器这三者来展开叙述。本文只会阐述一些相对常见的模板/方法，部分生僻的内容还请各位自行上网搜索。

容器 Containers

STL 容器还可以被细分成三个类别，分别是 序列式容器 (Sequence Containers)、关联式容器 (Associative Containers) 和 无序关联式容器 (Unordered Associative Containers)。

序列式容器 (Sequence Containers) 与常见容器适配器。

  1. vector 向量容器：向量容器可以被理解为我们常说的动态数组。与普通数组不同的是，动态数组的大小可以在运行过程中更改，并且用户可以任意地在此数组的末尾添加数据。它的优点是支持快速随机访问和在末尾插入删除元素。向量容器的基本使用方法如下：
#include <iostream>
#include <vector>  // 引入头文件
using namespace std;

int main(){
    // 创建一个整数类型，名为 vec 的向量容器，初始存放了数字1-5。
    vector<int> vec = {1, 2, 3, 4, 5};
    
    vec.push_back(6);  // 向容器末尾添加一个元素6。
    vec.size();  // 获取容器的大小，即容器内元素的个数。
    vec.resize(10);  // 动态更改容器的大小，将容器的大小设置为10。

    // 通过 for 循环对容器进行遍历：
    for (int i=0; i<vec.size(); i++){}
    for (int i : vec) {}
    return 0;
}
  1. queue 队列容器适配器：队列是一种基本的数据结构，其讲究 先进先出 (FIFO)，即最先添加进适配器的元素会被第一个弹出，以此类推。在队列中，所有元素都会从队尾入队，并从对首出队。队列适配器的优点是支持随机访问队首和队尾元素。队列容器严格意义上并非序列式容器，而是一种容器适配器。队列容器适配器的基本使用方法如下：
#include <iostream>
#include <queue>  // 引入头文件
using namespace std;

int main(){
    // 创建一个存放整数类型，名为 que 的队列容器适配器，一开始默认为空。
    queue<int> que;

    que.push(10);  // 向队尾添加一个新元素。
    que.front();  // 获取队首元素，此时队首元素为数字10。
    que.pop();  // 将队首元素出队，此时的队列容器为空。
    que.size();  // 获取队列的长度，即对内元素的个数。
    que.empty();  // 判断队列是否为空，为空返回真，否则返回假。

    // 队列元素不支持直接遍历，只能从头一个一个弹出。
    // 在弹出元素时需要保证队内不为空。
    while (!que.empty()){
        int t = que.front();
        que.pop();
        cout << t << endl;
    }
    return 0;
}
  1. stack 栈容器适配器：栈也是一种基本的数据结构，栈实现的是 后进先出 (LIFO)，即最后添加进该适配器的元素会最先弹出。在栈中，所有元素都会从栈顶入栈，并从栈顶出栈。栈容器严格意义上并非序列式容器，而是一种容器适配器。栈容器适配器的基本使用方法如下：
#include <iostream>
#include <stack>  // 引入头文件
using namespace std;

int main(){
    // 创建一个存放整数类型，名为 s 的栈容器适配器，一开始默认为空。
    stack<int> s;

    s.push(10);  // 将元素压入栈顶。
    s.top();  // 获取栈顶元素，此时的栈顶元素为数字10。
    s.pop();  // 将栈顶元素出栈，此时栈内没有元素。
    s.size();  // 获取栈内元素的个数。
    s.empty();  // 判断栈是否为空，为空返回真，否则返回假。

    // 与队列相同，栈内元素不支持直接遍历，只能从栈顶一个一个弹出。
    // 在弹出元素时需要保证栈内不为空。
    while (!s.empty()){
        int t = s.top();
        s.pop();
        cout << t << endl;
    }
    return 0;
}
  1. deque 双端队列容器：与队列类似，双端对类容器支持快速随机访问和在两端插入删除。上面提及到的 queue 容器适配器就是基于双端队列所实现的。双端队列容器的基本使用方法如下：
#include <iostream>
#include <deque>

int main() {
    // 创建一个整数类型，名为 deq 的双端队列容器，初始存放了数字1-5。
    deque<int> deq = {1, 2, 3, 4, 5};

    deq.push_front(0);  // 在前端添加元素。
    deq.push_back(6);  // 在末尾添加元素。

    // 通过 for 循环对容器进行遍历：
    for (int i : deq) cout << i << endl;
    return 0;
}
  1. list 双向链表容器：链表数据结构支持快速插入删除操作，但是通过索引访问元素会比较慢。双向链表的语法与双端队列相似。在一般算法实现上，双向链表的应用并不算广泛，因此不过多阐述。双向链表的基本使用方法如下：
#include <iostream>
#include <list>  // 引入头文件

int main() {
    // 创建一个整数类型，名为 lst 的双向队列容器，初始存放了数字1-5。
    list<int> lst = {1, 2, 3, 4, 5};

    lst.push_front(0);  // 在前端添加元素。
    lst.push_back(6);  // 在末尾添加元素。

    // 通过 for 循环对容器进行遍历：
    for (int i : lst) cout << i << endl;
    return 0;
}

关联式容器 (Associative Containers)

  1. set 集合容器：集合容器的定义与数学中的集合完全相同。集合中相同的元素只会被存入一次。集合可以进行高效的查找操作。集合容器的基本使用方法如下：
#include <iostream>
#include <set>  // 引入头文件

int main() {
    // 创建一个整数类型，名为 s 的集合容器，初始存放了许多数字。
    set<int> s = {3, 1, 4, 1, 5, 9};
    
    s.insert(2);  // 向集合内插入元素2。
    s.erase(2);  // 向集合中移除元素2。

    s.count(2);  // 检查元素是否存在于集合，如果返回真即存在，否则即不存在。
    s.size();  // 获取集合内元素的个数。
    s.clear();  // 清空集合。

    // 通过 for 循环对容器进行遍历：
    // 由于集合自带“去重”功能，最输出的结果为：1 3 4 5 9。
    for (auto i : s) cout << i << " ";
    return 0;
}
  1. map 映射容器：除了集合容器之外，该容器也经常在算法中被应用。映射容器用于存储键值对。其中键在该容器中是唯一，同时它还支持高效的查找操作（对于某些数据如果懒得离散化一定要试一下这个容器，我觉得真的很好用）。以下是映射容器的基本用法：
#include <iostream>
#include <map>  // 引入头文件

int main() {
    // 创建一个键为整数类型、值为字符串类型，名为 m 的映射容器。
    map<int, string> m;
    m[1] = "Macw07";  // 插入键值对。

    s.count(2);  // 检查元素是否存在于集合，如果返回真即存在，否则即不存在。
    s.size();  // 获取集合内元素的个数。
    return 0;
}

无序关联式容器 (Unordered Associative Containers)

一般情况下，所有的关联式容器默认都会按照存放数组（值/键）从小到大进行排序。但如果将这些关联式容器变成无序关联式容器，那么 STL 内部就不会默认对其进行排序。一般情况下，如果没有特殊需求推荐使用无序关联式容器，因为它们的运行效率通常都比有序的关联式容器要高很多。

以下是常见的无序关联式容器和有序关联式容器的声明代码：

map 与 unordered_map：

#include <map>  // 有序的。
#include <unordered_map>  // 无序的。

map<int, int> mp1;  // 有序映射表的声明。
unordered_map<int, int> mp2;  // 无序映射表的声明。

set 与 unordered_set ：

#include <set>  // 有序的。
#include <unordered_set>  // 无序的。

set<int> mp1;  // 有序集合的声明。
unordered_set<int> mp2;  // 无序集合的声明。

算法 Algorithms

终于讲完了容器部分，接下来来到了算法的部分。C++ 的 STL 供了许多算法，用于对容器中的元素进行操作。这些算法主要包括：排序、搜索、修改、集合操作、数值操作等。STL 的算法通常以函数模板的形式实现，可以与任意容器类型配合使用。

以下所有有关区间的内容均默认为 闭区间操作。

  1. 排序算法 sort 与 stable_sort。两种算法的目的都是对一个容器/数组进行排序。两个算法均传入三个参数，分别是排序区间的头尾地址和排序方式。其中排序方式不强制传参，对于整形类型的容器而言，默认按照从小到大的顺序进行排序。两种算法的作用基本相同，但 stable_sort 保证了排序的稳定性，普通的 sort 无法保证排序的稳定性。基本使用代码如下：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> vec = {5, 3, 8, 6, 2};
    int arr[] = {5, 4, 3, 2, 1};
    // 前两个参数传入的是地址。
    // xxx.begin()/ end() 表示获取某容器的首地址或尾地址。
    sort(vec.begin(), vec.end());  // 对动态数组进行排序。
    sort(arr, arr+5);  // 对数组进行排序。

    // 输出排序后的动态数组。
    for (int i : vec) cout << n << " ";
    return 0;
}

如果想要使用自定义排序，那么可以仿照以下方法来写：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 创建一个自定义比较函数。
// 传入两个参数（类型与所需要排序的容器类型一致）。
// 说直白点，想要哪个前一个参数考前就返回真，否则返回假。
bool cmp(int a, int b){
    return a > b;  // 按照从大到小的顺序排。
    // return a < b;  // 按照从小到大的顺序排。
}

int main() {
    vector<int> vec = {5, 3, 8, 6, 2};

    sort(vec.begin(), vec.end(), cmp);  // 对动态数组按照cmp规则进行排序。

    // 输出排序后的动态数组。
    for (int i : vec) cout << n << " ";
    return 0;
}
  1. 搜索算法 find：该算法帮助我们在指定范围内查找等于指定值的第一个元素。该算法也传入三个参数，也分别是查找区间的左地址和右地址，以及需要查找的对象。该算法的返回值也是一个地址。具体的使用方法如下：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> vec = {5, 3, 8, 6, 2};
    // 如需要获取所查找对象的索引，因在最后减去首地址。
    auto index = std::find(vec.begin(), vec.end(), 8) - vec.begin();
    return 0;
}
  1. 集合操作算法 set_union 和 set_intersection：之前已经提到了集合的容器，这两个算法均应用在集合容器（当然其他容器也可以）当中。其中 set_union 算法会将两个集合合并。set_intersection 算法可以求出两个集合的交集。这两个算法均传入五个参数，分别是第一个集合的左右地址、第二个集合的左右地址和存放最终计算结果的容器。两个函数的使用方法如下：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> vec1 = {1, 2, 3};
    vector<int> vec2 = {3, 4, 5};
    vector<int> unionVec, intersectionVec;

    // 计算 vec1 和 vec2 的并集，并将结果存储到 unionVec 数组中。    
    set_union(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), back_inserter(unionVec));

   // 计算 vec1 和 vec2 的交集，并将结果存储到 intersectionVec 数组中。    
    set_union(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), back_inserter(intersectionVec));
    return 0;
}
  1. 反转算法 reverse：反转一个容器（数组/字符串也可以）指定范围内的元素顺序。该算法传入两个参数，分别表示区间的左右地址。该算法具体的使用方法如下：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> vec = {1, 2, 3, 4, 5};
    // 反转整一个 vec 数组
    reverse(vec.begin(), vec.end());  // 此时 vec = {5, 4, 3, 2, 1}

    string str = "Macw07";
    reverse(str.begin(), str.end());  // 此时 str = "70wcaM"。
    return 0;
}
  1. 去重算法 unique 和 erase：unique 算法用于移除指定范围内相邻的重复元素（需要先排序）。该算法只能在保证容器内有序地情况下使用，否则算法将无法返回正确的结果。该算法的会将重复的元素存放到区间的末尾，并返回一个指针，表示从该指针开始到区间结束是重复元素所在的区间。而 erase 的用处是删除容器指定区间内的所有元素。相同地，两个算法都需传入两个参数，分别表示区间的左右地址。该算法具体的使用方法如下：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> vec = {1, 2, 2, 3, 4, 4, 5};

    // 去重。
    auto last = unique(vec.begin(), vec.end());
    // 删除重复元素。
    vec.erase(last, vec.end());
    return 0;
}
  1. 查找算法 lower_bound 和 upper_bound：lower_bound 和 upper_bound 是两种常用的搜索算法，主要用于有序范围内查找元素。它们分别返回 第一个不小于（大于或等于）指定值 和 第一个大于指定值的位置 。请注意，这两个算法需要在给定区间内的元素从小到大升序的情况下使用，否则将会返回错误的结果。这两个算法的底层原理是通过二分查找来实现的。假设存在一个数列 \([1, 2, 3, 5, 6, 6, 7]\)，那么这个数列对 \(4\) 求 \(lower\_bound\) 就是 \(3\)（索引），而这个数列对 \(6\) 求 \(upper\_bound\) 就是 \(6\)（索引）两个算法的代码示例如下：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> vec = {1, 2, 3, 4, 5, 6};

    // ---------- lower_bound 算法 ----------
    auto it1 = lower_bound(vec.begin(), vec.end(), 4);
    // 如果要获取索引，那么再减去首地址即可。
    int index1 =  lower_bound(vec.begin(), vec.end(), 4) - vec.begin();

    if (it1 != vec.end()) 
        cout << "Lower bound of 4 is: " << *it1 << endl;
    else 
        cout << "4 is not in the vector" << endl;


    // ---------- upper_bound 算法 ----------
    auto it2 = upper_bound(vec.begin(), vec.end(), 4);
    // 如果要获取索引，那么再减去首地址即可。
    int index2 =  upper_bound(vec.begin(), vec.end(), 4) - vec.begin();

    if (it2 != vec.end()) 
        cout << "Upper bound of 4 is: " << *it2 << endl;
    else 
        cout << "All elements are <= 4" << endl;

    return 0;
}

迭代器 Iterators

接下来来到了迭代器部分，迭代器是一种用于遍历容器元素的抽象概念。它提供了一种统一的访问容器内元素的方式，使得算法可以独立于容器类型工作，增强了代码的通用性和可重用性。

迭代器的基本概念

迭代器 是一种指针-like 对象（表示与指针类似），它允许你遍历容器中的元素。你可以使用迭代器访问容器的每个元素，而不需要了解容器的内部实现细节。

迭代器范围 由两个迭代器表示，通常是一个指向范围起始位置的迭代器和一个指向范围末尾位置的迭代器。这两个迭代器标识了一个半开区间，即左闭右开。

虽然迭代器与指针近乎相同，但也有细微的差别（在本文前问中，由于未详细讲解迭代器，因此将迭代器和指针统称为指针）。以下是迭代器的常见方法：

  1. .begin()：获取指向容器的第一个元素的迭代器。
  2. .end()：获取指向容器的最后一个元素的下一个位置的迭代器。
  3. 迭代器++：将迭代器指向容器的下一个位置。
  4. *迭代器：获取迭代器指向的元素（类似于通过地址取值）。

一般情况下，我们通过使用 auto 类型来实现迭代器（因为这个类型比较方面，可以在任何时候用）。auto 类型是 C++11 引入的一个关键字，用于在编译时自动推断变量的类型。使用 auto 关键字声明的变量会根据其初始化表达式的类型自动推导出变量的类型。这样做可以简化代码、提高可读性，并且使代码更具灵活性

通过使用 auto 类型来对 STL 容器进行遍历操作：

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

int main() {
    vector<int> vec = {1, 2, 3, 4, 5};

    // 使用迭代器遍历容器并输出元素。
    for (auto it = vec.begin(); it != vec.end(); it++) 
        cout << *it << " ";
    return 0;
}

小结

至此，对于 STL 的基本讲解就到此为止了。STL 标准模板库 本身是非常庞大的，因此本文并不涵盖所有的知识点。与此同时，我希望各位在使用不同的算法/容器的时候自行搜索有关该模板的时间复杂度，以更好的在做题过程中预估算法的整体耗时。

本文后续可能会持续更新。

stl

与【知识点】深入浅出STL标准模板库相似的内容：

【知识点】深入浅出STL标准模板库

本文全面介绍了C++标准模板库（STL）的基础知识，涵盖了容器、算法和迭代器的概念及其常见应用，旨在帮助读者掌握STL的基本用法和重要概念。

stl
0
WPF复习知识点记录

# WPF复习知识点记录 由于近几年主要在做Web项目，客户端的项目主要是以维护为主，感觉对于基础知识的掌握没有那么牢靠，趁着这个周末重新复习下WPF的相关知识。 文章内容主要来自大佬刘铁锰老师的经典著作《深入浅出WPF》。 因为是复习，所以知识内容不会一一记录，如有需要了解更多可以看书中内容。 *

wpf 复习 知识点 记录
204
Python 爬虫实战：驾驭数据洪流，揭秘网页深处

**爬虫，这个经常被人提到的词，是对数据收集过程的一种形象化描述。特别是在Python语言中，由于其丰富的库资源和良好的易用性，使得其成为编写爬虫的绝佳选择。本文将从基础知识开始，深入浅出地讲解Python爬虫的相关知识，并分享一些独特的用法和实用技巧。本文将以实际的网站为例，深入阐述各个处理部分，

python 爬虫 实战 驾驭
446
yolov1-yolov5 网络结构&正负样本筛选&损失计算

学习yolo系列，最重要的，最核心的就是网络模型、正负样本匹配、损失函数等三个方面。本篇汇总了yolov1-yolov5等5个版本的相关知识点，主要看点是在yolo框架搭建。初学者可以通过相关篇章搭建自己的知识点框架，然后再深入各个知识点，就像攻克一个又一个山头。当大部分的知识点都了然于胸，yolo...

yolov1 yolov5
0
糟了糟了，总部被SD画完都Q了，这篇深入浅出贴助你早日实现Stable Diffusion自由

想知道精致的AI插画是如何实现的吗？接下来，我将结合这个案例带你走进 Stable Diffusion 的世界，帮你系统性地了解并掌握这神奇AI绘画魔法。

总部 sd 深入浅出 早日
210
探索Java通信面试的奥秘：揭秘IO模型、选择器和网络协议，了解面试中的必备知识点！

通过深入探索Java通信面试的奥秘，我们将揭秘Java中的三种I/O模型（BIO、NIO和AIO）、选择器（select、poll和epoll）以及网络协议（如HTTP和HTTPS），帮助您了解在面试中必备的知识点。这些知识点对于网络编程和系统安全方面的求职者来说至关重要，掌握它们将为您的职业发展打下坚实的基础！

探索 java 通信 面试
261
Go类型全解：常量与变量大全！

本篇文章深入探讨了 Go 语言中类型确定值、类型不确定值以及对应类型转换的知识点，后续充分解析了常量与变量及其高级用法，并举出丰富的案例。 关注公众号【TechLeadCloud】，分享互联网架构、云服务技术的全维度知识。作者拥有10+年互联网服务架构、AI产品研发经验、团队管理经验，同济本复旦硕，

go 类型 常量 变量
43
从源码角度深入解析Callable接口

摘要：从源码角度深入解析Callable接口，希望大家踏下心来，打开你的IDE，跟着文章看源码，相信你一定收获不小。 本文分享自华为云社区《一个Callable接口能有多少知识点？》，作者： 冰 河。 并发编程一直是程序员们比较头疼的，如何编写正确的并发程序相比其他程序来说，是一件比较困难的事情，并

源码 角度 深入 解析
113
Spring入门系列：浅析知识点

本文介绍了学习Spring源码前需要掌握的核心知识点，包括IOC、AOP、Bean生命周期、初始化和Transaction事务。通过Hello World示例，讲解了如何使用Spring，并指出了深入了解Spring内部机制的方向。

spring 入门 系列 浅析
708
2.1万字，30张图详解操作系统常见面试题（收藏版）

耗时两周，新版的操作系统常见知识点/问题总结总算搞完了，手绘了30多张图。大家可以用来复习操作系统或者准备操作系统面试。对于大部分公司的面试来说基本够用了，不过，像腾讯、字节这种大厂的面试还是要适当深入一些。 这篇文章总结了一些我觉得比较重要的操作系统相关的问题比如 用户态和内核态、系统调用、进程和

详解 操作系统 常见 面试题
651
# 热门排行
微软 New Bing AI 申请与使用保姆级教程（免魔法） ChatGPT API使用介绍 ChatGPT开发实战 一篇带你了解如何使用纯前端类Excel表格构建现金流量表 手把手教你玩转 Excel 数据透视表 为什么 C# 可能是最好的第一编程语言 .NET 入门到高级路线 提高工作效率的神器：基于前端表格实现Chrome Excel扩展插件 React + Springboot + Quartz，从0实现Excel报表自动化 用Echarts实现前端表格引用从属关系可视化
© PmDaddy. 2023 PmDaddy教程网 All rights reserved.