数据结构利器之私房STL（中）

这篇文章 http://www.cnblogs.com/daoluanxiaozi/archive/2012/12/02/confidential-stl.html 由于严重违反了『博客园首页』的相关规则，因此笔者改将《私房STL》系列的每一篇都整合到博客园中，取消外链的做法。另，考虑篇幅的问题，此系列文章将分为上、中、下。此篇为《数据结构利器之私房STL（中）》。喜欢就顶下:-)

此系列的文章适合初学有意剖析STL和欲复习STL的同学们。

私房STL之map和set
私房STL之Hashtable
私房STL算法之全排列
私房STL算法之快速幂
私房STL之hash_set和hash_map

私房STL之map和set

一句话set：容器set底层是由RB_TREE实现的，它和（deque--->stack、queue）模式一样；色set的元素不允许重复；set中键值就是实值，实值就是键值，而键值是不可以更改的（但MS STL不这样做），所以set不允许对其中的元素进行更新；

一句话map：容器map底层也由RB_TREE实现，它和（deque--->stack、queue）模式一样；map中一个键值对应一个实值，不允许键值上的重复，内部是按键值来进行排序存储的，其中键值不允许被更改。

网络上有关于红黑树详细的解说，特别是复杂的红黑树元素操作算法，推荐@JULY 的文章：http://blog.csdn.net/v_JULY_v/article/details/6105630。本文主要介绍STL set/map的用法和笔者对其在实现上技巧实现技法的摘录，欢迎斧正。

set和map的创建与遍历

set和map都是由非线性空间来存储的，属于Bidrectional Iterator;测试添加元素的时候，故意添加已存在的键值，发现被拒绝，RB_TREE内部有insert_equal()和insert_unique()两个版本，set/map都调用后者。

set：

递归实现全排列
递归实现全排列是一个经典的算法。
当指数n为偶数时，A^n = A^(n/2) * A^(n/2)；
当指数n为奇数时，A^n = A^(n/2) * A^(n/2) * A 。
从上面的例子中，即10111b为奇数，A10111b=(A10110b)2 * A；10110b为偶数，A10110b=(A1011b)2 ，依次类推。。。。
hash_set和hash_map的创建与遍历
hash_set只需指定键值的类型，hash_map需指定键值和实值的类型。它们都可以像大多数的容器一样，通过迭代器，寻访元素。
......hash_set<int> ihs; ihs.insert(1);ihs.insert(5);ihs.insert(6);ihs.insert(4);ihs.insert(3);ihs.insert(3);ihs.insert(100);ihs.insert(200);/*故意的*/hash_set<int>::iterator beg = ihs.begin(),end = ihs.end(),ite;for(ite = beg; ite != end; ite++)cout << *ite << " ";cout << endl;......
200 1 3 4 100 5 6
可证见hash_set拒绝插入重复元素（与set性质相同），未排序（违反set性质）。
......hash_map<int,int> ihm;ihm.insert(pair<int,int>(1,100));ihm.insert(pair<int,int>(2,200));ihm.insert(pair<int,int>(3,300));ihm.insert(pair<int,int>(4,400));ihm.insert(pair<int,int>(5,500));hash_map<int,int>::iterator beg = ihm.begin(),end = ihm.end(),ite;for(ite = beg; ite != end; ite++)cout << "<" << ite->first << "," << ite->second << ">" << " ";cout << endl;cout << "ihm[1] = " << ihm[1] << endl;/*可以通过键值索引*/......
<1,100> <2,200> <3,300> <4,400> <5,500>
ihm[1] = 100
hash_set和hash_map的查找
有Hashtable的实现可知，hash_set和hash_map的平均查找效率一样很高，各自内部有实现find()查找函数，无需使用从头至尾遍历的STL <algorithm>find()函数。Standard C++ Library中的实例：http://msdn.microsoft.com/en-US/library/ea54hzhb(v=vs.80).aspx
建议
hash_set和hash_map还实现很多函数，给出参考链接：http://msdn.microsoft.com/en-US/library/y49kh4ha(v=vs.80).aspx
外链 @MoreWindows 同学的文章：http://blog.csdn.net/morewindows/article/details/7330323，里头的亮点便是C++里头语法的细节问题。
本文完 2012-10-23
捣乱小子 http://www.daoluan.net/