【C++】关联存储结构容器-set(集合)详解

目录

一、基本概念

二、内部实现

三、常用操作

3.1 构造函数

3.2 插入操作

3.3 删除操作

3.4 查找操作

3.5 访问元素

3.6 容量操作

3.7 交换操作

四、特性

五、应用场景

结语

---

一、基本概念

set是C++标准模板库（STL）中的一种关联容器，它主要用于存储唯一且有序的元素。set容器不允许元素重复，并且会自动对元素进行排序。set的内部实现通常基于红黑树（一种自平衡二叉搜索树），这使得set的插入、删除和查找操作的时间复杂度都是O(log n)。

---

二、内部实现

set容器的内部实现基于红黑树，红黑树是一种自平衡的二叉搜索树，具有以下特性：

• 每个节点是红色或黑色。
• 根节点是黑色。
• 每个叶子节点（NIL节点，空节点）是黑色。
• 如果一个节点是红色的，则它的两个子节点都是黑色的。
• 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

这些特性确保了红黑树在插入和删除操作后能够重新平衡，从而保持树的高度在对数级别，进而保证了set容器的高效性。

---

三、常用操作

set容器提供了丰富的成员函数来支持各种操作。

---

3.1 构造函数

set容器提供了多种构造函数，可以根据实际需求选择合适的构造函数来创建set对象。常见的构造函数包括：

• 默认构造函数：创建一个空的set对象。

#include <iostream>
#include <set>int main() {std::set<int> emptySet; // 使用默认构造函数创建一个空的set对象// 输出set的大小以验证其为空std::cout << "Size of emptySet: " << emptySet.size() << std::endl; // 输出应为0return 0;
}

• 初始化列表构造函数：通过初始化列表来创建set对象，并初始化元素。

#include <iostream>
#include <set>int main() {std::set<int> initListSet = {1, 2, 3, 4, 5}; // 使用初始化列表构造函数创建并初始化set对象// 遍历并输出set中的元素for (int num : initListSet) {std::cout << num << " ";}std::cout << std::endl;return 0;
}

• 复制构造函数：创建一个新的set对象，它是现有set对象的副本。

#include <iostream>
#include <set>int main() {std::set<int> originalSet = {1, 2, 3}; // 原始set对象std::set<int> copySet(originalSet); // 使用复制构造函数创建新的set对象作为副本// 验证复制是否成功std::cout << "Original set: ";for (int num : originalSet) {std::cout << num << " ";}std::cout << std::endl;std::cout << "Copied set: ";for (int num : copySet) {std::cout << num << " ";}std::cout << std::endl;return 0;
}

• 迭代器范围构造函数：通过一个已有的迭代器范围（如另一个容器的子范围）来构造set对象。

#include <iostream>
#include <set>
#include <vector>int main() {std::vector<int> vec = {10, 20, 30, 40, 50}; // 原始vector容器std::set<int> iteratorRangeSet(vec.begin(), vec.end()); // 使用迭代器范围构造函数创建set对象// 遍历并输出set中的元素for (int num : iteratorRangeSet) {std::cout << num << " ";}std::cout << std::endl;return 0;
}

• 指定排序方式的构造函数：当构造自定义类型的容器时，可以指定一个自定义的比较函数来确定元素的排序方式。 

#include <iostream>
#include <set>
#include <string>// 自定义比较函数，用于按字符串长度排序
struct CompareByLength {bool operator()(const std::string& lhs, const std::string& rhs) const {return lhs.length() < rhs.length();}
};int main() {std::set<std::string, CompareByLength> customSortSet = {"apple", "banana", "cherry", "date"}; // 使用自定义比较函数创建set对象// 遍历并输出set中的元素for (const std::string& str : customSortSet) {std::cout << str << " ";}std::cout << std::endl;return 0;
}

---

3.2 插入操作

set容器提供了多种插入元素的方法。

• insert方法：插入单个元素或插入一个范围内的元素。如果插入的元素已经存在于set中，则插入操作会被忽略。

