[Qt-interest] New container class needed in Qt

[Roopesh Chander]

When you say map["A"], the QMap makes use of the ordering it maintains
internally to perform the lookup of "A" in O(log n) time. So, to enable fast
lookup, the QMap internally stores its items in the order of the key (in a
skiplist). When iterating over the contents, it retrieves the items in the
same order.

In your case, you seem to be looking for ordering in terms of one key
(insertion time/order) and lookup in terms of another key (A/B/C). It's not
possible to achieve this without using an additional index (that stores
ordering based on the second key).

If you can give up on the lookup-on-A/B/C requirement, just a QMap would
suffice.

If you must have both, you can consider using two data structures like this:
  // for lookups
  QHash<QString /*A*/, QString /*Apple*/> hash;
  // for insertion order
  QList<QString /*A*/>;
The problem with this scheme is that whenever you delete items on a key
(like "A"), updating the QList would take O(n) time.

So, to fix that, we can say:
  // for lookups
  QHash<QString /*A*/, QPair<QString /*Apple*/, int /*insertion order*/>
hash;
  // for insertion order
  QMap<int /*insertion order*/, QString /*A*/>;
where we can cap deletion time to O(log n).

roop.

On Tue, Oct 18, 2011 at 11:04 AM, Mandeep Sandhu <
mandeepsandhu.chd at gmail.com> wrote:

> Hi All,
>
> I have a requirement where I want a Map/Hash like container on which I
> can do key based lookups but also have the items stored in the order
> in which they were inserted.
>
> To elaborate, I'll detail my requirement with a simple example.
>
> Consider that we have received a list of items from some external
> source. The list contains strings in a particular order, eg: ["D",
> "B", "A" , "C"].
>
> I want to however, store some associated values along with each item
> of the list. eg:
> A - "Apple"
> B - "Ball"
> C - "Cat"
> D - "Donkey" :)
>
> I want to store this in a dictionary like structure because I would
> want to later 'lookup' the associated values with a given key
> (A/B/C..).
>
> If I simply store it in a QMap, I can do lookups, but then the items
> would get sorted alphabetically (A,B,C,D). However I want to preserve
> the order of the keys. So using a QHash or QMap won't work.
>
> A way of achieving the require behavior is to use a List, so that the
> order of keys is preserved. But then there's no easy way to lookup any
> arbitrary value (apart from iterating the list).
> I don't want to maintain 2 structures (a list for keeping track of key
> order and a map for value lookup).
>
> Any suggestions about how existing container classes can be used to
> achieve this?
>
> Thanks,
> -mandeep
> _______________________________________________
> Qt-interest mailing list
> Qt-interest at qt.nokia.com
> http://lists.qt.nokia.com/mailman/listinfo/qt-interest
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.qt-project.org/pipermail/qt-interest-old/attachments/20111018/d049516c/attachment.html