Посоветуйте структуру данных
От: SergASh  
Дата: 01.01.17 19:41
Оценка:
Привет всем.

Нужна структура данных, работающая как словарь, только чтобы ключ был не одиночным значением, а диапазоном.
Основная операция будет поиск всех вхождений, ключи которых пересекаются с заданным диапазоном.

Например, словарь такой:
[ 5, 15] -> Царь
[35, 50] -> Медведь
[25, 40] -> Чурка

Подаем на вход [10, 30], получаем
[ 5, 15] -> Царь
[25, 40] -> Чурка

Производительность критична, хотелось бы чтоб она была сопоставима с таковой у SCG.Dictionary, то есть
почти всегда константа для поиска одиночного вхождения.

Идеальным был бы вариант, при котором метод поиска возвращал бы итератор, а не копировал результат в промежуточный контейнер.

В общем, хочу что-то схожее с тем, как устроен индекс в рсубд.
Может есть что-то готовое?
Отредактировано 02.01.2017 20:12 AndrewVK . Предыдущая версия .
структура данных диапазоны
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.