1. Toy模板网首页
  2. > Toy博客

一篇文章让你熟悉unordered_map及其模拟实现

10月前 作者：爱学习的鱼佬 分类：Toy博客 阅读(42) 违法举报

这篇具有很好参考价值的文章主要介绍了一篇文章让你熟悉unordered_map及其模拟实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一篇文章让你熟悉unordered_map及其模拟实现,C++进阶,数据结构进阶CPP,c++,数据结构,算法,哈希算法,哈希

unordered_map的定义

哈希表在 C++ 标准库中的实现有一段历史。在 C++98/03 标准中，没有正式定义标准的哈希表容器。不过，许多 C++ 标准库实现（例如STLPort、SGI STL等）提供了 hash_map 和 hash_set 等扩展容器，这些容器提供了哈希表的功能。

随着 C++11 标准的引入，正式引入了 std::unordered_map 和 std::unordered_set 等哈希表容器作为 C++ 标准库的一部分。这些容器在 C++11 标准中进行了规范化，并提供了标准的接口和语法，以便开发者能够在不同的 C++ 标准库实现之间更轻松地移植代码。

因此，虽然哈希表容器在 C++98/03 标准之前已经存在，但它在 C++11 标准中经历了一些重要的改进和规范化，成为了 C++ 标准库的一部分，也因此被更广泛地使用。

1. unordered_map的模板定义

template < class Key,                                    // unordered_map::key_type
           class T,                                      // unordered_map::mapped_type
           class Hash = hash<Key>,                       // unordered_map::hasher
           class Pred = equal_to<Key>,                   // unordered_map::key_equal
           class Alloc = allocator< pair<const Key,T> >  // unordered_map::allocator_type
           > class unordered_map;

C++ 中的 std::unordered_map 的模板定义是 C++ 标准库中的一个关联容器（Associative Container），用于实现键值对的哈希表。下面是对该模板参数的解释：

  1. Key：表示哈希表中的键类型，也就是用来查找值的类型。
  2. T：表示哈希表中的值类型，即与键相关联的值的类型。
  3. Hash：表示哈希函数的类型，用于计算键的哈希值。默认情况下，使用 std::hash<Key> 作为哈希函数。
  4. Pred：表示键比较的谓词，用于确定两个键是否相等。默认情况下，使用 std::equal_to<Key> 作为键比较谓词。
  5. Alloc：表示分配器类型，用于分配内存。默认情况下，使用 std::allocator<std::pair<const Key, T>> 作为分配器类型。

std::unordered_map 是一个用于存储键值对的容器，它使用哈希表来实现快速查找和插入。通过提供这些模板参数，可以自定义键、值类型以及哈希函数、键比较方式和内存分配方式，以满足不同的应用需求。

例如，你可以创建一个 std::unordered_map 实例，用于将字符串作为键，整数作为值，并且使用自定义的哈希函数和键比较方式。下面是一个示例：

#include <iostream>
#include <unordered_map>
#include <string>

// 自定义哈希函数
struct MyHash {
    size_t operator()(const std::string& key) const {
        // 简单示例：将字符串的长度作为哈希值
        return key.length();
    }
};

// 自定义键比较谓词
struct MyEqual {
    bool operator()(const std::string& lhs, const std::string& rhs) const {
        // 比较字符串是否相等
        return lhs == rhs;
    }
};

int main() {
    std::unordered_map<std::string, int, MyHash, MyEqual> myMap;
    myMap["apple"] = 5;
    myMap["banana"] = 3;

    std::cout << "apple: " << myMap["apple"] << std::endl;
    std::cout << "banana: " << myMap["banana"] << std::endl;

    return 0;
}

在这个示例中，我们创建了一个自定义的哈希函数 MyHash 和键比较谓词 MyEqual，并将它们用于 std::unordered_map 的模板参数中，以自定义键的哈希方式和比较方式。这允许我们根据字符串的长度来计算哈希值，并检查字符串是否相等。

2. unordered_map的成员类型

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

一篇文章让你熟悉unordered_map及其模拟实现,C++进阶,数据结构进阶CPP,c++,数据结构,算法,哈希算法,哈希

unordered_map构造函数

empty (1)	
explicit unordered_map ( size_type n = /* see below */,
                         const hasher& hf = hasher(),
                         const key_equal& eql = key_equal(),
                         const allocator_type& alloc = allocator_type() );
