zzz's c++ lib
- sbtree_map.h
- sbtree_set.h
- bpptree_map.h
- bpptree_set.h
- chash_map.h
- chash_set.h
- segment_array.h
标准库风格容器
standard library style
- sbtree系列
基于二叉搜索树实现,使用size平衡
可以随机访问,随机访问迭代器
有multimap/multiset实现
- bpptree系列
基于B+树实现
可以随机访问,随机访问迭代器
内存管理使用相同大小内存块
相比标准库map,迭代器在插入/删除元素之后会失效
sizeof(key)非巨大的情况下,插入/删除/查找速度都超过标准库map
sizeof(key)巨大的情况下去,内存占用会偏大,并且性能下降
遍历速度任何条件下都很快!比标准库map快得多!
有map/set/multimap/multiset实现
- chash系列
基于哈希表实现
内存集中分配,尽可能利用缓存加速
插入元素可能导致扩容,产生搬运数据操作
遍历速度飞快!
在允许重复key时候,equal_range返回local_iterator,仅支持erase操作
有map/set/multimap/multiset实现
- segment_array系列
基于B+树的节点管理策略实现
内存管理使用相同大小内存块
任意位置插入/删除成本都很低
- sbtree.natvis
- bpptree.natvis
- chash.natvis
- segment_array.natvis
加入到工程,调试时候有更友好的视图
custom views of native
- split_iterator
迭代器方式进行split
适配std::string
不需要额外的内存存储split后的数据
提供了size(),惰性计算,不推荐使用
提供了operator[index],从头扫描实现,不推荐使用
请保证传入的字符串的有效期,split过程中不会拷贝字符串
string_ref实现不完整,提供了to_value<>替换ato?接口
- sparse_array.h
稀松数组...不成熟的玩意...
#特性比较
#性能测试 各种容器的测试
OSX 10.11.3 (15D21)
XCode 7.1.1 (7B1005)
2.5 GHz Intel Core i7
16 GB 1600 MHz DDR3
- 测试采用与预先随机好的随机数5组,测试结果取平均值
- 横轴为容器元素数量
- 纵轴为平均每个元素耗费时间(纳秒)
- 后面的数字表示key大小(字节)
- insert_o -> 顺序插入
- insert_r -> 随机插入
- foreach -> 遍历
- find -> 查找
- erase -> 删除
- std::set -> std_set
- std::unordered_set -> std_hash
- chash_set -> chash_set
- bpptree_set -> bpptree_set
- std::multiset -> std_mset
- std::unordered_multiset -> std_mhash
- chash_multiset -> chash_mset
- sbtree_multiset -> sbtree_mset
- bpptree_multiset -> bpptree_mset
更详细的表格:
