注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

gmd20的个人空间

// 编程和生活

 
 
 

日志

 
 

C++ 管理一个排好序的vector, sorted_vector , ordered-vector boost::flat_[multi]map/set  

2013-03-07 00:26:12|  分类: 程序设计 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
打算试用一个排好序的vector来做另外一个 “字符串+ value” 的vector的索引, 其实就是字符串作为key,可以通过fnv32  的hash函数计算key,用于key的比较和索引。

之所以用排好序的vector而不是map,是出于考虑。我觉得vector内存连续比map那种好,可以对排序的vector 做二分查找,跟map的l查找的时间复杂度是一样的(文档说排序的vector查找要比map快一倍。) 应用中的插入和删除操作很少,这样即使排序的vector的插入和删除性能比map要差(O(N) 和 O(log N)的差异),那也影响不大

最初是这篇文章比较这两种结构的适用场合和性能差异的,写的比较详细,可以看一下。
Why you shouldn't use set (and what you should use instead)
Matt Austern
 http://lafstern.org/matt/col1.pdf 

Andrei Alexandrescu 在 Modern c++ Design 的一书给出了一个 AssocVector 的实现,底层封装了sorted vector,对外提供和map一样的接口。
http://loki-lib.sourceforge.net/html/a00025.html    需要梯子才能访问

根据boost的文档http://www.boost.org/doc/libs/1_53_0/doc/html/container/non_standard_containers.html#container.non_standard_containers.flat_xxx
有以下优点
  • Faster lookup than standard associative containers
  • Much faster iteration than standard associative containers
  • Less memory consumption for small objects (and for big objects if shrink_to_fit is used)
  • Improved cache performance (data is stored in contiguous memory)
  • Non-stable iterators (iterators are invalidated when inserting and erasing elements)
  • Non-copyable and non-movable values types can't be stored
  • Weaker exception safety than standard associative containers (copy/move constructors can throw when shifting values in erasures and insertions)
  • Slower insertion and erasure than standard associative containers (specially for non-movable types)

facebook 开源的c++库folly里面也有一个实现
根据说明,最好是在元素个数比较少,删除插入操作相对 lookup操作少很多情况下使用比较有优势。

最初是通过http://stackoverflow.com/questions/2710221/is-there-a-sorted-vector-class-which-supports-insert-etc  这里的信息找到上面的资料的
  评论这张
 
阅读(792)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017