Find first entry with key greater than given value in QMap

[kitfox]

I've created a QMap<int, MyDataType> myIndex; that is using the key as an index in a sparse array. I would like the user to be able to quickly look up the 'closest' value to a given index, even if that index is not in the map. That is, for any index I'm asked to look up, I'd like to find both the closest index that is less than or equal to it and the index that is greater than or equal to it. Is there a way to do this that is faster then just linearly scanning through all the keys?

[JonB]

@kitfox
I do not believe there is any fast method for this from a QMap.

[KroMignon]

@kitfox QMap keys are ascending ordered (cf. https://doc.qt.io/qt-5/qmap.html#details), so if you iter though map with QMapInterator with toBack() you can start for highest key value and then go to lowest with previous()

[kshegunov]

You'd be probably better off using an ordered array instead. Most of the time the tree rotations of QMap aren't worth it. Consider the following:

struct SparseArrayEntry
{
    int index;
    MyDataType data;
};
QVector<SparseArrayEntry> myIndex;

Sort with a custom comparator before searching and use a binary search for log(N) complexity (the same complexity as with QMap).