南宁网站建设专家,长沙近期大型招聘会,免费公司建站,网站服务器类型unordered_map 类模板和 map 类模板都是描述了这么一个对象#xff1a;它是由 std::pairconst Key, value 组成的可变长容器#xff1b; 这个容器中每个元素存储两个对象#xff0c;也就是 key - value 对。 1. unordered_map 在头文件上#xff0c;引入 unor… unordered_map 类模板和 map 类模板都是描述了这么一个对象它是由 std::pairconst Key, value 组成的可变长容器 这个容器中每个元素存储两个对象也就是 key - value 对。 1. unordered_map 在头文件上引入 unordered_map 来使用它。对于 unordered_map 而言最大的特点在于内部实现上使用到了「哈希表」散列表、hash_table 来进行映射存储它的模板类声明及其参数如下 /*** 程序来自STL源码 bits/unordered_map.h*/
templatetypename _Key, // key 类型 typename _Tp, // value 类型typename _Hash hash _Key, // 哈希函数typename _Pred equal_to _Key, // 用于比较两者是否相同的函数typename _Alloc allocator std::pairconst _Key, _Tp // 分配器描述了容器在内存管理上的细节不应该自己来处理除非写自己的容器
class unordered_map {
}; 在 unordered_map 内部使用的 Hash Table 对数据进行组织通过把键值 key 映射到 hash 表中的一个位置进行访问根据 hash 函数的特点 unordered_map 对于元素查找的时间复杂度可以达到 O(1) 但是它的元素排列是无序的。具体例子如下 int main() {using namespace std;// 首先创建一个无序 map它的 key 使用 int 类型value 使用 string 类型unordered_mapint, string unorderedMap; // 三种插入新元素的方法“茴”字有三种写法~unorderedMap.insert(make_pair(0, Alice)); unorderedMap[1] Bob;unorderedMap.insert(unordered_mapint, string::value_type(2, Candy));// 对内部元素挨个输出for (auto iter unorderedMap.begin(); iter ! unorderedMap.end(); iter) {cout iter-first - iter-second endl;/** : 输出如下可以得知它们在 key 的排序上并没有顺序* 2 - Candy* 0 - Alice* 1 - Bob*/}
} unordered_map 由于建立了哈希表所以它在最开始建立的时候比较耗时间但是它查询速度快呀~一般情况下用 unordered_map 是没有问题的。 2. map 对于 map 而言首先在头文件上引用 map 进来然后使用。它的类模板声明以及部分函数声明如下 /*** 程序来自C源码 bits/stl_map.h*/
templatetypename _Key, // key 类型typename _Tp, // value 类型typename _Compare std::less_Key, // 用于比较两个元素的比较函数typename _Alloc std::allocatorstd::pairconst _Key, _Tp // 分配器同样的描述了容器在内存管理上的细节不应该自己来处理除非写自己的容器
class map {
private:/// 将一个红黑树转换成 [multi]map.typedef typename __gnu_cxx::__alloc_traits_Alloc::templaterebindvalue_type::other _Pair_alloc_type;typedef _Rb_treekey_type, value_type, _Select1stvalue_type,key_compare, _Pair_alloc_type _Rep_type;
}; 在 map 的内部使用了「红黑树」red-black tree来组织数据因此默认的就已经实现了数据的排序。从下面例子中可以看出它默认实现了在 key 上排序实现递增 int main() {mapint, string mapper;mapper.insert(make_pair(0, Alice));mapper[1] Bob;mapper.insert(mapint, string::value_type(2, Candy));for (auto iter : mapper) {cout iter.first - iter.second endl;/** : 输出如下很明显的它们在 key 的排序上是递增排列的* 0 - Alice* 1 - Bob* 2 - Candy*/}
} 不过在存储上 map 却比较占用空间因为在红黑树中每一个节点都要额外保存父节点和子节点的连接因此使得每一个节点都占用较大空间来维护红黑树性质。 3. 总结 两种数据结构特点如下表格~
unordered_mapmap查找快AverageO(1) Worst CaseO(n)恒定的 log(n)插入和上面一样log(n) 平衡二叉树所用时间删除和上面一样log(n) 平衡二叉树所用时间是否排序不排序排序实现方法哈希表红黑树适用于查找操作频率高要求结果有序(按key排序)
