快捷導(dǎo)航

C++中unordered_set哈希集合的實現(xiàn)

更新時間：2025年11月11日 11:16:55 作者：MzKyle

std::unordered_set是C++標(biāo)準(zhǔn)庫中的無序關(guān)聯(lián)容器,基于哈希表實現(xiàn),具有元素唯一性和無序性特點,本文就來詳細(xì)的介紹一下unordered_set的使用,感興趣的可以了解一下

一、概述

std::unordered_set 是 C++ 標(biāo)準(zhǔn)庫（C++11 引入）中的無序容器，用于存儲唯一的元素（無重復(fù)值），底層基于哈希表（哈希桶） 實現(xiàn)。與 std::set（基于紅黑樹，元素有序）相比，它的核心特點是：

無序性：元素存儲順序與插入順序無關(guān)，不支持按Key排序訪問；
高效性：平均情況下，插入、刪除、查找操作的時間復(fù)雜度為 O(1)（最壞情況為 O(n)，取決于哈希函數(shù)質(zhì)量）；
唯一性：容器中不會存儲重復(fù)元素，插入重復(fù)值會被忽略。

二、頭文件與命名空間

使用 std::unordered_set 需包含頭文件 <unordered_set>，并位于 std 命名空間中：

#include <unordered_set>
using namespace std; // 或顯式使用 std::unordered_set

三、常用方法與示例

1. 構(gòu)造與析構(gòu)

std::unordered_set 提供多種構(gòu)造方式，滿足不同初始化需求：

方法	說明
unordered_set()	默認(rèn)構(gòu)造：創(chuàng)建空容器
unordered_set(initializer_list<T> init)	初始化列表構(gòu)造：用 {a, b, c} 初始化
unordered_set(InputIt first, InputIt last)	范圍構(gòu)造：用迭代器范圍 [first, last) 初始化
unordered_set(const unordered_set& other)	拷貝構(gòu)造

示例：

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

int main() {
    // 1. 默認(rèn)構(gòu)造
    unordered_set<int> us1;

    // 2. 初始化列表構(gòu)造
    unordered_set<int> us2 = {1, 2, 3, 4};

    // 3. 范圍構(gòu)造（從vector初始化）
    vector<int> vec = {5, 6, 7};
    unordered_set<int> us3(vec.begin(), vec.end());

    // 4. 拷貝構(gòu)造
    unordered_set<int> us4(us2);

    return 0;
}

2. 迭代器與遍歷

std::unordered_set 提供迭代器用于遍歷元素，由于無序性，遍歷順序與插入順序無關(guān)。

方法	說明
begin() / cbegin()	返回指向首元素的迭代器（cbegin() 為 const 版本）
end() / cend()	返回指向尾后位置的迭代器

示例：

unordered_set<int> us = {3, 1, 4, 1, 5}; // 重復(fù)的1會被自動去重
// 遍歷元素（順序不確定）
for (auto it = us.begin(); it != us.end(); ++it) {
    cout << *it << " "; // 可能輸出：3 1 4 5 
}
cout << endl;

// C++11 范圍for循環(huán)（更簡潔）
for (int val : us) {
    cout << val << " "; // 輸出順序與上相同（同一次運行中）
}

3. 容量相關(guān)

用于判斷容器狀態(tài)或獲取元素數(shù)量：

方法	說明
empty()	判斷容器是否為空（空返回 true）
size()	返回當(dāng)前元素個數(shù)
max_size()	返回容器理論上可存儲的最大元素個數(shù)（受系統(tǒng)限制）

示例：

unordered_set<string> us = {"apple", "banana"};
cout << "是否為空：" << (us.empty() ? "是" : "否") << endl; // 輸出：否
cout << "元素個數(shù)：" << us.size() << endl; // 輸出：2
cout << "最大容量：" << us.max_size() << endl; // 輸出：約1e18（取決于系統(tǒng)）

4. 元素修改（插入、刪除、清空）

這是 std::unordered_set 最核心的操作，用于維護(hù)容器中的元素。

方法	說明
insert(val)	插入元素 val，若已存在則忽略；返回 pair<iterator, bool>（迭代器指向元素，bool 表示是否插入成功）
insert(first, last)	插入迭代器范圍 [first, last) 中的元素
erase(val)	刪除值為 val 的元素，返回刪除的個數(shù)（0 或 1）
erase(it)	刪除迭代器 it 指向的元素，返回下一個元素的迭代器
clear()	清空所有元素
swap(other)	交換當(dāng)前容器與 other 的內(nèi)容

示例：

unordered_set<int> us;

// 插入元素
auto res1 = us.insert(10); 
cout << "插入10：" << (res1.second ? "成功" : "失敗") << endl; // 成功

auto res2 = us.insert(10); // 插入重復(fù)值
cout << "再次插入10：" << (res2.second ? "成功" : "失敗") << endl; // 失敗

// 插入多個元素
us.insert({20, 30, 40});

// 刪除元素（按值）
int del_count = us.erase(20);
cout << "刪除20的個數(shù)：" << del_count << endl; // 1

