How to find the nearest value in a QMap ?
-
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 said in How to find the nearest value in a QMap ?:
mapValues.lowerBound(currentValue)-1Purely OOI: someone has said
QMapkeys 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
skip-list (similar to a linearized binary tree)red-black tree so it has a logarithmic complexity for search and insert operations.Read and abide by the Qt Code of Conduct
-
@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.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/qt-5/containers.html
-
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.
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 ...
-
Here is the comparison https://doc.qt.io/qt-5/containers.html
@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
QMapI 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? -
@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
QMapI 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 ofQMapI 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.(Z(:^
-
@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 ofQMapI 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 theQMapitself) 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.
Read and abide by the Qt Code of Conduct
-
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 thatQMapkeys are stored sorted. If I have million sortedqreals 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. -
@kshegunov
We (I) are discussing the efficiency oflowerBound(), or whatever function one might write, being able to take advantage of the fact thatQMapkeys are stored sorted. If I have million sortedqreals 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 sortedqreals as the map keys,If you have that you're inventing a square wheel.
QMapisn'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 forQMapandstd::mapand 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.
