C++ 标准概述

一、STL容器

1、分类

序列式容器

• 数组(array)：定长的顺序表，C 风格数组的简单包装。
• 向量(vector)：后端可高效增加元素的顺序表。
• 双端队列(deque)：双端都可高效增加元素的顺序表。
• 列表(list)：可以沿双向遍历的链表。
• 单向列表：(forward_list) 只能沿一个方向遍历的链表。

谓词就是返回值为真或者假的函数。STL 容器中经常会使用到谓词，用于模板参数。

关联式容器

• 集合(set)：用以有序地存储 互异 元素的容器。其实现是由节点组成的红黑树，每个节点都包含着一个元素，节点之间以某种比较元素大小的谓词（谓词就是返回值为真或者假的函数。STL 容器中经常会使用到谓词，用于模板参数）进行排列。
• 多重集合(multiset)：用以有序地存储元素的容器。允许存在相等的元素。
• 映射(map)：由 {键，值} 对组成的集合，以某种比较键大小关系的谓词进行排列。
• 多重映射(multimap)：由 {键，值} 对组成的多重集合，亦即允许键有相等情况的映射。

无序（关联式）容器

• 无序（多重）集合(unordered_set/unordered_multiset)：与 set/multiset 的区别在于元素无序，只关心「元素是否存在」，使用哈希实现。
• 无序（多重）映射(unordered_map/unordered_multimap)：与 map/multimap 的区别在于键 (key) 无序，只关心「键与值的对应关系」，使用哈希实现。

容器适配器

容器适配器其实并不是容器。它们不具有容器的某些特点（如：有迭代器、有 clear() 函数……）。

• 栈(stack) 后进先出 (LIFO) 的容器，默认是对双端队列（deque）的包装。
• 队列(queue) 先进先出 (FIFO) 的容器，默认是对双端队列（deque）的包装。
• 优先队列(priority_queue) 元素的次序是由作用于所存储的值对上的某种谓词决定的的一种队列，默认是对向量（vector）的包装。

2、共有函数

begin()：返回指向开头元素的迭代器。

end()：返回指向末尾的下一个元素的迭代器。end() 不指向某个元素，但它是末尾元素的后继。

size()：返回容器内的元素个数。

max_size()：返回容器 理论上 能存储的最大元素个数。依容器类型和所存储变量的类型而变。

empty()：返回容器是否为空。

swap()：交换两个容器。

clear()：清空容器。

==、!=、<、>、<=、>=：按 字典序 比较两个容器的大小。（比较元素大小时 map 的每个元素相当于 set<pair<key, value>>，无序容器不支持 <、>、<=、>=。）

3、常用函数

下面只给出作者认为常用的函数，详细用法请参考官方中文文档cppreference（详细介绍了STL的用法）或者OI Wiki有关C++STL的部分。

vector 向量（后端可高效增加元素的顺序表）

• front()、back()：返回首、尾元素的引用（值，相当于 *begin()）。
• insert()：insert(pos,value) 在pos（迭代器）「前」插入value（值），insert(pos,first,last) 在pos（迭代器）「前」插入来自范围 [first「迭代器」, last「迭代器」) 的元素。
• erase()：earse(pos) 移除位于 pos（迭代器）的元素，earse(first,last) 移除范围 [first「迭代器」, last「迭代器」) 中的元素。
• push_back()、pop_back() ：在末尾插入、删除一个元素。

deque 双端队列（双端都可高效增加元素的顺序表）

• front()、back()：返回首、尾元素的引用（值，相当于 *begin()）。
• insert()：insert(pos,value) 在pos（迭代器）「前」插入value（值），insert(pos,first,last) 在pos（迭代器）「前」插入来自范围 [first「迭代器」, last「迭代器」) 的元素。
• erase()：earse(pos) 移除位于 pos（迭代器）的元素，earse(first,last)移除范围 [first「迭代器」, last「迭代器」) 中的元素。
• push_front() 、 pop_front() ：在头部插入、删除一个元素。
• push_back()、pop_back() ：在末尾插入、删除一个元素。

list 列表（可以沿双向遍历的链表）

• front()、back()：返回首、尾元素的引用（值，相当于 *begin()）。
• insert()：insert(pos,value) 在pos（迭代器）「前」插入value（值），insert(pos,first,last) 在pos（迭代器）「前」插入来自范围 [first「迭代器」, last「迭代器」) 的元素。
• erase()：earse(pos)移除位于 pos（迭代器）的元素，earse(first,last) 移除范围 [first「迭代器」, last「迭代器」) 中的元素。
• push_front() 、 pop_front() ：在头部插入、删除一个元素。
• push_back()、pop_back() ：在末尾插入、删除一个元素。

不支持随机访问，像list[num]是不合法的。

参考示例：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    // 初始化容器
    vector<int> v{1, 1, 2, 3, 5};
    deque<int> d{0, 1, 1, 2, 3, 5};
    list<int> l{0, 1, 1, 2, 3, 5};

    // 打印单个容器
    auto printContainer = [&](auto container)
    {
        for (auto it = container.begin(); it != container.end(); it++)
        {
            cout << *it << " ";
        }
    };

    // 打印所有容器
    auto printAll = [&]()
    {
        printContainer(v);
        cout << endl;
        printContainer(d);
        cout << endl;
        printContainer(l);
        cout << endl;
        cout << endl;
    };

    printAll();

    v.insert(v.end() - 1, 4);
    d.insert(d.end() - 1, 4);
    // list不支持随机访问 l.end() - 1 是不合法的
    l.insert(--l.end(), 4);
    printAll();

    v.erase(v.begin() + 1);
    d.erase(d.begin() + 1);
    // list不支持随机访问 l.begin() + 1 是不合法的
    l.erase(++l.begin());
    printAll();

    v.pop_back();
    d.pop_back();
    l.pop_back();
    printAll();

    d.pop_front();
    l.pop_front();
    printAll();
}