explicit unordered_map ( const allocator_type& alloc );
range (2)	
template <class InputIterator>
unordered_map ( 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_map ( const unordered_map& ump );
unordered_map ( const unordered_map& ump, const allocator_type& alloc );
move (4)	
unordered_map ( unordered_map&& ump );
unordered_map ( unordered_map&& ump, const allocator_type& alloc );
initializer list (5)	
unordered_map ( 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() );
  1. 默认构造函数 (1)：
    • explicit unordered_map ( size_type n = /* see below */, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& alloc = allocator_type() );
    • 创建一个空的 unordered_map，可选地指定容器的初始桶数 n、哈希函数 hf、键比较谓词 eql 和分配器 alloc。
  2. 使用分配器的构造函数 (1)：
    • explicit unordered_map ( const allocator_type& alloc );
    • 创建一个空的 unordered_map，使用指定的分配器 alloc。
  3. 范围构造函数 (2)：
    • template <class InputIterator> unordered_map ( 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_map，可选地指定初始桶数 n、哈希函数 hf、键比较谓词 eql 和分配器 alloc。
  4. 拷贝构造函数 (3)：
    • unordered_map ( const unordered_map& ump );
    • 创建一个新的 unordered_map，并使用另一个 unordered_map ump 中的内容进行拷贝构造。
    • unordered_map ( const unordered_map& ump, const allocator_type& alloc );
    • 创建一个新的 unordered_map，并使用另一个 unordered_map ump 中的内容进行拷贝构造，同时指定分配器 alloc。
  5. 移动构造函数 (4)：
    • unordered_map ( unordered_map&& ump );
    • 创建一个新的 unordered_map，并从另一个 unordered_map ump 中移动内容。
    • unordered_map ( unordered_map&& ump, const allocator_type& alloc );
    • 创建一个新的 unordered_map，并从另一个 unordered_map ump 中移动内容，同时指定分配器 alloc。
  6. 初始化列表构造函数 (5)：
    • unordered_map ( 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_map，可选地指定初始桶数 n、哈希函数 hf、键比较谓词 eql 和分配器 alloc。

以下是关于如何使用 std::unordered_map 构造函数的一些示例：

#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    // 示例 1: 默认构造函数
    std::unordered_map<int, std::string> myMap;  // 创建一个空的 unordered_map

    // 示例 2: 范围构造函数
    std::unordered_map<char, int> charCount;
    std::string text = "hello world";
    for (char c : text) {
        charCount[c]++;
    }
    std::unordered_map<char, int> copyMap(charCount.begin(), charCount.end());

    // 示例 3: 拷贝构造函数
    std::unordered_map<int, double> sourceMap = {{1, 1.1}, {2, 2.2}, {3, 3.3}};
    std::unordered_map<int, double> copyOfSource(sourceMap);

    // 示例 4: 移动构造函数
    std::unordered_map<std::string, int> source;
    source["apple"] = 5;
    source["banana"] = 3;
    std::unordered_map<std::string, int> destination(std::move(source));

    // 示例 5: 初始化列表构造函数
    std::unordered_map<std::string, int> fruitCount = {
        {"apple", 5},
        {"banana", 3},
        {"cherry", 8}
    };

    // 输出示例
    for (const auto& pair : fruitCount) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

unordered_map赋值运算符重载

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

赋值操作符允许你将一个 std::unordered_map 的内容赋值给另一个 std::unordered_map。以下是这些操作符及其重载方式的简要说明：

  1. 拷贝赋值操作符 (1)：
    • unordered_map& operator= (const unordered_map& ump);
    • 将一个已存在的 std::unordered_map 的内容拷贝给另一个已存在的 std::unordered_map。
  2. 移动赋值操作符 (2)：
    • unordered_map& operator= (unordered_map&& ump);
    • 将一个已存在的 std::unordered_map 的内容移动给另一个已存在的 std::unordered_map。这个操作会将原有的 std::unordered_map 置为有效但不再可用的状态。
  3. 初始化列表赋值操作符 (3)：
    • unordered_map& operator= (initializer_list<value_type> il);
    • 使用初始化列表 il 中的元素来赋值给 std::unordered_map。这个操作会替换原有的内容。

这些赋值操作符允许你在不同的情况下更新 std::unordered_map 的内容，可以用于拷贝、移动或替换哈希表中的键值对。以下是一些示例：

#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    std::unordered_map<std::string, int> source = {{"apple", 5}, {"banana", 3}};
    std::unordered_map<std::string, int> destination;

    // 拷贝赋值操作符示例
    destination = source;

    // 移动赋值操作符示例
    std::unordered_map<std::string, int> otherSource = {{"cherry", 8}};
    destination = std::move(otherSource);

    // 初始化列表赋值操作符示例
    destination = {{"grape", 12}, {"orange", 6}};

    // 输出示例
    for (const auto& pair : destination) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

这些示例演示了如何使用不同的赋值操作符来更新 std::unordered_map 的内容。无论是拷贝、移动还是用初始化列表替换，都可以根据需要轻松地更新哈希表对象的内容。

unordered_map容量函数（Capacity）

  1. empty() 函数:
    • bool empty() const noexcept;
    • 用于检查 std::unordered_map 是否为空。如果哈希表中不包含任何键值对，则返回 true；否则返回 false。该函数是不会抛出异常的。
  2. size() 函数:
    • size_type size() const noexcept;
    • 返回 std::unordered_map 中存储的键值对的数量。即返回哈希表的大小。如果哈希表为空，则返回 0。该函数是不会抛出异常的。
  3. max_size() 函数:
    • size_type max_size() const noexcept;
    • 返回 std::unordered_map 可以容纳的最大键值对数量，通常受到系统资源限制。这个值在不同的系统和编译器上可能会有所不同。该函数是不会抛出异常的。

这些函数使你能够查询和管理 std::unordered_map 的状态。例如，你可以使用 empty() 来检查哈希表是否为空，使用 size() 获取其当前大小，以及使用 max_size() 查看哈希表可以容纳的最大大小。

示例：

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> myMap;

    // 使用 empty() 函数检查是否为空
    if (myMap.empty()) {
        std::cout << "Map is empty." << std::endl;
    } else {
        std::cout << "Map is not empty." << std::endl;
    }

    // 添加一些键值对
    myMap[1] = "one";
    myMap[2] = "two";
    myMap[3] = "three";

    // 使用 size() 函数获取大小
    std::cout << "Size of the map: " << myMap.size() << std::endl;

    // 使用 max_size() 函数获取最大容量
    std::cout << "Max size of the map: " << myMap.max_size() << std::endl;

    return 0;
}

unordered_map迭代器（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;

  1. begin() 函数 (容器迭代器):

    • iterator begin() noexcept;
    • const_iterator begin() const noexcept;
    • 这两个版本的 begin() 函数用于返回指向 std::unordered_map 的第一个元素（键值对）的迭代器。第一个版本返回非常量迭代器，而第二个版本返回常量迭代器。这些函数是不会抛出异常的。

  2. begin(size_type n) 函数 (桶迭代器):

    • local_iterator begin(size_type n);

    • const_local_iterator begin(size_type n) const;

    • 这两个版本的 begin(size_type n) 函数用于返回指向特定桶（bucket）中第一个元素的迭代器，其中 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;

  1. end() 函数 (容器迭代器)

    :

    • iterator end() noexcept;
    • const_iterator end() const noexcept;
    • 这两个版本的 end() 函数用于返回指向 std::unordered_map 的尾部（末尾）的迭代器。第一个版本返回非常量迭代器，而第二个版本返回常量迭代器。这些函数是不会抛出异常的。

  2. end(size_type n) 函数 (桶迭代器):

    • local_iterator end(size_type n);

    • const_local_iterator end(size_type n) const;

    • 这两个版本的 end(size_type n) 函数用于返回指向特定桶（bucket）中的尾部（末尾）的迭代器，其中 n 是要访问的桶的索引。第一个版本返回非常量桶迭代器，而第二个版本返回常量桶迭代器。这些函数允许你在哈希表中的特定桶内迭代元素的末尾。

这些迭代器函数使你能够在 std::unordered_map 中遍历元素，不仅可以遍历整个容器，还可以遍历特定桶内的元素。以下是一些示例代码：

#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    std::unordered_map<int, std::string> myMap = {{1, "one"}, {2, "two"}, {3, "three"}};

    // 使用容器迭代器 begin()
    for (auto it = myMap.begin(); it != myMap.end(); ++it) {
        std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
    }

    // 使用桶迭代器 begin(size_type n)
    size_t bucketIndex = myMap.bucket(2); // 获取键 2 所在的桶索引
    for (auto it = myMap.begin(bucketIndex); it != myMap.end(bucketIndex); ++it) {
        std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
    }

    return 0;
}

在这个示例中，我们展示了如何使用容器迭代器 begin() 和 end()遍历整个哈希表，并使用桶迭代器 begin(size_type n) 和end(size_type n) 遍历特定桶中的元素。这些迭代器函数允许你有效地遍历和访问 std::unordered_map 中的元素。

3. cbegin()

container iterator (1)	
	  const_iterator cbegin() const noexcept;
bucket iterator (2)	
	  const_local_iterator cbegin ( size_type n ) const;
  1. cbegin() 函数 (常量容器迭代器):
    • const_iterator cbegin() const noexcept;
    • 这个函数返回一个指向 std::unordered_map 的第一个元素（键值对）的常量迭代器。它允许对哈希表进行只读遍历，不允许修改哈希表的内容。该函数是不会抛出异常的。
  2. cbegin(size_type n) 函数 (常量桶迭代器):
    • const_local_iterator cbegin(size_type n) const;
    • 这个函数用于返回指向特定桶（bucket）中第一个元素的常量桶迭代器，其中 n 是要访问的桶的索引。它允许只读遍历特定桶中的元素，不允许修改哈希表的内容。该函数是不会抛出异常的。

4. cend()

container iterator (1)	
	  const_iterator cend() const noexcept;
bucket iterator (2)	
	  const_local_iterator cend ( size_type n ) const;
  1. cend() 函数 (常量容器迭代器):
    • const_iterator cend() const noexcept;
    • 这个函数返回一个指向 std::unordered_map 的尾部（末尾）的常量迭代器。它允许对哈希表进行只读遍历，不允许修改哈希表的内容。该函数是不会抛出异常的。
  2. cend(size_type n) 函数 (常量桶迭代器):
    • const_local_iterator cend(size_type n) const;
    • 这个函数用于返回指向特定桶（bucket）中的尾部（末尾）的常量桶迭代器，其中 n 是要访问的桶的索引。它允许只读遍历特定桶中的元素，不允许修改哈希表的内容。该函数是不会抛出异常的。

这些常量迭代器函数对于在只读模式下访问 std::unordered_map 的元素非常有用。以下是一个示例代码：

#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    std::unordered_map<int, std::string> myMap = {{1, "one"}, {2, "two"}, {3, "three"}};

    // 使用常量容器迭代器 cbegin()
    for (auto it = myMap.cbegin(); it != myMap.cend(); ++it) {
        std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
    }

    // 使用常量桶迭代器 cbegin(size_type n)
    size_t bucketIndex = myMap.bucket(2); // 获取键 2 所在的桶索引
    for (auto it = myMap.cbegin(bucketIndex); it != myMap.cend(bucketIndex); ++it) {
        std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
    }

    return 0;
}

