对我挺有帮助,转载过来,已注明出处,还是挺厚道的吧
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类似):
-
-
#include<set>
-
#include<ctime>
-
#include<cstdio>
-
usingnamespacestd;
-
-
intmain()
-
{
-
printf("--set使用byMoreWindows(http://blog.csdn.net/MoreWindows)--\n\n");
-
constintMAXN=15;
-
inta[MAXN];
-
inti;
-
srand(time(NULL));
-
for(i=0;i<MAXN;++i)
-
a[i]=rand()%(MAXN*2);
-
-
set<int>iset;
-
set<int>::iteratorpos;
-
-
-
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');
-
-
-
intfindNum=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');
-
return0;
-
}
运行结果如下:
下面试下在set中使用类(结构体也可以类似这样做)。这个类很简单,只有一个成员变量,及设置和获取这个成员变量的成员函数。
-
-
-
#include<set>
-
#include<ctime>
-
#include<cstdio>
-
usingnamespacestd;
-
classNode
-
{
-
public:
-
Node(intnAge=0)
-
{
-
m_nAge=nAge;
-
}
-
Node(constNode&na)
-
{
-
m_nAge=na.GetAge();
-
}
-
intGetAge()
-
{
-
returnm_nAge;
-
}
-
private:
-
intm_nAge;
-
};
-
-
inlinebooloperator<(constNode&na,constNode&nb)
-
{
-
returnna.GetAge()<nb.GetAge();
-
}
-
intmain()
-
{
-
inti;
-
set<Node>nset;
-
for(i=0;i<MAXN;++i)
-
nset.insert(Node(i));
-
return0;
-
}
编译,直接报了3个错误!!1个在拷贝构造函数,2个在operator<()函数。如下图所示:
3个错误都是一样的:
errorC2662: “Node::GetAge”: 不能将“this”指针从“const Node”转换为“Node &” 转换丢失限定符
这是怎么回事呀?分析下,拷贝构造函数与operator<()函数出错,错误都指向了GetAge()函数,有点古怪,比较下它们与GetAge()函数,可以发现最大的不同点在于这2个函数都用到了const而GetAge()函数没有使用const。难道是这个导致报错了吗?先给GetAge()函数加个const看看,如下:
int GetAge()const//增加这个const
{
returnm_nAge;
}
再编译,不报错了。再查下资料,原因如下——因为那2个函数都使用了const修饰的对象,但GetAge()没有加上const以保证它不修改对象,编译器认为这种写法是不安全的,所以就毫不犹豫报了个错误。
这种错误如果不亲身体会下,到笔试面试时很可能写了个错误程序而自己还处于一无所知中(死在这些小细节上最不值得)。另外,如果使用VC6.0则不会提示详细的错误信息——“转换丢失限定符”。
STL还为set提供了一些集合运算的函数,如交集set_intersection()、并集set_union()、差集set_difference()和对称差集set_symmetric_difference()。这些就不详细介绍了,有兴趣可以自己动手试一试。
下面开始对set和hash_set作个性能测试(Win7 +VS2008Release下)。
测试代码如下:
-
-
#include<set>
-
#include<hash_set>
-
#include<iostream>
-
#include<ctime>
-
#include<cstdio>
-
#include<cstdlib>
-
usingnamespacestd;
-
usingnamespacestdext;
-
-
-
constintMAXN=1000000,MAXQUERY=5000000;
-
inta[MAXN],query[MAXQUERY];
-
-
voidPrintfSetUseTime(char*pszOperator,longlElapsetime)
-
{
-
printf("set的%s操作用时%d毫秒\n",pszOperator,lElapsetime);
-
}
-
voidPrintfHashSetUseTime(char*pszOperator,longlElapsetime)
-
{
-
printf("hash_set的%s操作用时%d毫秒\n",pszOperator,lElapsetime);
-
}
-
-
intmain()
-
{
-
printf("setVShash_set性能测试数据容量%d个查询次数%d次\n",MAXN,MAXQUERY);
-
constintMAXNUM=MAXN*4;
-
constintMAXQUERYNUM=MAXN*8;
-
printf("容器中数据范围[0,%d)查询数据范围[0,%d)",MAXNUM,MAXQUERYNUM);
-
printf("--byMoreWindows(http://blog.csdn.net/MoreWindows)--\n\n");
-
-
-
inti;
-
srand(time(NULL));
-
for(i=0;i<MAXN;++i)
-
a[i]=(rand()*rand())%MAXNUM;
-
-
srand(time(NULL));
-
for(i=0;i<MAXQUERY;++i)
-
query[i]=(rand()*rand())%MAXQUERYNUM;
-
-
set<int>nset;
-
hash_set<int>nhashset;
-
clock_tclockBegin,clockEnd;
-
-
-
-
printf("-----插入数据-----------\n");
-
-
clockBegin=clock();
-
nset.insert(a,a+MAXN);
-
clockEnd=clock();
-
PrintfSetUseTime("insert",clockEnd-clockBegin);
-
-
clockBegin=clock();
-
nhashset.insert(a,a+MAXN);
-
clockEnd=clock();
-
PrintfHashSetUseTime("insert",clockEnd-clockBegin);
-
-
-
-
printf("-----查找数据-----------\n");
-
-
intnFindSucceedCount,nFindFailedCount;
-
nFindSucceedCount=nFindFailedCount=0;
-
clockBegin=clock();
-
for(i=0;i<MAXQUERY;++i)
-
if(nset.find(query[i])!=nset.end())
-
++nFindSucceedCount;
-
else
-
++nFindFailedCount;
-
clockEnd=clock();
-
PrintfSetUseTime("find",clockEnd-clockBegin);
-
printf("查找成功次数:%d查找失败次数:%d\n",nFindSucceedCount,nFindFailedCount);
-
-
nFindSucceedCount=nFindFailedCount=0;
-
clockBegin=clock();
-
for(i=0;i<MAXQUERY;++i)
-
if(nhashset.find(query[i])!=nhashset.end())
-
++nFindSucceedCount;
-
else
-
++nFindFailedCount;
-
clockEnd=clock();
-
PrintfHashSetUseTime("find",clockEnd-clockBegin);
-
printf("查找成功次数:%d查找失败次数:%d\n",nFindSucceedCount,nFindFailedCount);
-
return0;
-
}
在数据容量100万,查询次数500万时,程序运行结果如下:
由于查询的失败次数太多,这次将查询范围变小使用再测试下:
由于结点过多,80多万个结点,set的红黑树树高约为19(2^19=524288,2^20=1048576),查询起来还是比较费时的。hash_set在时间性能上比set要好一些,并且如果查询成功的几率比较大的话,hash_set会有更好的表现。想知道为什么hash_set会有优良的性能表现,请看继集——《STL系列之七 深入分析hash_set》。
注1.MSDN上讲set的erase()是有返回值的,但在VS2008中查看set的源代码,erase()函数的三个重载版本中,有二个返回值都为void即无返回值,另一个返回size_type。 可以通过http://msdn.microsoft.com/zh-cn/library/8h4a3515(v=VS.90).aspx查看MSDN上对set的erase()说明。
转载请标明出处,原文地址:http://blog.csdn.net/morewindows/article/details/7029587
分享到:
相关推荐
c++ STL source code, hash and vector etc
源码之前了无秘密,你将看到vector的实现、list的实现、heap的实现、deque的实现、RB-tree的实现、hash-table的实现、set/map 的实现;你将看到各种算法(排序、搜寻、排列组合、数据移动与复制…)的实现;你甚至将...
STL 是“Standard Template Library”的缩写,中文译为“标准模板库”。...例如,vector 的底层为顺序表(数组),list 的底层为双向链表,deque 的底层为循环队列,set 的底层为红黑树,hash_set 的底层为哈希表。
STL源码剖析,这本书所呈现的源码,使读者看到vector的实现、list的实现、heap的实现、deque的实现、Red Black tree的实现、hash table的实现、set/map的实现;看到各种算法(排序、查找、排列组合、数据移动与复制...
23.22 集合求异set_symmetric_difference 399 23.23 最小值min 401 23.24 最大值max 402 23.25 最小元素min_element 403 23.26 最大元素max_element 404 23.27 字典比较lexicographical_compare 405 23....
c++ std stl各容器的应用场合及性能 map hash_map unordered_map multimap list forward_list vector set hash_set multiset unsorted_set queue deque priority_queue
源码之前了无秘密,你将看到vector的实现、list的实现、heap的实现、deque的实现、Red Black tree的实现、hash table的实现、set/map的实现;你将看到各种算法(排序、查找、排列组合、数据移动与复制技术)的实现;你...
1.2 stl 六大组件 - 功能与运用 004 1.3 gnu源码开放精神 007 1.4 hp stl实现版本 009 1.5 p.j. plauger stl实现版本 010 1.6 rouge wave stl实现版本 011 1.7 stlport 实现版本 012 1.8 sgi stl实现版本 总...
本书共分5篇26章,以“C++编程技术→C++ STL泛化技术基础→C++ STL容器技术→C++ STL算法技术→C++ STL迭代器技术”为线索具体展开,通过大量的源码分析和应用实例,详细介绍了C++ STL的技术原理和使用方法。...
23.22 集合求异set_symmetric_difference 399 23.23 最小值min 401 23.24 最大值max 402 23.25 最小元素min_element 403 23.26 最大元素max_element 404 23.27 字典比较lexicographical_compare 405 23....
1.2 STL 六大组件 - 功能与运用 004 1.3 GNU源码开放精神 007 1.4 HP STL实现版本 009 1.5 P.J. Plauger STL实现版本 010 1.6 Rouge Wave STL实现版本 011 1.7 STLport 实现版本 012 1.8 SGI STL实现版本 总...
linked_hash测试结果
23.22 集合求异set_symmetric_difference 399 23.23 最小值min 401 23.24 最大值max 402 23.25 最小元素min_element 403 23.26 最大元素max_element 404 23.27 字典比较lexicographical_compare 405 23....
》灰《《常好的STL教程Effective STL 目录 容器 条款1: 仔细选择你要的容器 条款2: 小心对“容器无关代码”的幻想 条款3: 使容器里对象的拷贝操作轻量而正确 条款4: 用empty来代替检查size是否为0 条款5: ...
这本书所呈现的源码,使读者看到vector的实现、list的实现、heap的实现、deque的实现、Red Black tree的实现、hash table的实现、set/map的实现;看到各种算法(排序、查找、排列组合、数据移动与复制技术)的实现;...
这本书所呈现的源码,使读者看到vector的实现、list的实现、heap的实现、deque的实现、Red Black tree的实现、hash table的实现、set/map的实现;看到各种算法(排序、查找、排列组合、数据移动与复制技术)的实现;...
这本书所呈现的源码,使读者看到vector的实现、list的实现、heap的实现、deque的实现、Red Black tree的实现、hash table的实现、set/map的实现;看到各种算法(排序、查找、排列组合、数据移动与复制技术)的实现...
源码之前了无秘密,你将看到vector的实现、list的实现、heap的实现、deque的实现、Red Black tree的实现、hash table的实现、set/map的实现;你将看到各种算法(排序、查找、排列组合、数据移动与复制技术)的实现;...
源码之前了无秘密,你将看到vector的实现、list的实现、heap的实现、deque的实现、RB-tree的实现、hash-table的实现、set/map 的实现;你将看到各种算法(排序、搜寻、排列组合、数据移动与复制…)的实现;你甚至将...
侯捷 STL源码剖析:一本剖析下面内容的书籍:vector、list、heap、deque、red black tree、hash table、set、map等等