一篇文章让你熟悉unordered_set及其模拟实现（上）-阿里云开发者社区

unordered_set的定义

unordered_set 是 C++ 标准库中的一个容器，用于存储唯一的元素，而且不按照任何特定的顺序来组织这些元素。它是基于哈希表实现的，因此可以在平均情况下提供常数时间的插入、删除和查找操作。

以下是使用 unordered_set 定义的基本示例：

#include <iostream>
#include <unordered_set>
int main() {
    // 创建一个unordered_set
    std::unordered_set<int> mySet;
    // 向unordered_set中插入元素
    mySet.insert(5);
    mySet.insert(2);
    mySet.insert(8);
    // 查找元素
    if (mySet.find(2) != mySet.end()) {
        std::cout << "元素 2 存在于unordered_set中" << std::endl;
    }
    // 遍历unordered_set中的元素
    for (const int& value : mySet) {
        std::cout << value << " ";
    }
    std::cout << std::endl;
    return 0;
}

unordered_set 提供了一种高效的方法来存储和检索不重复的值，但不保留它们的顺序。因此，如果你需要按顺序存储元素，可以考虑使用 std::set 或其他有序容器。

1. unordered_set的模板定义

template < class Key,                        // unordered_set::key_type/value_type
           class Hash = hash<Key>,           // unordered_set::hasher
           class Pred = equal_to<Key>,       // unordered_set::key_equal
           class Alloc = allocator<Key>      // unordered_set::allocator_type
           > class unordered_set;

Key（键/值类型）：这是在 unordered_set 中存储的元素类型。例如，如果您想要创建一个存储整数的 unordered_set，则将 Key 设置为 int。
Hash（哈希函数类型）：这是用于计算元素哈希值的函数对象类型。默认情况下，它是 std::hash<Key>，它提供了针对大多数内置类型的哈希函数。您也可以提供自定义的哈希函数。
Pred（键比较函数类型）：这是用于比较元素的函数对象类型。默认情况下，它是 std::equal_to<Key>，它执行标准的等于比较操作。您可以提供自定义的比较函数，以根据自己的需求确定元素是否相等。
Alloc（分配器类型）：这是用于分配和释放内存的分配器类型。默认情况下，它是 std::allocator<Key>，用于标准内存管理。您通常只需要在特殊情况下自定义分配器。

2. unordered_set的成员类型

以下别名是unordered_set的成员类型。它们被成员函数广泛用作参数和返回类型

unordered_set构造函数

empty (1) 
explicit unordered_set ( size_type n = /* see below */,
                         const hasher& hf = hasher(),
                         const key_equal& eql = key_equal(),
                         const allocator_type& alloc = allocator_type() );
explicit unordered_set ( const allocator_type& alloc );
range (2) 
template <class InputIterator>
         unordered_set ( InputIterator first, InputIterator last,
                         size_type n = /* see below */,
                         const hasher& hf = hasher(),
                         const key_equal& eql = key_equal(),
                         const allocator_type& alloc = allocator_type() );
copy (3)  
unordered_set ( const unordered_set& ust );
unordered_set ( const unordered_set& ust, const allocator_type& alloc );
move (4)  
unordered_set ( unordered_set&& ust );
unordered_set ( unordered_set&& ust, const allocator_type& alloc );
initializer list (5)  
unordered_set ( initializer_list<value_type> il,
                size_type n = /* see below */,
                const hasher& hf = hasher(),
                const key_equal& eql = key_equal(),
                const allocator_type& alloc = allocator_type() );

explicit unordered_set(size_type n = /* see below */, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& alloc = allocator_type());

创建一个空的 unordered_set。
n：哈希表的初始桶数。
hf：哈希函数。
eql：键的比较函数。
alloc：分配器。

template <class InputIterator> unordered_set(InputIterator first, InputIterator last, size_type n = /* see below */, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& alloc = allocator_type());

用迭代器范围 [first, last) 中的元素创建 unordered_set。
n：哈希表的初始桶数。
hf：哈希函数。
eql：键的比较函数。
alloc：分配器。

unordered_set(const unordered_set& ust);

用另一个 unordered_set 的副本创建一个新的 unordered_set。

unordered_set(unordered_set&& ust);

移动构造函数，使用另一个 unordered_set 的内容创建一个新的 unordered_set，并且源 unordered_set 不再包含这些元素。

unordered_set(initializer_list<value_type> il, size_type n = /* see below */, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& alloc = allocator_type());

使用初始化列表 il 创建 unordered_set。
n：哈希表的初始桶数。
hf：哈希函数。
eql：键的比较函数。
alloc：分配器。

以下是一些使用不同构造函数创建和初始化 std::unordered_set 的示例：

#include <iostream>
#include <unordered_set>
int main() {
    // 示例 1: 使用默认构造函数创建一个空的 unordered_set
    std::unordered_set<int> mySet1;
    // 示例 2: 使用迭代器范围初始化 unordered_set
    std::unordered_set<int> mySet2({1, 2, 3, 4, 5}); // 初始化列表
    std::unordered_set<int> mySet3(mySet2.begin(), mySet2.end()); // 从另一个集合复制
    // 示例 3: 使用复制构造函数创建一个新的 unordered_set
    std::unordered_set<int> mySet4(mySet3);
    // 示例 4: 使用移动构造函数创建一个新的 unordered_set
    std::unordered_set<int> mySet5(std::move(mySet4));
    // 示例 5: 使用初始化列表和自定义哈希函数
    std::unordered_set<std::string> mySet6({"apple", "banana", "cherry"}, 10, std::hash<std::string>(), std::equal_to<std::string>());
    // 遍历并打印 unordered_set 中的元素
    for (const int& value : mySet3) {
        std::cout << value << " ";
    }
    std::cout << std::endl;
    for (const std::string& fruit : mySet6) {
        std::cout << fruit << " ";
    }
    std::cout << std::endl;
    return 0;
}

这个示例演示了如何使用不同的构造函数来创建和初始化 std::unordered_set，包括使用默认构造函数、迭代器范围、复制构造函数、移动构造函数和初始化列表。还演示了如何自定义哈希函数和比较函数。

unordered_set赋值运算符重载

copy (1)  
unordered_set& operator= ( const unordered_set& ust );
move (2)  
unordered_set& operator= ( unordered_set&& ust );
initializer list (3)  
unordered_set& operator= ( intitializer_list<value_type> il );

这是关于 std::unordered_set 的不同赋值运算符重载：

unordered_set& operator= ( const unordered_set& ust );

复制赋值运算符。用另一个 unordered_set 的内容替换当前的 unordered_set 内容。

unordered_set& operator= ( unordered_set&& ust );

移动赋值运算符。使用另一个 unordered_set 的内容来替换当前的 unordered_set 内容，并且源 unordered_set 不再包含这些元素。

unordered_set& operator= ( initializer_list<value_type> il );

初始化列表赋值运算符。用初始化列表中的元素来替换当前 unordered_set 的内容。

这些赋值运算符允许您以不同的方式将元素从一个 std::unordered_set 赋值给另一个，包括复制、移动和使用初始化列表。这有助于管理和更新 unordered_set 的内容。

以下是使用不同类型的赋值运算符重载的示例：

