STL系列之六 set与hash_set
set和hash_set是STL中比较重要的容器，有必要对其进行深入了解。在STL中，set是以红黑树（RB-tree）作为底层数据结构的，hash_set是以Hash table（哈希表）作为底层数据结构的。set可以在时间复杂度为O(logN)情况下插入、删除和查找数据。hash_set操作的时间复杂度则比较复杂，这取决于哈希函数和哈希表的负载情况。下面列出set和hash_set的常用函数：
set和hase_set的更多函数请查阅MSDN。
set的使用范例如下（hash_set类似）：
// by MoreWindows( http://blog.csdn.net/MoreWindows ) #include <set> #include <ctime> #include <cstdio> using namespace std; int main() { printf("--set使用 by MoreWindows( http://blog.csdn.net/MoreWindows ) --\n\n"); const int MAXN = 15; int a[MAXN]; int i; srand(time(NULL)); for (i = 0; i < MAXN; ++i) a[i] = rand() % (MAXN * 2); set<int> iset; set<int>::iterator pos; //插入数据 insert()有三种重载 iset.insert(a, a + MAXN); //当前集合中个数 最大容纳数据量 printf("当前集合中个数: %d 最大容纳数据量: %d\n", iset.size(), iset.max_size()); //依次输出 printf("依次输出集合中所有元素-------\n"); for (pos = iset.begin(); pos != iset.end(); ++pos) printf("%d ", *pos); putchar('\n'); //查找 int findNum = MAXN; printf("查找 %d是否存在-----------------------\n", findNum); pos = iset.find(findNum); if (pos != iset.end()) printf("%d 存在\n", findNum); else printf("%d 不存在\n", findNum); //在最后位置插入数据，如果给定的位置不正确，会重新找个正确的位置并返回该位置 pos = iset.insert(--iset.end(), MAXN * 2); printf("已经插入%d\n", *pos); //删除 iset.erase(MAXN); printf("已经删除%d\n", MAXN); //依次输出 printf("依次输出集合中所有元素-------\n"); for (pos = iset.begin(); pos != iset.end(); ++pos) printf("%d ", *pos); putchar('\n'); return 0; }