跳到主要内容

C++ 中的unordered_set容器

什么是unordered_set？​

unordered_set是C++11标准引入的一种关联容器，它存储唯一的元素，并允许通过元素值快速检索元素。与有序的set容器不同，unordered_set内部使用哈希表实现，因此：

  • 元素在容器中没有特定的顺序
  • 查找、插入和删除操作的平均时间复杂度为O(1)
  • 不允许存储重复元素
提示

unordered_set是需要频繁查找、插入和删除操作，且不关心元素顺序时的理想选择。

头文件和命名空间​

要使用unordered_set，需要包含相应的头文件：

#include <unordered_set>

// 该容器位于std命名空间中
using namespace std;  // 或者使用std::unordered_set

基本用法​

创建unordered_set​

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    // 创建空的unordered_set
    unordered_set<int> numbers;
    
    // 使用初始化列表创建
    unordered_set<string> fruits = {"apple", "banana", "orange"};
    
    // 使用迭代器范围创建
    int arr[] = {10, 20, 30, 40, 50};
    unordered_set<int> numSet(arr, arr + 5);
    
    // 使用拷贝构造函数
    unordered_set<string> fruitsCopy(fruits);
    
    return 0;
}

基本操作​

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    unordered_set<int> numbers;
    
    // 插入元素
    numbers.insert(10);
    numbers.insert(20);
    numbers.insert(30);
    numbers.insert(10);  // 重复元素不会被插入
    
    // 打印元素数量
    cout << "Size: " << numbers.size() << endl;  // 输出: Size: 3
    
    // 检查元素是否存在
    if (numbers.find(20) != numbers.end()) {
        cout << "20 exists in the set" << endl;
    }
    
    // 使用count函数检查元素（对于set，结果只会是0或1）
    cout << "30 count: " << numbers.count(30) << endl;  // 输出: 30 count: 1
    cout << "40 count: " << numbers.count(40) << endl;  // 输出: 40 count: 0
    
    // 删除元素
    numbers.erase(20);
    
    // 遍历元素
    cout << "Elements: ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;  // 输出可能是: Elements: 30 10 (顺序不确定)
    
    // 清空容器
    numbers.clear();
    cout << "After clear, size: " << numbers.size() << endl;  // 输出: After clear, size: 0
    
    return 0;
}

哈希函数和桶​

unordered_set使用哈希表实现，我们可以查看和控制其内部结构：

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    unordered_set<string> words = {"hello", "world", "programming", "c++", "container"};
    
    // 查看桶的数量
    cout << "Bucket count: " << words.bucket_count() << endl;
    
    // 查看负载因子
    cout << "Load factor: " << words.load_factor() << endl;
    
    // 查看每个桶中的元素数量
    cout << "Elements in buckets: " << endl;
    for (size_t i = 0; i < words.bucket_count(); ++i) {
        cout << "Bucket " << i << ": " << words.bucket_size(i) << " elements" << endl;
    }
    
    // 查看特定元素在哪个桶
    cout << "\"c++\" is in bucket: " << words.bucket("c++") << endl;
    
    // 手动调整桶的数量
    words.rehash(20);
    cout << "After rehash, bucket count: " << words.bucket_count() << endl;
    
    return 0;
}

输出示例（具体值可能会不同）：

Bucket count: 8
Load factor: 0.625
Elements in buckets: 
Bucket 0: 1 elements
Bucket 1: 1 elements
Bucket 2: 0 elements
Bucket 3: 1 elements
Bucket 4: 1 elements
Bucket 5: 0 elements
Bucket 6: 1 elements
Bucket 7: 0 elements
"c++" is in bucket: 4
After rehash, bucket count: 23

自定义类型作为元素​

要将自定义类型用作unordered_set中的元素，需要提供哈希函数和相等性比较函数：

#include <iostream>
#include <unordered_set>
#include <string>
using namespace std;

// 自定义类型
struct Person {
    string name;
    int age;
    
    // 相等性比较
    bool operator==(const Person& other) const {
        return name == other.name && age == other.age;
    }
};

// 为Person类型定义哈希函数
namespace std {
    template<>
    struct hash<Person> {
        size_t operator()(const Person& p) const {
            return hash<string>()(p.name) ^ hash<int>()(p.age);
        }
    };
}

int main() {
    unordered_set<Person> people;
    
    // 添加一些Person对象
    people.insert({"Alice", 25});
    people.insert({"Bob", 30});
    people.insert({"Charlie", 22});
    
    // 查找
    Person searchPerson = {"Bob", 30};
    if (people.find(searchPerson) != people.end()) {
        cout << "Found Bob, age 30" << endl;
    }
    
    // 遍历
    for (const auto& person : people) {
        cout << person.name << ", " << person.age << endl;
    }
    
    return 0;
}

性能特性​

unordered_set的特性和性能对比如下：

与set对比：

特性unordered_setset
实现方式哈希表红黑树
元素顺序无序有序
查找/插入/删除平均复杂度O(1)O(log n)
查找/插入/删除最坏复杂度O(n)O(log n)
内存占用较高适中
迭代器失效情况仅当删除元素时仅当删除元素时
警告

当哈希函数质量较差或数据分布不均匀时，unordered_set可能会退化为O(n)的性能表现。

实际应用场景​

1. 去重操作​

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

vector<int> removeDuplicates(const vector<int>& input) {
    unordered_set<int> uniqueElements(input.begin(), input.end());
    return vector<int>(uniqueElements.begin(), uniqueElements.end());
}

int main() {
    vector<int> numbers = {1, 4, 2, 4, 5, 1, 3, 5, 6};
    
    vector<int> uniqueNumbers = removeDuplicates(numbers);
    
    cout << "Original array: ";
    for (int num : numbers) cout << num << " ";
    cout << endl;
    
    cout << "After removing duplicates: ";
    for (int num : uniqueNumbers) cout << num << " ";
    cout << endl;
    
    return 0;
}

