AI 助理
文档备案控制台
开发者社区 云原生 文章 正文

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

2023-10-11 782
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： unordered_map的定义哈希表在 C++ 标准库中的实现有一段历史。在 C++98/03 标准中，没有正式定义标准的哈希表容器。不

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构造函数

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。
  1. 使用分配器的构造函数 (1)：
  • explicit unordered_map ( const allocator_type& alloc );
  • 创建一个空的 unordered_map，使用指定的分配器 alloc。
  1. 范围构造函数 (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。
  1. 拷贝构造函数 (3)：
  • unordered_map ( const unordered_map& ump );
  • 创建一个新的 unordered_map，并使用另一个 unordered_mapump 中的内容进行拷贝构造。
  • unordered_map ( const unordered_map& ump, const allocator_type& alloc );
  • 创建一个新的 unordered_map，并使用另一个 unordered_mapump 中的内容进行拷贝构造，同时指定分配器 alloc。
  1. 移动构造函数 (4)：
  • unordered_map ( unordered_map&& ump );
  • 创建一个新的 unordered_map，并从另一个 unordered_mapump 中移动内容。
  • unordered_map ( unordered_map&& ump, const allocator_type& alloc );
  • 创建一个新的 unordered_map，并从另一个 unordered_mapump 中移动内容，同时指定分配器 alloc。
  1. 初始化列表构造函数 (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。
  1. 移动赋值操作符 (2)：
  • unordered_map& operator= (unordered_map&& ump);
  • 将一个已存在的 std::unordered_map 的内容移动给另一个已存在的 std::unordered_map。这个操作会将原有的 std::unordered_map 置为有效但不再可用的状态。
  1. 初始化列表赋值操作符 (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。该函数是不会抛出异常的。
  1. size() 函数:
  • size_type size() const noexcept;
  • 返回 std::unordered_map 中存储的键值对的数量。即返回哈希表的大小。如果哈希表为空，则返回 0。该函数是不会抛出异常的。
  1. 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 的第一个元素（键值对）的迭代器。第一个版本返回非常量迭代器，而第二个版本返回常量迭代器。这些函数是不会抛出异常的。
  1. 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 的尾部（末尾）的迭代器。第一个版本返回非常量迭代器，而第二个版本返回常量迭代器。这些函数是不会抛出异常的。
  1. 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 的第一个元素（键值对）的常量迭代器。它允许对哈希表进行只读遍历，不允许修改哈希表的内容。该函数是不会抛出异常的。
  1. 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 的尾部（末尾）的常量迭代器。它允许对哈希表进行只读遍历，不允许修改哈希表的内容。该函数是不会抛出异常的。
  1. 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 中的元素，确保不会修改哈希表的内容。

文章标签：
容器
C++
索引
存储
编译器
爱学习的鱼佬
目录
相关文章
泡沫o0
|
算法 编译器 程序员
【C/C++ 解惑 】 std::move 将左值转换为右值的背后发生了什么？
【C/C++ 解惑 】 std::move 将左值转换为右值的背后发生了什么？
泡沫o0
437 0
人才程序员
|
安全 C++
【C++11保姆级教程】移动构造函数（move constructor）和移动赋值操作符（move assignment operator）
【C++11保姆级教程】移动构造函数（move constructor）和移动赋值操作符（move assignment operator）
人才程序员
1932 0
Star时光
|
13天前
|
人工智能 智能硬件
告别“废话式”提问：让AI输出高质量答案的3个核心技巧
告别“废话式”提问：让AI输出高质量答案的3个核心技巧
Star时光
226 77
ali别离
|
人工智能 搜索推荐 异构计算
从HA3到AI·OS -- 全图化引擎破茧之路
ali别离
9099 0
hahaha无
|
10月前
|
存储 C++ 容器
unordered_set、unordered_multiset、unordered_map、unordered_multimap的介绍及使用
unordered_set是不按特定顺序存储键值的关联式容器，其允许通过键值快速的索引到对应的元素。在unordered_set中，元素的值同时也是唯一地标识它的key。在内部，unordered_set中的元素没有按照任何特定的顺序排序，为了能在常数范围内找到指定的key，unordered_set将相同哈希值的键值放在相同的桶中。unordered_set容器通过key访问单个元素要比set快，但它通常在遍历元素子集的范围迭代方面效率较低。它的迭代器至少是前向迭代器。前向迭代器的特性。
hahaha无
586 0
泡沫o0
|
算法 安全 C++
【C++ 泛型编程 入门篇】深入探索C++的numeric_limits：全面理解数值界限（一）
【C++ 泛型编程 入门篇】深入探索C++的numeric_limits：全面理解数值界限
泡沫o0
906 0
acw_ecd20250213
|
自然语言处理 测试技术 API
打通Agent最后一公里： 用阿里云无影AgentBay+LangChain实现浏览器自动化
langchain-agentbay-integration 是一个连接 LangChain 与阿里云无影 AgentBay 的工具包，支持浏览器自动化、代码执行等云端操作，助力开发者高效构建智能代理应用。
acw_ecd20250213
1485 0
打通Agent最后一公里： 用阿里云无影AgentBay+LangChain实现浏览器自动化
nanshaws
|
存储 Serverless C++
c++实现HashMap
这篇文章提供了一个用C++实现的简单HashMap类的示例代码，包括构造函数、put、get、remove和size方法，以及私有的hash函数，用于计算键的哈希值。该HashMap使用链地址法解决哈希冲突，适用于学习和理解哈希表的基本概念。
nanshaws
341 1
HermanYe996
|
算法 数据可视化 机器人
ROS2教程01 ROS2介绍
本文是ROS2（机器人操作系统的下一代）的介绍教程，内容包括ROS2的诞生背景、核心功能、特点、框架以及与ROS1的比较。文章涵盖了ROS2的通信系统、框架和工具、生态系统、全球性社区支持、完全开源、跨平台特性、多机协同能力、实时系统支持和更强的稳定性。此外，还提供了ROS2架构的详细介绍资源链接，适合对ROS2感兴趣的读者学习和了解。
HermanYe996
3442 1
菊头蝙蝠
|
C++
c++ unordered_map4种遍历方式
c++ unordered_map4种遍历方式
菊头蝙蝠
987 0

热门文章

最新文章

  • 1
    教你用Python发现即将流失的客户（附代码、安装教程、学习资源）
  • 2
    什么是缓存击穿？
  • 3
    tensorflow：流程，概念和简单代码注释
  • 4
    阿里云CDN加速和全站加速DCDN区别及如何选择？
  • 5
    iGraph 2015双促复盘总结
  • 6
    阿里云学生服务器购买价格及学生免费服务器配置领取条件
  • 7
    SpringCloud Alibaba - Nacos 作为配置中心 & 读取Properties配置信息
  • 8
    各大在线地图，使用的经纬度坐标为什么都精确到小数点之后第六位？
  • 9
    加载exe的PE信息并输出相关PE信息的一段c++代码
  • 10
    RhinoMock入门（7）——Do，With和Record-playback
  • 1
    Hermes Agent纯免费部署教程：适合新手尝鲜，阿里云提供ECS免费部署Hermes Agent
    45
  • 2
    新手也能搭！阿里云轻量服务器一键部署 Hermes Agent，开源自进化 AI 智能体
    78
  • 3
    Hermes Agent 部署教程：阿里云轻量服务器新手0基础搭建自进化AI智能体，太简单了
    91
  • 4
    超详细！Hermes Agent 一键部署全流程指南，轻松上手不踩坑
    242
  • 5
    普通摄像头秒变“透视仪”：黎曼分形透镜如何让微弱瑕疵无处遁形（军工项目之外研究）
    51
  • 6
    SpringBoot对接黄金白银期货数据API
    55
  • 7
    Maven 本地仓库替代私仓配置指南
    41
  • 8
    【SpringSecurity新手村系列】（4）验证码功能实现
    38
  • 9
    【SpringSecurity新手村系列】（3）自定义登录页与表单认证
    36
  • 10
    当旅行规划开始理解礼仪边界，Agent协同与​D​М‌X​Α‌РΙ才有用武之地
    45

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    开通oss服务