STL中mapset的数据结构及底层实现

1、STL 中 map、set 的数据结构及底层实现摘要：本文列出几个基本的 STLmap 和 STLset 的问题，通过解答这些问题讲解了 STL 关联容器内部的数据结构，最后提出了关于 UNIX/LINUX 自带平衡二叉树库函数和 map,set选择问题，并分析了 map,set 的优势之处。对于希望深入学习 STL 和希望了解 STLmap等关联容器底层数据结构的朋友来说，有一定的参考价值。vector（向量）STL 中标准而安全的数组。只能在 vector 的前面”增加数据。deque（双端队列 double-endedqueue）在功能上和 vector 相似，但是可以在前后两端向其中添

2、加数据。list（列表）一一游标一次只可以移动一步。如果你对链表已经很熟悉，那么 STL 中的 list 则是一个双向链表（每个节点有指向前驱和指向后继的两个指针）。set（集合）包含了经过排序了的数据，这些数据的值（value）必须是唯一的。map（映射）一一经过排序了的二元组的集合，map 中的每个元素都是由两个值组成，其中的 key（键值，一个 map 中的键值必须是唯一的）是在排序或搜索时使用，它的值可以在容器中重新获取；而另一个值是该元素关联的数值。比如，除了可以 ar43=overripe这样找到一个数据，map 还可以通过 arbanana=overripe这样的方法找到一个数据

3、。如果你想获得其中的元素信息，通过输入元素的全名就可以轻松实现。multiset（多重集）和集合（set）相似，然而其中的值不要求必须是唯一的（即可以有重复）。multimap（多重映射）和映射（map）相似，然而其中的键值不要求必须是唯一的（即可以有重复）。STLmap 和 set 的使用虽不复杂，但也有一些不易理解的地方，如：# 为何 map 和 set 的插入删除效率比用其他序列容器高？# 为何每次 insert 之后，以前保存的 iterator 不会失效？# 为何 map 和 set 不能像 vector 一样有个 reserve 函数来预分配数据？# 当数据元素增多时（10000

4、到 20000 个比较），map 和 set 的插入和搜索速度变化如何？或许有得人能回答出来大概原因，但要彻底明白，还需要了解C+STL 之所以得到广泛的赞誉，也被很多人使用，不只是提供了像 vector,string,list 等方便的容器，更重要的是 STL 封装了许多复杂的数据结构算法和大量常用数据结构操作。vector 封装数组，list 封装了链表，map 和 set 封装了二叉树等，在封装这些数据结构的时候，STL 按照程序员的使用习惯，以成员函数方式提供的常用操作，如：插入、排序、删除、查找等。让用户在STL 使用过程中，并不会感到陌生。C+STL 中标准关联容器 set,mul

5、tiset,map,multimap 内部采用的就是一种非常高效的平衡检索二叉树：红黑树，也成为 RB 机（Red-BlackTree）。RB 树的统计性能要好于一般的平衡二叉树（有些书籍根据作者姓名，Adelson-Velskii 和 Landis,将其称为 AVL-机）,所以被 STL 选择作为了关联容器的内部结构。本文并不会介绍详细 AVL 树和 RB 树的实现以及他们的优劣，关于 RB 树的详细实现参看红黑树：理论与实现（理论篇）。本文针对开始提出的几个问题的回答，来向大家简单介绍 map 和 set 的底层数据结构。为何 map 和 set 的插入删除效率比用其他序列容器高？大部分人

6、说，很简单，因为对于关联容器来说，不需要做内存拷贝和内存移动。说对了，确实如此。map 和 set 容器内所有元素都是以节点的方式来存储， 其节点结构和链表差不多， 指向父节点和子节点。结构图可能如下：A/BC/DEFG因此插入的时候只需要稍做变换，把节点的指针指向新的节点就可以了。删除的时候类似，稍做变换后把指向删除节点的指针指向其他节点就 OK 了。这里的一切操作就是指针换来换去，和内存移动没有关系。为何每次 insert 之后，以前保存的 iterator 不会失效？看见了上面答案的解释，你应该已经可以很容易解释这个问题。iterator 这里就相当于指向节点的指针，内存没有变，指向内存