#include <iostream>
#include <unordered_set>
int main() {
    // 示例 1: 复制赋值运算符
    std::unordered_set<int> set1 = {1, 2, 3};
    std::unordered_set<int> set2;
    set2 = set1; // 复制 set1 到 set2
    std::cout << "set2 after copy assignment: ";
    for (const int& value : set2) {
        std::cout << value << " ";
    }
    std::cout << std::endl;
    // 示例 2: 移动赋值运算符
    std::unordered_set<std::string> set3 = {"apple", "banana", "cherry"};
    std::unordered_set<std::string> set4;
    set4 = std::move(set3); // 移动 set3 到 set4
    std::cout << "set3 after move assignment: ";
    for (const std::string& fruit : set3) {
        std::cout << fruit << " "; // set3 不再包含元素
    }
    std::cout << std::endl;
    std::cout << "set4 after move assignment: ";
    for (const std::string& fruit : set4) {
        std::cout << fruit << " "; // set4 包含被移动的元素
    }
    std::cout << std::endl;
    // 示例 3: 初始化列表赋值运算符
    std::unordered_set<char> set5;
    set5 = {'a', 'b', 'c'}; // 使用初始化列表赋值
    std::cout << "set5 after initializer list assignment: ";
    for (const char& letter : set5) {
        std::cout << letter << " ";
    }
    std::cout << std::endl;
    return 0;
}

这个示例演示了不同类型的赋值运算符重载的用法，包括复制、移动和使用初始化列表赋值。注意，移动赋值后源 unordered_set 不再包含元素。

unordered_set容量函数（Capacity）

bool empty() const noexcept;

这个函数返回一个布尔值，指示集合是否为空。如果集合为空，它将返回 true；否则，返回 false。
const noexcept 表示这是一个不会抛出异常的常量成员函数。

size_type size() const noexcept;

这个函数返回集合中元素的数量，也就是集合的大小。
const noexcept 表示这是一个不会抛出异常的常量成员函数。
返回的类型 size_type 是一个无符号整数类型，通常是 std::size_t。

size_type max_size() const noexcept;

这个函数返回集合可能包含的最大元素数量。
const noexcept 表示这是一个不会抛出异常的常量成员函数。
返回的类型 size_type 是一个无符号整数类型，通常是 std::size_t。

这些函数允许您在使用 std::unordered_set 时查询集合的状态，例如检查是否为空、获取集合的大小以及了解集合可能包含的最大元素数量。由于它们都是常量成员函数并且不会抛出异常，因此可以在安全的情况下调用它们。

以下是使用 std::unordered_set 的成员函数 empty(), size(), 和 max_size() 的示例：

#include <iostream>
#include <unordered_set>
int main() {
    std::unordered_set<int> mySet;
    // 检查集合是否为空
    if (mySet.empty()) {
        std::cout << "集合为空" << std::endl;
    } else {
        std::cout << "集合不为空" << std::endl;
    }
    // 添加元素到集合
    mySet.insert(1);
    mySet.insert(2);
    mySet.insert(3);
    // 获取集合的大小
    std::cout << "集合的大小为: " << mySet.size() << std::endl;
    // 获取集合可能包含的最大元素数量
    std::cout << "集合可能包含的最大元素数量为: " << mySet.max_size() << std::endl;
    return 0;
}

这个示例演示了如何使用 empty() 函数来检查集合是否为空，使用 size() 函数来获取集合的大小，以及使用 max_size() 函数来获取集合可能包含的最大元素数量。根据示例中的操作，程序将输出相应的信息。

unordered_set迭代器（Iterators）

1. begin()

container iterator (1)  
      iterator begin() noexcept;
    const_iterator begin() const noexcept;
bucket iterator (2) 
      local_iterator begin ( size_type n );
    const_local_iterator begin ( size_type n ) const;

iterator begin() noexcept;

非常量版本的 begin() 函数返回指向集合中第一个元素的迭代器。您可以使用这个迭代器来遍历集合的元素。
const noexcept 表示这是一个不会抛出异常的非常量成员函数。

const_iterator begin() const noexcept;

常量版本的 begin() 函数返回指向集合中第一个元素的常量迭代器。这个常量迭代器只允许读取元素，不能修改它们。
const noexcept 表示这是一个不会抛出异常的常量成员函数。

local_iterator begin(size_type n);

这个函数用于获取指向桶 n 中第一个局部元素的迭代器。在哈希表中，元素被分布到不同的桶中，local_iterator 允许您在特定桶中遍历元素。
size_type n 参数指定桶的索引。

const_local_iterator begin(size_type n) const;

