[Development] Is QMap Broken

Mandeep Sandhu mandeepsandhu.chd at gmail.com
Thu Nov 6 17:51:43 CET 2014

On Thu, Nov 6, 2014 at 6:24 AM, Robert Knight <robertknight at gmail.com>

> > Consider the following program, shouldn't the end() iterator place each
> key at the end of the newly created QMap. Instead, the keys and subsequent
> iterations are sorted (somehow).
> Yes, that's the whole point of a QMap. If you don't care about the order
> of elements in a map, you should almost always use a hash
> (std::unordered_map or QHash), it is much faster - O(1) vs O(log(n)) for
> insertion and lookup.
> If you want a data structure that combines fast lookup and remembers the
> order of insertion, that is sometimes referred to as an 'ordered map' and
> there are implementations around - typically they glue together a linked
> list and a hash map.

Here's an implementation of an 'ordered map' I wrote sometime back. As
Robert mentioned, it's implemented using a linked list and a hash (Qt


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.qt-project.org/pipermail/development/attachments/20141106/87f1d87c/attachment.html>

More information about the Development mailing list