7、的指针怎么会失效呢(当然被删除的那个元素本身已经失效了)。相对于 vector 来说，每一次删除和插入，指针都有可能失效，调用 push_back 在尾部插入也是如此。因为为了保证内部数据的连续存放，iterator 指向的那块内存在删除和插入过程中可能已经被其他内存覆盖或者内存已经被释放了。即使时 push_back 的时候，容器内部空间可能不够，需要一块新的更大的内存，只有把以前的内存释放，申请新的更大的内存，复STL 的底层数据结构。制已有的数据元素到新的内存，最后把需要插入的元素放到最后，那么以前的内存指针自然就不可用了。特别时在和 find 等算法在一起使用的时候，牢记这个原则：不要

8、使用过期的 iterator。为何 map 和 set 不能像 vector 一样有个 reserve 函数来预分配数据？我以前也这么问，究其原理来说时，引起它的原因在于在 map 和 set 内部存储的已经不是元素本身了，而是包含元素的节点。也就是说 map 内部使用的 Alloc 并不是map声明的时候从参数中传入的 Alloc。例如：mapint,int,less,Allocintmap;这时候在 intmap 中使用的 allocator 并不是 Alloc,而是通过了转换的 Alloc,具体转换的方法时在内部通过 Alloc:rebind 重新定义了新的节点分配器，详细的实现参看彻底

9、学习 STL 中的 Allocator。其实你就记住一点，在 map 和 set 内面的分配器已经发生了变化，reserve 方法你就不要奢望了。当数据元素增多时(10000 和 20000 个比较)，map 和 set 的插入和搜索速度变化如何？如果你知道 10g2 的关系你应该就彻底了解这个答案。 在 map 和 set 中查找是使用二分查找， 也就是说，如果有 16 个元素，最多需要比较 4 次就能找到结果，有 32 个元素，最多比较 5 次。那么有 10000 个呢？最多比较的次数为 10g10000,最多为 14 次，如果是 20000 个元素呢？最多不过 15 次。看见了吧，当数据