在这个示例中，我们使用常量容器迭代器 cbegin() 和cend()遍历整个哈希表，并使用常量桶迭代器 cbegin(size_type n) 和cend(size_type n)遍历特定桶中的元素。这些常量迭代器函数允许你在只读模式下访问 std::unordered_map 中的元素，确保不会修改哈希表的内容。

unordered_map元素访问和元素查找函数

1. operator[]

  1. mapped_type& operator[] ( const key_type& k );：
    • 这个重载函数接受一个const引用类型的键（key_type），并返回与该键关联的值（mapped_type）的引用。
    • 如果键（k）存在于unordered_map中，它将返回该键的值的引用，允许你修改该值。
    • 如果键（k）不存在，它将在unordered_map中插入该键-值对，并返回一个默认构造的值的引用（通常为该类型的默认值）。
    • 这意味着你可以通过operator[]来读取或修改unordered_map中的值，而不需要显式地检查键是否存在或插入键-值对。
  2. mapped_type& operator[] ( key_type&& k );：
    • 这个重载函数接受一个右值引用类型的键（key_type），并返回与该键关联的值（mapped_type）的引用。
    • 与第一个重载函数类似，如果键（k）存在于unordered_map中，它将返回该键的值的引用，允许你修改该值。
    • 如果键（k）不存在，它将在unordered_map中插入该键-值对，并返回一个默认构造的值的引用。

以下是使用std::unordered_map的operator[]重载函数的示例：

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> myMap;

    // 使用 operator[] 插入键-值对
    myMap["apple"] = 3;
    myMap["banana"] = 2;
    myMap["cherry"] = 5;

    // 访问键的值并修改它
    std::cout << "Number of apples: " << myMap["apple"] << std::endl;
    myMap["apple"] = 4;

    // 访问不存在的键，会插入默认值并返回引用
    std::cout << "Number of oranges: " << myMap["orange"] << std::endl;

    // 使用右值引用的 operator[] 插入键-值对
    std::string fruit = "grape";
    myMap[std::move(fruit)] = 6;

    // 遍历输出所有键-值对
    for (const auto& kv : myMap) {
        std::cout << kv.first << ": " << kv.second << std::endl;
    }

    return 0;
}

在这个示例中，我们使用operator[]插入键-值对，访问并修改已存在的键的值，以及访问不存在的键，它会自动插入默认值。还演示了使用右值引用的operator[]来插入新的键-值对。最后，我们遍历输出了所有键-值对。

2. at

  1. 修改值的 at 函数：

    mapped_type& at(const key_type& k);
mapped_type& at(key_type&& k);

    这两个重载版本允许你根据键 k 修改关联容器中的值。如果键 k 存在于容器中，它会返回对应的值的引用，允许你修改这个值。如果键 k 不存在，它会抛出 std::out_of_range 异常。

    示例代码：

    std::unordered_map<std::string, int> myMap;
myMap["apple"] = 3;

// 使用 at 函数修改值
myMap.at("apple") = 4;

    如果键 "apple" 存在，它将修改值为 4。

  2. 只读访问值的 at 函数：

    const mapped_type& at(const key_type& k) const;

    这个重载版本允许你只读访问容器中的值。它返回与键 k 相关联的值的常量引用。如果键 k 不存在，它也会抛出 std::out_of_range 异常。

    示例代码：

    std::unordered_map<std::string, int> myMap;
myMap["apple"] = 3;

// 使用 at 函数只读访问值
int numberOfApples = myMap.at("apple");

    如果键 "apple" 存在，它将返回值 3，并且你可以将其存储在变量 numberOfApples 中。

总之，at 函数是一个用于安全地访问关联容器中元素的方法，因为它会检查键是否存在并在必要时抛出异常。这有助于避免访问不存在的键而导致的未定义行为。

3. find

  1. 非常量容器的 find 函数：

    iterator find(const key_type& k);

    这个版本的 find 函数用于非常量容器，返回一个迭代器（iterator）。如果容器中存在键 k，则迭代器指向与键 k 相关联的元素；如果键 k 不存在，它返回容器的 end() 迭代器，表示未找到。

    示例代码：

    std::unordered_map<std::string, int> myMap;
myMap["apple"] = 3;

// 使用 find 函数查找键 "apple"
auto it = myMap.find("apple");
if (it != myMap.end()) {
    // 找到了，输出值
    std::cout << "Value of 'apple': " << it->second << std::endl;
} else {
    // 未找到
    std::cout << "Key 'apple' not found." << std::endl;
}

  2. 常量容器的 find 函数：

    const_iterator find(const key_type& k) const;

    这个版本的 find 函数用于常量容器，返回一个常量迭代器（const_iterator）。它的功能与非常量版本相同，但不允许修改容器中的元素。

    示例代码：

    const std::unordered_map<std::string, int> myMap = {
    {"apple", 3},
    {"banana", 2},
    {"cherry", 5}
};

// 使用 const find 函数查找键 "banana"
auto it = myMap.find("banana");
if (it != myMap.end()) {
    // 找到了，输出值
    std::cout << "Value of 'banana': " << it->second << std::endl;
} else {
    // 未找到
    std::cout << "Key 'banana' not found." << std::endl;
}

总之，find 函数是一个用于在关联容器中查找特定键的非常有用的方法。如果你需要查找键是否存在并访问与之关联的值，find 函数是一个安全且高效的选择。

4. count

size_type count(const key_type& k) const;
  • k：要查找的键。
  • size_type：返回值类型，通常是一个无符号整数类型，表示键 k 在容器中的出现次数。

count 函数会在容器中查找键 k，并返回键的出现次数。如果键 k 存在于容器中，count 函数将返回 1 或更大的正整数，表示键出现的次数。如果键 k 不存在，函数将返回 0，表示键没有出现。

示例代码：

std::unordered_map<std::string, int> myMap = {
    {"apple", 3},
    {"banana", 2},
    {"cherry", 5}
};

// 计算键 "apple" 在容器中的出现次数
size_t appleCount = myMap.count("apple");
std::cout << "The count of 'apple': " << appleCount << std::endl;

// 计算键 "grape" 在容器中的出现次数
size_t grapeCount = myMap.count("grape");
std::cout << "The count of 'grape': " << grapeCount << std::endl;

在上面的示例中，count 函数首先计算键 “apple” 在容器中的出现次数（应为 1），然后计算键 “grape” 在容器中的出现次数（应为 0）。count 函数对于检查某个键是否存在于容器中以及统计键的出现次数非常有用。如果你需要知道某个键是否存在以及它出现了多少次，可以使用 count 函数进行查询。

5. equal_range

pair<iterator,iterator>
   equal_range ( const key_type& k );
pair<const_iterator,const_iterator>
   equal_range ( const key_type& k ) const;
  • k：要查找的键。
  • pair：返回值类型，一个包含两个迭代器的容器，表示范围的起始和结束位置。
  • iterator 和 const_iterator：迭代器类型，表示容器的迭代器和常量迭代器。

equal_range 函数会在容器中查找键 k，然后返回一个 pair，其中第一个元素是指向范围的开始位置的迭代器，第二个元素是指向范围的结束位置的迭代器。这个范围包括了所有键等于 k 的元素。

示例代码：

std::map<int, std::string> myMap = {
    {1, "one"},
    {2, "two"},
    {2, "another two"}, // 注意：键 2 重复
    {3, "three"}
};

// 查找键 2 在容器中的范围
auto range = myMap.equal_range(2);

