C++之STL整理（4）之set 用法（创建、赋值、增删查改）详解

注：整理一些突然学到的C++知识，随时mark一下
例如：忘记的关键字用法，新关键字，新数据结构

---

---

提示：本文为 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中时，它们将按照年龄进行排序。

总结