输出：

Original array: 1 4 2 4 5 1 3 5 6 
After removing duplicates: 6 5 4 3 2 1  // 顺序可能不同

2. 快速查找和记录已处理的元素​

#include <iostream>
#include <unordered_set>
#include <vector>
#include <string>
using namespace std;

bool isAllUnique(const string& str) {
    unordered_set<char> charSet;
    for (char c : str) {
        // 如果已经存在于集合中，则表示有重复
        if (charSet.find(c) != charSet.end()) {
            return false;
        }
        charSet.insert(c);
    }
    return true;
}

int main() {
    vector<string> testStrings = {
        "abcdefg",
        "hello",
        "programming",
        "unique"
    };
    
    for (const string& str : testStrings) {
        if (isAllUnique(str)) {
            cout << "\"" << str << "\" contains all unique characters." << endl;
        } else {
            cout << "\"" << str << "\" has duplicate characters." << endl;
        }
    }
    
    return 0;
}

输出：

"abcdefg" contains all unique characters.
"hello" has duplicate characters.
"programming" has duplicate characters.
"unique" contains all unique characters.

3. 统计集合交集​

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

int countCommonElements(const vector<int>& arr1, const vector<int>& arr2) {
    unordered_set<int> set(arr1.begin(), arr1.end());
    
    int count = 0;
    for (int num : arr2) {
        if (set.count(num) > 0) {
            count++;
            // 防止重复计数
            set.erase(num);
        }
    }
    
    return count;
}

int main() {
    vector<int> arr1 = {1, 2, 3, 4, 5, 8, 10};
    vector<int> arr2 = {5, 6, 7, 8, 9, 10, 11};
    
    int commonCount = countCommonElements(arr1, arr2);
    
    cout << "Array 1: ";
    for (int num : arr1) cout << num << " ";
    cout << endl;
    
    cout << "Array 2: ";
    for (int num : arr2) cout << num << " ";
    cout << endl;
    
    cout << "Number of common elements: " << commonCount << endl;
    
    return 0;
}

输出：

Array 1: 1 2 3 4 5 8 10 
Array 2: 5 6 7 8 9 10 11 
Number of common elements: 3

高级用法​

保留容量和负载因子​

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    // 预留空间
    unordered_set<int> numbers;
    numbers.reserve(1000);  // 预留1000个元素的空间
    
    // 设置最大负载因子
    numbers.max_load_factor(0.7f);  // 设置负载因子阈值为0.7
    
    // 获取当前负载因子
    cout << "Current load factor: " << numbers.load_factor() << endl;
    cout << "Max load factor: " << numbers.max_load_factor() << endl;
    
    return 0;
}

使用自定义哈希函数​

#include <iostream>
#include <unordered_set>
#include <functional>
using namespace std;

// 自定义哈希函数
struct CustomStringHash {
    size_t operator()(const string& str) const {
        // 一个简单的哈希函数
        size_t hash = 0;
        for (char c : str) {
            hash = hash * 31 + c;
        }
        return hash;
    }
};

int main() {
    // 使用自定义哈希函数创建unordered_set
    unordered_set<string, CustomStringHash> words;
    
    words.insert("hello");
    words.insert("world");
    words.insert("c++");
    
    cout << "Bucket count: " << words.bucket_count() << endl;
    
    for (const auto& word : words) {
        cout << word << " is in bucket " << words.bucket(word) << endl;
    }
    
    return 0;
}

常见操作复杂度​

操作时间复杂度（平均）时间复杂度（最坏）
插入元素O(1)O(n)
删除元素O(1)O(n)
查找元素O(1)O(n)
遍历容器O(n)O(n)
rehashO(n)O(n)

常见的问题与注意事项​

注意
  1. 迭代器失效：插入操作可能会导致rehash，使得所有迭代器都失效。
  2. 无序性：不要依赖元素顺序，因为它可能随时改变。
  3. 哈希冲突：大量哈希冲突会导致性能下降。
  4. 自定义类型：必须提供相等比较和哈希函数。

与其他容器的比较和选择​

  • 如果需要有序元素，使用set
  • 如果不需要有序但需要快速查找，使用unordered_set
  • 如果需要存储键值对，使用unordered_map
  • 如果不在意重复元素，可以考虑使用vector

总结​

unordered_set是C++11引入的一种基于哈希表的关联容器，其主要特点包括：

  1. 存储唯一的元素，不允许重复
  2. 元素无序存储
  3. 平均O(1)时间复杂度的查找、插入和删除操作
  4. 适用于需要频繁、快速查找的场景

在需要高效查找和去重的应用场景中，unordered_set是一个非常有用的容器。但同时需要注意，由于其基于哈希表实现，在极端情况下可能会有性能下降的问题。

练习题​

  1. 编写一个程序，统计一个字符串中出现的不同字符的数量。
  2. 使用unordered_set实现两个数组的交集操作。
  3. 创建一个函数，判断两个字符串是否是字母异位词（包含相同的字母，但顺序不同）。
  4. 设计一个简单的单词过滤器，过滤掉一组预定义的禁用词。
  5. 使用自定义类型作为unordered_set的元素，实现一个简单的学生记录系统。

延伸阅读​

  1. C++ Reference: std::unordered_set
  2. 哈希表的实现原理和常见哈希函数
  3. 比较unordered_set、set和multiset的异同
  4. 探索STL中其他的无序关联容器，如unordered_map、unordered_multiset等
  5. 泛型编程和迭代器在STL中的应用

通过掌握unordered_set容器，你可以更高效地解决涉及集合操作、去重和快速查找的编程问题。