// 输出范围中的元素
for (auto it = range.first; it != range.second; ++it) {
    std::cout << it->first << ": " << it->second << std::endl;
}

在上面的示例中，equal_range 函数查找键 2 在 myMap 中的范围，并返回一个包含范围的起始和结束迭代器的 pair。然后，我们使用迭代器遍历范围，输出范围中的元素。

equal_range 函数在处理关联容器中的重复键时非常有用，因为它允许你查找所有具有相同键的元素，并迭代遍历它们。

unordered_map修饰符函数

1. emplace

template <class... Args>
pair<iterator, bool> emplace ( Args&&... args );

std::unordered_map 的 emplace 函数用于在哈希表中插入新的键值对，并返回一个 std::pair，其中包含一个迭代器和一个布尔值。

  • Args&&... args 是模板参数包，允许你传递任意数量的参数。
  • pair<iterator, bool> 是返回值类型，其中 iterator 是插入或已存在键值对的迭代器，bool 表示插入是否成功。如果键已存在，则迭代器指向已存在的键值对，布尔值为 false；如果键不存在，则迭代器指向新插入的键值对，布尔值为 true。

以下是 emplace 函数的示例用法：

#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    std::unordered_map<int, std::string> myMap;

    // 使用 emplace 插入键值对
    auto result1 = myMap.emplace(1, "One");
    if (result1.second) {
        std::cout << "Insertion successful. Key: " << result1.first->first << ", Value: " << result1.first->second << std::endl;
    } else {
        std::cout << "Key already exists. Key: " << result1.first->first << ", Value: " << result1.first->second << std::endl;
    }

    // 尝试再次插入相同的键值对
    auto result2 = myMap.emplace(1, "Another One");
    if (result2.second) {
        std::cout << "Insertion successful. Key: " << result2.first->first << ", Value: " << result2.first->second << std::endl;
    } else {
        std::cout << "Key already exists. Key: " << result2.first->first << ", Value: " << result2.first->second << std::endl;
    }

    return 0;
}

在上述示例中，首先使用 emplace 函数插入一个键值对，然后再次尝试插入相同的键值对。根据返回的布尔值可以确定插入是否成功，以及插入的键值对是已存在的还是新插入的。

2. emplace_hint

与 emplace 不同，emplace_hint 允许你提供一个提示位置，以提高插入操作的性能。

以下是对 emplace_hint 函数的参数和用法的简要说明：

  • position：这是一个迭代器，它指示了插入位置的提示。新元素将插入到 position 之前。这个参数可以帮助容器更高效地插入元素，但不是必需的。
  • Args&&... args：这是一个可变参数模板，用于传递新元素的构造参数。根据元素类型的构造函数，你可以传递任意数量的参数。
  • 返回值：emplace_hint 返回一个迭代器，指向插入的新元素，或者如果插入失败，则返回一个指向容器中现有元素的迭代器。

下面是一个示例，演示了如何使用 emplace_hint 向 std::unordered_map 中插入新的键值对：

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> myMap;

    // 使用 emplace_hint 插入元素
    auto hint = myMap.emplace_hint(myMap.begin(), 1, "One");
    myMap.emplace_hint(hint, 2, "Two");
    myMap.emplace_hint(hint, 3, "Three");

    // 遍历 unordered_map 并打印键值对
    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

在这个示例中，emplace_hint 被用来插入新的键值对，通过 hint 提示位置，以提高插入的效率。注意，emplace_hint 可以在任何位置插入元素，但通常你会使用提示位置以避免不必要的搜索和移动操作。

3. insert

  1. pair<iterator, bool> insert(const value_type& val)：将一个键值对 val 插入到 unordered_map 中。如果插入成功，返回一个 pair，其中的 iterator 指向插入的元素，bool 表示插入是否成功。

    示例：

    std::unordered_map<int, std::string> myMap;
std::pair<int, std::string> pairToInsert(1, "One");
auto result = myMap.insert(pairToInsert);
if (result.second) {
    std::cout << "Insertion successful." << std::endl;
} else {
    std::cout << "Insertion failed (key already exists)." << std::endl;
}

  2. template <class P> pair<iterator, bool> insert(P&& val)：使用移动语义，将一个键值对 val 插入到 unordered_map 中。同样返回一个 pair，表示插入结果。

    示例：

    std::unordered_map<int, std::string> myMap;
auto result = myMap.insert(std::make_pair(1, "One"));
if (result.second) {
    std::cout << "Insertion successful." << std::endl;
} else {
    std::cout << "Insertion failed (key already exists)." << std::endl;
}

  3. iterator insert(const_iterator hint, const value_type& val)：在给定的位置 hint 处插入一个键值对 val。这个函数允许你提供一个位置提示，以提高插入效率。

    示例：

    std::unordered_map<int, std::string> myMap;
auto hint = myMap.begin(); // 可以是任何迭代器位置
myMap.insert(hint, std::make_pair(1, "One"));

  4. template <class P> iterator insert(const_iterator hint, P&& val)：与第三个函数类似，使用移动语义插入键值对，同时提供位置提示。

    示例：

    std::unordered_map<int, std::string> myMap;
auto hint = myMap.begin(); // 可以是任何迭代器位置
myMap.insert(hint, std::make_pair(1, "One"));

  5. template <class InputIterator> void insert(InputIterator first, InputIterator last)：用一对迭代器 [first, last) 指定的范围内的元素插入到 unordered_map 中。

    示例：

    std::unordered_map<int, std::string> myMap;
std::vector<std::pair<int, std::string>> data = {{1, "One"}, {2, "Two"}, {3, "Three"}};
myMap.insert(data.begin(), data.end());

  6. void insert(initializer_list<value_type> il)：使用初始化列表中的元素插入到 unordered_map 中。

    示例：

    std::unordered_map<int, std::string> myMap;
myMap.insert({{1, "One"}, {2, "Two"}, {3, "Three"}});

这些函数提供了多种插入键值对的方式，使你可以根据需求选择最合适的方法。

4. erase

  1. iterator erase(const_iterator position)：通过迭代器位置 position 删除对应键值对。返回指向删除元素之后位置的迭代器。

    示例：

    std::unordered_map<int, std::string> myMap = {{1, "One"}, {2, "Two"}, {3, "Three"}};
auto it = myMap.find(2); // 找到键为2的位置
if (it != myMap.end()) {
    myMap.erase(it); // 删除键为2的元素
}

  2. size_type erase(const key_type& k)：通过键 k 删除对应的键值对。返回删除的元素个数（0或1，因为键在 unordered_map 中是唯一的）。

    示例：

    std::unordered_map<int, std::string> myMap = {{1, "One"}, {2, "Two"}, {3, "Three"}};
size_t erased = myMap.erase(2); // 删除键为2的元素
std::cout << "Erased " << erased << " element(s)." << std::endl;

  3. iterator erase(const_iterator first, const_iterator last)：通过一对迭代器 [first, last) 删除指定范围内的键值对。返回指向删除操作之后位置的迭代器。

    示例：

    std::unordered_map<int, std::string> myMap = {{1, "One"}, {2, "Two"}, {3, "Three"}};
auto first = myMap.begin(); // 范围起始位置
auto last = myMap.find(2);  // 范围结束位置，找到键为2的位置
if (last != myMap.end()) {
    myMap.erase(first, last); // 删除范围内的元素
}

这些函数提供了不同的方式来删除 unordered_map 中的元素，根据需求可以选择最合适的方法。

5. clear

  • void clear() noexcept;：清空 unordered_map 中的所有键值对。这个操作会使 unordered_map 变为空，但不会改变容器的容量。

    示例：

    std::unordered_map<int, std::string> myMap = {{1, "One"}, {2, "Two"}, {3, "Three"}};
std::cout << "Size before clear: " << myMap.size() << std::endl;

