Q #2 已更新。请回答新问题#2! --Dannyu NDos，2017 年 1 月 17 日
我一直在制作一个名为 DRV 的关联容器, 表示有限离散随机变量。它是一棵红黑树。我从标准 std::map 得到了帮助, 但我也对此感到困惑。
问题 #1. 它的复制函数如何具有 O(n) 时间复杂度？不应该是 O(n log n) 吗？我的DRV的复制构造函数具有 O(log n)，使用 std::async , 不过。
旧问题 #2。 为什么它的默认分配器是 std::allocator<value_type> ？它不应该分配容器的内部节点类型吗？在这种情况下，不需要单独动态分配值。
新问题 #2。鉴于 Alloc是容器的分配器类型，容器必须持有什么分配器，Alloc或 typename std::allocator_traits<Alloc>::template rebind_alloc</*the type of the node*/> ？
最佳答案
- 拷贝构造函数不需要排序，只需要拷贝
N即可因此节点O(N) -
std::allocator<value_type>里面是“rebound”(搜索“rebind” here )来分配map节点(value + tree wiring data)
关于c++ - 如何复制红黑树，它的分配器应该是什么，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35218589/