How to find the nearest value in a QMap ?

QtVik

Hi,
I have a QMap which contains certain elements:

Ex:
qreal currentValue = 2.54325 ;
QMap<qreal, quint64> mapValues = getMapValue();

Now i want to check the closest to currentValue available in the mapValues.
How to check that ?

Thanks

sierdzio

Wow, a qreal works as key of a QMap? Don't you get comparison problems? I'd rather recommend swapping the args and using the quin64 as key, and qreal as value.

To find the closest value, you have to manually go through all elements and compare them. You can use the fact that QMap stores the values in an ascending order - so if you start from the beginning and find the closest value at some index, you can skip checking the remaining values.

Asperamanca

You should be able to get the next lower or equal item using std::lower_bound, then go to the following item and compare which one is closer to the desired value.

VRonin

mapValues.lowerBound(currentValue)-1

fearlazy

@QtVik said in How to find the nearest value in a QMap ?:

i want to check the closest to currentValue available in the mapValues.
How to check that ?

sort map's values!

JonB

@VRonin said in How to find the nearest value in a QMap ?:

mapValues.lowerBound(currentValue)-1

Purely OOI: someone has said QMap keys are stored sorted, so can we assume this method will take advantage of that and do a binary search? :)

kshegunov

@JonB said in How to find the nearest value in a QMap ?:

Purely OOI: someone has said QMap keys are stored sorted, so can we assume this method will take advantage of that and do a binary search? :)

Strictly speaking all searches for a key in the map are binary searches. The QMap is a ~~skip-list (similar to a linearized binary tree)~~ red-black tree so it has a logarithmic complexity for search and insert operations.

JonB

@kshegunov

so it has a logarithmic complexity for search and insert operations

Excellent! And where is that in the Qt docs? It has been commented elsewhere on the Interweb that Qt docs often do not say anything about search order complexity for many of its data structures, which is a shame.

sierdzio

Here is the comparison https://doc.qt.io/qt-5/containers.html

kshegunov

Yes, and a minor correction, it used to be skip-list in Qt4, now it's an ordinary red-black tree. I must get more coffee before I write ...

JonB

@sierdzio said in How to find the nearest value in a QMap ?:

Here is the comparison https://doc.qt.io/qt-5/containers.html

Ah ha, that is a useful link for all of us, thank you.

Mind you, in the case of QMap I don't see where you can access it by index number (only by key), so unless lowerBound() can do that privately I don't see where a binary search can be performed?

sierdzio

@JonB said in How to find the nearest value in a QMap ?:

@sierdzio said in How to find the nearest value in a QMap ?:
Mind you, in the case of QMap I don't see where you can access it by index number (only by key), so unless lowerBound() can do that privately I don't see where a binary search can be performed?

QMap<a,b> map;
const QList<a> keys = map.keys(); // This is sorted.

JonB

@sierdzio
Ah, so if you had to, you could binary search map.keys() (instead of the QMap itself) for a key, right?

kshegunov

You could, but why would you? The point is that you get an iterator to some position, which you can move back or forth. There's no sense in requiring indexing as well.

JonB

@kshegunov
We (I) are discussing the efficiency of lowerBound(), or whatever function one might write, being able to take advantage of the fact that QMap keys are stored sorted. If I have million sorted qreals as the map keys, and I want to find the nearest to a certain value as per OP's question, I'd like to search binarily, wouldn't I? Not sequentially by iterator. So I'll need to be able to specify an index number to access the map. Which is what @sierdzio showed me above with

const QList<a> keys = map.keys(); // This is sorted.

kshegunov

@JonB said in How to find the nearest value in a QMap ?:

@kshegunov
If I have million sorted qreals as the map keys,

If you have that you're inventing a square wheel. QMap isn't made for that stuff and is going to be outperformed by any contiguous-access container (vector).

and I want to find the nearest to a certain value as per OP's question, I'd like to search binarily, wouldn't I?

You already do with lowerBound. Binary trees have stable log key searching, which is why they're used so much for QMap and std::map and such.

Not sequentially by iterator.

The iterator is your pointer to the node when you traverse the tree. That's how the data's organized, you can't have random access on top of that, it's just not happening.

So I'll need to be able to specify an index number to access the map. Which is what @sierdzio showed me above with

Which traverses the whole tree (i.e. O(N) to get the keys) ... not very efficient.

QtVik

@VRonin :Thank you Ronin.