C++ STL使用技巧

C++官方语法文档

一、简介

1.vector：可变长数组，倍增的思想。

(1) size()：O(1)，所有容器都有。
(2) empty()：O(1)，所有容器都有。
(3) clear()：不是所有容器都有（比如queue就没有）。
(4) front()/back()
(5) push_back()/pop_back()
(6) begin()/end()：迭代器。
(7) []：和数组一样支持随机存取。
(8) 支持比较运算（解析2）
(9) 倍增的思想：
操作系统有这样同一个特点：

当系统为某一程序分配空间时，其所需的时间基本上与空间大小无关，与申请次数有关。

因此变长数组vector要尽量减少申请空间的次数。所以每次数组长度不够用的时候，我们就把数组长度乘以2，再把之前的元素copy过来。
由此得到，当我们申请一个长度为n的数组时，申请空间的的次数为log(n)，平均情况下每个元素额外的copy次数是1次（即平均情况下每插入一个数的时间复杂度是O(1)的）。这也是倍增思想的好处。

(10) 3种遍历方式

    // ①
    for (int i = 0; i < a.size(); i++) {
        cout << a[i] << " ";
    }
    cout << endl;
    // ②
    for (vector<int>::iterator i = a.begin(); i != a.end(); i++) {
        // vector<int>::iterator可以直接写成 auto
        cout << *i << " ";
    }
    cout << endl;
    // ③
    for (auto x : a) {
        cout << x << " ";// 注意这里是 x 而不是 *x
    }
    cout << endl;

2.pair<xxx, xxx>

(1) .first是第一个元素，.second是第二个元素。
(2) 支持比较运算。也是字典序，以first为第一关键字，second为第二关键字。
(3) 两种初始化方式

    // ①
    p = make_pair(10, "wyj");// 注意这里是小括号
    // ②
    p = { 10,"wyj" };// 注意这里是大括号

(4) pair最常见的用途
假设一个东西有两种不同的属性，可能要按其中一个属性来排序，就把要排序的哪个属性设为first，不需要排序的属性设为second。
(5) pair来存储三种不同的属性(要更多个的话就继续嵌套)

    pair<int, pair<int, int>> p;
    p = { 1, { 2,3 } };

(6) pair相比于结构体的优势
pair相当于帮我们实现了一个结构体(两个变量的)，并且自带一个比较函数，能够省一些代码。

3.string：字符串。

(1) size()，empty()，clear()，可以直接+=。
(2) a.substr(i, j)（取子串）：从字符串a的下标为i开始，截取长度为j的子串。如果没有第二个参数，就是认为从i开始截取到最后。
(3) c_str()：返回string对应的字符数组的头指针。
(4) string还有一个length()函数，其作用于size()一致。

4.queue：队列。

(1) size()，empty()，push()，back()，front()，top()
(2) queue没有clear()这个函数。想清空的话就这样：

    q = queue<int>();

5.priority_queue：优先队列，其实就是堆，且默认是大根堆。

(1) push()（插入一个元素），top()（返回堆顶），pop()（弹出堆顶），也没有clear()。
(2) 想定义小根堆的两种方法：
① 在向堆中插入数据时插入负数，-x按从大到小来排序其实就是x按从小到大来排序。

    priority_queue<int> heap;
    int x;
    heap.push(-x);

② 在定义时直接定义成小根堆

    priority_queue<int, vector<int>, greater<int>> heap;// 见解析3

(3) 定义priority_queue时需要#include<queue>。

6.stack：栈。

(1) push()，top()，pop()，empty()，size()。
(2) stack也没有clear()这个函数。

7.deque：双端队列

(1) 加强版的vector，队头队尾都可以插入删除，并且可以支持随机访问。
(2) size()，empty()，clear()，front()/back()，push_back()/pop_back()，push_front()/pop_front()，begin()/end()，[]。
(3) 缺点：速度慢，效率低，比一般的数组要慢好几倍。

8.set，map，multiset，multimap：都是基于平衡二叉树（红黑树）来实现的，本质上是动态维护有序序列。

(1) 都支持size()，empty()，clear()。
(2) begin()/end()：++/--操作，返回前驱和后继。
(3) set不允许有重复元素，如果向其中插入重复的元素，那么这个操作将被忽略。而multiset允许有重复元素。

(4) set/multiset

① insert()：插入一个数。时间复杂度为O(logn)。
② find()：查找一个数。如果找到该元素，则返回一个指向被查找元素的迭代器；如果未找到，则返回一个指向set容器中尾后位置（end()返回的迭代器）的迭代器。
③ count()：返回某一个数的个数。
④ erase()：有以下两种形式：（实际还有一种，见解析4）

