往期汇总:
C++STL(1) vector容器汇总
C++STL(2) list容器汇总
C++STL(3) queue容器汇总
C++STL(4) stack容器汇总
C++STL(5) set容器汇总
C++STL(6) map容器汇总
C++STL(7) unordered_map容器汇总
C++STL(7) unordered_map容器汇总
在C++
中,哈希表(Hash Table)的实现是通过标准库中的std::unordered_map
来实现的。std::unordered_map
是C++11引入的关联容器,基于哈希表(Hash Table)实现。
哈希表是一种使用哈希函数将键映射到存储桶(bucket)的数据结构,以实现快速的插入、删除和查找操作。std::unordered_map
提供了类似于std::map
的接口,但是不保持元素的顺序。
以下是std::unordered_map
的一些常用操作和特点:
- 插入元素:可以使用
insert
函数或者使用插入操作符[]
来插入键值对。
std::unordered_map<int, std::string> myMap;
myMap.insert(std::make_pair(1, "One"));
myMap[2] = "Two";
- 访问和修改元素:可以使用键来访问对应的值,并进行修改。
std::unordered_map<int, std::string> myMap;
myMap[1] = "One";
std::cout << myMap[1] << std::endl; // 输出 "One"
myMap[1] = "New One";
std::cout << myMap[1] << std::endl; // 输出 "New One"
- 删除元素:可以使用
erase
函数通过键来删除元素。
std::unordered_map<int, std::string> myMap;
myMap[1] = "One";
myMap[2] = "Two";
myMap.erase(2);
- 查找元素:可以使用
find
函数来查找元素。
cpp
std::unordered_map<int, std::string> myMap;
myMap[1] = "One";
auto it = myMap.find(1);
if (it != myMap.end()) {
std::cout << "Found: " << it->second << std::endl;
}
- 哈希函数:
std::unordered_map
使用键的哈希函数来确定元素在哈希表中的位置。可以自定义哈希函数来处理自定义类型的键。
std::unordered_map
提供了高效的插入、删除和查找操作,平均情况下的复杂度为常数时间O(1)。然而,它的元素顺序是不确定的,这在某些情况下可能是一个限制。如果您需要有序性或按照特定顺序访问元素,可以考虑使用std::map
。
请注意,std::unordered_map
是通过哈希表实现的,而不是红黑树(std::map
的底层数据结构)。因此,在某些情况下,哈希表的性能可能更好,但它可能会消耗更多的内存来存储哈希函数和桶结构。
-
大小和容量:
-
size
:返回std::unordered_map
中键值对的数量。 empty
:检查std::unordered_map
是否为空。-
max_size
:返回std::unordered_map
可以容纳的最大键值对数量。 -
遍历元素:
-
使用迭代器:可以使用迭代器遍历
std::unordered_map
中的键值对。
std::unordered_map<int, std::string> myMap = {{1, "One"}, {2, "Two"}, {3, "Three"}};
for (auto it = myMap.begin(); it != myMap.end(); ++it) {
std::cout << it->first << ": " << it->second << std::endl;
}
- 使用范围-based for 循环:C++11引入的范围-based for 循环可以更方便地遍历键值对。
std::unordered_map<int, std::string> myMap = {{1, "One"}, {2, "Two"}, {3, "Three"}};
for (const auto& pair : myMap) {
std::cout << pair.first << ": " << pair.second << std::endl;
}
-
桶操作:
-
bucket_count
:返回std::unordered_map
中桶的数量。 bucket_size
:返回指定桶中键值对的数量。bucket
:返回给定键的桶号。
std::unordered_map<int, std::string> myMap = {{1, "One"}, {2, "Two"}, {3, "Three"}};
size_t bucket = myMap.bucket(2);
std::cout << "Bucket for key 2: " << bucket << std::endl;
-
哈希策略:
-
hash_function
:返回用于计算键的哈希值的函数对象。 load_factor
:返回当前的负载因子(平均桶的大小)。rehash
:重新分配内存以适应指定数量的桶。
std::unordered_map<int, std::string> myMap = {{1, "One"}, {2, "Two"}, {3, "Three"}};
size_t numBuckets = myMap.bucket_count();
std::cout << "Current number of buckets: " << numBuckets << std::endl;
myMap.rehash(10);
numBuckets = myMap.bucket_count();
std::cout << "New number of buckets: " << numBuckets << std::endl;
- 自定义哈希函数:您可以为自定义类型提供自定义的哈希函数,以便在
std::unordered_map
中使用。
struct MyStruct {
int key;
std::string value;
};
struct MyHash {
std::size_t operator()(const MyStruct& obj) const {
// 自定义哈希函数的实现...
}
};
std::unordered_map<MyStruct, int, MyHash> myMap;
这些是std::unordered_map
的一些常用操作和功能。std::unordered_map
提供了高效的插入、删除和查找操作,并且在平均情况下具有常数时间复杂度。它是处理大量数据和需要快速查找的情况下的常用选择。根据您的特定需求,您可以选择适当的操作和功能来使用std::unordered_map
。std::unordered_map
提供了几种插入和删除元素的方式。以下是常用的插入和删除操作:
插入元素:
- 使用
insert
函数:可以使用insert
函数插入新的键值对。插入操作会创建一个新的键值对,并将其插入到std::unordered_map
中。
std::unordered_map<int, std::string> myMap;
// 使用 insert 函数插入键值对
myMap.insert(std::make_pair(1, "One"));
// 使用值初始化列表插入键值对(C++11及以上版本)
myMap.insert({2, "Two"});
// 使用 std::pair 的构造函数插入键值对
myMap.insert(std::pair<int, std::string>(3, "Three"));
- 使用插入操作符
[]
:可以使用插入操作符[]
来插入键值对。如果键不存在,则会创建一个新的键值对,并将其插入到std::unordered_map
中;如果键已经存在,则会更新对应的值。
std::unordered_map<int, std::string> myMap;
// 使用插入操作符[]插入键值对
myMap[1] = "One";
myMap[2] = "Two";
myMap[3] = "Three";
删除元素:
- 使用
erase
函数:可以使用erase
函数通过键来删除指定的键值对。
std::unordered_map<int, std::string> myMap = {{1, "One"}, {2, "Two"}, {3, "Three"}};
// 通过键删除指定的键值对
myMap.erase(2);
- 使用迭代器:可以使用迭代器来删除指定位置的键值对。迭代器指向要删除的键值对。
std::unordered_map<int, std::string> myMap = {{1, "One"}, {2, "Two"}, {3, "Three"}};
// 查找要删除的键值对的迭代器
auto it = myMap.find(2);
// 删除指定位置的键值对
if (it != myMap.end()) {
myMap.erase(it);
}
- 清空容器:可以使用
clear
函数清空整个std::unordered_map
,删除所有的键值对。
std::unordered_map<int, std::string> myMap = {{1, "One"}, {2, "Two"}, {3, "Three"}};
// 清空整个 unordered_map
myMap.clear();
这些是std::unordered_map
的常用插入和删除操作。插入操作可以使用insert
函数或插入操作符[]
,而删除操作可以使用erase
函数或迭代器。
std::unordered_map
和std::map
是C++标准库中的两个关联容器,它们之间有几个重要的区别:
- 底层数据结构:
std::unordered_map
:使用哈希表(hash table)实现,通过哈希函数将键映射到桶(bucket)上,提供了快速的查找、插入和删除操作。元素在容器中的存储位置并不按照键的顺序排列。-
std::map
:使用平衡二叉搜索树(balanced binary search tree,通常是红黑树)实现,保持键的有序性,在插入和删除时会进行平衡操作以保持树的平衡。元素在容器中按照键的顺序排列。 -
元素顺序:
std::unordered_map
:元素在容器中的存储顺序是不确定的,取决于哈希函数和桶的布局。因此,不能按照插入顺序或键的顺序进行迭代。-
std::map
:元素在容器中按照键的顺序进行排序,可以根据键的顺序进行迭代。 -
查找性能:
std::unordered_map
:通过哈希函数进行查找,平均情况下具有常数时间复杂度(O(1)),最坏情况下的时间复杂度为O(n),其中n是键值对的数量。-
std::map
:通过平衡二叉搜索树进行查找,具有对数时间复杂度(O(log n)),其中n是键值对的数量。在大多数情况下,查找速度比std::unordered_map
慢。 -
内存占用:
std::unordered_map
:由于哈希表的布局,可能需要更多的内存来存储桶和哈希冲突的解决方案。因此,它通常比std::map
使用更多的内存。std::map
:使用平衡二叉搜索树,不需要额外的哈希表和冲突解决方案,因此通常比std::unordered_map
使用更少的内存。
根据上述区别,您可以根据具体的需求来选择使用std::unordered_map
还是std::map
。如果您需要快速的查找、插入和删除操作,并且元素的顺序不重要,可以选择std::unordered_map
。如果您需要按照键的顺序进行迭代,或者在有序的键集合上进行操作,可以选择std::map
。