Привет всем.
Нужна структура данных, работающая как словарь, только чтобы ключ был не одиночным значением, а диапазоном.
Основная операция будет поиск всех вхождений, ключи которых пересекаются с заданным диапазоном.
Например, словарь такой:
[ 5, 15] -> Царь
[35, 50] -> Медведь
[25, 40] -> Чурка
Подаем на вход
[10, 30], получаем
[ 5, 15] -> Царь
[25, 40] -> Чурка
Производительность критична, хотелось бы чтоб она была сопоставима с таковой у SCG.Dictionary, то есть
почти всегда константа для поиска одиночного вхождения.
Идеальным был бы вариант, при котором метод поиска возвращал бы итератор, а не копировал результат в промежуточный контейнер.
В общем, хочу что-то схожее с тем, как устроен индекс в рсубд.
Может есть что-то готовое?