C++中的unordered_map和map区别

简介: `unordered_map` 类模板和 `map` 类模板都是描述了这么一个对象:它是由 `std::pair<const Key, value>` 组成的可变长容器,这个容器中每个元素存储两个对象,也就是 `key` - `value` 对。

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 排序)
目录
相关文章
|
26天前
|
存储 安全 编译器
在 C++中,引用和指针的区别
在C++中,引用和指针都是用于间接访问对象的工具,但它们有显著区别。引用是对象的别名,必须在定义时初始化且不可重新绑定;指针是一个变量,可以指向不同对象,也可为空。引用更安全,指针更灵活。
|
1月前
|
存储 JavaScript 前端开发
Set、Map、WeakSet 和 WeakMap 的区别
在 JavaScript 中,Set 和 Map 用于存储唯一值和键值对,支持多种操作方法,如添加、删除和检查元素。WeakSet 和 WeakMap 则存储弱引用的对象,有助于防止内存泄漏,适合特定场景使用。
|
1月前
|
C语言 C++
C 语言的关键字 static 和 C++ 的关键字 static 有什么区别
在C语言中,`static`关键字主要用于变量声明,使得该变量的作用域被限制在其被声明的函数内部,且在整个程序运行期间保留其值。而在C++中,除了继承了C的特性外,`static`还可以用于类成员,使该成员被所有类实例共享,同时在类外进行初始化。这使得C++中的`static`具有更广泛的应用场景,不仅限于控制变量的作用域和生存期。
53 10
|
1月前
|
存储 缓存 Java
【用Java学习数据结构系列】HashMap与TreeMap的区别,以及Map与Set的关系
【用Java学习数据结构系列】HashMap与TreeMap的区别,以及Map与Set的关系
35 1
WK
|
2月前
|
Python
map和filter的区别是什么
`map()`和`filter()`均为Python中的高阶函数,前者针对可迭代对象中的每个元素执行指定操作,如数值翻倍或字符串转大写;后者则筛选出符合条件的元素,例如仅保留偶数或非空字符串。两者均返回迭代器,并可通过`list()`等函数转换为所需的数据结构。具体使用时,应依据实际需求和场景选择合适的函数。
WK
18 1
|
1月前
|
C语言 C++
实现两个变量值的互换[C语言和C++的区别]
实现两个变量值的互换[C语言和C++的区别]
19 0
WK
|
2月前
map和filter的区别是什么
在编程中,`map` 和 `filter` 是处理数组或集合时常用的两个函数。`map` 用于将每个元素通过指定函数转换后生成新的数组,而 `filter` 则根据条件筛选出符合条件的元素组成新数组。两者的主要区别在于:`map` 的返回数组长度与原数组相同,但元素被转换;`filter` 的返回数组长度可能不同,只包含符合条件的元素。
WK
30 2
|
2月前
数组方法中的`forEach()`方法和`map()`方法有什么区别?
数组方法中的`forEach()`方法和`map()`方法有什么区别?
|
3月前
|
Java
【Java集合类面试二十二】、Map和Set有什么区别?
该CSDN博客文章讨论了Map和Set的区别,但提供的内容摘要并未直接解释这两种集合类型的差异。通常,Map是一种键值对集合,提供通过键快速检索值的能力,而Set是一个不允许重复元素的集合。
|
3月前
|
分布式计算 Serverless 数据处理