分享一个用红黑树实现的 C++的有序容器，特点是迭代器为 random_access_iterator (寻址复杂度为 O(lg n)), c++ 11/14/17 测试都可以用
ppxppx · 2022-09-26 11:09:02 +08:00 · 1338 次点击这是一个创建于 575 天前的主题，其中的信息可能已经有所发展或是发生改变。
curly
C++有序容器模板库
github: https://github.com/lidotcircle/curly
介绍
curly 实现了std::map, std::multimap, std::set 和 std::multiset 的替代品。区别在于 curly 实现的容器的迭代器是 random access iterartor(严格来说并不是, 因为单个寻址操作的时间复杂度为 O(lg n), 而指针为 O(1))。
下图是和 STL 容器的性能对比, 包括insert, erase, copy, std::distance3 和 std::advance。
时间复杂度的对比 std::set vs curly::pset vs curly::set2 (curly::set2的迭代器和std::set一样是bidirectional iterator, 仅用于测试 红黑树 实现的性能)
| 操作 | std::set |
curly::set2 |
curly::pset |
|---|---|---|---|
| insert | O(lg n) | O(lg n) | O(lg n) |
| erase | O(lg n), amortized O(n) | O(lg n) | O(lg n), amortized O(n) |
| copy assignment | O(n) | O(n) | O(n) |
| std::distance | O(n) | O(lg n) | O(n) |
| std::advance(iter, k) | O(k) | O(lg n) | O(k) |
用法
包含单个文件 include rbtree.hpp 即可
| STL container | curly container | curly container without random access iterator |
|---|---|---|
std::set |
curly::pset |
curly::set2 |
std::multiset |
curly::pmultiset |
curly::multiset2 |
std::map |
curly::pmap |
curly::map2 |
std::multimap |
curly::pmultimap |
curly::multimap2 |
PS：如果有用到寻址或者求第 K 元素的需求还是可以尝试下的，其他操作的性能还是不如 STL 的容器。
 |
1
java253738191 2022-09-26 14:13:03 +08:00
这图是用什么画的？
|
 |
2
wZuck 2022-09-26 14:17:40 +08:00
@java253738191 应该是 matplotlib 之类的
|
 |
3
ppxppx OP @java253738191 是 matplotlib, 从 googlebenchmark 生成的结果。
https://github.com/lidotcircle/curly/blob/master/tools/google_benchmark_plot/plot.py |
 |
4
illusory 2022-09-27 01:13:15 +08:00 via iPhone
|
Select Language