• 如果输入是x，那么就删除所有等于x的数。该种形式的时间复杂度为O(k + logn)，即查找为O(logn)，删除为O(k)。
• 如果输入是迭代器，那么就只删除该迭代器。

⑤ lower_bound()/upper_bound()
lower_bound(x)：返回大于等于x的最小的数的迭代器。
upper_bound(x)：返回大于x的最小的数的迭代器。
如果不存在，两个都返回end()。时间复杂度O(logn)。
⑥ set默认升序排序。定义降序排序的set(这个y总没讲):

    // ChatGPT还说greater需要#include<funtional>
    set<int, greater<int>> mySet;

(5) map/multimap

① insert()：注意插入的数是一个pair
② erase()：输入的参数是pair或者迭代器
③ []：可以像用数组一样来用map，但要注意[]的时间复杂度是O(logn)。

    map<string, int> a;
    a["wyj"] = 507;

④ lower_bound()/upper_bound()

(6) 优缺点

优点：支持和排序有关的操作。
缺点：增删改查操作的时间复杂度是O(logn)的。

9.unordered_set，unordered_map，unordered_multiset，unordered_multimap：都是基于哈希表来实现的，无序。

(1) 和8.set，map，multiset，multimap类似。
(2) 优点：增删改查的时间复杂度是O(1)的。
(3) 缺点

• 不支持lower_bound()/upper_bound()，因为内部无序。
• 不支持迭代器的++，--
• 不支持与排序有关的操作

(4) 需要#include<unorder_xxx>。

10.bitset：压位（解析1）。

(1) 优点：可以省 8 位空间。
例子：要开一个长度为 1024 的bool数组。在C++中，一个bool变量是 1B = 8位，如果直接开，那么需要大小为 1024 * 1B = 1KB 的空间。但此时如果用每一位代表一个bool值,就只需要大小为 1024 * 1位 = 128B 的空间了。以下为ChatGPT补充：
使用bitset是优化固定长度的布尔数组空间存储的一个非常好的方式，因为bitset在内部使用位来存储布尔值，这意味着每个布尔值只占用一个位，而不是使用传统布尔数组时的一个字节或更多。对于长度为 1024 的布尔数组，你可以这样定义一个bitset：

#include <bitset>
using namespace std;
int main() {
    bitset<1024> bits;

    // 使用 bits...
}

(2) 定义方法

    bitset<10000> S;// 长度为10000的bitset，"<>"中写的是个数

(3) 支持所有位运算操作
~，&，|，^（取反，与，或，异或）。
(4) 支持移位操作
>>，<<（右移一位，左移一位）。

#include <bitset>
#include <iostream>

int main() {
    std::bitset<8> bits(0b11010010); // 初始化为二进制 11010010

    // 左移操作
    bits <<= 2; // 结果为二进制 01001000
    std::cout << "After left shift:  " << bits << std::endl;

    // 右移操作
    bits >>= 3; // 结果为二进制 00001001
    std::cout << "After right shift: " << bits << std::endl;

    return 0;
}

(5) 支持基本的比较操作
==，!=（等于，不等于）。但不支持：>，<。
(6) []：可以取出某一位是 0 还是 1。
(7) count()：返回有多少个 1。
(8) any()：判断是否至少有一个 1。
(9) none()：判断是否全为 0。
(10) set()：把所有位变为 1。
(11) set(k, v)：将第k变成v。
(12) reset()：把所有位变成 0。
(13) flip()：把所有位取反，等价于~。
(14) flip(k)：把第k位取反。

二、解析

1.bitset

bitset 是 C++ 标准库中提供的一种模板类，它封装了一个固定大小的位序列，允许对位序列进行高效的位操作。bitset 类位于 <bitset> 头文件中，提供了一系列用于位操作的函数，使得位操作变得更加简单和直观。

基本特性

• 固定大小：在创建时，bitset 的大小（即它可以存储的位数）是固定的，并且在编译时确定。
• 直接访问：可以直接通过索引访问或修改 bitset 中的单个位。
• 位操作：支持各种位操作，包括位与、位或、位非、位异或、位移等，以及测试、设置、重置和翻转位的操作。

使用方法

创建一个 bitset：

#include <bitset>
#include <iostream>

int main() {
    std::bitset<8> bits(0b11010010); // 使用二进制字面量初始化一个8位的bitset
    std::cout << bits << std::endl; // 输出: 11010010
}

访问和修改位：

