杂项

$\text{RAII}$

$\text{RAII}$（$\text{Resource Acquisition Is Initialization}$）是一种资源管理的思想，它的基本内容是：资源的获取应当在对象的构造函数中进行，资源的释放应当在对象的析构函数中进行，即资源的有效期与持有资源的对象的生命期严格绑定。这样可以避免资源泄漏的问题。

一种面向对象实现 $\text{RAII}$ 的范式如下：

• 将每个资源封装入一个类，其中：
  • 构造函数请求资源，并建立所有类不变式，或在它无法完成时抛出异常，
  • 析构函数释放资源并且决不会抛出异常；
• 在使用资源时始终通过 $\text{RAII}$ 类的满足以下要求的实例：
  • 自身拥有自动存储期或临时生存期；
  • 或具有与自动或临时对象的生存期绑定的生存期。

C++ 的智能指针等就是对 $\text{RAII}$ 的一个实践。

重要

如果没有使用智能指针，应当着重在所有出口处（如 return 和 throw）提防内存泄漏和野指针。

C++ STL

C++ 本身提供了一套标准模板库（$\text{Standard Template Library}$，$\text{STL}$），其中包含了许多常用的数据结构和算法。在编程时，除了应当对语法有所了解，还应当熟悉这些库的使用方法，以避免重复造轮子。

前面提及过 <memory>、<optional>、<variant>、<any> 等库，下面再简单介绍几个常用的模版库。

<vector>

<vector> 主要提供了一个动态的连续数组 vector 的实现。vector 是一个自主动态管理内存的数组，其大小可以动态增长。vector 的时间复杂度与普通数组相近，提供 $O(1)$ 的随机访问（迭代器或数组访问），$O(1)$ 的尾部插入和删除（push_back 和 pop_back），和 $O(n)$ 的内部插入和删除（insert 和 erase）。

vector 具有一个对应的迭代器，可以通过迭代器来访问 vector 中的元素。对于 vector v，v.begin() 返回指向第一个元素的迭代器，v.end() 返回指向最后一个元素的下一个位置的迭代器。遍历的范式如：for(auto it = v.begin(); it != v.end(); it++)。这种遍历方式提供了更多的灵活性，例如：

• 如果需要修改 vector 中的元素，可以通过 *it 来访问迭代器指向的元素。
• 如果希望逆序遍历 vector，可以使用 v.rbegin() 和 v.rend()。
• 如果希望在遍历过程中删除元素，可以使用 v.erase(it)。但是需要注意，删除元素后，原先的 it 迭代器将失效，需要用 erase 的返回值重新赋值。
• 如果希望在遍历过程中插入元素，可以使用 v.insert(it, val)。同样，插入元素后，原先的 it 迭代器将失效。

另一方面，vector 也可以看作简单的数组，可以通过 v[i] 来访问第 i 个元素，通过 v.size() 来获取 vector 的大小。遍历的范式如：for(int i = 0; i < v.size(); i++)。

此外，可以利用 sort 函数对 vector 进行排序，例如 sort(v.begin(), v.end())。 还可以在 sort 函数中传入一个比较函数，来实现自定义排序。

自定义比较函数

对于 vector<T> v，可以通过 sort(v.begin(), v.end(), cmp) 来实现自定义排序。其中 cmp 是一个比较函数，其定义如下：

bool cmp(const T& a, const T& b) {
    // return true if a should be before b
    // return false if a should be after b
}

即，如果 a 应当在 b 之前，则返回 true，否则返回 false。

下面是一个简单的 vector 的使用示例：

vector<int> v;

v.push_back(1);
v.push_back(2); // adding element at rear. v = {1, 2}
v.push_back(3); // adding element at rear. v = {1, 2, 3}

v.pop_back(); // removing element from rear. v = {1, 2}

for(auto it = v.begin(); it != v.end(); it++) {
    cout << *it << " "; // output: 1 2
}

for(int i = 0; i < v.size(); i++) {
    cout << v[i] << " "; // output: 1 2
}

for(auto it = v.rbegin(); it != v.rend(); it++) {
    cout << *it << " "; // output: 2 1
}

// remove all elements with value 1
for(auto it = v.begin(); it != v.end(); ) {
    if(*it == 1) {
        it = v.erase(it); // remove element 1 and return the next iterator
    }else {
        it++;
    }
}

// insert element 4 at the beginning
v.insert(v.begin(), 4); // v = {4, 2}

// sort the vector
sort(v.begin(), v.end()); // v = {2, 4}

<map>

<map> 提供了一个键唯一的键值对容器 map。map 是一个有序的容器，其内部实现一般是红黑树。map 提供 $O(\log n)$ 的查找、插入和移除操作。

可以使用 map<T1, T2> 来定义一个 map，其中 T1 是键的类型，T2 是值的类型。map 的操作类似于 vector，对于 map 对象 m，可以通过 m[key] 来访问 map 中的元素，通过 m.size() 来获取 map 的大小。同样，map 容器包含一个迭代器，遍历的范式如：for(auto it = m.begin(); it != m.end(); it++)。

常用的操作有：

• 如果希望寻找 map 中是否存在某个键，可以使用 m.find(key)，返回一个迭代器，如果找到了，返回指向该键值对的迭代器，否则返回 m.end()。
• 如果希望插入元素或若键已存在则赋值给当前元素，可以使用 m.insert_or_assign(key, val)。 还可以使用类似数组的方式 m[key] = val 来插入或重新赋值元素。

集合容器

set.h 与 map.h 类似，提供了一个键值合一的集合容器 set。set 容器维护了一个集合，其中的元素是唯一的，可以对 set 进行插入、删除和查找操作，但是不支持通过下标访问元素。

<queue>

<queue> 中主要提供了一个优先队列（堆，且默认为大根堆） priority_queue 的实现。它提供了 $O(\log n)$ 的插入和删除操作，以及 $O(1)$ 的查找操作。

可以使用 priority_queue<T> 来定义一个 priority_queue，其中 T 是队列中元素的类型。

常用的操作有：

• 如果希望插入元素，可以使用 q.push(val)。
• 如果希望删除队首元素（即最大元素），可以使用 q.pop()。
• 如果希望查找队首元素，可以使用 q.top()。
• 如果希望判断队列是否为空，可以使用 q.empty()。
• 如果希望获取队列的大小，可以使用 q.size()。

自定义比较函数

对于 priority_queue<T>，可以通过 **priority_queue<T, vector<T>, cmp>** 来实现自定义排序。其中 cmp 是一个比较函数，其定义如下（与 sort 的比较相近）：

bool cmp(const T& a, const T& b) {
    // return true if a should be before b
    // return false if a should be after b
}

<sstream>

提供字符串流。主要应用为字符串分割。

// split string by delimiter
std::vector<std::string> splitString(const std::string& str, char delimiter) {
    std::vector<std::string> tokens;
    std::stringstream ss(str);
    std::string token;

    while (std::getline(ss, token, delimiter)) {
        tokens.push_back(token);
    }

    return tokens;
}

<cctype>

主要用于字符处理，提供了一些字符分类和字符转换的函数。常用的函数有：isalpha、isdigit、isalnum（字母或数字）、islower、isupper、tolower、toupper 等等。

<chrono>

主要用于时间处理的复杂操作，提供了一些时间点和时间段的类。如果不需要复杂的时间处理，可以使用 <ctime> 库。