К вопросу о C++, как operator++ работает в std::map? Ведь обход двоичного (красно-черного)
дерева требует стека и рекурсии в общем случае. А если в итераторе только ссылка на один текущий узел,
то поиск следующего по порядку превращается в нетривиальную задачу для "листьев" дерева: нужно подняться
наверх до узла имеющего "правого" наследника и спуститься вниз. Не быстро.
Для решения подобной проблемы известны прошитые деревья, но почему STL их не использует?
Для различения указателей и прошивки можно использовать раскрашенные указатели, благо у узла выравнивания явно чётное.
Здравствуйте, fk0, Вы писали:
fk0>Для решения подобной проблемы известны прошитые деревья, но почему STL их не использует?
Потому-что, как обычно всё в STL, пытаются балансировать по занимаемой памяти и скорости. Если решение общее и не известно как это дерево будут чаще использовать, такой подход кажется оптимальным. Если дерево позиционируется как map — ассоциативный массив, то эти прошития нафиг не уперлись. Если по дерево необходимо очень быстро ходить туда/сюда, то предпочтительней flatmap какой-нибудь.
Здравствуйте, fk0, Вы писали:
fk0>К вопросу о C++, как operator++ работает в std::map? Ведь обход двоичного (красно-черного) fk0>дерева требует стека и рекурсии в общем случае. А если в итераторе только ссылка на один текущий узел, fk0>то поиск следующего по порядку превращается в нетривиальную задачу для "листьев" дерева: нужно подняться fk0>наверх до узла имеющего "правого" наследника и спуститься вниз. Не быстро.
Так количество перемещение пропорциональна высоте дерева, а она имеет логарифмическую зависимость.
fk0>Для решения подобной проблемы известны прошитые деревья, но почему STL их не использует?
Потому как был выбран компромисс. Если вы еще два указателя добавите по будет использоваться больше памяти.
Можно было вообще обойтись без указателя на родителя, но итераторы были бы немного другими.
Здравствуйте, Videoman, Вы писали:
V>Здравствуйте, fk0, Вы писали:
fk0>>Для решения подобной проблемы известны прошитые деревья, но почему STL их не использует?
V>Потому-что, как обычно всё в STL, пытаются балансировать по занимаемой памяти и скорости. Если решение общее и не известно как это дерево будут чаще использовать, такой подход кажется оптимальным. Если дерево позиционируется как map — ассоциативный массив, то эти прошития нафиг не уперлись. Если по дерево необходимо очень быстро ходить туда/сюда, то предпочтительней flatmap какой-нибудь.
Но ведь прошивка практически ничего не стоит. Она не занимает памяти, она ускоряет итератор, она незначительно замедляет (O(1)) прочие операции.
fk0>>Для решения подобной проблемы известны прошитые деревья, но почему STL их не использует? _>Потому как был выбран компромисс. Если вы еще два указателя добавите по будет использоваться больше памяти.
Но ведь прошитое дерево не требует дополнительной памяти. Эти два указателя хранятся вместо NULL в листьях
не имеющих дочерних элементов.
_>Можно было вообще обойтись без указателя на родителя, но итераторы были бы немного другими.
Мне кажется, тогда итератор невозможно было бы сделать. Маленький итератор. В условно большом можно
хранить ссылку на дерево и путь в дереве конечно...
Здравствуйте, fk0, Вы писали:
fk0> Но ведь прошивка практически ничего не стоит. Она не занимает памяти, она ускоряет итератор, она незначительно замедляет (O(1)) прочие операции.
Значит не всё так просто. Еще один бит признак нужно где-то хранить. Насколько я знаю, некоторые реализации, для хранения признака ч/к узла используют признак четности/не четности адреса. А тут еще один бит нужно где-то хранить. Нужно изучить вопрос. В любом случае, если реализация прошитого дерева действительно не требует затрат по памяти, по скорости и не меняет интерфейс std::map, то можно делать предложения в комитет .
Здравствуйте, σ, Вы писали:
σ>Шитое дерево или штопаное, красно-чёрное или серо-зелёное — это чисто деталь реализации.
Так вопрос не в этом. Вопрос почему, если якобы одни преимущества и никаких недостатков, почему оно из коробки не такое? Я считаю что нужна дополнительная память. Дерево и так до хрена памяти жрёт, если честно, поэтому я им пользуюсь только в крайних случаях.
Вопрос про реализацию или спецификацию ?
Если реализовать согласно стандарту std::map то выходит красно-чёрное дерево.
Если вам порядок не важен есть std::unordered_map.
Обещают вроде как std::flat_map в C++23.
Стандартная бибилиотека не должна реализовывать все виды деревьев, которые есть.
Для этого есть другие библиотеки.
fk0>К вопросу о C++, как operator++ работает в std::map? Ведь обход двоичного (красно-черного) fk0>дерева требует стека и рекурсии в общем случае. А если в итераторе только ссылка на один текущий узел, fk0>то поиск следующего по порядку превращается в нетривиальную задачу для "листьев" дерева: нужно подняться fk0>наверх до узла имеющего "правого" наследника и спуститься вниз. Не быстро.
Да, подняться и опуститься. Overhead точно такой же, как в случае рекурсии, но код на вид более сложный.
Здравствуйте, fk0, Вы писали:
fk0> Но ведь прошитое дерево не требует дополнительной памяти. Эти два указателя хранятся вместо NULL в листьях fk0>не имеющих дочерних элементов.
Разве в листьях там NULL? А не ссылка на специальный "невалидный" элемент?
Значит не всё так просто. Еще один бит признак нужно где-то хранить. Насколько я знаю, некоторые реализации, для хранения признака ч/к узла используют признак четности/не четности адреса. А тут еще один бит нужно где-то хранить. Нужно изучить вопрос. В любом случае, если реализация прошитого дерева действительно не требует затрат по памяти, по скорости и не меняет интерфейс std::map, то можно делать предложения в комитет 
.