myMap.clear(); // 清空 unordered_map

std::cout << "Size after clear: " << myMap.size() << std::endl;

    输出：

    Size before clear: 3
Size after clear: 0

这个函数是一个无异常操作 (noexcept)，意味着它不会抛出异常。它可以在需要清空 unordered_map 的情况下使用，以释放容器占用的资源。

6. swap

  • void swap ( unordered_map& ump );：交换当前 unordered_map 与参数 ump 所表示的 unordered_map 的内容。这个操作不会改变容器的容量，只是交换它们的内容。

    示例：

    std::unordered_map<int, std::string> map1 = {{1, "One"}, {2, "Two"}};
std::unordered_map<int, std::string> map2 = {{3, "Three"}, {4, "Four"}};

std::cout << "map1 before swap:" << std::endl;
for (const auto& pair : map1) {
    std::cout << pair.first << ": " << pair.second << std::endl;
}

std::cout << "map2 before swap:" << std::endl;
for (const auto& pair : map2) {
    std::cout << pair.first << ": " << pair.second << std::endl;
}

map1.swap(map2); // 交换 map1 和 map2 的内容

std::cout << "map1 after swap:" << std::endl;
for (const auto& pair : map1) {
    std::cout << pair.first << ": " << pair.second << std::endl;
}

std::cout << "map2 after swap:" << std::endl;
for (const auto& pair : map2) {
    std::cout << pair.first << ": " << pair.second << std::endl;
}

    输出：

    map1 before swap:
1: One
2: Two
map2 before swap:
3: Three
4: Four
map1 after swap:
3: Three
4: Four
map2 after swap:
1: One
2: Two

这个函数非常有用，因为它可以在不需要创建临时对象的情况下，高效地交换两个 unordered_map 的内容。

unordered_map桶函数

1. bucket_count

bucket_count 函数用于获取 std::unordered_map 容器中当前桶（buckets）的数量。桶是哈希表中的存储位置，用于存储键值对。

size_type bucket_count() const noexcept;
  • size_type：表示无符号整数类型，通常是 size_t。
  • bucket_count()：该函数没有参数。
  • const：表示该函数不会修改容器的内容。
  • noexcept：表示该函数不会抛出异常。

该函数返回当前 unordered_map 容器中桶的数量。

示例代码：

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> map;
    map[1] = "One";
    map[2] = "Two";
    map[3] = "Three";
    map[4] = "Four";

    std::cout << "Bucket count: " << map.bucket_count() << std::endl;

    return 0;
}

在这个示例中，bucket_count 函数返回当前 std::unordered_map 中的桶数量，该数量取决于哈希函数和负载因子等因素。这个数量通常会比容器中实际的元素数量大，以确保元素能够均匀分布在桶中，从而提高查询性能。

2. max_bucket_count

max_bucket_count 函数用于获取 std::unordered_map 容器支持的最大桶（buckets）数量。桶是哈希表中的存储位置，用于存储键值对。

size_type max_bucket_count() const noexcept;
  • size_type：表示无符号整数类型，通常是 size_t。
  • max_bucket_count()：该函数没有参数。
  • const：表示该函数不会修改容器的内容。
  • noexcept：表示该函数不会抛出异常。

该函数返回 std::unordered_map 容器支持的最大桶数量。这个值通常受到底层哈希表实现和系统资源限制的影响。

示例代码：

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> map;

    // 获取最大桶数量并输出
    std::cout << "Max bucket count: " << map.max_bucket_count() << std::endl;

    return 0;
}

在这个示例中，max_bucket_count 函数返回 std::unordered_map 容器支持的最大桶数量。这个值是由编译器和系统决定的，通常取决于系统的可用内存和哈希表实现。

3. bucket_size

bucket_size 函数用于获取指定桶中的元素数量，它需要传入一个桶的索引作为参数。

size_type bucket_size(size_type n) const;
  • size_type：表示无符号整数类型，通常是 size_t。
  • bucket_size(n)：该函数接受一个参数 n，表示要查询的桶的索引。
  • const：表示该函数不会修改容器的内容。

这个函数返回指定桶中的元素数量。

示例代码：

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> map;

    // 插入一些键值对
    map[1] = "one";
    map[2] = "two";
    map[3] = "three";

    // 获取第一个桶中的元素数量
    size_t bucketIndex = map.bucket(1); // 获取键为1的元素所在的桶的索引
    size_t bucketSize = map.bucket_size(bucketIndex); // 获取该桶的元素数量

    std::cout << "Bucket size for key 1: " << bucketSize << std::endl;

    return 0;
}

在这个示例中，我们创建了一个 std::unordered_map 容器，插入了一些键值对，并使用 bucket_size 函数获取特定桶中的元素数量。请注意，我们首先使用 bucket 函数获取了键为1的元素所在的桶的索引。然后，我们使用 bucket_size 函数获取了该桶中的元素数量。

4. bucket

bucket 函数用于获取给定键所属的桶的索引，它需要传入一个键作为参数。

size_type bucket(const key_type& k) const;
  • size_type：表示无符号整数类型，通常是 size_t。
  • bucket(k)：该函数接受一个参数 k，表示要查询的键。
  • const：表示该函数不会修改容器的内容。

这个函数返回指定键所属的桶的索引。

示例代码：

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> map;

    // 插入一些键值对
    map["one"] = 1;
    map["two"] = 2;
    map["three"] = 3;

    // 获取键所属的桶的索引
    size_t bucketIndex1 = map.bucket("one");
    size_t bucketIndex2 = map.bucket("three");

    std::cout << "Bucket index for key 'one': " << bucketIndex1 << std::endl;
    std::cout << "Bucket index for key 'three': " << bucketIndex2 << std::endl;

    return 0;
}

在这个示例中，我们创建了一个 std::unordered_map 容器，插入了一些键值对，并使用 bucket 函数获取特定键所属的桶的索引。我们分别获取了键 “one” 和 “three” 所在的桶的索引。

unordered_map哈希策略函数

1. load_factor

float load_factor() const noexcept;

load_factor 函数用于获取当前散列表的负载因子，它返回一个 float 值表示负载因子。

负载因子是指当前散列表中包含的元素数量与桶的总数之比。通常，负载因子越小，散列表的性能越好，因为冲突的概率较低。

示例代码：

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> map;

    // 设置一些键值对
    map[1] = "one";
    map[2] = "two";
    map[3] = "three";

    // 获取当前负载因子
    float lf = map.load_factor();

    std::cout << "Load Factor: " << lf << std::endl;

    return 0;
}

在这个示例中，我们创建了一个 std::unordered_map 容器，并插入了一些键值对。然后，我们使用 load_factor 函数获取了当前负载因子，并将其打印出来。

2. max_load_factor

max_load_factor 函数用于设置或获取散列表的最大负载因子。最大负载因子是在发生重新哈希（rehashing）之前允许的最大负载因子。

  • float max_load_factor() const noexcept;：获取当前散列表的最大负载因子。
  • void max_load_factor(float z);：设置散列表的最大负载因子为 z。

示例代码：

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> map;

    // 获取当前最大负载因子
    float maxLF = map.max_load_factor();
    std::cout << "Current Max Load Factor: " << maxLF << std::endl;

    // 设置最大负载因子为新值
    map.max_load_factor(0.75);

    // 获取新的最大负载因子
    maxLF = map.max_load_factor();
    std::cout << "Updated Max Load Factor: " << maxLF << std::endl;

    return 0;
}

在这个示例中，我们首先获取了当前散列表的最大负载因子，然后将其修改为新值。通过调用 max_load_factor 函数，可以控制散列表在重新哈希之前的负载因子，以优化性能。

3. rehash

