跳转到内容

C++unordered set

来自代码酷

模板:Note

C++ unordered_set[编辑 | 编辑源代码]

unordered_set是C++标准模板库(STL)中提供的一种无序关联容器，它存储唯一元素（不允许重复值），并使用哈希表实现快速查找。与`std::set`不同，`unordered_set`中的元素不按特定顺序排列。

基本特性[编辑 | 编辑源代码]

  • 唯一性：每个元素在容器中必须是唯一的
  • 无序性：元素没有特定的排序顺序
  • 哈希实现：基于哈希表实现，平均情况下提供O(1)的查找复杂度
  • 动态大小：容器大小可动态变化
  • 不可修改元素：元素本身不可修改，但可以插入或删除

头文件与声明[编辑 | 编辑源代码]

使用`unordered_set`需要包含头文件： 

#include <unordered_set>

基本声明语法： 

std::unordered_set<DataType> name;

构造函数[编辑 | 编辑源代码]

`unordered_set`提供多种构造函数：

构造函数 描述
unordered_set() 默认构造函数，创建空容器
unordered_set(size_type n) 创建容器并预留n个桶
unordered_set(iterator first, iterator last) 用迭代器范围构造
unordered_set(const unordered_set& other) 拷贝构造函数

常用成员函数[编辑 | 编辑源代码]

容量相关[编辑 | 编辑源代码]

  • empty() - 检查容器是否为空
  • size() - 返回元素数量
  • max_size() - 返回可能的最大元素数量

元素访问[编辑 | 编辑源代码]

  • find(key) - 查找元素，返回迭代器
  • count(key) - 返回匹配元素的数量(0或1)

修改操作[编辑 | 编辑源代码]

  • insert(value) - 插入元素
  • erase(key/iterator) - 删除元素
  • clear() - 清空容器

桶操作[编辑 | 编辑源代码]

  • bucket_count() - 返回桶的数量
  • bucket_size(n) - 返回第n个桶中的元素数量
  • bucket(key) - 返回元素所在的桶

基本操作示例[编辑 | 编辑源代码]

创建与插入[编辑 | 编辑源代码]

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> numbers;
    
    // 插入元素
    numbers.insert(10);
    numbers.insert(20);
    numbers.insert(30);
    numbers.insert(20); // 重复元素不会被插入
    
    // 输出元素数量
    std::cout << "Size: " << numbers.size() << std::endl;
    
    return 0;
}

输出： 

Size: 3

查找元素[编辑 | 编辑源代码]

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<std::string> words = {"apple", "banana", "orange"};
    
    // 查找元素
    auto search = words.find("banana");
    if (search != words.end()) {
        std::cout << "Found: " << *search << std::endl;
    } else {
        std::cout << "Not found" << std::endl;
    }
    
    // 使用count检查存在性
    if (words.count("grape") > 0) {
        std::cout << "Grape exists" << std::endl;
    } else {
        std::cout << "Grape does not exist" << std::endl;
    }
    
    return 0;
}

输出： 

Found: banana
Grape does not exist

