On Thu, Nov 6, 2014 at 6:24 AM, Robert Knight <[email protected]> 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
_______________________________________________ Development mailing list [email protected] http://lists.qt-project.org/mailman/listinfo/development
