深入了解STL中set与hash_set，hash表基础

 1 #include <set>
 2 #include <ctime>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     const int MAXN = 15;
 9     int a[MAXN];
10     int i;
11     srand(time(NULL));
12     for (i = 0; i < MAXN; ++i)
13         a[i] = rand() % (MAXN * 2);
14 
15     set<int> iset;   
16     set<int>::iterator pos; 
17 
18     //插入数据 insert()有三种重载
19     iset.insert(a, a + MAXN);
20 
21     //当前集合中个数 最大容纳数据量
22     printf("当前集合中个数: %d     最大容纳数据量: %d\n", iset.size(), iset.max_size());
23 
24     //依次输出
25     printf("依次输出集合中所有元素-------\n");
26     for (pos = iset.begin(); pos != iset.end(); ++pos)
27         printf("%d ", *pos);
28     putchar('\n');
29 
30     //查找
31     int findNum = MAXN;
32     printf("查找 %d是否存在-----------------------\n", findNum);
33     pos = iset.find(findNum);
34     if (pos != iset.end())
35         printf("%d 存在\n", findNum);
36     else
37         printf("%d 不存在\n", findNum);
38 
39     //在最后位置插入数据，如果给定的位置不正确，会重新找个正确的位置并返回该位置
40     pos  = iset.insert(--iset.end(), MAXN * 2); 
41     printf("已经插入%d\n", *pos);
42 
43     //删除
44     iset.erase(MAXN);
45     printf("已经删除%d\n", MAXN);
46 
47     //依次输出
48     printf("依次输出集合中所有元素-------\n");
49     for (pos = iset.begin(); pos != iset.end(); ++pos)
50         printf("%d ", *pos);
51     putchar('\n');
52     return 0;
53 }

 1 #include <set>
 2 #include <hash_set>
 3 #include <iostream>
 4 #include <ctime>
 5 #include <cstdio>
 6 #include <cstdlib>
 7 using namespace std;
 8 using namespace stdext;  //hash_set
 9 
10 // MAXN个数据 MAXQUERY次查询
11 const int MAXN = 10000, MAXQUERY = 5000000;
12 int a[MAXN], query[MAXQUERY];
13 
14 void PrintfContainertElapseTime(char *pszContainerName, char *pszOperator, long lElapsetime)
15 {
16     printf("%s 的%s操作 用时 %d毫秒\n", pszContainerName, pszOperator, lElapsetime);
17 }
18 
19 int main()
20 {
21     printf("set VS hash_set 性能测试 数据容量 %d个 查询次数 %d次\n", MAXN, MAXQUERY);
22     const int MAXNUM = MAXN * 4;
23     const int MAXQUERYNUM = MAXN * 4;
24     printf("容器中数据范围 [0, %d) 查询数据范围[0, %d)\n", MAXNUM, MAXQUERYNUM);
25     
26     //随机生成在[0, MAXNUM)范围内的MAXN个数
27     int i;
28     srand(time(NULL));
29     for (i = 0; i < MAXN; ++i)
30         a[i] = (rand() * rand()) % MAXNUM;
31     //随机生成在[0, MAXQUERYNUM)范围内的MAXQUERY个数
32     srand(time(NULL));
33     for (i = 0; i < MAXQUERY; ++i)
34         query[i] = (rand() * rand()) % MAXQUERYNUM;
35 
36     set<int>       nset;
37     hash_set<int> nhashset;
38     clock_t  clockBegin, clockEnd;
39 
40 
41     //insert
42     printf("-----插入数据-----------\n");
43 
44     clockBegin = clock();  
45     nset.insert(a, a + MAXN); 
46     clockEnd = clock();
47     printf("set中有数据%d个\n", nset.size());
48     PrintfContainertElapseTime("set", "insert", clockEnd - clockBegin);
49 
50     clockBegin = clock();  
51     nhashset.insert(a, a + MAXN); 
52     clockEnd = clock();
53     printf("hash_set中有数据%d个\n", nhashset.size());
54     PrintfContainertElapseTime("hase_set", "insert", clockEnd - clockBegin);
55 
56 
57     //find
58     printf("-----查询数据-----------\n");
59 
60     int nFindSucceedCount, nFindFailedCount; 
61     nFindSucceedCount = nFindFailedCount = 0;
62     clockBegin = clock(); 
63     for (i = 0; i < MAXQUERY; ++i)
64         if (nset.find(query[i]) != nset.end())
65             ++nFindSucceedCount;
66         else
67             ++nFindFailedCount;
68     clockEnd = clock();
69     PrintfContainertElapseTime("set", "find", clockEnd - clockBegin);
70     printf("查询成功次数： %d    查询失败次数： %d\n", nFindSucceedCount, nFindFailedCount);
71     
72     nFindSucceedCount = nFindFailedCount = 0;
73     clockBegin = clock();  
74     for (i = 0; i < MAXQUERY; ++i)
75         if (nhashset.find(query[i]) != nhashset.end())
76             ++nFindSucceedCount;
77         else
78             ++nFindFailedCount;
79     clockEnd = clock();
80     PrintfContainertElapseTime("hash_set", "find", clockEnd - clockBegin);
81     printf("查询成功次数： %d    查询失败次数： %d\n", nFindSucceedCount, nFindFailedCount);
82     return 0;
83 }