QHash behaviour



  • Hi guys,

    I want to create a not ordered list organized in pairs. In order to achieve that I used a QHash as follows:

    @
    QHash<int,QString> lista;
    QHash<int,QString>::const_iterator i;
    lista[3] = "Three";
    lista[2] = "Two";
    lista[1] = "One";
    i = lista.constBegin();
    while(i != lista.constEnd())
    {
    qDebug() << i.key() << i.value();
    i++;
    }
    @

    But it's writing a key ordered list:

    1 "One"
    2 "Two"
    3 "Three"

    instead of:

    3 "Three"
    2 "Two"
    1 "One"

    What am I doing wrong?

    Thanks.



  • The order of QHash is undefined. That does not mean that there is no order, just that Qt doesn't guarantee any particular order for you to rely on. If you want a create a non-ordered list, why do you care in which order your results are printed?


  • Moderators

    QHash, as you noted, is unordered. This means that that iterating over it will return the results in an arbitrary order, not necessarily the order in which you inserted them.

    So, I would maintain that you're not doing anything wrong, except perhaps expecting the wrong results.

    What are you trying to accomplish? If you're wanting a container where you can insert arbitrarily-paired objects in a certain order and always fetch them in that order, you could consider using something like
    @QList< QPair<int, QString> >@ which would preserve the sequence in which you inserted the pairs of objects.

    Or, if you're still needing random access to the items, you could insert them into the hash as you are currently doing and additionally keep a QList of the keys in the order in which you inserted them.



  • Xm..
    When i run app at first time i get: 3,2,1;
    Then:2,3,1;
    Then:3,2,1;



  • Again: why is that relevant? Why do you care in what order the results are returned?



  • Actually I need to load it in insertion order.

    Thanks.


  • Moderators

    See my post above.



  • In that case, QHash is not your class to use. Nor is QMap. Use a something like this:
    @
    typedef QPair<int, QString> intStringPair;
    QVector<intStringPair> vector(3);
    //do your inserts
    @

    You may replace the QPair with a struct, and the QVector with a QList if you prefer.



  • So what would be the solution to keep the insertion order and still enjoy the fast lookup of a hash?


  • Moderators

    I suggested above, keeping a QList (or QVector) of the keys for iteration purposes, and using the QHash to store the values.



  • Certainly not as elegant as a single container. Perhaps such a container would make a good addition to Qt?


  • Moderators

    It's not something that I've needed to do very often. And in the instances it has been, it's been simple enough to write a wrapper class that combines the functionality of the the two. But YMMV.



  • QMap is usually a good enough replacement, but when needed, I have also used a list of structures in combination with a QHash. I usually just stored either the list index in the hash, or alternatively a pointer to the struct in the list. Also: you should consider how big your list really is, and if it even makes sense to use a QHash. You say you need QHash, but remember that QHash is not always faster than QMap or even iterating over a QVector.



  • Obviously such a data structure would make sense in large collections where order is important just as fast lookup. In such scenario even a single extra pointer could end up costing plenty of memory. And then there is the indirection performance penalty.



  • Basically, what you are looking for is a hash with multiple keys. There are such classes available, but not in Qt. That does not mean you can't use them. For instance, take a look at "Boost.MultiIndex":http://www.boost.org/doc/libs/1_41_0/libs/multi_index/doc/tutorial/index.html

    Note that the additional storage and indirection penalties will always be there. Either they are inside the container, or external, but you are going to need additional data for bookkeeping if you want to access the data in more than one way.



  • I'm not been able to create QHash<int,QVariant> var.

    Is that impossible?

    Why?

    When I try that I see the errors below:

    In file included from c:\QtSDK\Desktop\Qt\4.8.1\mingw\include\QtCore/QHash:1,
    from ....\complementos/matriz.h:5,
    from ....\complementos\matriz.cpp:1:
    c:\QtSDK\Desktop\Qt\4.8.1\mingw\include\QtCore/qhash.h: In instantiation of 'QHashNode<int, QVariant>':
    c:\QtSDK\Desktop\Qt\4.8.1\mingw\include\QtCore/qhash.h:521: instantiated from 'static void QHash<Key, T>::deleteNode2(QHashData::Node*) [with Key = int, T = QVariant]'
    c:\QtSDK\Desktop\Qt\4.8.1\mingw\include\QtCore/qhash.h:570: instantiated from 'void QHash<Key, T>::freeData(QHashData*) [with Key = int, T = QVariant]'
    c:\QtSDK\Desktop\Qt\4.8.1\mingw\include\QtCore/qhash.h:283: instantiated from 'QHash<Key, T>::~QHash() [with Key = int, T = QVariant]'
    ....\complementos\matriz.cpp:4: instantiated from here
    c:\QtSDK\Desktop\Qt\4.8.1\mingw\include\QtCore/qhash.h:253: error: 'QHashNode<int, T>::value' has incomplete type
    c:\QtSDK\Desktop\Qt\4.8.1\mingw\include\QtCore/qobject.h:66: error: forward declaration of 'struct QVariant'
    mingw32-make.exe[1]: *** [debug/matriz.o] Error 1
    mingw32-make.exe: *** [debug] Error 2
    10:55:23: The process "C:\QtSDK\mingw\bin\mingw32-make.exe" exited with code 2.
    Error while building project cliente (target: Desktop)
    When executing build step 'Make'



  • You probably didn't #include <QVariant>



  • Ok!

    It works!



  • <schoolmaster mode>
    Do you understand how I arrived at that conclusion?



  • No.

    I would appreciate if you explain.



  • @In file included from c:\QtSDK\Desktop\Qt\4.8.1\mingw\include\QtCore/QHash:1, from ....\complementos/matriz.h:5, from ....\complementos\matriz.cpp:1:
    c:\QtSDK\Desktop\Qt\4.8.1\mingw\include\QtCore/qhash.h: In instantiation of ‘QHashNode<int, QVariant>’:
    c:\QtSDK\Desktop\Qt\4.8.1\mingw\include\QtCore/qhash.h:521: instantiated from ‘static void QHash<Key, T>::deleteNode2(QHashData::Node*) [with Key = int, T = QVariant]’
    c:\QtSDK\Desktop\Qt\4.8.1\mingw\include\QtCore/qhash.h:570: instantiated from ‘void QHash<Key, T>::freeData(QHashData*) [with Key = int, T = QVariant]’
    c:\QtSDK\Desktop\Qt\4.8.1\mingw\include\QtCore/qhash.h:283: instantiated from ‘QHash<Key, T>::~QHash() [with Key = int, T = QVariant]’
    ....\complementos\matriz.cpp:4: instantiated from here
    c:\QtSDK\Desktop\Qt\4.8.1\mingw\include\QtCore/qhash.h:253: error: ‘QHashNode<int, T>::value’ has incomplete type
    c:\QtSDK\Desktop\Qt\4.8.1\mingw\include\QtCore/qobject.h:66: error: forward declaration of ‘struct QVariant’
    mingw32-make.exe1: *** [debug/matriz.o] Error 1
    mingw32-make.exe: *** [debug] Error 2
    10:55:23: The process “C:\QtSDK\mingw\bin\mingw32-make.exe” exited with code 2.
    Error while building project cliente (target: Desktop)
    When executing build step ‘Make’
    @

    It is a useful skill to learn how to read compilation errors. This one has a couple of instantiated from... lines, that are not all that relevant here. Especially if they point into the Qt library. Look for the lines related to your own code instead. Line 7 is where it gets interesting. Do you spot the "... has incomplete type"? And on the next line: forward declaration of struct QVariant?

    Hmmm... QVariant is not a struct, but a class. So, it seems your QHash doesn't know all it needs to know about QVariant, as it assumes it is a struct. That led me to the conclusion that you did not include the relevant header file.

    Also, you should understand that using forward declared types in templates doesn't work. You need to have the full type information available when instantiating your template.



  • In range0's defense - those compiler errors are pretty far from informative. It does take some time and experience to be able to make out something useful out of them.

    Andre - how come Creator doesn't offer some Java like feature to automatically add the needed includes? Or maybe there is one already?



  • Nothing to defend. Template errors can be tricky to learn to read, that's why I asked and took the time to explain.

    As for auto-add the header: There is the magic ALT+Enter that you can try. It does offer in some cases to add the needed include. However, I did not find it very reliable in this case. Or rather, I did not find the whole pattern yet. I would not appreciate QtCreator automatically including every class I use. Especially in headers, I tend to use forward declares wherever I can.



  • Andre,

    Thank you very much for your explanation!


Log in to reply
 

Looks like your connection to Qt Forum was lost, please wait while we try to reconnect.