rehash 函数用于重新调整散列表的桶（buckets）数量，以便容纳至少 n 个元素，以提高散列表的性能。重新哈希会更改桶的数量，重新分布元素，因此它可能会耗费一些时间。

  • void rehash(size_type n);：重新调整散列表的桶的数量，使其至少能够容纳 n 个元素。

示例代码：

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> map;

    // 添加一些元素
    map[1] = "One";
    map[2] = "Two";
    map[3] = "Three";

    // 获取当前桶的数量
    size_t currentBucketCount = map.bucket_count();
    std::cout << "Current Bucket Count: " << currentBucketCount << std::endl;

    // 重新调整桶的数量
    map.rehash(10);

    // 获取新的桶的数量
    currentBucketCount = map.bucket_count();
    std::cout << "Updated Bucket Count: " << currentBucketCount << std::endl;

    return 0;
}

在这个示例中，我们首先添加了一些元素到散列表中，然后使用 rehash 函数将桶的数量重新调整为 10。重新哈希可能会在添加大量元素后用于优化性能，以确保负载因子保持在合适的范围内。

4. reserve

reserve 函数用于预留至少能够容纳 n 个元素的桶空间，以提高散列表的性能。这个函数可以帮助你在插入大量元素之前分配足够的桶空间，以避免频繁的重新哈希操作。

  • void reserve(size_type n);：预留至少能够容纳 n 个元素的桶空间。

示例代码：

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> map;

    // 预留足够的桶空间
    map.reserve(100);  // 预留至少能容纳 100 个元素的桶空间

    // 添加一些元素
    for (int i = 0; i < 100; ++i) {
        map[i] = "Value " + std::to_string(i);
    }

    // 获取当前桶的数量
    size_t currentBucketCount = map.bucket_count();
    std::cout << "Current Bucket Count: " << currentBucketCount << std::endl;

    return 0;
}

在这个示例中，我们使用 reserve 函数预留了至少能够容纳 100 个元素的桶空间，然后向散列表中添加了 100 个元素。这可以帮助提高性能，因为预留了足够的桶空间，避免了在插入元素时频繁的重新哈希操作。

unordered_map开散列形式模拟实现

修改上篇哈希博客的哈希表实现

template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};
  • operator() 是函数调用运算符的重载，允许对象像函数一样被调用。
  • 函数接受一个参数 key，该参数表示要计算哈希值的键。
  • 函数体内， (size_t)key 将键 key 强制转换为 size_t 类型，以得到其哈希值。
  • 哈希值是一个用于标识键在哈希表中位置的数值。通常，哈希函数会将不同的键映射到不同的哈希值，以便在哈希表中进行高效的查找操作

哈希迭代器增加

template<class K, class T, class Hash, class KeyOfT>
struct __HashIterator
{
	typedef HashNode<T> Node;
	typedef HashTable<K, T, Hash, KeyOfT> HT;
	typedef __HashIterator<K, T, Hash, KeyOfT> Self;

	Node* _node;
	HT* _pht;

	__HashIterator(Node* node, HT* pht)
		:_node(node)
		, _pht(pht)
	{}

	T& operator*()
	{
		return _node->_data;
	}

	T* operator->()
	{
		return &_node->_data;
	}

	Self& operator++()
	{
		if (_node->_next)
		{
			// 当前桶中迭代
			_node = _node->_next;
		}
		else
		{
			// 找下一个桶
			Hash hash;
			KeyOfT kot;
			size_t i = hash(kot(_node->_data)) % _pht->_tables.size();
			++i;
			for (; i < _pht->_tables.size(); ++i)
			{
				if (_pht->_tables[i])
				{
					_node = _pht->_tables[i];
					break;
				}
			}

			// 说明后面没有有数据的桶了
			if (i == _pht->_tables.size())
			{
				_node = nullptr;
			}
		}

		return *this;
	}

	bool operator!=(const Self& s) const
	{
		return _node != s._node;
	}

	bool operator==(const Self& s) const
	{
		return _node == s._node;
	}
};
  1. typedef HashNode<T> Node;：为 HashNode<T> 类型起一个别名 Node，HashNode 通常表示哈希表中的节点。
  2. typedef HashTable<K, T, Hash, KeyOfT> HT;：为 HashTable 模板类实例化后的类型起一个别名 HT，HashTable 通常表示哈希表。
  3. typedef __HashIterator<K, T, Hash, KeyOfT> Self;：为迭代器自身的类型起一个别名 Self，这个别名在迭代器内部用于定义迭代器类型。
  4. Node* _node;：指向当前迭代节点的指针。迭代器用于遍历哈希表中的节点，当前节点的信息存储在 _node 中。
  5. HT* _pht;：指向哈希表的指针。哈希表的信息存储在 _pht 中，迭代器可能需要访问哈希表的属性以实现迭代操作。
  6. T& operator*()：重载 * 运算符，使迭代器可以像指针一样用 * 来访问当前节点的数据。
  7. T* operator->()：重载 -> 运算符，使迭代器可以像指针一样用 -> 来访问当前节点的数据。
  8. Self& operator++()：重载前置自增运算符 ++，使迭代器可以前进到下一个节点。该函数会检查当前桶内是否还有节点，如果有，则移到下一个节点；否则，找到下一个非空桶，将 _node 指向该桶的第一个节点。
  9. bool operator!=(const Self& s) const：重载不等于运算符 !=，用于比较两个迭代器是否不相等。
  10. bool operator==(const Self& s) const：重载等于运算符 ==，用于比较两个迭代器是否相等。
typedef __HashIterator<K, T, Hash, KeyOfT> iterator;

iterator begin()
{
	for (size_t i = 0; i < _tables.size(); ++i)
	{
		if (_tables[i])
		{
			return iterator(_tables[i], this);
		}
	}

	return end();
}

iterator end()
{
	return iterator(nullptr, this);
}
  1. typedef __HashIterator<K, T, Hash, KeyOfT> iterator;：这一行定义了 iterator 类型为 __HashIterator 的别名，从而使你能够像使用普通的 C++ 迭代器一样使用它。
  2. iterator begin() 函数：这个函数返回指向哈希表中第一个非空桶的迭代器。它通过遍历 _tables 容器中的桶，找到第一个非空桶，并创建一个对应的迭代器，然后返回该迭代器。如果没有找到非空桶，就返回 end() 迭代器，表示遍历结束。
  3. iterator end() 函数：这个函数返回表示遍历结束的迭代器。它返回一个迭代器，其中的 _node 成员为 nullptr，表示当前没有有效节点可供迭代。这在标识迭代结束时非常有用。

添加__stl_num_primes函数

inline size_t __stl_next_prime(size_t n)
{
	static const size_t __stl_num_primes = 28;
	static const size_t __stl_prime_list[__stl_num_primes] =
	{
		53, 97, 193, 389, 769,
		1543, 3079, 6151, 12289, 24593,
		49157, 98317, 196613, 393241, 786433,
		1572869, 3145739, 6291469, 12582917, 25165843,
		50331653, 100663319, 201326611, 402653189, 805306457,
		1610612741, 3221225473, 4294967291
	};

	for (size_t i = 0; i < __stl_num_primes; ++i)
	{
		if (__stl_prime_list[i] > n)
		{
			return __stl_prime_list[i];
		}
	}

	return -1;
}
  • __stl_num_primes 定义了一个常量数组，其中包含了一系列素数值。这些素数值是经过精心选择的，用于在数据结构的容量扩展时作为新容量的候选值。
  • 函数首先遍历这个素数数组，找到第一个大于给定数 n 的素数，并返回它。这个操作保证了容器的大小总是选择了一个足够大的素数，以降低哈希冲突的概率。
  • 如果没有找到适合的素数，函数返回 -1，这表示发生了异常情况，可以根据需要进行错误处理。

