map和set的原理

时间:2021-02-01 13:41:16

1)map:经过排序了的二元组的集合,map中的每个元素都是由两个值组成,其中的key(键值,一个map中的键值必须是唯一的) 是在排序或搜索时使用,它的值可以在容器中重新获取;而另一个值是该元素关联的数值。比如,除了可以ar[43] = "overripe"这样找到一个数据,map还可以通过ar["banana"] = "overripe"这样的方法找到一个数据。如果你想获得其中的元素信息,通过输入元素的全名就可以轻松实现

2)set:包含了经过排序了的数据,这些数据的值(value)必须是唯一的

3)map和set的基本原理:红黑树

4)额外问题:

# 为何map和set的插入删除效率比用其他序列容器高?因为对于关联容器来说,不需要做内存拷贝和内存移动。说对了,确实如此。map和set容器内所有元素都是以节点的方式来存储,其节点结构和链表差不多,指向父节点和子节点。插入和删除就是指针换来换去,和内存移动没有关系

# 为何每次insert之后,以前保存的iterator不会失效?iterator这里就相当于指向节点的指针,内存没有变,指向内存的指针怎么会失效呢(当然被删除的那个元素本身已经失效了)。相对与vector来说,vector每次插入和删除,指针都有可能会失效,比如:当该内存块不够它扩容时,它会申请其它内存块,此时指针会失效!

# 当数据元素增多时(10000到20000个比较),map和set的插入和搜索速度变化如何?STL的优势并不在于算法,而在于内存碎片。如果你需要经常自己去new一些节点,当节点特别多,而且进行频繁的删除和插入的时候,内存碎片就会存在,而STL采用自己的Allocator分配内存,以内存池的方式来管理这些内存,会大大减少内存碎片,从而会提升系统的整体性能。当时间运行很长时间后(例如后台服务程序),map的优势就会体现出来。从另外一个方面讲,使用map会大大降低你的编码难度,同时增加程序的可读性。学习STL map, STL set之数据结构基础看来是很有必要的。