Kailas - 5 months ago 16

C++ Question

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.