Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

why does qmap uses skiplist instead ob rb-tree?

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.

like image 371
sohel Avatar asked Oct 01 '12 10:10

sohel


1 Answers

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"

like image 101
leemes Avatar answered Nov 10 '22 02:11

leemes