map unordered_map 性能
作者:
假如有点困
,
2024-07-19 16:19:38
,
所有人可见
,
阅读 10
unordered_map通常在性能上优于map,尤其是在查找、插入和删除操作方面。 这是因为:
map基于红黑树实现,保证了键值对的顺序,这使得遍历操作较为高效,但查找、插入和删除操作的时间复杂度为O(log n)。
unordered_map基于哈希表实现,不保证元素的顺序,理想情况下查找、插入和删除操作的时间复杂度为O(1)。虽然在哈希冲突较多的情况下,性能会下降至O(n),但通常通过再哈希等策略保持高效。
因此,如果不需要维护键的顺序,且关注快速的插入、删除和查找操作,unordered_map是更优的选择。如果需要保持键的顺序,或者频繁进行区间查找,则map更为合适。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
int main()
{
map<char,int> mp;
mp['b']=2;
mp['a']=1;
mp['c']=3;
for(auto [u,v]:mp){
cout<<u<<' '<<v<<endl;
}
return 0;
}
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
int main()
{
map<string,int> mp;
mp["bac"]=2;
mp["abc"]=1;
mp["cba"]=3;
for(auto [u,v]:mp){
cout<<u<<' '<<v<<endl;
}
return 0;
}
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
int main()
{
map<string,int> mp;
mp["abc"]=2;
mp["aac"]=1;
mp["aca"]=3;
for(auto [u,v]:mp){
cout<<u<<' '<<v<<endl;
}
return 0;
}