Kailas - 1 year ago 61
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.

Thanks,
Kailas

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download