【内容补充】C++ STL库函数总结（纯手打，主要偏向ACM竞赛方面使用）

### C++ STL库函数总结（侧重ACM竞赛） #### 集合(Set) 集合是C++标准模板库(STL)中的一个重要容器，它基于红黑树实现，具有高效的查询、插入和删除性能。集合中的元素不会重复，并且默认情况下按照元素的自然顺序排序。 ##### 定义 集合是由节点组成的红黑树结构，每个节点都包含一个元素。这些节点通过一个作用于元素对的谓词来排列，这意味着集合中的元素都是唯一的。默认情况下，集合会根据元素的`<`运算符来进行排序，也就是说，默认情况下集合是按照升序排列的。 **注释**： - **默认排序**：集合默认按照升序排序，可以通过指定排序准则来改变排序方式。 - **自定义排序**：可以通过提供第二个模板参数（如`std::greater<int>`）来实现降序排列。 - **包含头文件**：使用降序排列需要包含`<functional>`头文件。 - **字符串处理**：若要存储字符串，则应使用C++的`std::string`类型，而非C风格的字符串。 ##### 创建集合 创建集合的方式有多种： - **直接声明**： ```cpp set<int> st; // 默认按升序排序 set<int, greater<int>> st; // 按降序排序 ``` - **从数组初始化**： ```cpp int a[10] = {2, 3, 4, 5, 6}; set<int> st(a, a + 10); ``` ##### 成员函数 集合提供了丰富的成员函数，用于数据的操作和管理。 - **迭代器成员函数**： - `begin()`：返回指向集合中第一个元素的迭代器。 - `end()`：返回指向集合中最后一个元素之后的迭代器。 - `rbegin()`：返回指向集合中最后一个元素的反向迭代器。 - `rend()`：返回指向集合中第一个元素之前的反向迭代器。 - `find(key)`：查找键值为`key`的元素，若找到则返回该元素的迭代器；否则返回`end()`。 - `upper_bound(key)`：返回集合中第一个大于`key`的元素的迭代器。 - `lower_bound(key)`：返回集合中第一个大于等于`key`的元素的迭代器。 - **元素操作成员函数**： - `insert(value)`：向集合中插入元素。 - `erase(iterator)`：删除由迭代器指向的元素。 - `erase(key)`：删除键值为`key`的所有元素。 - `clear()`：清除集合中的所有元素。 - `count(key)`：返回键值为`key`的元素数量（集合中一个元素最多只出现一次，因此返回值只能是0或1）。 - `empty()`：判断集合是否为空。 - `size()`：返回集合中元素的数量。 - **其他成员函数**： - `swap(set)`：与另一个集合交换内容。 - `equal_range(key)`：返回一个包含两个迭代器的对，第一个迭代器指向集合中第一个大于等于`key`的元素，第二个迭代器指向第一个大于`key`的元素。 - `get_allocator()`：返回用于分配集合中元素内存的分配器对象。 - `key_comp()`：返回一个函数对象，用于比较集合中的键值。 - `value_comp()`：返回一个函数对象，用于比较集合中的元素值。 - `max_size()`：返回集合能容纳的最大元素数量。 ##### 集合操作示例 下面是一个简单的示例，展示了如何使用集合的基本操作： ```cpp #include <iostream> #include <iterator> #include <set> #include <algorithm> int main() { set<int> eg1; eg1.insert(1); eg1.insert(100); eg1.insert(10); eg1.insert(9); // 遍历set set<int>::iterator set_iter = eg1.begin(); cout << "Set named eg1:" << endl; for (; set_iter != eg1.end(); set_iter++) { cout << *set_iter << " "; } cout << endl; set<int> eg2; for (int i = 6; i < 15; i++) { eg2.insert(i); } // 输出eg2 cout << "Set named eg2:" << endl; for (set<int>::iterator it = eg2.begin(); it != eg2.end(); ++it) { cout << *it << " "; } cout << endl; // 求集合的并集 set<int> union_set; std::set_union(eg1.begin(), eg1.end(), eg2.begin(), eg2.end(), std::inserter(union_set, union_set.begin())); cout << "Union of eg1 and eg2:" << endl; for (set<int>::iterator it = union_set.begin(); it != union_set.end(); ++it) { cout << *it << " "; } cout << endl; // 求集合的交集 set<int> intersect_set; std::set_intersection(eg1.begin(), eg1.end(), eg2.begin(), eg2.end(), std::inserter(intersect_set, intersect_set.begin())); cout << "Intersection of eg1 and eg2:" << endl; for (set<int>::iterator it = intersect_set.begin(); it != intersect_set.end(); ++it) { cout << *it << " "; } cout << endl; return 0; } ``` 通过以上介绍和示例，我们可以看到集合在ACM竞赛和其他编程场景中的强大功能。合理利用集合的特性，可以帮助我们高效地解决实际问题。