10、量增大一倍的时候，搜索次数只不过多了 1 次，多了 1/14 的搜索时间而已。你明白这个道理后，就可以安心往里面放入元素了。最后，对于 map 和 setWinter 还要提的就是它们和一个 c 语言包装库的效率比较。在许多 unix 和 linux平台下，都有一个库叫 isc,里面就提供类似于以下声明的函数：voidtree_init(void*tree);void*tree_srch(void*tree,int(*compare)(),void*data);voidtree_add(void*tree,int(*compare)(),void*data,void(*del_uar)();i

11、nttree_delete(void*tree,int(*compare)(),void*data,void(*del_uar)();inttree_trav(void*tree,int(*trav_uar)();voidtree_mung(void*tree,void(*del_uar)();许多人认为直接使用这些函数会比 STLmap 速度快，因为 STLmap 中使用了许多模板什么的。其实不然，它们的区别并不在于算法，而在于内存碎片。如果直接使用这些函数，你需要自己去new 一些节点，当节点特别多，而且进行频繁的删除和插入的时候，内存碎片就会存在，而 STL 采用自己的 Allocato

12、r 分配内存，以内存池的方式来管理这些内存，会大大减少内存碎片，从而会提升系统的整体性能。Winter 在自己的系统中做过测试，把以前所有直接用 isc 函数的代码替换成 map,程序速度基本一致。当时间运行很长时间后(例如后台服务程序)，map 的优势就会体现出来。从另外一个方面讲，使用 map 会大大降低你的编码难度，同时增加程序的可读性。何乐而不为？学习 STLmap,STLset 之数据结构基础作者：winter摘要：本文列出几个基本的 STLmap 和 STLset 的问题，通过解答这些问题讲解了 STL 关联容器内部的数据结构，最后提出了关于 UNIX/LINUX 自带平衡二叉树库

13、函数和 map,set选择问题，并分析了 map,set 的优势之处。对于希望深入学习 STL 和希望了解 STLmap等关联容器底层数据结构的朋友来说，有一定的参考价值。STLmap 和 set 的使用虽不复杂，但也有一些不易理解的地方，如：# 为何 map 和 set 的插入删除效率比用其他序列容器高？# 为何每次 insert 之后，以前保存的 iterator 不会失效？# 为何 map 和 set 不能像 vector 一样有个 reserve 函数来预分配数据？# 当数据元素增多时(10000 到 20000 个比较)，map 和 set 的插入和搜索速度变化如何？或许有得人能回答

14、出来大概原因，但要彻底明白，还需要了解 STL 的底层数据结构。C+STL 之所以得到广泛的赞誉，也被很多人使用，不只是提供了像 vector,string,list 等方便的容器，更重要的是 STL 封装了许多复杂的数据结构算法和大量常用数据结构操作。vector 封装数组，list 封装了链表，map 和 set 封装了二叉树等，在封装这些数据结构的时候，STL 按照程序员的使用习惯，以成员函数方式提供的常用操作，如：插入、排序、删除、查找等。让用户在STL 使用过程中，并不会感到陌生。C+STL 中标准关联容器 set,multiset,map,multimap 内部采用的就是一种非常高

15、效的平衡检索二叉树：红黑树，也成为 RB 机（Red-BlackTree）。RB 树的统计性能要好于一般的平衡二叉树（有些书籍根据作者姓名，Adelson-Velskii 和 Landis,将其称为 AVL-机）,所以被 STL 选择作为了关联容器的内部结构。本文并不会介绍详细 AVL 树和 RB 树的实现以及他们的优劣，关于 RB 树的详细实现参看红黑树：理论与实现（理论篇）。本文针对开始提出的几个问题的回答，来向大家简单介绍 map 和 set 的底层数据结构。为何 map 和 set 的插入删除效率比用其他序列容器高？大部分人说，很简单，因为对于关联容器来说，不需要做内存拷贝和内存移动。

16、说对了，确实如此。map 和 set 容器内所有元素都是以节点的方式来存储， 其节点结构和链表差不多， 指向父节点和子节点。结构图可能如下：A/BC/DEFG因此插入的时候只需要稍做变换，把节点的指针指向新的节点就可以了。删除的时候类似，稍做变换后把指向删除节点的指针指向其他节点就 OK 了。这里的一切操作就是指针换来换去，和内存移动没有关系。为何每次 insert 之后，以前保存的 iterator 不会失效？看见了上面答案的解释，你应该已经可以很容易解释这个问题。iterator 这里就相当于指向节点的指针，内存没有变，指向内存的指针怎么会失效呢（当然被删除的那个元素本身已经失效了）。相对

17、于 vector 来说，每一次删除和插入，指针都有可能失效，调用 push_back 在尾部插入也是如此。因为为了保证内部数据的连续存放，iterator 指向的那块内存在删除和插入过程中可能已经被其他内存覆盖或者内存已经被释放了。即使时 push_back 的时候，容器内部空间可能不够，需要一块新的更大的内存，只有把以前的内存释放，申请新的更大的内存，复制已有的数据元素到新的内存，最后把需要插入的元素放到最后，那么以前的内存指针自然就不可用了。特别时在和 find 等算法在一起使用的时候，牢记这个原则：不要使用过期的 iterator。为何 map 和 set 不能像 vector 一样有个

18、 reserve 函数来预分配数据？我以前也这么问，究其原理来说时，引起它的原因在于在 map 和 set 内部存储的已经不是元素本身了，而是包含元素的节点。也就是说 map 内部使用的 Alloc 并不是map声明的时候从参数中传入的 Alloc。例如：mapint,int,less,Allocintmap;这时候在 intmap 中使用的 allocator 并不是 Alloc,而是通过了转换的 Alloc,具体转换的方法时在内部通过 Alloc:rebind 重新定义了新的节点分配器，详细的实现参看彻底学习 STL 中的 Allocator。其实你就记住一点，在 map 和 set 内面

19、的分配器已经发生了变化，reserve方法你就不要奢望了。当数据元素增多时(10000 和 20000 个比较)，map 和 set 的插入和搜索速度变化如何？如果你知道 10g2 的关系你应该就彻底了解这个答案。在 map 和 set 中查找是使用二分查找，也就是说，如果有 16 个元素，最多需要比较 4 次就能找到结果，有 32 个元素，最多比较 5 次。那么有10000 个呢？最多比较的次数为 10g10000,最多为 14 次，如果是 20000 个元素呢？最多不过 15 次。看见了吧，当数据量增大一倍的时候，搜索次数只不过多了 1 次，多了 1/14 的搜索时间而已。你明白这个道理后，就可以安心往里面放入元素了。最后，对于 map 和 setWinter 还要提的就是它们和一个 c 语言包装库的效率比较。在许多unix 和 linux 平台下，都有一个库叫