STL源码分析：map

清疚 2023-06-24 11:24 30阅读 0赞

STL里面map是基于一颗红黑树来实现的，map其实是对红黑树的接口做了一下封装。  
对于底层的红黑树来说，map底层的红黑树的实例化为：

typedef rb_tree<key_type, value_type, 
                      select1st<value_type>, key_compare, Alloc> rep_type;

而value\_type为pair.

typedef pair<const Key, T> value_type;

也就是说，对于map来说，它是把数据从key到value的映射关系写成一个pair，再把整个pair作为value插入到红黑树里面去。

而模板实参 `select1st<value_type>` 则是rb\_tree的KeyOfValue参数的实际值，说明map准备把每个value的第一个元素作为key.

map的其他没啥好说的。  
主要是看看的它对取下标运算符的重载：

T& operator[](const key_type& k) { 
        return (*((insert(value_type(k, T()))).first)).second;
      }

也就是说使用operator\[\] 运算符的时候，它会先尝试插入一个元素value\_type(k,T()).k是我们给定的key,而value则是类别T的默认构造函数做出来的value。  
如果参数k存在于map中，那倒也没事。  
如果参数k不存在map中，那就是新插入一个key-value进去，这样map的size啥的可就变化了。  
例如：

#include <map>
    using namespace std;
    int main()
    { 
    	map<int, int> storage;
    	printf("%d\n", storage[110]);
    	printf("%d\n", storage.size());
    	system("pause");
    	return 0;
    }

输出的是0和1，说明插入成功了。  
上面这个例子说明了，我们如果使用了operator\[\]，要千万注意用find()或count()查看当前key是否存在会受这种插入的影响。

发表评论取消回复

表情：

评论列表（有 0 条评论，30人围观）

还没有评论，来说两句吧...

相关阅读

相关 Map 源码分析

与List、Set、Queue不同，Map是以`<K,V>`结构进行存储，其中Map接口是一个顶级接收，它定义了操作一些Map的基本方法，下面的继承图展示了一些常用的Map继承

素颜马尾好姑娘i/ 2023年10月01日 10:52/ 0 赞/ 57 阅读

相关 STL源码分析：map

STL里面map是基于一颗红黑树来实现的，map其实是对红黑树的接口做了一下封装。对于底层的红黑树来说，map底层的红黑树的实例化为： typedef rb_t

清疚/ 2023年06月24日 11:24/ 0 赞/ 31 阅读

相关 STL源码分析：SGI STL的内存管理 allocator

前言 STL源码的框架类精髓在于，它把对象的创建过程细分为两步，一步是申请内存，另外一步是在申请到的内存上调用构造函数初始化那一块内存。今天来分析一个STL的allo

超、凢脫俗/ 2023年05月30日 06:06/ 0 赞/ 162 阅读

相关 Map接口源码分析

package java.util; import java.util.function.BiConsumer; import java.ut

矫情吗；*/ 2022年12月23日 11:11/ 0 赞/ 240 阅读

相关 JDK源码分析-Map接口

Map接口以键值方式存储，常用的实现类有HashMap，Hashtable，ConcurrentHashMap，TreeMap，LinkedHashMap等。 jdk

忘是亡心i/ 2022年11月21日 04:13/ 0 赞/ 232 阅读

相关 STL源码剖析——关联容器之hash_map

前言由于前文介绍的《[散列表][Link 1][hashtable][Link 1]》中，可以知道hash table在查找、删除和插入节点是常数时间，优于RB-Tr

柔光的暖阳◎/ 2022年08月12日 15:28/ 0 赞/ 219 阅读

相关 STL源码剖析——关联容器之map

前言在SGI STL中的容器map，底层实现机制是RB-Tree，是因为map的操作RB-Tree都能实现，有关RB-Tree的剖析请看《[STL源码剖析——RB-T

悠悠/ 2022年08月12日 12:00/ 0 赞/ 237 阅读

相关【STL】从源码看map

map 与set相同，map同样是以红黑树RB\_Tree为底层机制的关联式容器。map的每一个元素都拥有两个值，一个键值（key）和一个实值（value）。它的内部实现是用

不念不忘少年蓝@/ 2022年07月15日 11:53/ 0 赞/ 226 阅读

相关 STL源码剖析-hash_map / hash_multimap

类似于标准的map以rb\_tree为底层实现，hash\_map以hashtable为底层实现，hash\_map的底层操作也是由hashtabe提供。运用map，为的是

矫情吗；*/ 2022年05月21日 06:12/ 0 赞/ 234 阅读

相关 Map源码解析之HashMap源码分析

实现原理 HashMap 是数组 + 链表 + 红黑树（JDK1.8 增加了红黑树部分）实现的。 HashMap 的工作原理 HashMap 基于 hashing

快来打我*/ 2021年09月26日 14:20/ 0 赞/ 621 阅读