I have a large amount of double <vectors> each of them containing up to several 100s of values. Just for your information the values belong to a time series, the values are just measured time distances in seconds.
Now I am looking for a performant way to find gaps within a vector. For each value in the vector there should be a tolerance +/- 10% add to the value itself. After streching my values this way I want to determine areas which are not covered by this strechings.
e.g. for the vector containing the values
2.0 2.1 2.13 2.2 3.5 3.6 3.9 6.4 7.0
the function should output the unoccupied areas 2.42-3.15 and 4.29-5.76.
Is there a library function I could use for an efficient calculation of theses gaps?
So, in essence you would look at each pair of consecutive elements (A and B), and if their difference is large (A*1.1 < B), then store a pair of values (A*1.1, B*0.9).
You could do the iteration with std::transform, but I don't know whether that is more efficient than explicit loop.
"Measured series" could mean that that data is not "sorted" and cannot be reordered (i.e. sorted). Even then it is O(N), but obviously with a larger constant.