为什么QMap使用跳表而不是红黑树？

Question

7

我想知道为什么QMap选择了跳表数据结构而不是红黑树？关于并发数据结构和跳表相对于红黑树的优缺点，有一个非常有趣的SO线程。这确实是一次非常有趣的对话，包含了有用的链接，但是QMap不是线程安全的，它没有默认的互斥锁来同步访问。需要使用包装器或子类化才能实现。

对我来说，编写“手工制作”的跳过列表而不是红黑树并不更简单，所以这也不是很明显。

在非线程安全的Qt容器中，是否存在任何致命缺陷？

提前感谢您的回答。

- sohel

我不太同意。我从来没有理解红黑树。我发现跳表相对容易理解和实现。使用红黑树时，你必须考虑许多不同的插入和删除情况，而这个重新平衡的过程似乎很麻烦。除非你需要良好的最坏情况性能，否则我认为跳表是可以胜任的。 - sellibitze

众口难调。我不敢打赌我能比别人更快地用C++编写跳表，尤其是在你提到的某些麻烦之处。但红黑树是一种杰作数据结构，而且在我看来，QMap作为Qt的基本块之一是值得的 :) - sohel

1

似乎他们在第5版中又切换回了红黑树。 - Martin Drozdik

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- leemes · Accepted Answer

我曾经也认为 QMap 被设计成线程安全的，因此被实现为基于跳表的字典。但似乎这并不是原因。其实它更简单： "可执行文件中的代码更少，每个节点占用的内存更小"。

事实上，QMap 曾经是以红黑树实现的。