set 集合（用以有序地存储互异元素的容器）

• insert(value) 当容器中没有等价元素的时候，将元素value(值）插入到 set 中。
• erase()：earse(value)移除值为value（值）的所有元素并返回删除元素的个数，earse(pos) 移除位于 pos（迭代器）的元素，earse(first,last)移除范围 [first「迭代器」, last「迭代器」) 中的元素。
• count(value)：返回 set 内键为value（值）的元素数量。
• find(value)：在 set 内存在键为value（值）的元素时会返回该元素的迭代器，否则返回 end()。

map 映射（由 对组成的集合，以某种比较键大小关系的谓词进行排列）

• insert(pair<Key,T>(key,value))：map 中插入一个类型为 pair<Key,T> 的值。（或者直接通过 m[key] = value直接插入）

在利用下标访问 map 中的某个元素时，如果 map 中不存在相应键的元素，会自动在 map 中插入一个新元素，并将其值设置为默认值（对于整数，值为零；对于有默认构造函数的类型，会调用默认构造函数进行初始化）。
当下标访问操作过于频繁时，容器中会出现大量无意义元素，影响 map 的效率。因此一般情况下推荐使用 find() 函数来寻找特定键的元素。

• erase()：earse(value) 移除值为value（值）的所有元素并返回删除元素的个数，earse(pos) 移除位于 pos（迭代器）的元素，earse(first,last) 移除范围 [first「迭代器」, last「迭代器」) 中的元素。
• count(value)：返回 map 内键为value（值）的元素数量。
• find(value)：在 map 内存在键为value（值）的元素时会返回该元素的迭代器，否则返回 end()。

需要注意的是，对 map 的迭代器解引用后，得到的是类型为 pair<Key,T> 的键值对。

stack

STL「栈」(std::stack) 是一种后进先出 (Last In, First Out) 的容器适配器，仅支持查询或删除最后一个加入的元素（栈顶元素），不支持随机访问，且为了保证数据的严格有序性，不支持迭代器。

• top()：访问栈顶元素（如果栈为空，此处会出错）。
• push(value)：向栈中插入元素value（值）。
• pop()：删除栈顶元素。

queue

STL「队列」(std::queue) 是一种先进先出 (First In, First Out) 的容器适配器，仅支持查询或删除第一个加入的元素（队首元素），不支持随机访问，且为了保证数据的严格有序性，不支持迭代器。

• front()：访问队首元素（如果队列为空，此处会出错）。
• push(value)：向队列中插入元素value（值）。
• pop()：删除队首元素。

二、STL算法

STL 提供了大约 100 个实现算法的模版函数，基本都包含在 <algorithm> 之中，还有一部分包含在 <numeric> 和 <functional>。详细用法请参考官方中文文档cppreference（详细介绍了STL的用法）或者OI Wiki有关C++STL的部分。这里还是给出作者认为常用的函数。

• find：顺序查找。find(first「迭代器」, last「迭代器」, value)，其中 value 为需要查找的值。
• reverse：翻转数组、字符串。reverse(first「迭代器」, last「迭代器」)。
• unique：去除容器中相邻的重复元素。unique(first「迭代器」, last「迭代器」)，返回值为指向 去重后 容器结尾的迭代器，原容器大小不变。与 sort 结合使用可以实现完整容器去重。
• sort：排序。sort(first「迭代器」, last「迭代器」, cmp)，cmp 为自定义的比较函数。
• max_element、min_element：返回范围内的最大、最小的元素。max_element(first「迭代器」, last「迭代器」)、min_element(first「迭代器」, last「迭代器」)。

STL自带两个从左到右降序/升序的两个函数 greater<T(与容器类型一致)>()/less<T(与容器类型一致)>()（是的，真的从左到右是降序greater升序less🤔，你可以直接用下面的例子试一试）。cmp函数是一个返回值为 bool类型的函数模板如下：bool cmp(const Type1 &a, const Type2 &b){ ... return };（可以理解为排序后的值代入函数返回true）

参考示例：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    vector<int> v1{2, 4, 1, 5, 3, -6};
    vector<int> v2{2, 4, 1, 5, 3, -6};
    vector<int> v3{2, 4, 1, 5, 3, -6};

    sort(v1.begin(), v1.end(), greater<int>());
    sort(v2.begin(), v2.end(), less<int>());
    // 绝对值小的在前，大的在后
    auto cmp = [](const int &a, const int &b)
    {
        return abs(a) < abs(b);
    };
    sort(v3.begin(), v3.end(), cmp);

    for (auto value : v1)
    {
        cout << value << " ";
    }
    cout << endl;
    for (auto value : v2)
    {
        cout << value << " ";
    }
    cout << endl;
    for (auto value : v3)
    {
        cout << value << " ";
    }
    cout << endl;
}

三、后记

终于写完了其实文章大部分都是搬运的OI Wiki只是我自己在上面找一些用法时感觉很杂（毕竟人家比较专业，很多东西要写全）自己就写了一个STL常见用法的文章🙃，自己写小项目或者打比赛这些也差不多了。

还有两个特殊的类 string和 pair，由于我懒😝 string 和 vector 差不多（还是有许多不同比如关于子串的操作），pair 用法少，就不写了。详细还是要自己参考别人专业的文章和官方文档🥰。

四、参考链接

OI Wiki : https://oi-wiki.org/lang/csl/

cppreference : https://zh.cppreference.com/