c++ - 如何复制红黑树，它的分配器应该是什么

Question

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*/> ？

Answer 1

1. 拷贝构造函数不需要排序，只需要拷贝N即可因此节点 O(N)
2. std::allocator<value_type>里面是“rebo​​und”(搜索“rebind” here )来分配map节点(value + tree wiring data)