[Qt-interest] New container class needed in Qt

[Roopesh Chander]

Interesting. I didn't know Python had this. Python's OrderedDict internally
seems to use two data structures:
- a doubly linked list for ordering items - stores key ("A") and value
("Apple")
- a hash: key is "A"; value is a pointer to a linked list node

This is somewhat similar to our solution with a QHash and a QMap, but more
optimal. Our QHash mapped the key to an index in the QMap, and we have make
a second lookup in the QMap to delete a key: O(1) + O(log n)  time. The
Python data structure needs just one lookup in O(1), and after that, it's
just pointer manipulations.

Unfortunately, I don't think we can implement this approach in Qt with just
a QLinkedList (which is a doubly linked list) and a QHash, because afaik,
QLinkedList does not let us manipulate its pointers directly.

A new container that can do this would be handy, yes.

roop.

On Tue, Oct 18, 2011 at 12:58 PM, Mandeep Sandhu <
mandeepsandhu.chd at gmail.com> wrote:

> On Tue, Oct 18, 2011 at 11:45 AM, Roopesh Chander <roop at forwardbias.in>
> wrote:
> > 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).
>
> Actually, I was looking for something like what Python has - an
> ordered dictionary:
>
> http://docs.python.org/library/collections.html#collections.OrderedDict
>
> Maybe we should have a similar equivalent in Qt as well? :)
>
> >
> >   // 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).
>
> Thanks, this approach looks promising.
>
> -mandeep
>
> > 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/b377fa61/attachment.html