这是一个创建于 1116 天前的主题，其中的信息可能已经有所发展或是发生改变。
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