Эффективное отображение диапазонов на группы значений

Question

Я пытаюсь определить подходящий способ сделать следующее.

Я хотел бы иметь диапазон -> установить поиск в пределах определенного диапазона (скажем, [0x0 - 0xffffffff]). Значения вставляются в диапазон в диапазонах (поэтому, если мы работаем с T = уникальными строками), я мог бы вставить ("beef3490", [0x1234, 0xFFFF]); и один идентификатор может иметь несколько вставок, которые могут или не могут перекрываться. Кроме того, могут быть вставлены другие значения, которые перекрываются, и где они перекрываются, в результате я должен получить набор уникальных строк. Наконец, значения также могут быть удалены из диапазонов (не обязательно совпадающих, но обычно содержащихся в их начальном диапазоне вставки).

Вот упрощенный пример использования:

insert("beef3490", [0x1234, 0xFFFF])
insert("beef3490", [0x11111, 0x22222])
insert("flam1456", [0x8000, 0xA0000])
remove("beef3490", [0x21000, 0x22000])
lookup(0x0) -> set<>
lookup(0x2000) -> set<beef3490>
lookup(0x9456) -> set<beef3490, flam1456>
lookup(0x21212) -> set<flam1456>
lookup(0x99789) -> set<flam1456>

Это приводит к ряду вопросов для меня:

1. Есть ли обобщенное название для такого рода проблем или проблемы подобного типа, из которой я мог бы понять?

2. Что является идеальной реализацией с учетом следующих ограничений:

   • Быстрое / очень быстрое время поиска
   • Использование памяти не увеличивается (т. Е. Следующие операции имеют одинаковую площадь)
   • • Вставить [10,20], Вставить [20,30], Удалить [14,24]
   • • Вставка [10,15], Вставка [25,30]
   • Как и в прошлом, структура данных должна иметь стабильность в долго работающей системе
   • Время вставки / удаления не совсем ужасно (хотя они не должны быть такими же быстрыми, как поиск)

3. Учитывая идеальную реализацию, есть ли у вас совет для использования его в C++

Спасибо за все ответы и помощь.

Answer 1

Есть ли обобщенное название для такого рода проблем или проблемы подобного типа, из которой я мог бы понять?

Эта проблема является проблемой дерева интервалов или дерева сегментов. В частности, древовидная структура / структура данных должна выполнять агрегирование операций перекрытия. Это означает, что когда в структуру вставляются два пересекающихся диапазона, значение поиска для точки в обоих диапазонах эквивалентно val(диапазон A) + val(диапазон B). Операция "+" может быть добавлением, если значения являются целыми числами, или в случае множеств это будет операция объединения.

Что такое идеальная реализация с учетом ограничений

Самобалансирующееся дерево двоичного поиска (например, красно-черное дерево или дерево козла отпущения), созданное для оптимизации поиска на основе диапазонов. Операции вставки дополнительно пересекают диапазоны по мере необходимости для получения правильных возвращаемых значений. Способы разделения диапазонов варьируются в зависимости от ваших требований, но обычно это либо "объединение", которое отбрасывает информацию об исходных диапазонах, но имеет меньшую занимаемую площадь, либо "разделение", из которого все еще можно вывести исходные диапазоны.

Учитывая идеальную реализацию, есть ли у вас совет для использования его в C++

Смотрите boost:: icl. (Увеличить интервальную библиотеку контейнеров)