qwertyu uytrewq qwertyu uytrewq - 3 months ago 11
C++ Question

map range of float values to single value in c++

I have array of key-frames that looks as

sruct key-frame
{ float time;
matrix4x4 transformMatrix;}


array is sorted according to time value. Also I have

float value;


I access this array millions of times. Array itself remains unchanged. My goal is to find index of first keyframe that has
time
bigger then
value
. Can this be done in constant time? Does c++ has something that maps not overlaping ranges of values to particular value?

Answer

The std::upper_bound function will do exactly this in O(log n) time for collections that support random access iterators (yours most surely does.) You'll need to tell it how to compare the structs, which you can do with a lambda function like so:

auto keyframe_iterator = 
    std::upper_bound(keyframes.begin(), keyframes.end(), value, 
    [](const keyframe& a, const keyframe& b) { a.time < b.time; });`
Comments