这个函数的主要目的是为了优化哈希表的性能，确保它的容量总是选择一个适当的素数，以提高哈希算法的效率(参考STL源码)。

修改insert函数

pair<iterator, bool> Insert(const T& data)
{
	Hash hash;
	KeyOfT kot;

	// 去重
	iterator ret = Find(kot(data));
	if (ret != end())
	{
		return make_pair(ret, false);
	}

	// 负载因子到1就扩容
	if (_size == _tables.size())
	{
		vector<Node*> newTables;
		newTables.resize(__stl_next_prime(_tables.size()), nullptr);
		// 旧表中节点移动映射新表
		for (size_t i = 0; i < _tables.size(); ++i)
		{
			Node* cur = _tables[i];
			while (cur)
			{
				Node* next = cur->_next;

				size_t hashi = hash(kot(cur->_data)) % newTables.size();
				cur->_next = newTables[hashi];
				newTables[hashi] = cur;

				cur = next;
			}

			_tables[i] = nullptr;
		}

		_tables.swap(newTables);
	}

	size_t hashi = hash(kot(data)) % _tables.size();
	// 头插
	Node* newnode = new Node(data);
	newnode->_next = _tables[hashi];
	_tables[hashi] = newnode;
	++_size;

	return make_pair(iterator(newnode, this), true);
}
  1. 首先，代码创建了一个 Hash 和一个 KeyOfT 的实例，这是为了获取键的哈希值和键本身。
  2. 接下来，代码通过调用 Find(kot(data)) 函数来检查是否已经存在具有相同键的元素。如果找到了相同的键，就不进行插入操作，而是返回一个 pair，其中 iterator 部分指向已存在的元素，而 bool 部分设置为 false 表示插入失败。
  3. 如果没有找到相同的键，就会继续进行插入操作。首先，代码检查当前哈希表的负载因子是否达到了1（即元素个数等于哈希表大小），如果是的话，就需要进行扩容操作。
  4. 扩容操作会创建一个新的哈希表 newTables，其大小通过调用 __stl_next_prime(_tables.size()) 来确定，这确保了新的表大小是一个素数。然后，代码会遍历旧的哈希表，将每个节点重新映射到新的哈希表中。这是为了保持哈希表的均匀分布和减少哈希冲突的可能性。
  5. 最后，代码计算待插入元素的哈希值，并将新节点插入到新的哈希表中。这是通过在头部插入方式实现的，新节点的 _next 指针指向当前桶的头节点，然后更新当前桶的头节点为新节点。同时，元素个数 _size 会增加 1。
  6. 最终，代码返回一个 pair，其中 iterator 部分指向新插入的元素，而 bool 部分设置为 true 表示插入成功。

添加桶函数

size_t Size()
{
	return _size;
}

// 表的长度
size_t TablesSize()
{
	return _tables.size();
}

// 桶的个数
size_t BucketNum()
{
	size_t num = 0;
	for (size_t i = 0; i < _tables.size(); ++i)
	{
		if (_tables[i])
		{
			++num;
		}
	}

	return num;
}

size_t MaxBucketLenth()
{
	size_t maxLen = 0;
	for (size_t i = 0; i < _tables.size(); ++i)
	{
		size_t len = 0;
		Node* cur = _tables[i];
		while (cur)
		{
			++len;
			cur = cur->_next;
		}

		if (len > maxLen)
		{
			maxLen = len;
		}
	}

	return maxLen;
}
  1. Size(): 这个函数返回哈希表中元素的总数量，即哈希表的大小。
  2. TablesSize(): 此函数返回哈希表内部存储桶的数量，也就是哈希表的实际大小。
  3. BucketNum(): 这个函数用于计算当前哈希表中非空桶的数量，也就是包含元素的桶的个数。
  4. MaxBucketLenth(): 此函数用于查找哈希表中最长桶的长度，也就是具有最多元素的桶中元素的数量。

修改后HashTable.h全部代码

#pragma once
#include<iostream>
#include<utility>
#include<vector>
#include<string>
using namespace std;
template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t val = 0;
		for (auto ch : key)
		{
			val *= 131;
			val += ch;
		}

		return val;
	}
};
namespace Bucket
{
	template<class T>
	struct HashNode
	{
		T _data;
		HashNode<T>* _next;

		HashNode(const T& data)
			:_data(data)
			, _next(nullptr)
		{}
	};

	// 前置声明
	template<class K, class T, class Hash, class KeyOfT>
	class HashTable;

	template<class K, class T, class Hash, class KeyOfT>
	struct __HashIterator
	{
		typedef HashNode<T> Node;
		typedef HashTable<K, T, Hash, KeyOfT> HT;
		typedef __HashIterator<K, T, Hash, KeyOfT> Self;

		Node* _node;
		HT* _pht;

		__HashIterator(Node* node, HT* pht)
			:_node(node)
			, _pht(pht)
		{}

		T& operator*()
		{
			return _node->_data;
		}

		T* operator->()
		{
			return &_node->_data;
		}

		Self& operator++()
		{
			if (_node->_next)
			{
				// 当前桶中迭代
				_node = _node->_next;
			}
			else
			{
				// 找下一个桶
				Hash hash;
				KeyOfT kot;
				size_t i = hash(kot(_node->_data)) % _pht->_tables.size();
				++i;
				for (; i < _pht->_tables.size(); ++i)
				{
					if (_pht->_tables[i])
					{
						_node = _pht->_tables[i];
						break;
					}
				}

				// 说明后面没有有数据的桶了
				if (i == _pht->_tables.size())
				{
					_node = nullptr;
				}
			}

			return *this;
		}

		bool operator!=(const Self& s) const
		{
			return _node != s._node;
		}

		bool operator==(const Self& s) const
		{
			return _node == s._node;
		}
	};

	template<class K, class T, class Hash, class KeyOfT>
	class HashTable
	{
		typedef HashNode<T> Node;

		template<class K, class T, class Hash, class KeyOfT>
		friend struct __HashIterator;
	public:
		typedef __HashIterator<K, T, Hash, KeyOfT> iterator;

		iterator begin()
		{
			for (size_t i = 0; i < _tables.size(); ++i)
			{
				if (_tables[i])
				{
					return iterator(_tables[i], this);
				}
			}

			return end();
		}

		iterator end()
		{
			return iterator(nullptr, this);
		}

		~HashTable()
		{
			for (size_t i = 0; i < _tables.size(); ++i)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
		}

		inline size_t __stl_next_prime(size_t n)
		{
			static const size_t __stl_num_primes = 28;
			static const size_t __stl_prime_list[__stl_num_primes] =
			{
				53, 97, 193, 389, 769,
				1543, 3079, 6151, 12289, 24593,
				49157, 98317, 196613, 393241, 786433,
				1572869, 3145739, 6291469, 12582917, 25165843,
				50331653, 100663319, 201326611, 402653189, 805306457,
				1610612741, 3221225473, 4294967291
			};

			for (size_t i = 0; i < __stl_num_primes; ++i)
			{
				if (__stl_prime_list[i] > n)
				{
					return __stl_prime_list[i];
				}
			}

			return -1;
		}

		pair<iterator, bool> Insert(const T& data)
		{
			Hash hash;
			KeyOfT kot;

			// 去重
			iterator ret = Find(kot(data));
			if (ret != end())
			{
				return make_pair(ret, false);
			}

			// 负载因子到1就扩容
			if (_size == _tables.size())
			{
				vector<Node*> newTables;
				newTables.resize(__stl_next_prime(_tables.size()), nullptr);
				// 旧表中节点移动映射新表
				for (size_t i = 0; i < _tables.size(); ++i)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;

						size_t hashi = hash(kot(cur->_data)) % newTables.size();
						cur->_next = newTables[hashi];
						newTables[hashi] = cur;

						cur = next;
					}

					_tables[i] = nullptr;
				}

