C++之STL整理（4）之set 用法（创建、赋值、增删查改）详解
注：整理一些突然学到的C++知识，随时mark一下
例如：忘记的关键字用法，新关键字，新数据结构
C++ 的map用法整理
提示：本文为 C++ 中 set构造、赋值、接口 的写法和举例
一、set的初始化
STL 中的set是一个关联容器，它存储的元素都是键值一体的（key-value pair），并且也会根据键（key）自动排序。set存储的元素（键）是唯一的，不允许键重复，并且默认按照从小到大的顺序进行排序（和map一样也可以通过提供一个自定义的比较函数或对象来改变排序方式，自定义类型必须增加）。std::set 的元素通过其键或迭代器进行访问，并且在这个容器中，键也是值（key is value），也就是说set相当于键值一体的map。
set的基本操作
插入元素：使用 insert 成员函数向 set 中插入元素。如果元素已经存在，则不会插入重复的元素。.insert()的返回值是个pair结构的对组 pair<iterator, bool> bool代表插入是否成功。
查找元素：使用 find 成员函数来查找元素。如果找到元素，则返回指向该元素的迭代器；否则返回 end() 迭代器。
删除元素：使用 erase 成员函数来删除元素。你可以通过迭代器或键来删除元素。
遍历元素：使用迭代器iterator来遍历 set 中的元素。由于 set 是有序的，所以遍历将按照元素的排序顺序进行。
示例
下面是一个简单的 std::set 使用示例：
#include <iostream>
#include <set>
int main() {
std::set<int> mySet;
// 插入元素
mySet.insert(3);
mySet.insert(1);
mySet.insert(4);
mySet.insert(1); // 不会插入重复的元素
// 遍历并打印元素
for (int num : mySet) {
std::cout << num << " ";
}
std::cout << std::endl; // 输出: 1 3 4
// 查找元素
if (mySet.find(3) != mySet.end()) {
std::cout << "Found 3 in the set." << std::endl;
}
// 删除元素
mySet.erase(4);
// 再次遍历并打印元素
for (int num : mySet) {
std::cout << num << " ";
}
std::cout << std::endl; // 输出: 1 3
return 0;
}
性能特点
插入和删除操作：由于 std::set 是基于红黑树实现的，所以插入和删除操作的平均时间复杂度为 O(log n)，其中 n 是集合中元素的数量。
查找操作：查找操作的平均时间复杂度也是 O(log n)。
内存使用：set 通常需要比数组或向量更多的内存，因为它需要存储额外的信息来维护树的平衡。
1、set初始化
（1）构造函数初始化
set<T> st; 和 multiset<T> mst;这两个是默认构造函数，用于创建一个空的 set 或 multiset。
示例：
std::set<int> mySet; // 创建一个空的整数set
std::multiset<std::string> myMultiSet; // 创建一个空的字符串multiset
set(const set &st); 和 multiset(const multiset &mst);
这些是拷贝构造函数，用于创建一个新的 set 或 multiset，它是现有 set 或 multiset 的副本。
示例：
std::set<int> mySet = {1, 2, 3};
std::set<int> anotherSet(mySet); // 创建一个mySet的副本
（2）赋值操作
set& operator=(const set &st); 和 multiset& operator=(const multiset &mst);是重载的等号操作符，用于将一个 set 或 multiset 的内容赋值给另一个已经存在的 set 或 multiset。
示例：
std::set<int> mySet = {1, 2, 3};
std::set<int> anotherSet;
anotherSet = mySet; // 将mySet的内容赋给anotherSet
（3）swap函数;
swap 是一个成员函数，用于交换两个 set 或 multiset 的内容。
std::set<int> mySet = {1, 2, 3};
std::set<int> anotherSet = {4, 5, 6};
mySet.swap(anotherSet); // 交换两个set的内容
3、大小操作
成员函数size();返回 set 或 multiset 中元素的数量。
成员函数empty();判断 set 或 multiset 是否为空。如果为空，返回 true；否则返回 false。
示例：
std::set<int> mySet = {1, 2, 3, 4, 5};
std::cout << "Size of mySet: " << mySet.size() << std::endl; // 输出: Size of mySet: 5
std::set<int> mySet;
if (mySet.empty()) {
std::cout << "mySet is empty." << std::endl;
} else {
std::cout << "mySet is not empty." << std::endl;
} // 输出: mySet is empty.
二、set的增删查改
1、插入操作insert
insert(elem);用于在 set 或 multiset 中插入一个元素。如果元素已存在（对于 set），则不会重复插入。
std::set<int> mySet;
mySet.insert(5); // 插入元素5
mySet.insert(3); // 插入元素3
2、删操作erase、clear
clear();清除 set 或 multiset 中的所有元素。
erase(pos);删掉迭代器 pos 所指向的元素，并返回指向下一个元素的迭代器。
std::set<int> mySet = {1, 2, 3, 4, 5};
auto it = mySet.find(3); // 查找元素3的迭代器
if (it != mySet.end()) {
it = mySet.erase(it); // 删除元素3，it现在指向4
}
mySet.clear(); // 清空set，现在mySet是空的
erase(beg, end);删除区间 [beg, end) 内的所有元素，并返回指向 end 之后元素的迭代器。
std::set<int> mySet = {1, 2, 3, 4, 5};
auto it = mySet.find(3); // 查找元素3的迭代器
if (it != mySet.end()) {
mySet.erase(it, std::next(it)); // 删除元素3（包括3）之后的所有元素
}
erase(elem);删除容器中值为 elem 的元素。对于 set，这只会删除一个元素（如果存在的话），因为 set 中的元素是唯一的。对于 multiset，会删除所有值为 elem 的元素。
std::multiset<int> myMultiSet = {1, 2, 2, 3, 4, 4, 4};
myMultiSet.erase(2); // 删除一个值为2的元素
myMultiSet.erase(4); // 删除一个值为4的元素，现在myMultiSet中还有两个4
3、查找操作 find
find(key);在 set 或 multiset 中查找键 key。如果找到，返回指向该键的元素的迭代器；否则返回 end() 迭代器。
std::set<int> mySet = {1, 2, 3, 4, 5};
auto it = mySet.find(3); // 查找元素3
if (it != mySet.end()) {
std::cout << "Found: " << *it << std::endl; // 输出: Found: 3
} else {
std::cout << "Not found." << std::endl;
}
4、统计count
count(key);对于 set，由于元素是唯一的，count(key) 要么返回 1（如果 key 存在），要么返回 0（如果 key 不存在）。对于 multiset，它返回 key 出现的次数。
std::multiset<int> myMultiSet = {1, 2, 2, 3, 4, 4, 4};
size_t countOfTwo = myMultiSet.count(2); // 查找元素2出现的次数
std::cout << "Number of 2s: " << countOfTwo << std::endl; // 输出: Number of 2s: 2
三、指定排序规则
您提到的内容是关于std::set和std::multiset容器的一个重要特性，即可以自定义排序规则。默认情况下，这些容器使用std::less来比较元素，但是可以通过提供自定义的比较函数或仿函数（functor）来改变排序规则。
1、指定set容器的排序规则
创建set或multiset时指定排序规则通常是通过传递一个比较对象（比如函数对象或lambda表达式）给容器的构造函数（第二个参数）来实现的。这个比较对象必须满足比较函数的要求，假设对于任何两个类型T的对象a和b，比较对象comp有以下规则条件：
comp(a, b)在a小于b时返回true
comp(b, a)在b小于a时返回true
comp(a, a)对于任何a都返回false
示例：
#include <iostream>
#include <set>
#include <string>
// 自定义比较函数对象
struct MyCompare {
bool operator()(const std::string& a, const std::string& b) const {
// 这里我们按照字符串的长度进行排序，而不是默认的字典序
return a.size() < b.size();
}
};
int main() {
// 使用自定义比较对象创建set
std::set<std::string, MyCompare> mySet;
// 插入元素，它们将按照字符串长度排序
mySet.insert("apple");
mySet.insert("banana");
mySet.insert("cherry");
// 输出set中的元素，将看到它们按长度排序
for (const auto& str : mySet) {
std::cout << str << ' ';
}
std::cout << std::endl;
return 0;
}
2、 对于自定义数据类型，set 必须指定排序规则
当使用自定义数据类型作为set或multiset的键时，通常需要提供一个比较函数或仿函数来定义如何比较这些对象。这是因为std::set和std::multiset需要知道这个新数据类型如何对元素进行排序。
示例：
假设我们有一个自定义的Person类，我们想要根据年龄对Person对象进行排序：
#include <iostream>
#include <set>
#include <string>
// 自定义数据类型
struct Person {
std::string name;
int age;
Person(const std::string& name, int age) : name(name), age(age) {}
};
// 自定义比较函数对象，用于Person类型的set
struct PersonCompare {
bool operator()(const Person& a, const Person& b) const {
return a.age < b.age; // 按照年龄升序排序
}
};
int main() {
// 使用自定义比较对象创建set来存储Person对象
std::set<Person, PersonCompare> peopleSet;
// 插入Person对象
peopleSet.insert(Person("Alice", 30));
peopleSet.insert(Person("Bob", 20));
peopleSet.insert(Person("Charlie", 25));
// 输出set中的Person对象，将看到它们按年龄排序
for (const auto& person : peopleSet) {
std::cout << person.name << ": " << person.age << std::endl;
}
return 0;
}
在这个例子中，我们定义了一个PersonCompare仿函数来告诉set如何比较Person对象。这样，当我们将Person对象插入到set中时，它们将按照年龄进行排序。