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

Question

Q #2 已更新。请回答新问题#2！ --Dannyu NDos，2017 年 1 月 17 日

我一直在制作一个名为 DRV 的关联容器，它代表一个有限的离散随机变量。它是一棵红黑树。我从标准 std::map 那里得到了帮助，但我也从中感到困惑。

Q #1. 它的copy ctor怎么有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

拷贝构造函数不需要排序，只需要拷贝N个节点即可O(N)
std::allocator<value_type>是"rebound"（搜索"rebind"here）里面分配map节点（值+树布线数据）

Answer 2

我自己对问题 #1 的回答： 我是这样做的：
1.递归复制开头的(容器大小/2)个元素，颜色全黑
2.复制下面的元素，这是最中心的元素，将成为根元素，颜色为黑色。
3.递归复制最后剩下的元素，颜色全黑。 4. 将2.中复制的元素与1.中复制的元素中的根元素连接起来
5. 将2.中复制的元素与3.中复制的元素中的根元素连接起来
6. 将最深的元素涂成红色。
例如：http://imgur.com/gallery/tUtoK
这将在 O(n) 时间内生成一棵完美平衡的 red-black 树。
即使我使用 std::async 将其并行化，由于阿姆达尔定律，它仍然具有 O(n) 时间复杂度。
这是实现：

/* includes... */
template <class T, class Comp = std::less<T>, class Alloc = std::allocator<T>> class set { // A red-black tree, motivated from std::set
public:
    /* typedefs... */
protected:
    typedef RedBlackTreeNode<T> Nodev; // The node type
    typedef Nodev *pNodev; // The pointer to node type
    typedef typename std::allocator_traits<Alloc>::template rebind_alloc<Nodev> Rebounda; // Rebound allocator type
    typedef std::allocator_traits<Rebounda> Reboundat; // Rebound allocator traits
    mutable ListNode_e endn; // The past-the-end node
    size_type sz; // Size
    value_compare comp; // comparator
    Rebounda alloc; // allocator
    pNodev initp() const noexcept { // the pointer to the node at the end
        return static_cast<pNodev>(endn.pre);
    }
    void partial_clear(const_iterator i) noexcept { // Destructs the node at i and after
        while (cend() != i) {
            pNodev p = static_cast<pNodev>(i++.refer);
            Reboundat::destroy(alloc, p);
            Reboundat::deallocate(alloc, p, 1);
        }
    }
    /// partial_copy_Lvalue, partial_assign_Lvalue
    /// @steps
    ///    1. Copy the (container size / 2) elements at the beginning recursively, with color all black.
    ///    2. Copy the following element, which is the centermost element and will be the root element, with color black.
    ///    3. Copy the remaining element at the end recursively, with color all black.
    ///    4. Connect the element copied in 2. with the root element among the elements copied in 1.
    ///    5. Connect the element copied in 2. with the root element among the elements copied in 3.
    ///    6. Paint the deepest elements red.
    /// @param
    ///    size: the size of the container
    ///    other_i: the iterator refering the element to be copied in 2.
    /// @return
    ///    pNodev: the pointer to the root of the (partial) tree
    ///    size_type: the depth of the shallowest leaf node of the (partial) tree
    std::pair<pNodev, size_type> partial_copy_Lvalue(size_type size, const_iterator &&other_i) {
        if (size == 0)
            return std::make_pair(nullptr, 0);
        else {
            std::pair<pNodev, size_type> l = partial_copy_Lvalue(size >> 1, std::move(other_i)); /// 1.
            Reboundat::construct(alloc, Reboundat::allocate(alloc, 1), endn, Nodev::color_t::black, *other_i++); /// 2.
            pNodev resultp = initp();
            std::pair<pNodev, size_type> r = partial_copy_Lvalue(size - (size >> 1) - 1, std::move(other_i)); /// 3.
            resultp->left = l.first; /// 4.
            resultp->right = r.first; /// 5.
            if (resultp->left)
                resultp->left->parent = resultp; /// 4.
            if (resultp->right)
                resultp->right->parent = resultp; /// 5.
            if (l.second < r.second && resultp->right)
                resultp->right->colorleavesred(); /// 6, case 1
            else if (l.second > r.second && resultp->left)
                resultp->left->colorleavesred(); /// 6, case 2
            return std::make_pair(resultp, std::min(l.second, r.second) + 1);
        }
    }
    void copy(const set &other) { // Copies the nodes from other. Precondition : this is empty
        if (!other.empty())
            partial_copy_Lvalue(other.sz, other.cbegin());
    }
    std::pair<pNodev, size_type> partial_assign_Lvalue(size_type size, ListIt<T> &&this_i,
        const_iterator &&other_i, const const_iterator &other_cend) {
        if (size == 0) {
            if (other_i == other_cend)
                partial_clear(const_iterator(this_i.refer));
            return std::make_pair(nullptr, 0);
        } else {
            std::pair<pNodev, size_type> l = partial_assign_Lvalue(size >> 1, std::move(this_i), std::move(other_i), other_cend); /// 1.
            std::pair<pNodev, size_type> r;
            pNodev resultp;
            if (this_i.refer == cend().refer) {
                Reboundat::construct(alloc, Reboundat::allocate(alloc, 1), endn, Nodev::color_t::black, *other_i++); /// 2, case 1
                resultp = initp();
                r = partial_copy_Lvalue(size - (size >> 1) - 1, std::move(other_i)); /// 3, case 1
            } else {
                resultp = static_cast<pNodev>(this_i.refer);
                static_cast<pNodev>(this_i.refer)->parent = nullptr;
                static_cast<pNodev>(this_i.refer)->color = Nodev::color_t::black;
                *this_i++ = *other_i++; /// 2, case 2
                r = partial_assign_Lvalue(size - (size >> 1) - 1, std::move(this_i), std::move(other_i), other_cend); /// 3, case 2
            }
            resultp->left = l.first; /// 4.
            resultp->right = r.first; /// 5.
            if (resultp->left)
                resultp->left->parent = resultp; /// 4.
            if (resultp->right)
                resultp->right->parent = resultp; /// 5.
            if (l.second < r.second && resultp->right)
                resultp->right->colorleavesred(); /// 6, case 1
            else if (l.second > r.second && resultp->left)
                resultp->left->colorleavesred(); /// 6, case 2
            return std::make_pair(resultp, std::min(l.second, r.second) + 1);
        }
    }
public:
    /* constructors... */
    virtual ~set() {
        clear();
    }
    set &operator = (const set &other) {
        sz = other.sz;
        if (std::allocator_traits<Alloc>::propagate_on_container_copy_assignment::value && alloc != other.alloc) {
            clear();
            alloc = other.alloc;
            copy(other);
        } else
            partial_assign_Lvalue(other.sz, ListIt<T>(cbegin().refer), other.cbegin(), other.cend());
        return *this;
    }
    /* ... */
};

另请参阅：

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

How to copy a red-black tree, and what should its allocator be

c++

copy

containers

assign

allocator