// 刪除元素（按迭代器）
auto it = us.find(30); // 先查找元素
if (it != us.end()) {
    us.erase(it); // 刪除30
}

// 清空容器
us.clear();
cout << "清空后大?。? << us.size() << endl; // 0

5. 元素查找

用于判斷元素是否存在或獲取元素位置：

方法	說明
find(val)	查找值為 val 的元素，返回指向該元素的迭代器；若不存在，返回 end()
count(val)	返回值為 val 的元素個數(shù)（0 或 1，因元素唯一）
contains(val)	C++20 新增，判斷元素 val 是否存在（返回 bool），比 count() 更直觀

示例：

unordered_set<string> fruits = {"apple", "banana", "cherry"};

// 查找元素
auto it = fruits.find("banana");
if (it != fruits.end()) {
    cout << "找到：" << *it << endl; // 找到：banana
} else {
    cout << "未找到" << endl;
}

// 計數(shù)（判斷存在性）
if (fruits.count("orange") == 1) {
    cout << "存在orange" << endl;
} else {
    cout << "不存在orange" << endl; // 輸出此句
}

// C++20 contains
if (fruits.contains("apple")) {
    cout << "存在apple" << endl; // 輸出此句
}

6. 哈希策略相關(guān)

std::unordered_set 底層依賴哈希表，以下方法用于控制哈希表的性能：

方法	說明
load_factor()	返回當(dāng)前負(fù)載因子（元素數(shù) / 桶數(shù)），反映哈希表的擁擠程度
max_load_factor()	返回或設(shè)置最大負(fù)載因子（默認(rèn)值通常為 1.0）。當(dāng)實際負(fù)載因子超過此值時，哈希表會自動擴(kuò)容（重哈希）
rehash(n)	強(qiáng)制將桶數(shù)設(shè)置為至少 n，可能觸發(fā)重哈希
reserve(n)	預(yù)分配空間，確保容器可容納 n 個元素而無需重哈希（比 rehash() 更常用）

示例：

unordered_set<int> us;

// 預(yù)分配空間（避免頻繁重哈希）
us.reserve(1000); // 確?？扇菁{1000個元素

// 插入元素
for (int i = 0; i < 500; ++i) {
    us.insert(i);
}

cout << "當(dāng)前負(fù)載因子：" << us.load_factor() << endl; // ~0.5（500/1000）
cout << "最大負(fù)載因子：" << us.max_load_factor() << endl; // 1.0

// 修改最大負(fù)載因子
us.max_load_factor(0.8);
cout << "修改后最大負(fù)載因子：" << us.max_load_factor() << endl; // 0.8

四、自定義類型的使用

std::unordered_set 存儲自定義類型（如結(jié)構(gòu)體）時，需滿足兩個條件：

提供哈希函數(shù)：告訴容器如何計算元素的哈希值；
提供相等比較函數(shù)：用于解決哈希碰撞（不同元素可能有相同哈希值）。

示例：存儲自定義 Person 結(jié)構(gòu)體

#include <string>

struct Person {
    string name;
    int age;

    // 定義相等比較（用于解決哈希碰撞）
    bool operator==(const Person& other) const {
        return name == other.name && age == other.age;
    }
};

// 特化 std::hash 用于 Person（提供哈希函數(shù)）
namespace std {
    template<> struct hash<Person> {
        size_t operator()(const Person& p) const {
            // 組合 name 和 age 的哈希值（簡單實現(xiàn)）
            size_t h1 = hash<string>()(p.name);
            size_t h2 = hash<int>()(p.age);
            return h1 ^ (h2 << 1); // 哈希組合
        }
    };
}

int main() {
    unordered_set<Person> people;
    people.insert({"Alice", 25});
    people.insert({"Bob", 30});

    // 查找
    Person target = {"Alice", 25};
    if (people.contains(target)) {
        cout << "找到 Alice" << endl;
    }
    return 0;
}

五、與 std::set 的對比

特性	std::unordered_set	std::set
底層實現(xiàn)	哈希表	紅黑樹（平衡二叉樹）
元素順序	無序	有序（默認(rèn)升序）
插入/刪除/查找復(fù)雜度	平均 O(1)，最壞 O(n)	O(log n)
內(nèi)存占用	較高（哈希表需額外空間）	較低
適用場景	頻繁查找、不關(guān)心順序	需要有序遍歷、范圍查詢（如 lower_bound）

六、注意事項

哈希函數(shù)質(zhì)量：差的哈希函數(shù)會導(dǎo)致大量碰撞，使性能退化到 O(n)，需確保哈希值分布均勻；
元素不可修改：std::unordered_set 的元素是 const 類型（修改會破壞哈希表結(jié)構(gòu)），若需修改，需先刪除再插入；
重哈希開銷：當(dāng)負(fù)載因子超過閾值時，容器會自動重哈希（重建哈希表），可能導(dǎo)致性能波動，可通過 reserve() 提前分配空間避免；
自定義類型要求：必須提供哈希函數(shù)和相等比較函數(shù)，否則編譯報錯。

到此這篇關(guān)于C++中unordered_set哈希集合的實現(xiàn)的文章就介紹到這了,更多相關(guān)C++ unordered_set哈希集合內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: