[Development] Is QMap Broken

[Mandeep Sandhu]

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

> > 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
classes).

https://github.com/mandeepsandhu/qt-ordered-map

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