#include <iostream>
#include <set>int main() {std::set<int> mySet;// 插入单个元素auto result1 = mySet.insert(5);if (result1.second) {std::cout << "Inserted 5 successfully." << std::endl;} else {std::cout << "5 already exists in the set." << std::endl;}// 尝试插入已存在的元素auto result2 = mySet.insert(5);if (result2.second) {std::cout << "Inserted 5 successfully." << std::endl;} else {std::cout << "5 already exists in the set." << std::endl;}// 插入一个范围内的元素（例如，从数组）int arr[] = {1, 2, 3, 4, 5};mySet.insert(arr, arr + 5);// 打印 set 中的元素std::cout << "Elements in the set: ";for (const auto& elem : mySet) {std::cout << elem << " ";}std::cout << std::endl;return 0;
}

上述代码输出：

 

• emplace方法：直接在容器中构造元素，避免临时对象的创建和复制，性能更优。

#include <iostream>
#include <set>
#include <string>class Person {
public:std::string name;int age;Person(std::string name, int age){this->name = name;this->age = age;}// 需要定义 < 运算符，以便 set 可以对 Person 进行排序bool operator<(const Person& other) const {if (name != other.name) {return name < other.name;}return age < other.age;}
};int main() {std::set<Person> mySet;// 使用 emplace 插入单个元素mySet.emplace("Alice", 30);mySet.emplace("Bob", 25);// 尝试插入已存在的元素（根据我们的定义，name 和 age 都相同才算相同元素）auto result = mySet.emplace("Alice", 30);if (result.second) {std::cout << "Inserted Alice, 30 successfully." << std::endl;} else {std::cout << "Alice, 30 already exists in the set." << std::endl;}// 打印 set 中的元素std::cout << "Elements in the set: ";for (const auto& person : mySet) {std::cout << person.name << ", " << person.age << " ";}std::cout << std::endl;return 0;
}

上述代码输出：

 

---

3.3 删除操作

set容器提供了多种删除元素的方法。

• erase方法：删除指定元素、删除指定位置的元素或删除指定范围内的元素。

#include <iostream>
#include <set>int main() {// 创建一个set容器并添加一些元素std::set<int> mySet = {1, 2, 3, 4, 5};// 打印原始setstd::cout << "Original set: ";for (const auto& elem : mySet) {std::cout << elem << " ";}std::cout << std::endl;// 删除指定元素（例如，删除元素3）mySet.erase(3);std::cout << "After erasing element 3: ";for (const auto& elem : mySet) {std::cout << elem << " ";}std::cout << std::endl;// 插入元素以便演示删除指定位置的元素mySet.insert(3);mySet.insert(6);// 打印当前setstd::cout << "Current set before erasing position: ";for (const auto& elem : mySet) {std::cout << elem << " ";}std::cout << std::endl;// 删除指定位置的元素（例如，删除第一个元素，即1）auto it = mySet.begin();mySet.erase(it);std::cout << "After erasing first element: ";for (const auto& elem : mySet) {std::cout << elem << " ";}std::cout << std::endl;// 删除指定范围内的元素（例如，删除从3到5的元素）it = mySet.find(3); // 找到3的迭代器if (it != mySet.end()) {auto nextIt = std::next(it); // 指向下一个元素（4）的迭代器auto lastIt = mySet.find(5); // 找到5的迭代器，若不存在则返回end()if (lastIt != mySet.end()) {mySet.erase(nextIt, std::next(lastIt)); // 注意std::next(lastIt)是为了包含5但不越界} else {mySet.erase(nextIt, mySet.end()); // 若5不存在，删除从4到末尾的所有元素}}std::cout << "After erasing range [3, 5]: ";for (const auto& elem : mySet) {std::cout << elem << " ";}std::cout << std::endl;return 0;
}

上述代码输出：

 

• clear方法：清空set容器中的所有元素。