bits[2] = 1; // 将第2位（从0开始计数）设置为1
bool bit = bits[2]; // 读取第2位的值

进行位操作：

std::bitset<8> bits1(0b11010010);
std::bitset<8> bits2(0b10111010);

auto bits_or = bits1 | bits2; // 位或操作
auto bits_and = bits1 & bits2; // 位与操作
auto bits_xor = bits1 ^ bits2; // 位异或操作
bits1 <<= 2; // 左移两位
bits2 >>= 3; // 右移三位

std::cout << "OR: " << bits_or << std::endl;
std::cout << "AND: " << bits_and << std::endl;
std::cout << "XOR: " << bits_xor << std::endl;

其他常用操作：

bits.flip(); // 翻转所有位
bits.set(); // 将所有位设置为1
bits.reset(); // 将所有位重置为0
bits.count(); // 返回设置为1的位的数量
bits.size(); // 返回bitset的大小，即位数

优势和应用场景

• 高效的位级操作：bitset 为位级操作提供了一种高效且类型安全的方式，相比于传统的位操作（如使用整数类型和位操作符），它更加直观和易于管理。
• 内存效率：对于需要大量位操作的场景，使用 bitset 可以节省内存，因为它直接操作位而不是字节或更大的数据单位。
• 应用场景：bitset 适用于需要处理位图、位掩码、位字段等需要大量位操作的场景，如网络协议分析、硬件接口编程、编码解码、算法实现等领域。

总之，bitset 是 C++ 提供的一个强大的工具，用于在需要固定大小位数组的情况下进行有效的位操作。

2. vector容器的比较运算

在 C++ 中，std::vector 容器支持几种比较运算，这些运算允许我们比较两个 vector 对象的内容。比较运算遵循字典序（lexicographical order）规则，即从两个 vector 的第一个元素开始比较，如果两个元素不相等，则比较结果决定了两个 vector 的比较结果。如果在某一位置发现第一个不相等的元素，则停止比较，并根据这两个元素的比较结果返回。如果所有相对应的元素都相等，但 vector 的大小不同，则较短的 vector 被认为是较小的。如果所有元素都相等且大小也相等，则两个 vector 被认为是相等的。

以下是 std::vector 支持的比较运算符：

• 等于 (==)：如果两个 vector 的大小相同，并且在相对应位置的元素都相等，那么这两个 vector 被认为是相等的。
• 不等于 (!=)：如果两个 vector 在至少一个相对应位置的元素不相等，或者它们的大小不同，那么这两个 vector 被认为是不相等的。
• 小于 (<)：如果按照字典序比较时，第一个 vector 在第一个不同的元素上小于第二个 vector，或者第一个 vector 是第二个 vector 的前缀（并且第一个 vector 更短），那么第一个 vector 被认为小于第二个 vector。
• 小于等于 (<=)：如果第一个 vector 小于第二个 vector，或者两个 vector 相等，则第一个 vector 被认为小于等于第二个 vector。
• 大于 (>)：如果按照字典序比较时，第一个 vector 在第一个不同的元素上大于第二个 vector，或者第一个 vector 包含第二个 vector 作为其前缀（并且第一个 vector 更长），那么第一个 vector 被认为大于第二个 vector。
• 大于等于 (>=)：如果第一个 vector 大于第二个 vector，或者两个 vector 相等，则第一个 vector 被认为大于等于第二个 vector。

这些比较运算使得 vector 容器可以很容易地参与排序操作、搜索算法，以及作为容器的键值进行比较。比较运算的实现确保了 vector 可以直接用于标准算法库中需要比较运算的场合，如 std::sort、std::binary_search 等。

3. 如何定义小根堆

在 C++ 中，std::priority_queue 是一个容器适配器，它提供了队列的功能，其中的元素按照优先级出队。默认情况下，std::priority_queue 使用 std::less<T> 作为比较函数，构造一个大根堆（最大堆），即优先队列的顶部（使用 top() 访问）是队列中的最大元素。

通过显式指定 std::priority_queue 的模板参数，可以改变容器的行为，构造小根堆（最小堆）等其他类型的优先队列。具体来说：

• 第一个模板参数 int 指定了容器中存储的元素类型。
• 第二个模板参数 vector<int> 指定了底层容器类型，std::priority_queue 用它来存储元素。虽然 std::priority_queue 默认使用 std::vector 作为底层容器，这里显式地指定了它，以便为模板提供完整的参数列表。
• 第三个模板参数 greater<int> 指定了比较函数，这决定了元素的排列顺序。std::greater<int> 是一个函数对象，它使得两个整数进行比较时，较小的整数被认为“优先级更高”。

