帮助整合-手册1stl本文列出几个基本STLmap和STLset问题通过解答这些

STLmapSTLsetSTL关联容器UNIX/LINUXmap,set选择问map,setSTLSTLmap等关联容STLmapset#mapset#为何每次insert之后，以前保存的iterator不会失效#mapsetvectorreserve#，mapSTL的底层数据结构。C++STLvector,string,list等方STLvector封装数组，list封装了链表，mapset封装了二叉树等，在封装这些数据结构的时候，STL让用户在STL使用过程中，并不会感到陌生。C++STL中标准关联容器set,multiset,map,multimap内部采用的就是一种非常高效的平衡二叉树(有些书籍根据作者，Adelson-Velskii和Landis，将其称为AVL-树)，所以被STL选择作为了关联容器的内部结构。本文并不会介绍详细AVLRB树的实现以及他们的优劣，关于RB树的详细实现参看树:理论与实现(理论篇)。本文针对开始mapset的底层数据结构。map和set实如此。map和set容器内所有元素都是以节点的方式来，其节点结构和链表差不多，指向父节点节点。结构图可能如下：A/ /\/\DEFGOK为何每次insert之后，以前保存的iterator不会失，看见了上面答案的解释，你应该已经可以很容易解释这个问题。iterator这里就相当于指向失效了)vectorpush_back在尾部插入也是如此。因为为了保证内部数据的连续存放，iterator指向的那块内存在删除和内存已有的数据元素到新的内存，最后把需要插入的元素放到最后，那么以前的内存find等算法在一起使用的时候，牢记这个原则：不要使iterator。，map和set不能像vectorreserve我以前也这么问，究其原理来说时，引起它的原因在于在map和set内部的已经不是元素本身了，而是包含元素的节点。也就是说map的Alloc并不是map<Key,Compare,Alloc>的时候从参数中传入的Alloc。例如：map<int,int,less<int>,Alloc<int>>intmap;intmapallocatorAlloc<int>,Alloc，具体转换STLAllocatormapset内面的分配器已经发生了变化，reserve方法你就不要奢望了。，maplog2mapset中查找是使用二分查找，16432510000log100001420000151次，多1/14的搜索时间而已。你明白这个道理后，就可以安心往里面放入元素了。map和setWinter还要提的就是它们和一个c和linux平台下，都有一个库叫isc，里面就提供类似于以下的函数voidtree_init(voidvoid*tree_srch(void**tree,int(*compare)(),voidvoidtree_add(void**tree,int(*compare)(),void*data,void(*del_uar)());inttree_delete(void**tree,int(*compare)(),void*data,void(*del_uar)());inttree_trav(void**tree,int(*trav_uar)());voidtree_mung(void**tree,voidSTLmapSTLmap中使用了许多模板什么new会存在，而STL采用自己的Allocator分配内存，以内存池的方式来