Câu hỏi Cách lặp qua một std :: set trả về kết quả đã sắp xếp


Vùng chứa std :: set (hoặc std :: map) là một cấu trúc dữ liệu mà STL cung cấp. Trong hầu như tất cả các trình biên dịch, nó được thực hiện như một cây R & B với việc ghi nhật ký được bảo đảm (n), tìm và loại bỏ thời gian.

https://en.wikipedia.org/wiki/Red%E2%80%93black_tree

Trong một cây đỏ và đen, các phần tử được sắp xếp dựa trên toán tử "ít" của phần tử được lưu trữ. Vì vậy, về cơ bản nếu một gốc là N + 1, N sẽ ở bên trái cây con trong khi N + 2 sẽ ở bên phải cây con và thứ tự này sẽ được quyết định bởi toán tử ít hơn.

Câu hỏi của tôi là khi thực thi mã dưới đây:

 set<unsigned long>::iterator it;
 for (it = myset.begin(); it != myset.end(); it++) {
     cout << *it;
 }

các phần tử được trả về theo thứ tự được sắp xếp. Làm thế nào điều này có thể được xem xét thực tế là cấu trúc dữ liệu cơ bản là một cây đỏ và đen? Có một danh sách liên kết riêng biệt được lưu trữ để có thể lặp lại từ cây con ngoài cùng bên trái đến cây con ngoài cùng bên phải không? Nếu không phải là cơ chế đằng sau việc thực hiện này bằng cách sử dụng một cây R & B?


8
2017-11-04 16:02


gốc


Tôi nghĩ rằng đây có thể là bản sao của stackoverflow.com/questions/2558153/… - i4h
Nó không phải là một bản sao của câu hỏi trên, mà về cơ bản trả lời một thông tin mà tôi đã nêu trong câu hỏi này - cấu trúc dữ liệu cơ bản là cây R & B. - ralzaul


Các câu trả lời:


Chúng ta có thể tìm thấy một câu trả lời dứt khoát bằng cách xem mã nguồn (libstdc ++ 5.2.1 trong trường hợp này). Đây là cách một nút cây trông như thế nào:

// <libstdc++>/include/bits/stl_tree.h
struct _Rb_tree_node_base {
  typedef _Rb_tree_node_base* _Base_ptr;

  _Rb_tree_color    _M_color;
  _Base_ptr     _M_parent;
  _Base_ptr     _M_left;
  _Base_ptr     _M_right;

  // ...
}

Vì vậy, mỗi nút chứa một màu, và con trỏ đến cha mẹ của nó và con trái và phải của nó. Gia tăng được thực hiện như sau:

//  <libstdc++>/include/bits/stl_tree.h
struct _Rb_tree_iterator {
  _Self& operator++() {
    _M_node = _Rb_tree_increment(_M_node);
    return *this;
  }

// ...

private:
    _Base_ptr _M_node;
};

Số gia tăng thực tế không nằm trong tiêu đề công khai nữa, nhưng trong phần được biên soạn của thư viện:

// <libstdc++>/src/c++98/tree.cc
static _Rb_tree_node_base* local_Rb_tree_increment(_Rb_tree_node_base* __x) throw ()
{
    if (__x->_M_right != 0) {
        __x = __x->_M_right;
        while (__x->_M_left != 0)
            __x = __x->_M_left;
     } else {
         _Rb_tree_node_base* __y = __x->_M_parent;
         while (__x == __y->_M_right)  {
             __x = __y;
             __y = __y->_M_parent;
         }
         if (__x->_M_right != __y)
             __x = __y;
     }
     return __x;
 }

Vì vậy, cuối cùng, đó là một cuốn sách giáo khoa thực hiện traversal cây: Các iterator giữ một con trỏ đến nút "hiện tại", và để có được đến nút tiếp theo nó đi lên trong cây miễn là nó đến từ các con phải. Nếu nó đến từ đứa trẻ bên trái, nó sẽ rơi xuống nút con ngoài cùng bên trái của đứa trẻ bên phải.


8
2017-11-04 18:20





Trình vòng lặp thực hiện [tra cứu cây đầu tiên theo chiều sâu].1 Điều này thường được thực hiện trong một thuật toán đệ quy. Vì việc sử dụng trình vòng lặp không thể được thực hiện đệ quy, nên trình vòng lặp trong nội bộ giữ một chồng nơi nó được sao cho nó có thể quay trở lại cây.

Cập nhật: nhờ Chris Dodd cho chỉ ra rằng các nút cây RB có con trỏ đến cha mẹ của họ, do đó, các iterator chỉ đơn giản là có thể làm theo những người lên đến các yếu tố tiếp theo.


2
2017-11-04 16:14



Các nút cây RB chứa các con trỏ tới nút cha, vì vậy không cần một ngăn xếp - một trình lặp (iterator) chỉ là một con trỏ tới một nút, và tăng hoặc giảm nó chỉ đi qua cây. - Chris Dodd
do đó, một sự truyền tải trật tự được thực hiện bằng cách sử dụng con trỏ lạc hậu từ lá đến gốc? - ralzaul