这是常量版本的 begin(size_type n) 函数，返回指向桶 n 中第一个局部元素的常量迭代器。

2. end()

container iterator (1)  
      iterator end() noexcept;
    const_iterator end() const noexcept;
bucket iterator (2) 
      local_iterator end (size_type n);
    const_local_iterator end (size_type n) const;

iterator end() noexcept;

非常量版本的 end() 函数返回指向集合末尾的迭代器。它通常用于与 begin() 配合来遍历整个集合的元素。
const noexcept 表示这是一个不会抛出异常的非常量成员函数。

const_iterator end() const noexcept;

常量版本的 end() 函数返回指向集合末尾的常量迭代器。这个常量迭代器只允许读取元素，不能修改它们。
const noexcept 表示这是一个不会抛出异常的常量成员函数。

local_iterator end(size_type n);

这个函数用于获取指向桶 n 的结束局部元素的迭代器。在哈希表中，元素被分布到不同的桶中，local_iterator 允许您在特定桶中遍历元素。
size_type n 参数指定桶的索引。

const_local_iterator end(size_type n) const;

这是常量版本的 end(size_type n) 函数，返回指向桶 n 的结束局部元素的常量迭代器。

3. cbegin()

container iterator (1)  
const_iterator cbegin() const noexcept;
bucket iterator (2) 
const_local_iterator cbegin ( size_type n ) const;

const_iterator cbegin() const noexcept;

这个函数返回指向集合中第一个元素的常量迭代器。与 begin() 类似，但这是一个常量成员函数，只允许读取元素而不能修改它们。
const noexcept 表示这是一个不会抛出异常的常量成员函数。

const_local_iterator cbegin(size_type n) const;

这个函数用于获取指向桶 n 中第一个局部元素的常量迭代器。在哈希表中，元素被分布到不同的桶中，const_local_iterator 允许您在特定桶中遍历元素。
size_type n 参数指定桶的索引

4. cend()

container iterator (1)  
const_iterator cend() const noexcept;
bucket iterator (2) 
const_local_iterator cend ( size_type n ) const;

const_iterator cend() const noexcept;

这个函数返回指向集合末尾的常量迭代器。与 end() 类似，但这是一个常量成员函数，只允许读取元素而不能修改它们。
const noexcept 表示这是一个不会抛出异常的常量成员函数。

const_local_iterator cend(size_type n) const;

这个函数用于获取指向桶 n 的常量局部结束元素的迭代器。在哈希表中，元素被分布到不同的桶中，const_local_iterator 允许您在特定桶中遍历元素。
size_type n 参数指定桶的索引。

unordered_set元素查找函数

1. find

iterator find ( const key_type& k );
const_iterator find ( const key_type& k ) const;

std::unordered_set 提供了 find() 成员函数，用于查找指定键值是否存在于集合中，并返回一个迭代器，指向包含该键值的元素（如果存在）或指向 end()（如果不存在）。

以下是 std::unordered_set 中 find() 函数的两个重载形式：

iterator find(const key_type& k);

这个版本的 find() 函数返回一个迭代器，指向包含键值 k 的元素（如果存在），否则返回指向 end() 的迭代器。
如果要对找到的元素进行修改，可以使用此迭代器。

const_iterator find(const key_type& k) const;

这是常量版本的 find() 函数，返回一个常量迭代器，用于查找包含键值 k 的元素（如果存在），否则返回指向 end() 的常量迭代器。
如果您只需要查找元素而不打算修改它，可以使用此常量迭代器。

这些 find() 函数是在 std::unordered_set 中查找特定键值的常见方式，它们允许你快速确定某个键是否存在于集合中，并让你访问该元素（如果存在）。

以下是使用 std::unordered_set 的 find() 函数的示例：

