unordered_set用法詳解

一、unordered_set初探

unordered_set是C++ STL（標準模板庫）提供的一個容器，是一種集合（Set）容器的一種。它是一個存儲唯一且無序元素的容器，內部元素由哈希函數進行組織管理，因此可以快速地查找元素。

可以使用C++中的#include 來引用unordered_set, 任何支持哈希函數std::hash和比較運算符==的類型都可以用作unordered_set中元素的數據類型。默認情況下，unordered_set中元素按順序排列，不允許重複元素。

#include 
#include 

int main() {
    std::unordered_set myset = {1, 2, 3};
    for (int i : myset) {
        std::cout << i << " ";
    }
    return 0;
}

輸出：1 2 3

二、unordered_set的基本操作

1.插入元素

使用insert()函數向unordered_set中插入新的元素：

#include 
#include 

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

輸出：1 2 3 4 5

2.元素查找

可以使用count(key)函數來查找unordered_set中是否存在指定的元素，若存在返回1，否則為0。

#include 
#include 

int main() {
    std::unordered_set myset = {1, 2, 3};
    if (myset.count(2)) {
        std::cout << "2 is in myset." << std::endl;
    }
    if (myset.count(4)) {
        std::cout << "4 is in myset." << std::endl;
    }
    return 0;
}

輸出：2 is in myset.

3.元素刪除

可以使用erase(key)函數來刪除unordered_set中指定的元素，該函數返回一個指向被刪元素下一個元素的迭代器。

#include 
#include 

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

輸出：1 3

4.判斷是否為空

可使用empty()函數來判斷unordered_set是否為空。

#include 
#include 

int main() {
    std::unordered_set myset = {1, 2, 3};
    if (myset.empty()) {
        std::cout << "myset is empty." << std::endl;
    } else {
        std::cout << "myset is not empty." << std::endl;
    }
    return 0;
}

輸出：myset is not empty.

三、unordered_set的高級操作

1.初始容量和負載因子

unordered_set的初始容量和負載因子可以通過構造函數進行指定。初始容量指unordered_set在未插入元素前容器中最多可以容納多少元素，而負載因子則指元素數量達到容量的一定比例後unordered_set將進行重新哈希。一般情況下，初始容量和負載因子的默認值是8和1.0，可以根據需求進行設定。

#include 
#include 

int main() {
    std::unordered_set myset = {1, 2, 3};
    std::cout << "myset's size: " << myset.size() << std::endl;
    std::cout << "myset's bucket count: " << myset.bucket_count() << std::endl;
    std::cout << "myset's max bucket count: " << myset.max_bucket_count() << std::endl;
    std::cout << "myset's load factor: " << myset.load_factor() << std::endl;
    std::cout << "myset's max load factor: " << myset.max_load_factor() << std::endl;

    std::unordered_set yourset(10, 0.3);
    std::cout << "yourset's size: " << yourset.size() << std::endl;
    std::cout << "yourset's bucket count: " << yourset.bucket_count() << std::endl;
    std::cout << "yourset's max bucket count: " << yourset.max_bucket_count() << std::endl;
    std::cout << "yourset's load factor: " << yourset.load_factor() << std::endl;
    std::cout << "yourset's max load factor: " << yourset.max_load_factor() << std::endl;
    return 0;
}

輸出：

myset’s size: 3

myset’s bucket count: 8

myset’s max bucket count: 1152921504606846975

myset’s load factor: 0.375

myset’s max load factor: 1

yourset’s size: 0

yourset’s bucket count: 29

yourset’s max bucket count: 1152921504606846975

yourset’s load factor: 0

yourset’s max load factor: 0.3

2.哈希策略

unordered_set中元素的哈希策略可以使用模板參數指定，默認哈希策略是std::hash。

#include 
#include 
#include 

struct myclass {
    std::size_t operator()(const std::string& s) const {
        return std::hash()(s);
    }
};

int main() {
    std::unordered_set myset = {"apple", "banana", "orange"};
    for (const std::string& s : myset) {
        std::cout << s << " ";
    }
    return 0;
}

輸出：banana orange apple

3.桶迭代器和哈希策略

桶迭代器可以讓我們遍歷unordered_set中的所有桶，每個桶中包含多個元素，並且桶內元素的位置是沒有關係的，即我們無法預測某個元素在桶內的位置。通過桶迭代器我們可以自定義哈希策略，並調整桶的大小來達到更好的性能。

#include 
#include 
#include 
#include 

struct myclass {
    std::size_t operator()(const std::string& s) const {
        return std::hash()(s);
    }
};

int main() {
    std::unordered_set myset = {"apple", "banana", "orange", "pear", "watermelon", "pineapple"};
    std::vector bucketsizes;
    for (unsigned i = 0; i < myset.bucket_count(); ++i) {
        bucketsizes.push_back(myset.bucket_size(i));
    }
    std::sort(bucketsizes.begin(), bucketsizes.end());
    std::cout << "largest bucket size: " << bucketsizes.back() << std::endl;
    std::cout << "smallest bucket size: " << bucketsizes.front() << std::endl;
    return 0;
} 

輸出：

largest bucket size: 2

smallest bucket size: 1

四、unordered_set的時間複雜度

unordered_set的各種操作的平均時間複雜度為O(1)，最壞情況下為O(n)。

五、總結

unordered_set提供了快速存儲和查找唯一元素的容器，可以通過哈希函數、負載因子等方式進行優化。我們可以使用unordered_set進行快速地元素插入、查找、刪除等操作，並且可以通過自定義哈希函數和桶迭代器進行更深層次的優化。