почему qmap использует skiplist вместо ob rb-tree?

Я удивляюсь, почему QMap реализует структуру данных skiplist, а не rb-tree? Существует очень интересный поток SO о структурах данных параллелизма и преимуществах пропуска списка по сравнению с rb. -дерево, плюсы и минусы. Это действительно ОЧЕНЬ интересный диалог с полезными ссылками, но QMap не является потокобезопасным, он не выполняет никаких блокировок мьютексов для синхронизации доступа из коробки. Требуется оболочка или создание подклассов.

Для меня не проще написать «сделанный своими руками» пропущенный список вместо rb-tree, так что это тоже неочевидно.

Есть ли какая-нибудь функция уничтожения в контексте не поточно-безопасного контейнера Qt?

Tnx заранее.


c++ qt red-black-tree skip-lists qmap
person sohel    schedule 01.10.2012    source источник
comment
Позволю себе не согласиться. Я никогда не разбирался в деревьях РБ. Я считаю, что skip lits довольно легко понять и реализовать. С деревьями RB вы должны учитывать множество различных случаев для вставки и удаления, и этот материал по ребалансировке выглядит как PITA. Я думаю, что если вам не нужна хорошая производительность в худшем случае, списки пропуска подойдут.   -  person sellibitze    schedule 01.10.2012
comment
Много мужчин, много умов. Я не буду держать пари, что я напишу реализацию rb-дерева быстрее, чем кто-то напишет список пропуска, особенно в c ++. Yp какой-то PITA, как вы упомянули. Но rb-tree - это шедевральная структура данных, и IMHO QMap заслуживает его как одного из базовых блоков Qt :)   -  person sohel    schedule 01.10.2012
comment
Похоже, что в версии 5 перешли обратно на rb-tree   -  person Martin Drozdik    schedule 17.06.2013

Ответы (1)


arrow_upward
3
arrow_downward

Однажды я тоже подумал, что QMap спроектирован как потокобезопасный и поэтому реализован как словарь на основе списка пропуска. Видимо, причина не в этом. Это намного проще: «Меньше кода в исполняемом файле и меньше памяти на узел».

Действительно, QMap когда-то был реализован как RB-дерево.

Источник: Qt Quarterly 19, раздел «Ассоциативные контейнеры»

person leemes    schedule 01.10.2012