why does qmap uses skiplist instead ob rb-tree?

Question

I wounder why does QMap realised over skiplist data-structure and not rb-tree? There is very interesting SO thread about concurrency data-structs and skip-list benefits over rb-tree, pros and cons. It is indeed VERY interesing dialog with helpfull links, but QMap is not thread safe, it doesnt do any mutex locking for syncing access out of the box. It requires wrapper or subclassing.

For me its not simplier to write "hand-made" skiped list instead of rb-tree, so this is not obvious either.

Is there any kill-feature in context of non thread-safe Qt container?

Tnx in advance.

Antiicer

I beg to differ. I never understood RB trees. I find skip lits rather easy to understand and implement. With RB trees you have to consider lots of different cases for insert and delete and this rebalancing stuff seems like a PITA. Unless you require good worst case performance, skip lists are fine, I think. – Grimonia

Many men, many minds. I wont bet that I'll writ rb-tree realisation faster then someone will write skip list, especially in c++.yp some kind of PITA as you mentioned. But rb-tree is a masterpiece data-structure, and IMHO QMap deservs it as beeing one of the base blocks of Qt:) – Antiicer

It seems that they switched back to the rb-tree in version 5 – Melyndamem

Answer 1

I once thought too that QMap is designed to be thread-safe and thus implemented as a skip list based dictionary. Apparently this doesn't seem to be the reason. It is much simpler: "Less code in the executable and less memory per node."

Indeed, QMap once was implemented as a RB-tree.

Source: Qt Quarterly 19, Section "Associative Containers"

Culpable