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

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），用于实现键值对的哈希表。下面是对该模板参数的解释：

Key：表示哈希表中的键类型，也就是用来查找值的类型。
T：表示哈希表中的值类型，即与键相关联的值的类型。
Hash：表示哈希函数的类型，用于计算键的哈希值。默认情况下，使用 std::hash<Key> 作为哈希函数。
Pred：表示键比较的谓词，用于确定两个键是否相等。默认情况下，使用 std::equal_to<Key> 作为键比较谓词。
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)：

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)：

explicit unordered_map ( const allocator_type& alloc );
创建一个空的 unordered_map，使用指定的分配器 alloc。

范围构造函数 (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。

拷贝构造函数 (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。

移动构造函数 (4)：

unordered_map ( unordered_map&& ump );
创建一个新的 unordered_map，并从另一个 unordered_mapump 中移动内容。
unordered_map ( unordered_map&& ump, const allocator_type& alloc );
创建一个新的 unordered_map，并从另一个 unordered_mapump 中移动内容，同时指定分配器 alloc。

初始化列表构造函数 (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)：

unordered_map& operator= (const unordered_map& ump);
将一个已存在的 std::unordered_map 的内容拷贝给另一个已存在的 std::unordered_map。

移动赋值操作符 (2)：

unordered_map& operator= (unordered_map&& ump);
将一个已存在的 std::unordered_map 的内容移动给另一个已存在的 std::unordered_map。这个操作会将原有的 std::unordered_map 置为有效但不再可用的状态。

初始化列表赋值操作符 (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）

empty() 函数:

bool empty() const noexcept;
用于检查 std::unordered_map 是否为空。如果哈希表中不包含任何键值对，则返回 true；否则返回 false。该函数是不会抛出异常的。

size() 函数:

size_type size() const noexcept;
返回 std::unordered_map 中存储的键值对的数量。即返回哈希表的大小。如果哈希表为空，则返回 0。该函数是不会抛出异常的。

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;

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

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

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;

end()函数 (容器迭代器):

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

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;

cbegin() 函数 (常量容器迭代器):

const_iterator cbegin() const noexcept;
这个函数返回一个指向 std::unordered_map 的第一个元素（键值对）的常量迭代器。它允许对哈希表进行只读遍历，不允许修改哈希表的内容。该函数是不会抛出异常的。

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;

cend() 函数 (常量容器迭代器):

const_iterator cend() const noexcept;
这个函数返回一个指向 std::unordered_map 的尾部（末尾）的常量迭代器。它允许对哈希表进行只读遍历，不允许修改哈希表的内容。该函数是不会抛出异常的。

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及其模拟实现（上）

unordered_map的定义

1. unordered_map的模板定义

2. unordered_map的成员类型

unordered_map构造函数

unordered_map赋值运算符重载

unordered_map容量函数（Capacity）

unordered_map迭代器（Iterators）

1. begin()

2. end()

3. cbegin()

4. cend()

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

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

unordered_map的定义

1. unordered_map的模板定义

2. unordered_map的成员类型

unordered_map构造函数

unordered_map赋值运算符重载

unordered_map容量函数（Capacity）

unordered_map迭代器（Iterators）

1. begin()

2. end()

3. cbegin()

4. cend()

热门文章

最新文章

相关电子书