浅谈map和unordered_map的应用场景

map和unordered_map的适用场景

底层结构介绍

  • map底层是红黑树结构
  • unordered_map底层是哈希结构;
    在这里插入图片描述

Hash适用场景(unordered_map)

内存存角度来说hash因为底层维护了哈希表的存在,内存消耗远大于红黑树,但是因为哈希表增删查改时的直接映射,使其增删查效率来说可以做到平均O(1)常数级别时间复杂度(红黑树需要依次进行关键码比较,时间是logN的复杂度还要加上平衡节点旋转的时间),那么对数据修改较多且不考虑内存问题的场景可以优先考虑hash;

libesl

RB-Tree适用场景(map)

但是红黑树是基于搜索树设计的,具有天然的有序性hash因为存在哈希冲突所以不能保证存储的数据有序,那么对数据存储存在有序性需求的优先使用红黑树;(比如红黑树中,一个中序遍历,就能把储存的数据从小到大把数据按序展现出来)

sqlite

总结

map红黑树,频繁的增删查改效率可能会不如hash的unordered_map,但是它有序在迭代操作一段范围的存储元素的时候效率高
unordered_map哈希结构,频繁的增删查改切不考虑内存:则效率高于map红黑树,但是它存储的数据无有序性面对迭代操作一段范围的存储元素效率较低

IDA

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注