#include <iostream>
#include <set>int main() {// 创建一个set容器并添加一些元素std::set<int> mySet = {1, 2, 3, 4, 5};// 打印原始setstd::cout << "Original set: ";for (const auto& elem : mySet) {std::cout << elem << " ";}std::cout << std::endl;// 清空set容器中的所有元素mySet.clear();std::cout << "After clearing the set: ";if (mySet.empty()) {std::cout << "The set is empty.";} else {for (const auto& elem : mySet) {std::cout << elem << " ";}}std::cout << std::endl;return 0;
}

上述代码输出：

---

3.4 查找操作

set容器提供了高效的查找操作。

• find方法：查找指定元素的迭代器。如果找到该元素，则返回指向该元素的迭代器；否则返回end()迭代器。

#include <iostream>
#include <set>int main() {// 创建一个set容器并插入一些元素std::set<int> mySet = {1, 2, 3, 4, 5};// 使用find方法查找元素int valueToFind = 3;auto it = mySet.find(valueToFind);if (it != mySet.end()) {std::cout << "Found " << valueToFind << " at position: " << *it << std::endl;} else {std::cout << valueToFind << " not found in the set." << std::endl;}
}

• count方法：返回容器中给定值的数量（对于set容器，一般返回1或0）。

#include <iostream>
#include <set>int main() {// 创建一个set容器并插入一些元素std::set<int> mySet = {1, 2, 3, 4, 5};// 使用count方法计算元素数量std::cout << "Count of " << valueToFind << ": " << mySet.count(valueToFind) << std::endl;return 0;
}

• lower_bound和upper_bound方法：分别返回指向大于或等于给定元素的第一个元素的迭代器和指向大于给定元素的第一个元素的迭代器。

#include <iostream>
#include <set>int main() {// 创建一个set容器并插入一些元素std::set<int> mySet = {1, 2, 3, 4, 5};// 使用lower_bound和upper_bound方法int lowerBoundValue = 3;int upperBoundValue = 4;auto lowerIt = mySet.lower_bound(lowerBoundValue);auto upperIt = mySet.upper_bound(upperBoundValue);// -1代表未找到std::cout << "Lower bound of " << lowerBoundValue << ": " << (lowerIt != mySet.end() ? *lowerIt : -1) << std::endl;std::cout << "Upper bound of " << upperBoundValue << ": " << (upperIt != mySet.end() ? *upperIt : -1) << std::endl;return 0;
}

上述代码输出：

 

• equal_range方法：返回一个pair，表示给定元素在set容器中的范围（前闭后开）。

#include <iostream>
#include <set>int main() {// 创建一个set容器并插入一些元素std::set<int> mySet = {1, 2, 3, 4, 5};int valueToFind = 3;// 使用equal_range方法auto range = mySet.equal_range(valueToFind);// -1代表未找到std::cout << "Equal range of " << valueToFind << ": [" << (range.first != mySet.end() ? *range.first : -1) << ", " << (range.second != mySet.end() ? *range.second : -1) << ")" << std::endl;return 0;
}

上述代码输出： 

 

---

3.5 访问元素

set容器提供了通过迭代器和成员函数来访问元素的方法。由于set容器中的元素是唯一的且有序的，因此不能直接通过下标来访问元素。但可以通过迭代器来遍历set容器中的元素。在C++11 及更高版本中，也可以使用范围 for 循环来遍历 std::set 容器中的元素。

#include <iostream>
#include <set>int main() {// 创建一个 std::set 容器，并插入一些整数元素std::set<int> mySet = {1, 3, 5, 7, 9, 2, 4, 6, 8, 0};// 使用迭代器来遍历 std::set 容器中的元素for (std::set<int>::iterator it = mySet.begin(); it != mySet.end(); ++it) {std::cout << *it << " ";}std::cout << std::endl;// 也可以使用范围 for 循环来遍历 std::set 容器中的元素（C++11 及更高版本）for (int elem : mySet) {std::cout << elem << " ";}std::cout << std::endl;return 0;
}

---

3.6 容量操作

set容器提供了一些容量相关的操作来管理和查询容器的大小。

• empty方法：判断容器是否为空。