				_tables.swap(newTables);
			}

			size_t hashi = hash(kot(data)) % _tables.size();
			// 头插
			Node* newnode = new Node(data);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_size;

			return make_pair(iterator(newnode, this), true);
		}

		iterator Find(const K& key)
		{
			if (_tables.size() == 0)
			{
				return end();
			}

			Hash hash;
			KeyOfT kot;
			size_t hashi = hash(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					return iterator(cur, this);
				}

				cur = cur->_next;
			}

			return end();
		}

		bool Erase(const K& key)
		{
			if (_tables.size() == 0)
			{
				return false;
			}

			Hash hash;
			KeyOfT kot;
			size_t hashi = hash(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					// 1、头删
					// 2、中间删
					if (prev == nullptr)
					{
						_tables[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}

					delete cur;
					--_size;

					return true;
				}

				prev = cur;
				cur = cur->_next;
			}

			return false;
		}

		size_t Size()
		{
			return _size;
		}

		// 表的长度
		size_t TablesSize()
		{
			return _tables.size();
		}

		// 桶的个数
		size_t BucketNum()
		{
			size_t num = 0;
			for (size_t i = 0; i < _tables.size(); ++i)
			{
				if (_tables[i])
				{
					++num;
				}
			}

			return num;
		}

		size_t MaxBucketLenth()
		{
			size_t maxLen = 0;
			for (size_t i = 0; i < _tables.size(); ++i)
			{
				size_t len = 0;
				Node* cur = _tables[i];
				while (cur)
				{
					++len;
					cur = cur->_next;
				}

				if (len > maxLen)
				{
					maxLen = len;
				}
			}

			return maxLen;
		}

	private:
		vector<Node*> _tables;
		size_t _size = 0; // 存储有效数据个数
	};
};

利用哈希表封装实现unordered_map

#pragma once
#include "HashTable.h"

namespace yulao
{
	template<class K, class V, class Hash = HashFunc<K>>
	class unordered_map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename Bucket::HashTable<K, pair<K, V>, Hash, MapKeyOfT>::iterator iterator;

		iterator begin()
		{
			return _ht.begin();
		}

		iterator end()
		{
			return _ht.end();
		}

		pair<iterator, bool> Insert(const pair<K, V>& kv)
		{
			return _ht.Insert(kv);
		}

		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
			return ret.first->second;
		}

	private:
		Bucket::HashTable<K, pair<K, V>, Hash, MapKeyOfT> _ht;
	};
}

这里我们就将unordered_map的基础功能简易实现完毕啦！！！文章来源地址https://www.toymoban.com/news/detail-722261.html

到了这里，关于一篇文章让你熟悉unordered_map及其模拟实现的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 这篇文章，让你了解ERC-1155 多代币标准协议

    用于多种代币管理的合约标准接口。 单个部署的合约可以包括同质化代币、非同质化代币或其他配置（如半同质化代币）的任何组合。 ERC1155 的显着特点是它使用单个智能合约一次代表多个代币。这就是为什么它的balanceOf功能不同于 ERC20 和 ERC777 的原因：它有一个额外的id参

    2024年02月01日
    浏览(50)
  • Hive详解（一篇文章让你彻底学会Hive）

    Hive详解（一篇文章让你彻底学会Hive）

    概述 Hive是由Facebook(脸书)开发的后来贡献给了Apache的一套数据仓库管理工具，针对海量的结构化数据提供了读、写和管理的功能。 图-1 Hive图标 Hive本身是基于Hadoop，提供了类SQL(Hive Query Language，简称为HQL)语言来操作HDFS上的数据，而底层实际上是将用户书写的SQL转化为了MapR

    2024年04月12日
    浏览(47)
  • 通过一篇文章让你了解Linux的重要性

    通过一篇文章让你了解Linux的重要性

    Linux是一种自由和开放源代码的操作系统，由林纳斯·托瓦兹于1991年首次发布。它基于Unix，具有模块化设计，支持多任务和多用户，能在多种硬件平台上运行。Linux系统在全球范围内得到广泛应用，包括服务器、移动设备、嵌入式系统等领域。其强大的功能、稳定性和安全性

    2024年04月15日
    浏览(37)
  • C++初阶之一篇文章让你掌握vector（模拟实现）

    C++初阶之一篇文章让你掌握vector（模拟实现）

    模拟实现vector是为了深入理解和学习C++标准库中vector容器的工作原理和实现细节。 vector是C++标准库中最常用的容器之一，它提供了动态数组的功能，并且具有自动扩容和内存管理的特性，使得在使用时非常方便。 模拟实现vector有以下几个优点： 学习数据结构与算法 ：实现

    2024年02月14日
    浏览(46)

  • 一篇文章让你彻底了解vuex的使用及原理（上）

    文章讲解的 Vuex 的版本为 4.1.0 ，会根据一些 api 来深入源码讲解，帮助大家更快掌握 vuex 的使用。 使用 Vue 实例的 use 方法把 Vuex 实例注入到 Vue 实例中。 use 方法执行的是插件的中的 install 方法 src/store.js 从上面可以看到 Vue 实例通过 provide 方法把 store 实例 provide 到了根实例

    2023年04月23日
    浏览(60)
  • 一篇文章让你了解ADAS-HIL测试方案

    一篇文章让你了解ADAS-HIL测试方案

    ADA S （Advanced Driber Assistant System），高级驾驶辅助系统， 先进驾驶辅 助系统，作用于辅助汽车驾驶，通过感知、决策和执行，帮助驾驶员察觉可能发生的危险，是提高安全性的主动安全技术，保障行驶安全，已成当前汽车装载必备系统；并普遍认为是实现自动驾驶AD的过程性

    2023年04月08日
    浏览(39)
  • FPGA入门有多难?这篇文章让你吃透零基础入门技巧！

    FPGA入门有多难?这篇文章让你吃透零基础入门技巧！

    FPGA是一个高度集成化的芯片，其学习过程既需要编程，又需要弄懂硬件电路和计算机架构。涉及到的知识和基础非常多， 如果不合理地安排学习内容，学习过程会非常漫长和枯燥 。这使很多想要学习FPGA小伙伴望而却步，那么，**FPGA到底有多难入门？**今天移知教育小编就带

    2024年02月04日
    浏览(53)
  • C++初阶之一篇文章让你掌握vector（理解和使用）

    C++初阶之一篇文章让你掌握vector（理解和使用）

    在C++中，std::vector是标准模板库（STL）中的一种动态数组容器，它可以存储任意类型的元素，并且能够自动调整大小。std::vector提供了许多方便的成员函数，使得对数组的操作更加简单和高效。 vector声明 ： template class T, class Alloc = allocatorT ; 这是 std::vector 的一般模板定义。它

    2024年02月14日
    浏览(50)

  • 一篇文章让你弄懂分布式一致性协议Paxos

    Paxos算法由Leslie Lamport在1990年提出，它是少数在工程实践中被证实的强一致性、高可用、去中心的分布式协议。Paxos协议用于在多个副本之间在有限时间内对某个决议达成共识。Paxos协议运行在允许消息重复、丢失、延迟或乱序，但没有拜占庭式错误的网络环境中，它利用“大

    2024年02月09日
    浏览(44)
  • C++初阶之一篇文章让你掌握string类（模拟实现）

    C++初阶之一篇文章让你掌握string类（模拟实现）

    模拟实现 std::string 是一个有挑战性的练习，它可以带来多方面的收益，尤其对于学习 C++ 和深入了解字符串操作以及动态内存管理的机制。以下是模拟实现 std::string 的一些好处和重要意义： 学习 C++ 内存管理 ：std::string 是一个动态分配内存的容器，模拟实现需要手动处理内

    2024年02月15日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包