65
правок
Изменения
м
==Примечания== <references />* [[List order maintance]]
Minor: interwiki to list order maintance added
[[Файл:Полная персистентность.png]]
Для реализации описанного в предыдущем пункте метода преобразования структур данных в полностью персистентные нам нужен такой список, который поддерживает операции <tex>\mathrm{insert After(p,q})</tex> (вставить <tex>q</tex> после <tex>p</tex>) и <tex>\mathrm{order(p,q)}</tex> (должен уметь отвечать на запросы вида "<tex>p</tex> лежит в этом списке до <tex>q</tex>"). <tex>\mathrm{order(p,q)}</tex> возвращает <tex>1</tex>, если <tex>p</tex> лежит до <tex>q</tex> и <tex>0</tex> иначе. Это список с поддержкой запроса о порядке [[List order maintenance|''List Order Maintenance'' <ref>[http://www.cs.au.dk/~gerth/aa11/slides/order.pdf List Order Maintenance]</ref>], который обе эти операции делает за <tex>O(1)</tex>.
В ''change log'' «толстого» узла теперь будем добавлять два события: одно указывает на изменение, произошедшее в соответствующей версии, а другое на его отмену. События будут добавляться в ''change log'' не по номерам версий, а по их порядку в списке версий ''List Order Maintenance''.
* [[Персистентная очередь]]
* [[Персистентный дек]]
== Источники информации ==
