How to find the nearest value in a QMap ?

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

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.

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.

mapValues.lowerBound(currentValue)1

@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!

@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? :)

@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
skiplist (similar to a linearized binary tree)redblack tree so it has a logarithmic complexity for search and insert operations.

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.

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

Yes, and a minor correction, it used to be skiplist in Qt4, now it's an ordinary redblack tree. I must get more coffee before I write ...

@sierdzio said in How to find the nearest value in a QMap ?:
Here is the comparison https://doc.qt.io/qt5/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 unlesslowerBound()
can do that privately I don't see where a binary search can be performed?

@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 ofQMap
I don't see where you can access it by index number (only by key), so unlesslowerBound()
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.

@sierdzio
Ah, so if you had to, you could binary searchmap.keys()
(instead of theQMap
itself) for a key, right?

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.

@kshegunov
We (I) are discussing the efficiency oflowerBound()
, or whatever function one might write, being able to take advantage of the fact thatQMap
keys are stored sorted. If I have million sortedqreal
s 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 withconst QList<a> keys = map.keys(); // This is sorted.

@JonB said in How to find the nearest value in a QMap ?:
@kshegunov
If I have million sortedqreal
s 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 contiguousaccess 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 forQMap
andstd::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.

@VRonin :Thank you Ronin.