阅读量:0
一.set
1.1set基本概念
特点：
所有元素在插入时，会自动排序，并且不能插入重复元素。
本质：
set/multiset属于关联式容器，底层是红黑树。
set/multiset区别
1.set不允许容器中有重复的元素
2.multiset允许容器中有重复的元素
1.2set构造和赋值
构造set容器：
- 默认构造函数：
std::set<Type> set_name; - 区间构造函数：
std::set<Type> set_name(iterator_begin, iterator_end); - 拷贝构造函数：
std::set<Type> set_name(another_set); - 拷贝构造函数（部分元素）：
std::set<Type> set_name(another_set, iterator_begin, iterator_end);
- 默认构造函数：
赋值操作：
- 拷贝赋值：
set_name = another_set; - 移动赋值（自C++11起）：
set_name = std::move(another_set); - 重载 = ：
std::set<Type> set_name = another_set;
- 拷贝赋值：
其中，Type是set中存储的元素类型。需要注意的是，set中的元素默认按照升序进行排序，并且所有元素都是唯一的。如果需要自定义排序规则或元素比较函数，可以使用带有自定义比较函数的构造函数和赋值操作符。
以下是一些示例代码：
// 构造set容器 std::set<int> mySet1; // 默认构造函数 int arr[] = {1, 2, 3, 4, 5}; std::set<int> mySet2(arr, arr + 5); // 区间构造函数，指针也可 std::set<int> anotherSet = mySet2; // 拷贝构造函数 // 赋值操作 std::set<int> mySet3; mySet3 = anotherSet; // 拷贝赋值 std::set<int> mySet4; mySet4 = std::move(anotherSet); // 移动赋值 | 构造函数 | 示例 |
|---|---|
| 默认构造函数 | std::set<Type> set_name; |
| 区间构造函数 | std::set<Type> set_name(begin, end); |
| 拷贝构造函数 | std::set<Type> set_name(another_set); |
| 拷贝构造函数（部分元素） | std::set<Type> set_name(another_set, iterator_begin, iterator_end); |
| 赋值操作 | 示例 |
|---|---|
| 拷贝赋值 | set_name = another_set; |
| 移动赋值（自C++11起） | set_name = std::move(another_set); |
1.3set大小和交换
在STL中，set（或者其他关联容器）具有以下两个常用的成员函数来获取容器的大小以及交换容器内容：
大小操作：
size()：返回容器中元素的个数。empty()：检查容器是否为空，如果为空则返回true，否则返回false。
交换操作：
swap()：将当前容器的内容与另一个容器进行交换。
以下是使用示例：
#include <iostream> #include <set> int main() { std::set<int> mySet = {1, 2, 3, 4, 5}; // 大小操作 std::cout << "Set的大小为：" << mySet.size() << std::endl; if (mySet.empty()) { std::cout << "Set为空" << std::endl; } else { std::cout << "Set不为空" << std::endl; } // 交换操作 std::set<int> anotherSet = {10, 20, 30}; mySet.swap(anotherSet); std::cout << "交换后的mySet：" << std::endl; for (const auto& num : mySet) { std::cout << num << " "; } std::cout << std::endl; std::cout << "交换后的anotherSet：" << std::endl; for (const auto& num : anotherSet) { std::cout << num << " "; } std::cout << std::endl; return 0; } 输出结果：
Set的大小为：5 Set不为空 交换后的mySet： 10 20 30 交换后的anotherSet： 1 2 3 4 5 通过调用size()函数可以获取set的大小，使用empty()函数可以判断set是否为空。而使用swap()函数可以交换两个set容器的内容。
| 大小操作 | 说明 |
|---|---|
size() | 返回set容器中元素的个数。 |
empty() | 检查set容器是否为空，如果为空则返回true，否则返回false。 |
| 交换操作 | 说明 |
|---|---|
swap(other_set) | 将当前set容器的内容与另一个set容器other_set进行交换。 |
1.4set的插入和删除
插入操作：
insert(val)：将值为val的元素插入set容器中。insert(start, end)：将迭代器范围内的元素插入set容器中。emplace(args)：在set容器中构造一个新元素，使用args参数传递构造参数。
删除操作：
erase(val)：从set容器中删除值等于val的元素。erase(iterator)：删除按照迭代器指定的元素。erase(start, end)：删除迭代器范围内的元素。clear()：删除set容器中的所有元素。
以下是使用示例：
#include <iostream> #include <set> int main() { std::set<int> mySet; // 插入操作 mySet.insert(1); mySet.insert(2); mySet.insert(3); mySet.emplace(4); std::set<int> anotherSet = {5, 6, 7}; mySet.insert(anotherSet.begin(), anotherSet.end()); // 删除操作 mySet.erase(3); mySet.erase(mySet.find(4)); mySet.erase(mySet.begin(), mySet.find(5)); mySet.clear(); return 0; } 请注意，set是按照元素的自然排序进行存储的，因此在插入操作时会按照排序规则进行插入。在删除操作时，可以指定特定的元素值进行删除，或者使用迭代器进行删除，也可以删除迭代器范围内的一系列元素。使用clear()函数可以删除set容器中的所有元素。
| 插入操作 | 说明 |
|---|---|
insert(val) | 将值为val的元素插入set容器中。 |
insert(start, end) | 将迭代器范围内的元素插入set容器中。 |
emplace(args) | 在set容器中构造一个新元素，并使用args参数传递构造参数。 |
| 删除操作 | 说明 |
|---|---|
erase(val) | 从set容器中删除值等于val的元素。 |
erase(iterator) | 删除按照迭代器指定的元素。 |
erase(start, end) | 删除迭代器范围内的元素。 |
clear() | 删除set容器中的所有元素。 |
1.5set的查找和统计
在STL中，set（或其他关联容器）具有以下常用的成员函数来进行元素的查找和统计：
查找操作：
count(val)：返回set容器中值等于val的元素的个数（由于set中元素唯一，所以返回值只能是0或1）。find(val)：返回一个迭代器，指向set容器中值等于val的元素，如果未找到则返回指向容器末尾的迭代器end()。lower_bound(val)：返回一个迭代器，指向set容器中第一个不小于val的元素。upper_bound(val)：返回一个迭代器，指向set容器中第一个大于val的元素。equal_range(val)：返回一个pair，包含两个迭代器，分别指向set容器中等于val的元素的起始位置和结束位置。
统计操作：
size()：返回set容器中元素的个数。
以下是使用示例：
#include <iostream> #include <set> int main() { std::set<int> mySet = {1, 2, 3, 4, 5}; // 查找操作 int count = mySet.count(3); std::cout << "值为3的元素在set中出现的次数：" << count << std::endl; auto it = mySet.find(4); if (it != mySet.end()) { std::cout << "找到了值为4的元素" << std::endl; } else { std::cout << "未找到值为4的元素" << std::endl; } auto lower = mySet.lower_bound(3); auto upper = mySet.upper_bound(3); std::cout << "大于等于3的第一个元素：" << *lower << std::endl; std::cout << "大于3的第一个元素：" << *upper << std::endl; auto range = mySet.equal_range(3); std::cout << "等于3的元素范围：" << *range.first << " - " << *range.second << std::endl; // 统计操作 std::cout << "set的大小：" << mySet.size() << std::endl; return 0; } 输出结果：
值为3的元素在set中出现的次数：1 找到了值为4的元素 大于等于3的第一个元素：3 大于3的第一个元素：4 等于3的元素范围：3 - 4 set的大小：5 通过以上示例可以看出，使用count()函数可以统计set容器中值等于给定值的元素个数。使用find()函数可以查找set容器中值等于给定值的元素，并返回其迭代器。lower_bound()函数可以返回第一个不小于给定值的元素的迭代器，而upper_bound()函数则返回第一个大于给定值的元素的迭代器。equal_range()函数返回一个pair，包含了等于给定值的元素的起始位置和结束位置。size()函数用于统计set容器中元素的个数。
| 查找操作 | 说明 |
|---|---|
count(val) | 返回set容器中值等于val的元素的个数（返回值只能是0或1，因为set中元素唯一）。 |
find(val) | 返回一个迭代器，指向set容器中值等于val的元素，如果未找到则返回指向容器末尾的迭代器 end()。 |
lower_bound(val) | 返回一个迭代器，指向set容器中第一个不小于val的元素。 |
upper_bound(val) | 返回一个迭代器，指向set容器中第一个大于val的元素。 |
equal_range(val) | 返回一个pair，包含两个迭代器，分别指向set容器中等于val的元素的起始位置和结束位置。 |
| 统计操作 | 说明 |
|---|---|
size() | 返回set容器中元素的个数。 |
1.6set的insert返回值
使用insert函数在set容器中插入元素时，返回值是一个pair类型的迭代器和布尔值。
- 如果插入的元素在set容器中不存在（即唯一性），则返回的布尔值为
true，且迭代器指向新插入的元素位置。 - 如果插入的元素在set容器中已经存在（即已有相同的元素），则返回的布尔值为
false，且迭代器指向与已存在的元素相等的位置。
以下是使用示例：
#include <iostream> #include <set> int main() { std::set<int> mySet = {1, 2, 3}; auto result = mySet.insert(4); if (result.second) { std::cout << "插入成功，新元素的值为：" << *result.first << std::endl; } else { std::cout << "插入失败，重复的元素的值为：" << *result.first << std::endl; } result = mySet.insert(2); if (result.second) { std::cout << "插入成功，新元素的值为：" << *result.first << std::endl; } else { std::cout << "插入失败，重复的元素的值为：" << *result.first << std::endl; } return 0; } 输出结果：
插入成功，新元素的值为：4 插入失败，重复的元素的值为：2 在上面的示例中，首先使用insert(4)插入一个在set容器中不存在的元素，因此返回的布尔值为true，迭代器指向新插入的元素位置。
接下来使用insert(2)插入一个已经存在的元素，由于set容器的唯一性特性，插入失败，返回的布尔值为false，迭代器指向与已存在的元素相等的位置。
1.7set自定义排序
在C++的STL中，set容器默认按照升序进行排序。在插入元素时，set容器会自动将元素按照特定的比较函数进行排序，以保证容器中的元素始终按照升序排列。
如果需要使用自定义的排序规则，可以在创建set容器时通过传递一个自定义的比较函数对象来指定排序规则。比较函数对象应满足严格弱排序（Strict Weak Ordering）的要求，即有传递性、反对称性和完全性。
例如，假设我们想要按照降序排列set容器中的元素，可以通过自定义比较函数对象来实现：
#include <iostream> #include <set> // 自定义的比较函数对象，仿函数 class DescendingComparator { bool operator()(int a, int b) const { return a > b; // 降序排序 } }; int main() { std::set<int, DescendingComparator> mySet = {5, 2, 7, 1, 9}; // 打印排序后的set容器内容 for (const auto& elem : mySet) { std::cout << elem << " "; } std::cout << std::endl; return 0; } 输出结果：
9 7 5 2 1 在上面的示例中，我们通过传递自定义的比较函数对象DescendingComparator来创建set容器mySet，从而实现按照降序排列的功能。
需要注意的是，通过自定义比较函数对象来指定排序规则时，当容器中的元素具有相等的排序键时，set容器仍然能够确保元素的唯一性。
const修饰的成员函数
bool operator()(int a, int b) const {
return a > b; // 降序排序
}
const成员函数具有以下几个特点：
不修改成员变量：
const成员函数承诺不会修改类对象的成员变量的值。在const成员函数中，所有非静态的成员变量都被视为const，无法直接修改它们的值。只能访问成员变量的值或调用其他的const成员函数。可以被常量对象调用：
const成员函数可以被常量对象调用，而非const成员函数无法被常量对象调用。常量对象是指使用const修饰的对象，它们的成员函数只能调用对象的const成员函数。重载：
const成员函数和非const成员函数可以同时存在，并且可以根据是否为常量对象来进行重载。这样可以在不同的情况下调用不同的成员函数版本。对象状态不变：
const成员函数内部的逻辑不会改变对象的状态，也就是说，它不会修改对象的数据成员。这可以让使用者在调用const成员函数时，放心地假设对象不会被修改。可以调用其他
const成员函数：在const成员函数内部，可以调用其他的const成员函数。这是因为在const成员函数内部，所有的非静态成员变量都被视为const，因此只能调用const成员函数来保证对象状态的不变性。
总结起来，const成员函数由于其不修改对象状态的特性，能够提供更高的安全性和可靠性。它们可以被常量对象调用，不会修改对象的成员变量，可以重载非const成员函数，以及可以相互调用。
1.8set存储自定义类型
在C++中，可以使用std::set容器来存储自定义类型。
要在std::set中存储自定义类型，需要满足以下两个条件：
提供比较函数：
std::set是一个有序容器，它要求元素能够进行比较来确定它们的顺序。为了实现自定义类型的比较，你可以通过重载小于运算符（<）或为该类型提供一个自定义的比较函数对象。这个比较函数或运算符将被用于确定元素的顺序。例如，假设有一个自定义类型
Person，我们可以重载<运算符来定义其比较方式，或者提供一个比较函数对象，如下所示：struct Person { std::string name; int age; // 通过重载 < 运算符定义比较方式 bool operator<(const Person& other) const { return age < other.age; } }; // 或者通过提供自定义的比较函数对象 struct AgeComparator { bool operator()(const Person& a, const Person& b) const { return a.age < b.age; } };为容器指定比较方式：在创建
std::set对象时，需要指定元素的比较方式。你可以通过传递一个比较函数对象作为std::set的第二个模板参数，或者默认使用默认的比较方式（利用元素类型的<运算符）。例如：std::set<Person> people; // 使用自定义比较函数对象 std::set<Person, AgeComparator> people; // 使用自定义比较函数对象 std::set<int> numbers; // 使用整数类型的默认比较方式
在存储自定义类型的std::set中，元素将按照它们的比较方式进行排序，保证元素的唯一性。你可以使用insert()函数向std::set中插入元素，使用find()函数在std::set中查找元素。同时，std::set还提供了其他常见的操作，如删除元素、遍历元素等。
1.9set函数接口
| 类别 | 函数接口 |
|---|---|
| 构造函数 | set() |
set(InputIt first, InputIt last) | |
set(const set& other) | |
set(set&& other) | |
| 赋值运算符 | operator= |
operator=(set&& other) | |
| 迭代器 | begin() |
end() | |
| 容量 | empty() |
size() | |
max_size() | |
| 修改器 | insert(const value_type& value) |
insert(InputIt first, InputIt last) | |
erase(const value_type& value) | |
erase(iterator position) | |
erase(iterator first, iterator last) | |
clear() | |
| 查找 | find(const value_type& value) |
count(const value_type& value) | |
lower_bound(const value_type& value) | |
upper_bound(const value_type& value) | |
equal_range(const value_type& value) | |
| 比较 | operator== |
operator!= | |
operator< | |
operator> | |
operator<= | |
operator>= |
例子
operator<=是 std::set 容器的比较运算符之一，用于比较两个 std::set 是否满足部分顺序关系。下面是使用 operator<= 进行比较的方法：
首先，假设有两个 std::set 对象，例如 set1 和 set2。
std::set<T> set1; std::set<T> set2; 要使用 operator<= 进行比较，只需要将这两个集合放在一个条件语句中，并使用 operator<= 进行比较。例如：
if (set1 <= set2) { // set1 是 set2 的子集或等于 set2 } else { // set1 不是 set2 的子集 } 当条件为真时，表示 set1 是 set2 的子集，或者两个集合完全相等。否则，当条件为假时，表示 set1 不是 set2 的子集。
请注意，这里的子集关系取决于 std::set 中元素的部分顺序关系，即集合中的元素按升序排列。
operator<=比较的是两个集合的关系，而不是集合中元素的值之间的关系。如果你想比较集合中的元素的值，请使用迭代器或其他比较方法进行元素比较。
二.multiset
std::set和std::multiset是C++标准库中的两种关联容器，它们的函数接口在大部分功能上是相同的，但在某些特定操作上有一些区别。
以下是std::set和std::multiset之间函数接口的主要区别：
插入操作：对于
std::set，insert()函数返回一个std::pair对象，用于指示插入是否成功，并且如果插入的元素已经存在，则不会插入重复元素。而对于std::multiset，insert()函数直接插入元素，允许存储重复元素。删除操作：
erase()函数在std::set和std::multiset中的行为略有不同。在std::set中，erase()函数将删除与给定值相等的元素，并返回删除的元素数量（0或1）。在std::multiset中，erase()函数将删除所有与给定值相等的元素，并返回删除的元素数量。元素计数：
count()函数在std::set和std::multiset中的行为也略有不同。在std::set中，count()函数返回一个整数，表示与给定值相等的元素的数量（0或1）。而在std::multiset中，count()函数返回一个整数，表示与给定值相等的元素的数量。查找操作：
find()函数在std::set和std::multiset中的行为相同，都是用于在容器中查找与给定值相等的元素，并返回指向该元素的迭代器。如果找不到匹配的元素，则返回容器的end()迭代器。
除了上述区别外，std::set和std::multiset其他常见的函数接口，如迭代器操作、大小和容量查询等，基本上是相同的。
，这只是std::set和std::multiset之间在函数接口上的一些区别，它们共享相似的函数接口，因为它们都是基于相同的关联容器概念，并遵循C++标准库的通用规范。
下面是std::set和std::multiset之间函数接口的主要区别的整理表格：
| 函数接口 | std::set | std::multiset |
|---|---|---|
| 插入操作 | insert()函数返回std::pair对象，不插入重复元素 | 直接插入元素，允许存储重复元素 |
| 删除操作 | erase()函数删除等于给定值的元素，返回删除数量 | erase()函数删除等于给定值的所有元素，返回删除数量 |
| 元素计数 | count()函数返回0或1 | count()函数返回与给定值相等的元素数量 |
| 查找操作 | find()函数返回指向匹配元素的迭代器 | find()函数返回指向匹配元素的迭代器 |
| 其他常见操作 | 迭代器操作、大小和容量查询等 | 迭代器操作、大小和容量查询等 |
三.unordered_set
无序set
| 函数接口 | std::set | std::unordered_set |
|---|---|---|
| 排序顺序 | 元素按升序排列 | 不对元素进行排序 |
| 插入操作 | insert()函数返回一个std::pair对象，不插入重复元素 | 插入元素，不插入重复元素 |
| 查找操作 | find()函数返回指向匹配元素的迭代器 | find()函数返回指向匹配元素的迭代器 |
| 删除操作 | erase()函数删除等于给定值的元素并返回删除的数量 | erase()函数删除等于给定值的元素并返回删除的数量 |
| 元素计数 | count()函数返回值只能是0或1，因为集合中元素唯一 | count()函数返回与给定值相等的元素数量 |
| 迭代器范围遍历 | 可以使用迭代器范围进行区间遍历 | 可以使用迭代器范围进行区间遍历 |
| 内部实现 | 基于红黑树实现，保持元素有序 | 基于哈希表实现，元素无序 |
| 性能特点 | 插入和删除操作相对较慢，查找操作较快 | 插入和删除操作相对较快，查找操作速度由哈希函数质量决定 |
| 内存占用 | 需要额外的存储空间来维护红黑树结构 | 需要额外的存储空间来维护哈希表结构 |
| 迭代顺序 | 根据元素值进行排序 | 根据哈希函数和桶排序顺序，元素顺序不固定 |
unordered_set是基于哈希表实现的，因此在插入和查找操作时具有较快的平均时间复杂度。而set是基于红黑树实现的，保证了元素的有序性，但插入和删除操作相对较慢。在选择使用哪个容器时，可以根据实际需求和性能要求进行评估。
四.unordered_multiset
std::unordered_multiset是C++标准库中的一种关联容器，它实现了一个无序的、允许重复元素的集合（Multiset）。与std::unordered_set不同，std::unordered_multiset允许存储多个相同的元素，而不是将重复元素视为错误。
以下是std::unordered_multiset相较于std::unordered_set的一些主要特点和区别：
- 元素存储：
std::unordered_multiset以无序的方式存储元素，并允许多个相同的元素存在。 - 插入重复元素：
insert()函数可以插入重复的元素。 - 删除元素：
erase()函数可以删除与给定值相等的所有元素。 - 元素计数：
count()函数返回某个给定值在容器中的数量，可以用于统计重复元素的个数。 - 迭代器范围遍历：可以使用迭代器范围进行区间遍历，包括重复元素。
std::unordered_multiset使用哈希表（hash table）来实现存储和快速查找元素，而不会按照元素的顺序进行排序。如果你需要保持元素的有序性，请考虑使用std::multiset，它是一个有序的、允许重复元素的集合容器。
| 函数接口 | std::unordered_multiset | std::unordered_set |
|---|---|---|
| 元素存储 | 无序存储、允许重复元素 | 无序存储、不允许重复元素 |
| 插入操作 | insert()函数可以插入重复元素 | insert()函数不插入重复元素 |
| 删除操作 | erase()函数删除与给定值相等的所有元素，并返回删除的数量 | erase()函数删除等于给定值的元素，并返回删除的数量 |
| 元素计数 | count()函数返回与给定值相等的元素数量 | count()函数返回0或1，因为集合中不存储重复项 |
| 迭代器范围遍历 | 可以使用迭代器范围进行区间遍历，包括重复的元素 | 可以使用迭代器范围进行区间遍历，不包括重复的元素 |
| 内部实现 | 基于哈希表实现，元素无序 | 基于哈希表实现，元素无序 |
| 性能特点 | 插入和删除操作性能较快，查找操作速度取决于哈希函数和负载因子的质量 | 插入和删除操作性能较快，查找操作速度取决于哈希函数和负载因子的质量 |
| 内存占用 | 需要额外的存储空间来维护哈希表结构 | 需要额外的存储空间来维护哈希表结构 |
| 迭代顺序 | 元素的顺序是无序的 | 元素的顺序是无序的 |
五.四种set总结
在C++中，有四种不同的集合容器：std::set、std::multiset、std::unordered_set和std::unordered_multiset。
std::set：- 基于红黑树实现的有序集合容器。
- 每个元素在容器中都是唯一的，不允许重复元素。
- 元素按照升序存储，并且支持高效的查找、插入和删除操作。
- 没有哈希函数的开销，也没有哈希冲突的问题。
std::multiset：- 基于红黑树实现的有序多重集合容器。
- 允许存储重复的元素，即可以有多个相等的元素。
- 元素按照升序存储，并且支持高效的查找、插入和删除操作。
std::unordered_set：- 基于哈希表实现的无序集合容器。
- 每个元素在容器中都是唯一的，不允许重复元素。
- 元素存储顺序是无序的，但在平均情况下，插入、查找和删除操作都具有较快的时间复杂度。
- 元素类型需要提供哈希函数和相等比较函数。
std::unordered_multiset：- 基于哈希表实现的无序多重集合容器。
- 允许存储重复的元素，即可以有多个相等的元素。
- 元素存储顺序是无序的，但在平均情况下，插入、查找和删除操作都具有较快的时间复杂度。
- 元素类型需要提供哈希函数和相等比较函数。
总结来说，std::set和std::unordered_set是无序容器，而std::multiset和std::unordered_multiset是允许存储重复元素的无序容器。其中，std::set和std::multiset中的元素是有序存储的，而std::unordered_set和std::unordered_multiset中的元素是无序存储的，但具有更快的插入、查找和删除操作。选择使用哪种容器取决于你的需求，包括是否需要有序存储元素以及对性能的要求。
头文件：
std::set：#include <set>std::multiset：#include <set>std::unordered_set：#include <unordered_set>std::unordered_multiset：#include <unordered_set>
