QHash behaviour

? Offline

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.

andre

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?

mlong

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.

? Offline

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

andre

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

? Offline

Actually I need to load it in insertion order.

Thanks.

mlong

See my post above.

andre

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.

? Offline

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

mlong

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

? Offline

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

mlong

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.

andre

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.

? Offline

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.

andre

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.

? Offline

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'

andre

You probably didn't #include <QVariant>

? Offline

Ok!

It works!

andre

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

? Offline

No.

I would appreciate if you explain.