A Qt collection that is ordered and can be accessed via hash key ... ?

[doberkofler]

I would need to keep track of a sorted (the order does matter) list of entries that should nevertheless be hashed using a QString for quick look up.
If i do understand the Qt generic collection classes correctly this cannot be done or at least not in an easy way.
- QHash provides the keyed access but does not keep track of the order of insertion
- QList on the other hand has it's order but does not support hashed access
What would be the best way to solve this in Qt?

[JohannesMunk]

What about QMap? Ordered by key..

and in case of multiple values for the same key.. by insertion-order:

"Returns a list containing all the values associated with key key, from the most recently inserted to the least recently inserted one."

Johannes

[doberkofler]

Unfortunately I need to order of insertion and this would not seem to work with QMap.

[JohannesMunk]

Just keep a separate QList pointing to the same items then. That's how I did that in the past.

You can of course write your own ListHash class that provides/handles both.

There is not a single class for that, because the internal structure of a hashmap doesn't allow to keep the order of insertion plainly visible. Items are put to a certain slot (determined by the hash function) of the hashmap regardless of when they are added. That's what makes the lookup fast. You can't efficiently provide a sequential access in that same data structure. You just use a second one..

Johannes

[wysota]

Unfortunately I need to order of insertion and this would not seem to work with QMap.

You can't have both at once without duplicating information. Hash-based access requires items to be ordered (somehow) according to the hash, otherwise using the hash has no benefit. Long story short - you need two structures, as already suggested.

But I would do it the other way round - keep the "main" data in the list and have a hash for mapping item id to position in the sequence. It somehow seems more appropriate to me than storing data in the hash and then the pointers to those items in the list.

template <class T> class HashedList : public QVector<T> {
public:
//...
void addItem(const T &item) {
  int h = qHash(item);
  int pos = count();
  m_hash.insert(h, pos);
  append(item);
}
 int hashedIndexOf(const T& item) const {
   int h = qHash(item);
   return m_hash.value(h, -1);
 }
 // etc.
private:
  QHash<int, int> m_hash;
};

template <class T> class HashedList : public QVector<T> {
public:
//...
void addItem(const T &item) {
  int h = qHash(item);
  int pos = count();
  m_hash.insert(h, pos);
  append(item);
}
 int hashedIndexOf(const T& item) const {
   int h = qHash(item);
   return m_hash.value(h, -1);
 }
 // etc.
private:
  QHash<int, int> m_hash;
};

To copy to clipboard, switch view to plain text mode 

Note that this REQUIRES hashes to be unique. If you can't guarantee that, substitute the integer with the item "name" (QString). Alternatively make your class implicitly or better yet explicitly shared and have two separate structures with shallow copies of the items. With implicit sharing this gets tricky, explicit sharing is best. An alternative is to use pointers as JohannesMunk suggested.

[doberkofler]

Thank you for the reply! Using two lists and sharing the items seems to be a reasonable approach but I guess this would only be possible when using pointers (dynamically allovated items) to share them between two columns or is there also a way to share items in a collection with valkue semantics?

[wysota]

"Implicit" and "explicit" sharing are the magic words here.