C++ 容器中map和unordered map区别详解
极智视界 人气:0C++ 中 map 和 unordered_map区别
map 和 unordered_map 都可以看做是一种 key-value
的映射关系,unordered_map 可以理解为 无序版的map。unordered_map 是在 C++11 标准才出现的,所以你在代码中如果使用了 unordered_map,则在编译的时候要使用 c++11及以后的标准 进行编译。
这里直击要点:
- map 底层是 红黑树,(1) 增、删、改、查都是十分平稳的
log(n)
的复杂度,(2) 基于二叉查找树,数据是有序排列的 (按 key 排序)。在存储上 map 比较占用空间,因为在红黑树中,每一个节点都要额外保存父节点和子节点的连接,因此使得每一个节点都占用较大空间来维护红黑树的性质。 - unordered_map 底层是 hash表, 其查找的复杂度是常数级别的
O(1)
,构造的时候如果有冲突时间成本会增加,并且做不到数据有序排列。冲突的解决:当冲突数小于8的时候用链式地址法解决冲突,当冲突大于8的时候使用红黑树解决冲突。
来把区别用表格展示:
map 和 unordered_map 在代码使用上十分类似,来看看两者的用法:
int main(){ //// map 用法 map<int, string> _ismap; // 增的三种方法 _ismap.insert(make_pair(0, "kobe")); _ismap[1] = "james"; _ismap.insert(map<int, string>::value_type(2, "curry")); // 遍历 for (auto &iter : _ismap){ cout << iter.first << " : " << iter.second << endl; /* * 输出如下 按key递增排序 * 0 : kobe * 1 : james * 2 : curry */ } // 删除 map<int, string> ::iterator _mapIter = _ismap.find(0); _ismap.erase(_mapIter); // 删除指定的key // _ismap.erase(0); // 删除key=0的键值对 // _ismap.erase(std::begin(_ismap)); // 删除第一个键值对 //// unordered_map 用法 unordered_map<int, string> _isunorderedMap; // 增的三种方法 _isunorderedMap.insert(make_pair(0, "yaoming")); _isunorderedMap[1] = "yi"; _isunorderedMap.insert(unordered_map<int, string>::value_type(2, "zhouqi")); // 遍历 for (auto iter = unorderedMap.begin(); iter != unorderedMap.end(); iter++){ cout << iter->first << " : " << iter->second << endl; /* * 输出如下 乱序 * 2 : zhouqi * 0 : yaoming * 1 : yi */ // 删除 auto _unorderedIter = _isunorderedMap.find(0); _isunorderedMap.erase(_unorderedIter); // 删除指定的key // _unorderedIter.erase(0); // 删除key=0的键值对 // _unorderedIter(_unorderedIter.begin()); // 删除第一个键值对 } }
加载全部内容