如何複製紅黑樹，其分配器應該是什麼

Question

Q＃2更新。請回答新的Q＃2！ - Dannyu NDos，2017年1月17日

我一直在製作一個名爲DRV的關聯容器，它代表了一個有限的離散隨機變量。這是一棵紅黑色的樹。我從標準std::map得到了幫助，但我也對此產生了困惑。

Q＃1。它的拷貝如何具有O（n）時間複雜度？它不應該是O（n log n）嗎？不過，我的DRV的拷貝文件有O（log n），使用std::async。

舊Q＃2。爲什麼它的默認分配器是std::allocator<value_type>？它沒有分配容器的內部節點類型？在這種情況下，這些值不需要單獨動態分配。

新Q＃2。由於Alloc是容器的分配器類型，容器必須擁有哪個分配器，Alloc或typename std::allocator_traits<Alloc>::template rebind_alloc</*the type of the node*/>？

Answer 1

1. 拷貝構造函數不需要進行排序，它只是需要複製這樣O(N)
2. std::allocator<value_type>N節點是「反彈」（搜索「重新綁定」 here）內部分配地圖節點（值+樹佈線數據）

Answer 2

我自己回答問題1：我這樣做是這樣的：
複製（容器大小/ 2）元素在遞歸地開始，顏色全黑。
2.複製以下元素，它是最中心的元素，並且是根元素，其顏色爲黑色。
3.遞歸複製剩餘的元素，顏色全部爲黑色。 4.連接元件在2.複製與1.
5.複製的元素中的根元素連接在2.複製與複製的元素之間的根元素的元素在3.
6.把最深的元素塗成紅色。
例如：http://imgur.com/gallery/tUtoK
這將在O（n）時間內完成一個完美平衡的紅黑樹。
即使我使用std::async將其並行化，由於Amdahl定律，它仍然具有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 is allocator-aware container assignment implemented?