C++标准模板库中的无序集

C++标准模板库(STL)是C++语言的标准库之一，其中包括了大量的容器，算法和函数对象等组件。其中最常用的容器之一就是无序集(unordered_set)。无序集是一个存储唯一元素的容器，不同于有序集合(set)的是，内部元素的顺序是不固定的。

无序集基本用法

无序集的基本用法与其他STL容器类型非常类似，使用无序集需要包含头文件，然后使用命名空间std即可。

以下是无序集的基本定义和初始化示例代码：

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> mySet = {1, 2, 3, 4, 5};
    for (auto i: mySet) {
        std::cout << i << " ";
    }
    return 0;
}

上述代码定义并初始化了一个无序集mySet，包含了五个整数。然后使用range-based for循环对整个无序集进行遍历，输出每个元素的值。

无序集中的元素是唯一的，因此如果添加重复元素，无序集内部会自动去重，只保存一个元素。

以下是添加重复元素的示例代码：

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> mySet = {1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 5};
    for (auto i: mySet) {
        std::cout << i << " ";
    }
    return 0;
}

上述代码定义并初始化了一个无序集mySet，包含了多个重复的整数。然后使用range-based for循环对整个无序集进行遍历，输出每个元素的值。由于重复元素被自动去重，输出结果中只包含了五个元素。

无序集的常用操作

无序集的操作与其他STL容器操作类似，包括插入，查找，删除等。下面是无序集常用操作的示例代码：

插入元素

使用insert()函数可以向无序集中插入元素。例如以下代码可以向无序集mySet中插入元素6和7：

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> mySet = {1, 2, 3, 4, 5};
    mySet.insert(6);
    mySet.insert(7);
    for (auto i: mySet) {
        std::cout << i << " ";
    }
    return 0;
}

删除元素

使用erase()函数可以从无序集中删除元素。例如以下代码使用erase()函数删除元素3：

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> mySet = {1, 2, 3, 4, 5};
    mySet.erase(3);
    for (auto i: mySet) {
        std::cout << i << " ";
    }
    return 0;
}

查找元素

可以使用find()函数查找无序集中的元素，如果元素存在则返回指向该元素的迭代器，否则返回end()迭代器。例如以下代码使用find()函数查找元素4：

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> mySet = {1, 2, 3, 4, 5};
    auto it = mySet.find(4);
    if (it != mySet.end()) {
        std::cout << "Element found: " << *it << std::endl;
    } else {
        std::cout << "Element not found" << std::endl;
    }
    return 0;
}

元素个数

可以使用size()函数获取无序集中的元素个数，例如以下代码输出无序集mySet中的元素个数：

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> mySet = {1, 2, 3, 4, 5};
    std::cout << "mySet size: " << mySet.size() << std::endl;
    return 0;
}

清空元素

可以使用clear()函数清空无序集中的所有元素，例如以下代码清空无序集mySet中的所有元素：

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> mySet = {1, 2, 3, 4, 5};
    mySet.clear();
    std::cout << "mySet size after clearing: " << mySet.size() << std::endl;
    return 0;
}

无序集的哈希函数

无序集(hash)的底层实现是使用哈希表(hash table)，因此必须存在一种哈希函数来将元素映射到哈希表中。C++标准模板库中默认提供了一些哈希函数，可以直接用于自定义类型，也可以自己定义哈希函数。

如果需要使用自定义类型，例如自定义类Person，需要重载哈希函数。以下是重载Person类哈希函数的示例代码：

#include <iostream>
#include <unordered_set>

class Person {
    public:
        std::string name;
        int age;
    public:
        Person(std::string n, int a): name(n), age(a) {}
        bool operator==(const Person& p) const {
            return name == p.name && age == p.age; 
        }
};

namespace std {
    template <> struct hash<Person> {
        size_t operator()(const Person& p) const {
            return hash<std::string>()(p.name) ^ hash<int>()(p.age); 
        }
    };
}

int main() {
    std::unordered_set<Person> mySet = {{"Tom", 28}, {"Alice", 25}, {"Bob", 30}};
    for (auto p: mySet) {
        std::cout << p.name << ", " << p.age << std::endl;
    }
    return 0;
}

上述代码定义了一个Person类，包含了名字(name)和年龄(age)两个成员变量。然后使用std命名空间下的hash模板类重载了哈希函数，将Person对象映射到哈希表中。最后定义了一个无序集mySet，用于存储Person对象并输出信息。