因此，当你声明：

priority_queue<int, vector<int>, greater<int>> heap;

你实际上创建了一个优先队列，它内部使用小根堆来组织数据。在这个优先队列中，每次调用 top() 会得到当前队列中“最小”的元素，而不是“最大”的元素。每次调用 pop() 则会移除队列中的最小元素。

这种方式让 std::priority_queue 变得更加灵活，可以根据需要构造最小堆或最大堆，以及基于自定义优先级的其他复杂数据结构。这在需要快速访问和删除最小元素（例如在某些特定的算法中，如 Dijkstra 的最短路径算法）的场景下特别有用。

4. set的erase()

在 C++ 标准库中，std::set 是一个基于红黑树的有序集合，它不允许重复的元素，并且能够保证其中元素的排序。std::set 提供了 erase() 成员函数，用于从集合中删除元素。这个函数有几种不同的形式，允许以不同的方式指定要删除的元素。

(1) 使用方法

① 通过指定元素的值删除

size_type erase(const key_type& key);

• key：要删除的元素的值。
• 返回值：被删除元素的数量（对于 std::set 来说，这个值只能是 0 或 1，因为 std::set 不允许重复元素）。

② 通过迭代器指定要删除的元素

iterator erase(iterator pos);

• pos：指向要删除元素的迭代器。
• 返回值：指向被删除元素之后元素的迭代器。

③ 删除指定范围内的元素

iterator erase(iterator first, iterator last);

• first, last：要删除的元素范围的起始和结束迭代器（左闭右开区间）。
• 返回值：指向最后一个被删除元素之后元素的迭代器。

(2) 示例

#include <iostream>
#include <set>

int main() {
    std::set<int> mySet = {1, 2, 3, 4, 5};

    // 通过值删除
    mySet.erase(3);

    // 通过迭代器删除
    auto it = mySet.find(2);
    if (it != mySet.end()) {
        mySet.erase(it);
    }

    // 输出剩余元素
    for (int elem : mySet) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

(3) 注意事项

• 使用迭代器删除元素时，必须确保迭代器有效且不等于 end()，因为尝试解引用一个指向 set 结尾的迭代器是未定义行为。
• 删除操作会改变 set 的大小，如果在删除操作中使用了多个迭代器遍历 set，需要注意迭代器失效的问题。
• erase() 操作的时间复杂度通常是对数时间复杂度（O(log n)），其中 n 是 set 中元素的数量，这是因为需要在红黑树中查找到要删除的元素。然而，如果直接给出迭代器，时间复杂度则为常数时间复杂度（O(1)），因为不需要再次查找元素。

std::set 的 erase() 函数提供了灵活的方式来删除集合中的元素，无论是单个元素还是一范围内的多个元素，都能够有效地从集合中移除，同时保持集合的有序性。

(4) 如何在for循环中使用erase()函数来删除set中的所有元素

在 for 循环中使用 erase() 函数来删除 std::set 中的所有元素时，要特别注意迭代器的有效性。因为当一个元素被删除后，指向该元素的迭代器会失效，但 std::set::erase() 函数会返回一个指向被删除元素之后元素的迭代器，可以利用这一点来安全地删除元素。

① 使用迭代器遍历并删除所有元素

你可以在 for 循环中这样使用 erase() 函数：

std::set<int> mySet = {1, 2, 3, 4, 5};

for (auto it = mySet.begin(); it != mySet.end(); ) {
    it = mySet.erase(it);
}

在这个例子中，erase() 调用删除了当前迭代器 it 指向的元素，并返回了指向下一个元素的迭代器，然后循环继续进行，直到遍历完集合。这种方式可以确保在删除元素的同时不会让迭代器失效，因为每次 erase() 都会返回一个新的有效迭代器。

② 删除特定条件的元素

如果你想在遍历时根据某些条件删除元素，可以在循环中添加条件判断：

for (auto it = mySet.begin(); it != mySet.end(); ) {
    if (/* some condition */) {
        it = mySet.erase(it);
    } else {
        ++it;
    }
}

这里，只有满足特定条件的元素会被删除，其他元素的迭代将继续。

③ 删除所有元素

如果你的目标是删除 std::set 中的所有元素，使用 erase() 函数遍历整个集合并不是最高效的方法。std::set 提供了 clear() 成员函数，可以直接删除所有元素：

mySet.clear();

这会移除集合中的所有元素，是清空 std::set 的推荐方式，因为它直接和明确地表达了意图，同时也具有更高的效率。