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进行快速地元素插入、查找、删除等操作，并且可以通过自定义哈希函数和桶迭代器进行更深层次的优化。