[SOLVED] QMap keys() collection - accessing an item by position
-
I have a QMap for data that grows - a logging type of scenario.
For some specific cases, I need to get the key for a certain position (i.e. the 142nd key).
I tried these options:
@int keyFromPos = map.keys().at(pos);@
@
QMap<int, int>::const_iterator it = map.constBegin(); // int,int for simplicity
it += pos;
int keyFromPos = it.key();
@Both ways take longer and longer as the map grows larger. Is there an efficient way to access the key for a specific position?
-
With a map I don't think so. It's a structure optimized for fast value lookup not key traversal. If you don't mind the duplication maybe you could store keys separately in a (sorted) vector? There's no better performance than constant time.
-
Hi,
"This":http://qt-project.org/doc/qt-5/containers.html#algorithmic-complexity might be useful
-
Thanks Chris, SGaist.
But for option 1, when I access QMap::keys() - I'm no longer using QMap for key traversal - no? I'm looking at a QList<int> where the complexity should be constant time - same time regardless of size.
This made me suspect that the issue is not with the access to the key at position but rather the generation of the QList<> instance when I call QMap::keys().
So I checked and indeed, just calling QMap::keys() takes more and more time as the map grows.
I'll consider having my own sorted keys collection on the side for the fastest access.
-
Yes, your conclusion is right. keys() does not just return a pre-existing list from the insides of a map. It actually constructs that list in that moment, and constructing that list is not constant time. A map is a (whatever kind) tree structure and to build the list of keys you need to go through each and every node of that tree (following pointers) and copy it out to the list. As I said map is not well suited for this type of operation. While lookup is O(log n) building the list is at least O(n), and it's a quite big O in that case (memory copy one by one and pointer traversal).
-
Thanks for your comment. The results I have for iterating (operation+=) the iterator are acceptable for now.
