Addition . Boost , Chapter 1. Boost.Icl , Function Reference

Добавление		интервал Карты	элемент Наборы	элемент Карты
<`T& T::add(constP&)`>	e i	b p		b
`T& add(T&, const P&)`	e i	b p	e	b
`J T::add(J pos, const P&)`	i	p		b
`J add(T&, J pos, const P&)`	i	p	e	b
`T& operator +=(T&, const P&)`	e i S	b p	e s	b m
`T operator + (T, const P&)`	e i S	b p	e s	b m
<`T& operator\|=( T&, constP&)`>	e i S	b p	e s	b m
<`Toperator \|(T, constP&)`> <`T operator\| (const P&, T)`>	e i S	b p	e s	b m

Функции и операторы, реализующиеДобавлениенаобъектах icl, приведены в таблице выше.<operator|=>и<operator|>являются поведенческими идентичными<operator +=>и<operator +>. Это избыточность, которая была введена намеренно, потому чтоустановленный союзсемантика часто присоединяется<operators |=>и<|>.

Описание дополнения

<Sets>

Добавление к наборам реализуетсет-союз

<Maps>

Добавление на Картах реализует функциюобъединения карт, аналогичнуюустановленного союза. Если при вставке пары значений элемента<(k,v)>ключ<k>уже находится на карте, функция сложения распространяется на связанное значение. Эта функциональность была введена какагрегат при столкновениидля карт элементов иагрегат при перекрытиидля интервальных карт.

Узнайте больше овозможности добавления карти связанных с нимисемантических вопросахпосле ссылок.

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

Для<Sets>добавлениеивведениереализованы одинаково. Функции<add>и<insert>распадаются на одну и ту же функцию. Для<Maps>добавленияивставкиработают по-разному. Функция<add>выполняет агрегации на столкновении или перекрытии, в то время как функция<insert>вставляет только значения, которые еще не имеют ключевых значений.

Functions

Допустимые комбинации типов для функции члена<T&T::add(constP&)>можно резюмировать в таблицеперегрузкиниже:

// overload table for    T\P| e i b p  
T& T::add(const P&)      ---+--------
T& add(T&, const P&)      s | s
                          m |     m
                          S | S S
                          M |     M M

Следующая таблица содержит характеристики сложности для<add>.

Table 1.21. Time Complexity for member function add on icl containers

<`T& T::add(constP&)`> <`T&add(T&,const P&)`>	Тип домена	Тип интервала	домен отображение тип	Интервал отображение тип
<`std::set`>	O(log n)
<`icl::map`>			O(log n)
`interval_set` `separate_interval_set`	O(log n)	амортизирован O(log n)
<`split_interval_set`>	O(log n)	O(n)
<`interval_map`> <`split_interval_map`>			O(log n)	O(n)

Hinted addition

Функция<JT::add(Jprior,constP&addend)>допускает добавление впостоянного времени, если<addend>можно вставить сразу после итератора<prior>без столкновения. Если это невозможно, характеристики сложности указаны для неподсказанного дополнения выше. Намеченное дополнение доступно для этих комбинаций типов:

// overload table for addition with hint        T\P| e i b p   
J T::add(J prior, const P&)                     ---+--------
J add(T&, J prior, const P&)                     s | s
                                                 m |     m
                                                 S |   S
                                                 M |       M

Inplace operators

Возможные перегрузки места<T&operator +=(T&,constP&)>приведены в двух таблицах, которые показывают допустимые комбинации типов. Рядовые типы показывают инстанциации типа аргумента<T>. Типы колонок показывают инстанциации типа аргумента<P>. Если возможна комбинация типов аргументов, соответствующая ячейка таблицы содержит тип результата операции.Заполнители ] будут использоваться для Первая таблица показывает перегрузки<+=>для.контейнеры элементов, вторая таблица относится кинтервальные контейнеры.

// 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

Для определения допустимых перегрузок мы отделяемконтейнеры элементовотинтервальных контейнеров. Внутри каждой группы поддерживаются все комбинации типов для операции, которые соответствуют конструкцииiclи наборам законов, которые устанавливают семантикуicl.

Также могут быть определены перегрузки междуконтейнерами элементовиконтейнерами интервалов. Но это не было сделано по прагматическим причинам: Каждая дополнительная комбинация типов для операции увеличивает пространство возможных перегрузок. Это делает разрешение перегрузки компиляторами более сложным, подверженным ошибкам и замедляет скорость компиляции. Сообщения об ошибках при неразрешимых или неоднозначных перегрузках трудно читать и понимать. Поэтому перегрузка пространства имен глобальными функциями вiclограничена разумным полем комбинаций, которые описаны здесь.

Complexity

Для различных комбинаций типов аргументов<T>и<P>выбраны различные реализации<operator+=>. Эти реализации показывают различные характеристики сложности. Если<T>представляет собой тип контейнера, комбинация элементов доменаeили пар значений элементаb) является более быстрой, чем комбинация интерваловiили пар значений интервалаp, которая, в свою очередь, быстрее, чем комбинация элементов или контейнеров интервала. Следующая таблица показываетвременные сложностисложения дляicl'sКонтейнеры.

Размеры<n>и<m>в утверждениях сложности — это размеры объектов<Ty>и<Px>:

n = iterative_size(y);
m = iterative_size(x); //if P is a container type

Обратите внимание, что для контейнера с интервалом количество элементов<T::size>отличается от количества интервалов, которые вы можете повторять. Поэтому используется функция<T::iterative_size()>, которая обеспечивает желаемый вид размера.

Table 1.22. Time Complexity for inplace Addition on element containers

<`T& operator+= (T&y,const P& x)`>	Тип домена	домен отображение тип	__ch_icl_sets	_ch_icl_maps__
`std::set`	O(log n)		O(m)
`icl::map`		O(log n)		O(m)

Характеристики сложности по времени несложения для интервальных контейнеров приведены в этой таблице.

Table 1.23. Time Complexity for inplace Addition on interval containers

<`T& operator+= (T&y,const P& x)`>		Тип домена	Тип интервала	домен отображение тип	Интервал отображение тип	Интервал устанавливает	интервал Карты
интервал_множества	`interval_set` `separate_interval_set`	O(log n)	amortized O(log n)			O(m log(n+m))
	<`split_interval_set`>	O(log n)	O(n)			O(m log(n+m))
interval_maps				O(log n)	O(n)		O(m log(n+m))

Так как реализация элементов и интервальных контейнеров основана насвязи красно-черного дерева, реализацияstd:: Контейнеры имеют логарифмическую сложность для добавления элементов. Добавление интервалов или пар значений интервала амортизируется логарифмическим для<interval_sets>и<separate_interval_sets>и линейным для<split_interval_sets>и<interval_maps>. Добавление является линейным для контейнеров элементов и линейным для интервальных контейнеров.

Infix operators

Допустимые комбинации типов для исправления<operator +>определяются таблицами перегрузок ниже.

// 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              e  |             S1 S2 S3
                                b  |       m            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

See also . . .

Subtraction
<>Insertion

Вернуться в раздел...


Интерфей

Статья Addition раздела Chapter 1. Boost.Icl Function Reference может быть полезна для разработчиков на c++ и boost.

Addition

Boost , Chapter 1. Boost.Icl , Function Reference

Boost C++ Libraries