LINUX.ORG.RU
решено Форум — Development  

operator++ для элементов бинарного дерева

 ,


0

1

Как реализован операторы operator++ для бинарного дерева, лежащего в основе std::set, std::map ... и в других ассоциативных контейнерах STL? Интересует алгоритм, согласно которому принимается решение: по имеющемося указателю перейти к следующему указателю. (Т.е. что считать следующим указателем?).

 std::set<int> s;
 s.insert(3);
 s.insert(2);
 s.insert(5);
 std::set<int>::iterator i = s.begin();
 std::cout << *i << ' ';
 ++i;
 s.insert(1);
 std::cout << *i << ' ';

std::map хранит данные в отсортированном виде, соотвественно, итерация по ним будет в порядке возрастания.

std::set - не ассоциативный контейнер, но внутри устроен точно так же, то есть, тоже в порядке возрастания.

BTW, этим порядком можно управлять. См. объявления шаблонов для каждого контейнера.

Как с этим делом в unordered_map, не знаю, подозреваю, что там тоже отсортировано, но по значению хеш-функции.

E ★★★
()
Ответ на: комментарий от E

насколько я понимаю map и set хранят все внутри в виде сбалансированного двоичного дерева, и конечно же элементы отсортированы. И не очень мне понятно как имея только указатель на узел дерева переместится к следующему элементу ... хотелось бы что-то про разработку итератора с operator++ для деревьев почитать.

Самому кроме как обойти дерево и сформировать вспомагательный список, например, при вызове метода begin никаких идей не приходит.

linux276
() автор топика
Ответ на: комментарий от linux276

Обходить всё дерево не надо, насколько я понимаю, достаточно подняться на уровень выше, там не так много вариантов: либо спуститься в правую ветку, либо поняться ещё на уровень выше и снова проверить. Для этого достаточно знать только текущий элемент, больше ничего. begin указывает на самый левый лист, спуститься к нему - не проблема, возможно, его ещё и кешируют.

Про разработку ничего не знаю, увы, но всегда можно покопаться в исходниках <set> и <map>, контейнеры шаблонные и в хедерах всё есть.

E ★★★
()
Ответ на: комментарий от E

в исходниках в stl_tree.h все предельно просто ) : 

      _Self&
      operator++()
      {
        _M_node = _Rb_tree_increment(_M_node);
        return *this;
      }

где реализация _Rb_tree_increment пока не понятно.

но есть ссылка на Cormen, Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990)

linux276
() автор топика
Ответ на: комментарий от linux276

где реализация _Rb_tree_increment

в либе.

Но E тебе верно сказал. В каждом узле дерева хранится ссылка на родителя, 

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

инкремент просто переходит к нему, потом идет опять к самому нижнему левому листу, но уже справа от родителя. и тд.

Впрочем дерево можно обойти и без опоры на родителя, используя стек.

anonymous
()
Ответ на: комментарий от linux276

Почитай про представления бинарных деревьев, для начала.

pon4ik ★★★★★
()

нырнуть в сырцы? чё увидел требующего объяснения?

qulinxao ★★☆
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
Development