|
|
|
IntersectionBoost , Chapter 1. Boost.Icl , Function Reference
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Пересечение |
интервал |
интервал |
интервал |
элемент |
элемент |
|---|---|---|---|---|---|
| |||||
| |||||
| |||||
|
Функции и операторы, связанные спересечениемнаобъектах icl, приведены в таблице выше.
|
Описание пересечения | |
|---|---|
| Пересечение на наборах реализуетустановленное пересечение |
| Пересечение на Картах реализует функциюПересечение карты, аналогичнуюустановленному пересечению. Если на пересечении пара значений элемента Если кодомен_тип не имеет операции пересечения, связанные значения объединяются с помощью сложения. Для парциальных типов карт это приводит к добавлению на пересечении доменов пересекающихся наборов. Для полных карт пересечение и сложение в данном случае идентичны. См. такжепересечение на Картах чисел. Карту можно пересекать с ключевыми типами: элементом (интервал для интервала_карт) и набором. Это приводит к выбору подкарты и может быть определено как обобщенная функция отбора на Картах . |
Перегруженная функция
void add_intersection(T&
result,
const T& y, const P& x)
позволяет накопить пересечениеуихв первом аргументерезультата.Результатможет уже содержать данные. В этом случае пересечениеуихявляетсядобавленнымсодержаниемрезультатом.
T s1 = f, s2 = f, y = g; P x = h; // The effect of add_intersection(s1, y, x); // add_intersection s2 += (y & x); // and & followed by += assert(s1==s2); // is identical
Это может быть удобно, если пересечение используется как обобщенная функция выбора. Используя типы элементов или сегментов дляP, мы можем выбрать небольшие части контейнерауи накопить их всекции.
Допустимые комбинации типов для функцииvoidadd_intersection[T&,constT&,constP&]можно суммировать в таблицеперегрузкиниже. По сравнению с другими таблицами перегрузки места расположения аргументов функций различны: Заголовки строк обозначают типT*этогообъекта. Заголовки колонок обозначают типPаргумента второй функции. Ячейки таблицы содержат аргументыTпересеченийрезультата, который является первым аргументом функций.
/* overload table for */ T\P| e i b p void T::add_intersection(T& result, const P&)const ---+-------- s | s m | m m S | S S M | M M M M
Следующая таблица содержит характеристики сложности для функцииadd_intersection.
Table 1.34. Time Complexity for function add_intersection on icl containers
|
|
Тип домена |
интервал |
домен |
Интервал |
|---|---|---|---|---|
O(log n) | ||||
O(log n) | O(log n) | |||
O(log n) | O(n) | |||
O(log n) | O(n) | O(n) | O(n) |
В приведенных ниже таблицах перегрузки приведены допустимые комбинации типов для оператора пересечения&=. Что касается моделей перегрузкивычитанияпересечений, то они возможны в пределах наборов и карт, но также и для карт в сочетании сключевыми объектами, которые являютсяключевыми элементами, интерваламии. Набор ключей.
// overload tables for element containers: interval containers: T& operator &= (T&, const P&) &= | e b s m &= | e i b p S M ---+-------- ---+------------ s | s s S | S S S m | m m m m M | M M M M M M
В то время как пересечение на картах можно рассматривать какобобщение множества пересечений. Комбинация на Картах и Наборах может быть интерпретирована какобобщенная функция выбора, поскольку она позволяет выбирать части карт, используяключилиобъекты выбора. Итак, у нас естьобобщенное пересечениедля этих перегрузок,
/* (Generalized) intersection */ &= | e b s m &= | e i b p S M ---+-------- ---+------------ s | s s S | S S S m | m m M | M M M
иaвыбор ключевых объектовздесь:
/* Selection by key objects */ &= | e b s m &= | e i b p S M ---+-------- ---+------------ s | s s S | S S S m | m m M | M M M
Различия по различным функциям оператора&=находятся в строке карты таблиц. Обе функции сводятся вместе для наборов в функции, установленного пересечения.
Характеристики сложности операций на месте пересечения приведены в следующих таблицах, где
n = iterative_size(y); m = iterative_size(x); //if P is a container type
Table 1.36. Time Complexity for inplace intersection on interval containers
|
|
Тип домена |
интервал |
домен |
Интервал |
интервал |
интервал |
|---|---|---|---|---|---|---|
интервал_множества | O(log n) | O(n) | O(m log(n+m)) | |||
интервал_карты | O(log n) | O(n) | O(log n) | O(n) | O(m log(n+m)) | O(m log(n+m)) |
Дляicl'sдоступны следующие перегрузки:
// overload tables for element containers: interval containers: T operator & (T, const P&) & | e b s m & | e i b p S1 S2 S3 M1 M3 T operator & (const P&, T) ---+-------- ---+--------------------------- e | s m e | S1 S2 S3 M1 M3 b | m i | i S1 S2 S3 M1 M3 s | s s m b | M1 M3 m | m m m m p | M1 M3 S1 | S1 S1 S1 S2 S3 M1 M3 S2 | S2 S2 S2 S2 S3 M1 M3 S3 | S3 S3 S3 S3 S3 M1 M3 M1 | M1 M1 M1 M1 M1 M1 M1 M1 M3 M3 | M3 M3 M3 M3 M3 M3 M3 M3 M3
Для устранения неясностей между интервальными контейнерами в качестве результирующего типа выбираютболее тонкийконтейнерный тип.
Опять же, мы можем разделить таблицы перегрузки оператора&в части, описывающей.*обобщенное пересечениена интервальных контейнерах и вторая часть, определяющая*отбор по ключевому объектуфункциональность.
/* (Generalized) intersection */ & | e b s m & | e i b p S1 S2 S3 M1 M3 ---+-------- ---+--------------------------- e | s e | S1 S2 S3 b | m i | i S1 S2 S3 s | s s b | M1 M3 m | m m p | M1 M3 S1 | S1 S1 S1 S2 S3 S2 | S2 S2 S2 S2 S3 S3 | S3 S3 S3 S3 S3 M1 | M1 M1 M1 M3 M3 | M3 M3 M3 M3
/* Selection by key objects */ & | e b s m & | e i b p S1 S2 S3 M1 M3 ---+-------- ---+--------------------------- e | s m e | S1 S2 S3 M1 M3 b | i | i S1 S2 S3 M1 M3 s | s s m b | m | m m p | S1 | S1 S1 S1 S2 S3 M1 M3 S2 | S2 S2 S2 S2 S3 M1 M3 S3 | S3 S3 S3 S3 S3 M1 M3 M1 | M1 M1 M1 M1 M1 M3 | M3 M3 M3 M3 M3
|
экзаменатор |
десктрипция |
|---|---|
| Испытания, если |
|
Tests, if |
|
|
bool intersects(const T&, const P&) T\P| e b s m T\P| e i b p S M bool disjoint(const T&, const P&) ---+-------- ---+------------ s | 1 1 S | 1 1 1 m | 1 1 1 1 M | 1 1 1 1 1 1
See also . . .
Back to section . . .
Статья Intersection раздела Chapter 1. Boost.Icl Function Reference может быть полезна для разработчиков на c++ и boost.
:: Главная :: Function Reference ::
реклама |
