Kailas Kailas - 2 months ago 9
C++ Question

Efficient Search through list of Ranges

I have list of ranges { start, end }, and a value (point) , now I am looking for effective way to get last n th index from range in which given value is present.

For example:
List: [ { 0, 4 }, {5, 10 }, {11, 14 }, {15, 20} , {21, 25} ]
n : 2
value: 22

So here, 22 is in range {21, 25 } which is at index 4 ( 0 based ).
and since n is 2, function should return index of {11, 14 } because this is n th range from matching range.

Here, I can write binary function easily since I have sorted list of ranges. But I do not want to write while / for , I am looking for some C++ 11 / 14 algorithms / lambdas if available, which can solve this issue.

Can you please help?

Thanks,
Kailas

Answer

I like Jan's answer, but since the appropriate solution is notably different if your data is known to be sorted, here's an answer for the question as-asked:

#include <cstddef>
#include <utility>
#include <stdexcept>
#include <algorithm>
#include <iterator>

template<typename RngT, typename ValT, typename OffsetT>
std::size_t find_prev_interval(RngT const& rng, ValT const& value, OffsetT const offset) {
    using std::begin; using std::end;
    auto const first = begin(rng), last = end(rng);
    auto const it = std::lower_bound(
        first, last, value,
        [](auto const& ivl, auto const& v) { return ivl.second < v; }
    );

    // optional if value is *known* to be present
    if (it == last || value < it->first) {
        throw std::runtime_error("no matching interval");
    }

    auto const i = std::distance(first, it);
    return offset <= i
      ? i - offset
      : throw std::runtime_error("offset exceeds index of value");
}

As the implementation only needs forward-iterators, this will work for any standard library container or C-array; however for std::set<> or something like boost::containers::flat_set<>, you'll want to alter the logic to call rng.lower_bound() rather than std::lower_bound(). Also, replace exceptions with something like boost::optional if it is usual for offset to be too high to return a valid index.