1. unordered_map
在头文件上,引入 <unordered_map>
来使用它。对于 unordered_map
而言,最大的特点在于内部实现上,使用到了哈希表(散列表、hash_table
)来进行映射存储,它的模板类声明及其参数如下:
/**
* 程序来自STL源码 bits/unordered_map.h
*/
template<typename _Key, // key 类型
typename _Tp, // value 类型
typename _Hash = hash <_Key>, // 哈希函数
typename _Pred = equal_to <_Key>, // 用于比较两者是否相同的函数
typename _Alloc = allocator <std::pair<const _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_map<int, string> unorderedMap;
// 三种插入新元素的方法,“茴”字有三种写法~
unorderedMap.insert(make_pair(0, "Alice"));
unorderedMap[1] = "Bob";
unorderedMap.insert(unordered_map<int, 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
*/
template<typename _Key, // key 类型
typename _Tp, // value 类型
typename _Compare = std::less<_Key>, // 用于比较两个元素的比较函数
typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > // 分配器,同样的描述了容器在内存管理上的细节,不应该自己来处理,除非写自己的容器
class map {
private:
/// 将一个红黑树转换成 [multi]map.
typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
rebind<value_type>::other _Pair_alloc_type;
typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
key_compare, _Pair_alloc_type> _Rep_type;
};
在 map
的内部,使用了红黑树(red-black tree
)来组织数据,因此默认的就已经实现了数据的排序。从下面例子中可以看出,它默认实现了在 key
上排序实现递增:
int main() {
map<int, string> mapper;
mapper.insert(make_pair(0, "Alice"));
mapper[1] = "Bob";
mapper.insert(map<int, 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_map |
map |
|
---|---|---|
查找 | 快,Average:O(1) ,Worst Case:O(n) |
恒定的 log(n) |
插入 | 和上面一样 | log(n) + 平衡二叉树所用时间 |
删除 | 还和上面一样 | log(n) + 平衡二叉树所用时间 |
是否排序 | 不排序 | 排序 |
实现方法 | 哈希表 | 红黑树 |
适用于 | 查找操作频率高 | 要求结果有序(按 key 排序) |