一、unordered_map排序
unordered_map是C++11新增的容器之一,它不像map有排序功能。但是我们仍然可以通过一些方法对unordered_map进行排序:
1. 使用pair对unordered_map进行排序
// 使用pair对unordered_map进行排序
#include
#include
#include
using namespace std;
int main(){
unordered_map
umap = {{2, 3}, {1, 4}, {7, 6}, {4, 1}, {3, 2}};
auto cmp = [](const pair
&a, const pair
&b) { return a.second < b.second; }; vector
> vec(umap.begin(), umap.end()); sort(vec.begin(), vec.end(), cmp); for(auto &it : vec){ cout << it.first << ": " << it.second << endl; } return 0; }
2. 使用结构体对unordered_map进行排序
// 使用结构体对unordered_map进行排序
#include
#include
#include
using namespace std;
struct compare{
bool operator()(const pair
&a, const pair
&b) { return a.second < b.second; } }; int main(){ unordered_map
umap = {{2, 3}, {1, 4}, {7, 6}, {4, 1}, {3, 2}}; set
, compare> sorted_set(umap.begin(), umap.end()); for(auto &it : sorted_set){ cout << it.first << ": " << it.second << endl; } return 0; }
二、unordered_map自定义类型
unordered_map不仅可以对基本类型进行使用,也可以使用自定义类型。自定义类型作为key时,需要重载hash函数和==运算符。
// unordered_map自定义类型
#include
#include
using namespace std;
struct Book {
string name;
int price;
};
struct HashFunc {
size_t operator() (const Book &book) const {
return hash
() (book.name) ^ hash
() (book.price);
}
};
struct EqualKey {
bool operator() (const Book &a, const Book &b) const {
return a.name == b.name && a.price == b.price;
}
};
int main() {
unordered_map
myMap; myMap[{"C++ Primer", 88}] = 100; myMap[{"Computer Network", 59}] = 50; for(auto &bookPrice : myMap) { cout << bookPrice.first.name << " " << bookPrice.first.price << " " << bookPrice.second << endl; } return 0; }
三、unordered_map用法
1. unordered_map基本操作
unordered_map和其他STL容器使用方法类似,包括插入,访问,删除,迭代等等
#include
#include
using namespace std;
int main(){
unordered_map
myMap; // 定义unordered_map
myMap.insert({1, 2}); // 插入{1, 2}
myMap.emplace(2, 3); // 插入{2, 3}
myMap[3] = 4; // 插入{3, 4}
// 判断key是否存在
if(myMap.count(1))
cout << "Key 1 exists" << endl;
// 删除一个键值对
myMap.erase(2);
// 迭代输出
for(auto &it: myMap)
cout << it.first << ": " << it.second << endl;
return 0;
}
2. unordered_map查找
unordered_map提供了一些方法查找元素。其中find()和count()方法比较常用。find()返回一个迭代器,count()返回一个bool类型的值,表示key是否存在。
// unordered_map查找
#include
#include
using namespace std;
int main() {
unordered_map
myMap = {{1, 2}, {2, 4}, {3, 6}};
// find()方法
if(myMap.find(2) != myMap.end())
cout << "The value of key 2 is " << myMap.find(2)->second << endl;
// count()方法
if(myMap.count(3))
cout << "Key 3 exists." << endl;
return 0;
}
四、unordered_map性能
unordered_map在插入、查找、删除元素的时间复杂度都是O(1)的,与元素数量无关,因此性能非常高。
以插入为例,下面是一个比较unordered_map和map插入速度的例子:
#include
#include
五、map和unordered_map的区别
二者最主要的区别在于内部实现的数据结构不同。map使用红黑树实现,因此元素按照key的大小排列,而unordered_map使用哈希表实现,因此元素的顺序是无序的。
二者在性能方面也有所不同。在查找、插入、删除元素时,unordered_map的时间复杂度都是O(1),而map的时间复杂度是O(logN)。
六、unordered_map底层实现
unordered_map的底层实现使用了哈希表。哈希表包含一个数组和一个哈希函数,哈希函数将元素映射到数组中的一个索引位置。如果两个元素的哈希值相同,那么它们会被映射到数组中同一个索引位置,因此哈希表需要解决冲突的问题。
解决冲突的方式有很多种,其中最常见的是链表法。如果一个索引位置上已经有元素了,那么新元素会被插入到这个元素的链表中。如果链表过长,会影响unordered_map的性能,因此C++11引入了基于哈希表的高质量实现——robin hood hashing。
七、unordered_map和map
unordered_map和map提供了类似的功能,二者都可以插入、查找、删除元素。unordered_map在元素数量较大时性能比map更高,而map保证元素按照key的大小排序。
除了性能和元素排序方式的不同之外,二者的使用方法几乎一样,因此可以根据实际需要选择使用哪一个容器。
八、unordered_map输出
unordered_map可以通过迭代器输出全部元素。如果需要将unordered_map转换为vector,可以使用vector的初始化器列表(initializer list):vector
// unordered_map输出
#include
#include
#include
// make_pair()
using namespace std;
int main(){
unordered_map
myMap = {{1, 2}, {2, 4}, {3, 6}};
for(auto & it : myMap){
cout << it.first << ": " << it.second << endl;
}
// 转换为vector
vector
> vec(myMap.begin(), myMap.end()); for(auto & it : vec){ cout << it.first << ": " << it.second << endl; } return 0; }
九、c++ unordered_map
C++11引入了unordered_map,是一种基于哈希表的关联容器,可以对数据进行快速查找。
unordered_map的使用方法与STL中的其他容器类似,但由于其底层实现的差异,一些特性也有所不同。通过深入研究unordered_map的使用,可以让你更好地应用这个容器,从而更加高效地解决相关问题。