分享一个用红黑树实现的 C++的有序容器，特点是迭代器为 random_access_iterator (寻址复杂度为 O(lg n)), c++ 11/14/17 测试都可以用

[ppxppx]

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 的容器。

[java253738191]

这图是用什么画的？

[wZuck]

@java253738191 应该是 matplotlib 之类的

[ppxppx]

@java253738191 是 matplotlib, 从 googlebenchmark 生成的结果。

https://github.com/lidotcircle/curly/blob/master/tools/google_benchmark_plot/plot.py

[illusory]

https://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/tree_based_containers.html GNU 扩展里有类似物

[ppxppx]

@illusory 确实是，😂😂之前都没找到类似的