#include <iostream>
#include <unordered_set>
int main() {
    std::unordered_set<int> mySet = {1, 2, 3, 4, 5};
    // 查找特定键值
    int keyToFind = 3;
    auto it = mySet.find(keyToFind);
    // 检查元素是否存在
    if (it != mySet.end()) {
        std::cout << "键值 " << keyToFind << " 存在于集合中，对应的元素是 " << *it << std::endl;
    } else {
        std::cout << "键值 " << keyToFind << " 不存在于集合中" << std::endl;
    }
    // 尝试查找一个不存在的键值
    int nonExistentKey = 6;
    auto nonExistentIt = mySet.find(nonExistentKey);
    if (nonExistentIt != mySet.end()) {
        std::cout << "键值 " << nonExistentKey << " 存在于集合中，对应的元素是 " << *nonExistentIt << std::endl;
    } else {
        std::cout << "键值 " << nonExistentKey << " 不存在于集合中" << std::endl;
    }
    return 0;
}

在这个示例中，我们使用 find() 函数查找特定的键值（3 和 6），并根据查找结果输出相应的信息。如果键值存在于集合中，find() 返回指向该元素的迭代器，否则返回指向 end() 的迭代器。

2. count

size_type count ( const key_type& k ) const;

std::unordered_set 提供了 count() 成员函数，用于计算指定键值在集合中的出现次数。这个函数接受一个键值作为参数，并返回一个表示键值在集合中出现的次数的整数。

以下是 std::unordered_set 中 count() 函数的示例用法：

#include <iostream>
#include <unordered_set>
int main() {
    std::unordered_set<int> mySet = {1, 2, 2, 3, 4, 5, 5, 5};
    // 计算指定键值的出现次数
    int keyToCount = 2;
    std::unordered_set<int>::size_type occurrences = mySet.count(keyToCount);
    std::cout << "键值 " << keyToCount << " 在集合中出现了 " << occurrences << " 次" << std::endl;
    // 计算一个不存在的键值的出现次数
    int nonExistentKey = 6;
    std::unordered_set<int>::size_type nonExistentOccurrences = mySet.count(nonExistentKey);
    std::cout << "键值 " << nonExistentKey << " 在集合中出现了 " << nonExistentOccurrences << " 次" << std::endl;
    return 0;
}

在这个示例中，我们使用 count() 函数来计算指定键值在集合中的出现次数。对于存在的键值（例如2），count() 将返回键值在集合中的实际出现次数，而对于不存在的键值（例如6），count() 将返回0。这个函数对于统计元素出现的次数非常有用。

3. equal_range

pair<iterator,iterator>
   equal_range ( const key_type& k );
pair<const_iterator,const_iterator>
   equal_range ( const key_type& k ) const;

std::unordered_set 提供了 equal_range() 成员函数，用于查找与指定键值相等的元素范围。这个函数返回一个 std::pair，包含两个迭代器，分别指向范围的开始和结束。

以下是 std::unordered_set 中 equal_range() 函数的两个不同重载的示例用法：

#include <iostream>
#include <unordered_set>
int main() {
    std::unordered_set<int> mySet = {1, 2, 2, 3, 4, 5, 5, 5};
    // 查找与指定键值相等的元素范围
    int keyToFind = 2;
    auto range = mySet.equal_range(keyToFind);
    std::cout << "元素范围，键值 " << keyToFind << ": ";
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    // 尝试查找一个不存在的键值的元素范围
    int nonExistentKey = 6;
    auto nonExistentRange = mySet.equal_range(nonExistentKey);
    std::cout << "元素范围，键值 " << nonExistentKey << ": ";
    for (auto it = nonExistentRange.first; it != nonExistentRange.second; ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    return 0;
}

在这个示例中，我们使用 equal_range() 函数来查找与指定键值相等的元素范围。对于存在的键值（例如2），equal_range() 返回一个包含范围的 std::pair，并使用迭代器遍历该范围。对于不存在的键值（例如6），equal_range() 返回一个范围，但这个范围为空，因此迭代器范围为相等的 begin() 和 end()，不会有元素遍历。这个函数对于查找集合中具有相同键值的元素非常有用。

一篇文章让你熟悉unordered_set及其模拟实现（上）