删除元素[编辑 | 编辑源代码]

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<char> letters = {'a', 'b', 'c', 'd', 'e'};
    
    // 通过值删除
    letters.erase('c');
    
    // 通过迭代器删除
    auto it = letters.find('d');
    if (it != letters.end()) {
        letters.erase(it);
    }
    
    // 输出剩余元素
    for (char ch : letters) {
        std::cout << ch << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

输出： 

e a b

哈希函数与自定义类型[编辑 | 编辑源代码]

默认情况下，`unordered_set`使用`std::hash`来计算元素的哈希值。对于自定义类型，需要提供哈希函数和相等比较函数。

自定义类型示例[编辑 | 编辑源代码]

#include <iostream>
#include <unordered_set>
#include <string>

struct Person {
    std::string name;
    int age;
    
    // 相等运算符重载
    bool operator==(const Person& other) const {
        return name == other.name && age == other.age;
    }
};

// 自定义哈希函数
struct PersonHash {
    std::size_t operator()(const Person& p) const {
        return std::hash<std::string>()(p.name) ^ std::hash<int>()(p.age);
    }
};

int main() {
    std::unordered_set<Person, PersonHash> people;
    
    people.insert({"Alice", 30});
    people.insert({"Bob", 25});
    people.insert({"Alice", 30}); // 重复，不会被插入
    
    std::cout << "Number of people: " << people.size() << std::endl;
    
    return 0;
}

输出： 

Number of people: 2

性能分析[编辑 | 编辑源代码]

`unordered_set`的平均时间复杂度如下：

操作 平均复杂度 最坏情况
插入 O(1) O(n)
删除 O(1) O(n)
查找 O(1) O(n)

性能受以下因素影响： 1. 哈希函数的质量 2. 桶的数量和负载因子 3. 元素的数量

负载因子与重新哈希[编辑 | 编辑源代码]

负载因子(load factor)是容器中元素数量与桶数量的比值：

解析失败 (语法错误): {\displaystyle \text{load factor} = \frac{\text{size}}{\text{bucket\_count}}}

可以通过以下函数管理负载因子：

  • load_factor() - 返回当前负载因子
  • max_load_factor() - 获取或设置最大负载因子
  • rehash(n) - 设置桶的数量为至少n
  • reserve(n) - 预留空间至少容纳n个元素

实际应用案例[编辑 | 编辑源代码]

单词去重[编辑 | 编辑源代码]

#include <iostream>
#include <unordered_set>
#include <vector>
#include <string>

std::vector<std::string> remove_duplicates(const std::vector<std::string>& words) {
    std::unordered_set<std::string> unique_words(words.begin(), words.end());
    return {unique_words.begin(), unique_words.end()};
}

int main() {
    std::vector<std::string> words = {"apple", "banana", "apple", "orange", "banana"};
    auto unique_words = remove_duplicates(words);
    
    std::cout << "Unique words:" << std::endl;
    for (const auto& word : unique_words) {
        std::cout << word << std::endl;
    }
    
    return 0;
}

输出： 

Unique words:
orange
banana
apple

图算法中的访问记录[编辑 | 编辑源代码]

在图的遍历算法中，`unordered_set`常用于记录已访问的节点： 

#include <iostream>
#include <unordered_set>
#include <vector>

void dfs(int node, const std::vector<std::vector<int>>& graph, 
         std::unordered_set<int>& visited) {
    if (visited.count(node)) return;
    
    visited.insert(node);
    std::cout << "Visiting node: " << node << std::endl;
    
    for (int neighbor : graph[node]) {
        dfs(neighbor, graph, visited);
    }
}

int main() {
    // 邻接表表示的图
    std::vector<std::vector<int>> graph = {
        {1, 2},    // 节点0的邻居
        {0, 3},    // 节点1的邻居
        {0},       // 节点2的邻居
        {1}        // 节点3的邻居
    };
    
    std::unordered_set<int> visited;
    dfs(0, graph, visited);
    
    return 0;
}

输出： 

Visiting node: 0
Visiting node: 1
Visiting node: 3
Visiting node: 2

unordered_set vs set[编辑 | 编辑源代码]

特性 unordered_set set
实现方式 哈希表 红黑树
元素顺序 无序 有序(默认升序)
查找复杂度 平均O(1)，最差O(n) O(log n)
内存使用 通常更多 通常更少
适用场景 快速查找，不关心顺序 需要有序元素或范围查询

最佳实践[编辑 | 编辑源代码]

1. 当需要快速查找且不关心元素顺序时，优先选择`unordered_set` 2. 对于自定义类型，确保提供良好的哈希函数 3. 预先使用`reserve()`分配足够空间可以提高性能 4. 监控负载因子，必要时进行重新哈希 5. 避免频繁的插入删除操作，这可能导致哈希表频繁重组

总结[编辑 | 编辑源代码]

`unordered_set`是C++ STL中一个强大的容器，提供了基于哈希表的快速查找能力。它特别适合需要高效查找、插入和删除唯一元素的场景。理解其内部工作原理和性能特性有助于在实际编程中做出更明智的选择。

检索自“https://wiki.echo.cool/index.php?title=C%2B%2Bunordered_set&oldid=574”