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 中的元素，确保不会修改哈希表的内容。
