对list的查找的另一种作法

大家用了stl的list后都知道,他的节点在内存中的位置是固定的,但是当删除或查找某个指定节点时需要遍历,这样当list很大时,这个遍历过程未免有些性能诟病。当然大家会很容易想到hash_map,但是hash_map在节点数超过一定数量后也会进行“扩容”操作,这样存在大量的对象的搬迁。我们看看list的特点:结构简单,节点的内存地址固定,添加删除操作快捷;再看看hash_map的特点:查找速度快,节点的内存地址可能不固定(依赖是否扩容),如果我们将两者结合可以解决某些特殊应用场合(指那些可能需要记录节点内存位置的场合)。用一个list和一个hash_map来管理一个数据列表,list记录具体的节点的数据,hash_map用于记录list的迭代器地址,这样需要查找一个键值为key的对象在list中的节点时,可以通过hash_map来进行定位,具体性能如何没有测试过,应该不会比list的直接遍历查找慢,大家可以自己试试。

posted on 2006-06-10 16:46 PeakGao 阅读(1406) 评论(3)  编辑 收藏 引用 所属分类: C++技术

评论

# re: 对list的查找的另一种作法 2006-06-10 17:02 LOGOS

很想跟你说,iterator是不稳定的对象,insert,delete或者其他一些操作,都会使得当前拥有的iterator失效。  回复  更多评论   

# re: 对list的查找的另一种作法 2006-06-11 21:06 PeakGao

@LOGOS
是的,iterator会随着节点的增删而导致prev,next节点地址无效,你不要去真正记录iterator的地址,记录节点地址就可以了  回复  更多评论   

# re: 对list的查找的另一种作法 2012-02-23 17:35 g

grt  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2006年6月>
28293031123
45678910
11121314151617
18192021222324
2526272829301
2345678

导航

统计

常用链接

留言簿(9)

随笔分类(67)

随笔档案(65)

搜索

最新评论

阅读排行榜

评论排行榜