.Интервальная контейнерная библиотека (ICL)предоставляет<intervals>и два вида интервальных контейнеров:<interval_sets>и<interval_maps>.

Two Aspects

<Interval_sets>и<interval_maps>выделяют два различных аспекта в их интерфейсах: (1) Функциональность набора или карты, которая является болееабстрактным аспектом. И (2) функциональность контейнера интервалов, который является более конкретным иаспект реализации. На практике оба аспекта полезны и поэтому поддерживаются.

Первый аспект, который будет называтьсяфундаментальнымаспектом, является более важным. Это означает, что мы можем использовать<interval_set>или<interval_map>как набор или картуэлементов. Он выполняет те же функции.

interval_set<int> mySet;
mySet.insert(42);
bool has_answer = contains(mySet, 42);

Второй аспект, который будет называться, позволяет использовать тот факт, что элементы<interval_sets>сгруппированы винтервалов, которые мы можем повторять.

// Switch on my favorite telecasts using an interval_set
interval<seconds>::type news(make_seconds("20:00:00"), make_seconds("20:15:00"));
interval<seconds>::type talk_show(make_seconds("22:45:30"), make_seconds("23:30:50"));
interval_set<seconds> myTvProgram;
myTvProgram.add(news).add(talk_show);
// Iterating over elements (seconds) would be silly ...
for(interval_set<seconds>::iterator telecast = myTvProgram.begin();
    telecast != myTvProgram.end(); ++telecast)
    //...so this iterates over intervals
   TV.switch_on(*telecast);

Работа с<interval_sets>и<interval_maps>может быть полезной всякий раз, когда элементы множества появляются в смежных кусках:<intervals>. Это, очевидно, имеет место во многих проблемных областях, особенно в областях, которые имеют дело с вычислениями, связанными с датой и временем.

Addabitlity and Subtractability

В отличие от<std::sets>и<maps>,<interval_sets>и<interval_maps>реализуют понятия<Addable>и<Subtractable>. Так<interval_sets>определяют<operator+=>, который естественным образом реализуется какзаданное соединениеи<operator-=>, который, следовательно, реализуется какзаданное различие. ВИкл<interval_maps>также можно добавлять и вычитать. Очень плодотворной оказалась концепция распространения сложения или вычитания до<interval_map's>ассоциированных значений в тех случаях, когда вставка интервальной пары значений в<interval_map>приводила к столкновению вставленной интервальной пары значений с интервальными парами значений, которые уже находятся в<interval_map>. Эта операция распространения называетсяагрегат на перекрытие.

Aggregate on Overlap

Это первый мотивирующий пример очень маленькой партии, демонстрирующейагрегат на перекрытиипринцип<interval_maps>:

В качестве примера Мария вступает в партию первой. Она присутствует во время временного интервала<[20:00,22:00)>. Гарри приходит позже. Он находится в пределах<[21:00,23:00)>.

typedef std::set<string> guests;
interval_map<time, guests> party;
party += make_pair(interval<time>::right_open(time("20:00"), time("22:00")), guests("Mary"));
party += make_pair(interval<time>::right_open(time("21:00"), time("23:00")), guests("Harry"));
// party now contains
[20:00, 21:00)->{"Mary"}
[21:00, 22:00)->{"Harry","Mary"} //guest sets aggregated on overlap
[22:00, 23:00)->{"Harry"}

При перекрытии интерваловсоответствующие наборы именнакоплены.точки перекрытия. Накопление содержимого при перекрытии интервалов осуществляется через<operator+=>, который должен быть реализован для соответствующих значений<interval_map>. В примере соответствующие значения<guest sets>.<guest set>,<operator+=>,<operator+=>, [скрыто], [скрыто].

Как видно из примера,<interval_map>имеет какдекомпозиционное поведение(по временному измерению), так инакопительное поведение(по связанным значениям).

Добавляемость и агрегат на перекрытии являются полезными функциями<interval_maps>, реализованными с помощью функций<add>и<operator+=>. Но вы также можете использовать их страдиционнойсемантикой вставки, которая ведет себя как<std::map::insert>обобщенная для интервальной вставки.

В дополнение к интервальным контейнерам мы можем работать с контейнерами элементов, которыеповеденчески равныинтервальным контейнерам: В основном они имеют одинаковую функциональность.<std::set>STL представляет собой такую эквивалентную реализацию множества. Из-за возможностей агрегации интервальных карт icl<std::map>принципиально не полностью эквивалентен<interval_map>. Поэтому в icl есть дополнительный шаблон класса<icl::map>для карт элементов.

Следующие таблицы дают обзор основных шаблонов классов, предоставляемыхicl.

Когда мы добавляем интервалы или пары значений интервала в интервальные контейнеры, интервалы могут быть добавлены различными способами: Интервалы могут быть объединены, разделены или разделены. Различные интервалы сочетания стилей показаны на примере в таблицах ниже.

{[1    3)        }
+     [2    4)
+               [45)
={[1              5)}

  {[1      3)}         }
+       [2      4)
+                 [4 5)
= {[1           4)[4 5)}

  {[1      3)          }
+       [2      4)
+                 [4 5)
= {[1 2)[2 3)[3 4)[4 5)}

  {[1      3)->1          }
+       [2      4)->1
+                 [4 5)->1
= {[1 2)[2 3)[3      5)   }
  | ->1  ->2     ->1      |

  {[1      3)->1          }
+       [2      4)->1
+                 [4 5)->1
= {[1 2)[2 3)[3 4)[4 5)   }
  | ->1  ->2  ->1  ->1    |