#include <iostream>
#include <set>int main() {// 创建一个空的 std::set 容器std::set<int> mySet;// 使用 empty 方法判断容器是否为空if (mySet.empty()) {std::cout << "The set is empty." << std::endl;} else {std::cout << "The set is not empty." << std::endl;}return 0;
}

• size方法：返回容器当前元素的数量。

#include <iostream>
#include <set>int main() {// 创建一个空的 std::set 容器std::set<int> mySet;// 向 set 容器中添加一些元素mySet.insert(1);mySet.insert(2);mySet.insert(3);// 使用 size 方法返回容器当前元素的数量std::cout << "The set has " << mySet.size() << " elements." << std::endl;return 0;
}

• max_size方法：返回set容器能够容纳元素的最大值（虽然set容器没有容量的概念，但这个方法可以返回一个理论上的最大值）。

#include <iostream>
#include <set>int main() {// 创建一个空的 std::set 容器std::set<int> mySet;// 使用 max_size 方法返回 set 容器能够容纳元素的最大值// 注意：这个值通常非常大，表示理论上可以容纳的元素数量，而不是实际容量限制std::cout << "The maximum number of elements the set can hold is " << mySet.max_size() << "." << std::endl;return 0;
}

上述代码输出：

3.7 交换操作

set容器提供了swap方法来交换两个set容器的内容。

#include <iostream>
#include <set>int main() {// 创建两个 std::set 容器，并插入一些元素std::set<int> set1 = {1, 2, 3, 4, 5};std::set<int> set2 = {6, 7, 8, 9, 10};// 打印交换前的容器内容std::cout << "Before swap:" << std::endl;std::cout << "set1: ";for (int elem : set1) {std::cout << elem << " ";}std::cout << std::endl;std::cout << "set2: ";for (int elem : set2) {std::cout << elem << " ";}std::cout << std::endl;// 使用 swap 方法交换两个容器的内容set1.swap(set2);// 打印交换后的容器内容std::cout << "After swap:" << std::endl;std::cout << "set1: ";for (int elem : set1) {std::cout << elem << " ";}std::cout << std::endl;std::cout << "set2: ";for (int elem : set2) {std::cout << elem << " ";}std::cout << std::endl;return 0;
}

上述代码输出：

 

---

四、特性

1. 自动排序：set容器中的元素会自动根据其值进行排序。你不需要像使用数组或链表那样手动排序。

2. 唯一性：set容器只存储唯一的元素，这样可以确保数据的一致性，不会出现重复的数据。

3. 高效的查找操作：由于set实现为红黑树，其查找、插入和删除操作的平均时间复杂度为O(log n)。

4. 标准容器：set是C++标准库的一部分，因此与其它标准库组件有良好的兼容性。

5. 值的不可变性：一旦将一个元素插入到set中，你就不能更改该元素的值（尽管可以通过删除旧元素并插入新元素来间接实现更改）。

6. 内存使用：由于set需要为每个元素分配内存并维护一棵红黑树，所以它的内存使用可能会比其它容器（如数组或向量）更高。

7. 迭代器的稳定性：set的迭代器在删除元素后可能会失效。如果你在迭代过程中删除元素，可能会导致未定义的行为。为了安全地删除元素，你可以先保存要删除元素的迭代器，然后在迭代完成后再进行删除。

---

五、应用场景

1. 去重：set容器自动去重的特性使其成为处理去重问题的理想选择。

2. 集合运算：set支持并集、交集和差集等集合运算，适用于需要进行集合操作的场景。

3. 有序存储：set中的元素自动按顺序排列，适合需要有序存储的场景。

4. 查找：set的查找操作时间复杂度为O(log n)，适用于需要快速查找的场景。

结语

在C++的标准模板库（STL）中，set容器作为一种关联存储结构，以其独特的性质和高效的性能，在数据管理和处理中扮演着重要角色。通过本文深入学习和掌握set容器的使用方法和技巧，程序员可以更好地应对各种复杂的编程挑战，提升编程能力和水平。希望本文的介绍能够对你理解和使用set容器有所帮助。

如需更多信息，建议查阅C++参考手册中的set： 

https://cppreference.cn/w/cpp/container/set