QMap implementation
-
QMap in 4.x was implemented with skip-list, now in version 5.0 it's red-black tree. Can someone explain reason for change and what's difference between these implementations (speed/memory/SLOC)?
-
You should ask this on development mailing list, or the developer who did that change (I think KDAB was responsible for container updates).
-
Without having looked at the implementation details in Qt, a red-black tree is simply a type of binary search tree. A binary search tree provides fast key lookup, as required for an associative array (map). That's because, in each search step, the number of items left to be searched is divided by two. However this only works in a "balanced" binary search tree, where each item has the same number of successors on its "left" and "right" side. Unfortunately it can happen that a binary search tree degenerates into something that look pretty much like a linked list! Then key lookup will become slow, because we (essentially) need to walk through all items, one after another. Now one could maintain a "perfectly balanced" binary search tree, by re-balancing after each "insert" or "delete" operation. This gives the best possible search performance, but "insert" and "delete" operations become too expensive! Finally the red-black tree uses a few clever rules that assure that our binary search tree won't degenerate too much, maintaining an "almost balanced" binary search tree. But as the rules are not as strict as with a "perfectly balanced" binary search tree, the red-black tree provides much faster "insert" and "delete" operations, while also guaranteeing fast key lookup (not as fast as a "perfectly balanced" binary search tree, but almost as fast). For details you may look at the Wikipedia article about the red-black tree...
(I never implemented a "skip list" before, but it looks pretty much like a linked-list with a few "shortcut" links)
