How to find the nearest value in a QMap ?

[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.