3.5　set

3.5.1　set是什么

C++ STL之所以得到广泛的赞誉，也被很多人使用，不只是提供了像vector、string、list等方便的容器，更重要的是STL封装了许多复杂的数据结构算法和大量

常用数据结构操作。vector封装数组，list封装了链表，map和set封装了二叉树等，在封装这些数据结构的时候，STL按照程序员的使用习惯，以成员函数方式提供的常用操作，如：插入、排序、删除、查找等。让用户在STL使用过程中，并不会感到陌生。

关于set，必须说明的是set关联式容器。set作为一个容器也是用来存储同一数据类型的数据类型，并且能从一个数据集合中取出数据，在set中每个元素的值都唯一的，而且系统能根据元素的值自动进行排序。应该注意的是set中数元素的值不能直接被改变。C++ STL中标准关联容器set、multiset、map、multimap内部采用的都是红黑树。红黑树的统计性能要好于一般平衡二叉树，所以被STL选择作为了关联容器的内部结构。

关于set有下面几个问题需要注意。

（1）为何map和set的插入删除效率比用其他序列容器高？

表面上看，因为对于关联容器来说，不需要做内存拷贝和内存移动。set容器内所有元素都是以节点的方式来存储，其节点结构和链表差不多，指向父节点和子节点，set的结构图如图3-6所示。

因此插入的时候只需要稍做变换，把节点的指针指向新的节点就可以了。删除的时候类似，稍做变换后把指向删除节点的指针指向其他节点即可。这里的一切操作就是指针换来换去，和内存移动没有关系。

（2）为何每次insert之后，以前保存的iterator不会失效？

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

（3）当数据元素增多时，set的插入和搜索速度变化如何？

如果知道log2的关系就应该彻底了解这个答案。在set中查找是使用二分查找，也就是说，如果有16个元素，最多需要比较4次就能找到结果，有32个元素，最多比较5次。那么有10?000个元素时为log10?000，即最多为14次，如果是20000个元素呢？最多不过15次。可见，当数据量增大一倍的时候，搜索次数只不过多了1次。当明白这个道理后，就可以安心往里面放入元素了。