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

Containedness

	интервалы		интервал Карты		элемент Карты
`bool T::empty()const`		1	1	1	1
`bool is_empty(const T&)`	1	1	1	1	1
`bool contains(const T&, const P&)` `bool within(const P&, const T&)`	e i	e i S	e i S b p M	e s	b m

Эта группа функций относится ксодержитЭдность, которая должна быть фундаментальной дляers. Функция<contains>перегружена. Он охватывает различные виды содержательности: содержащиеся элементы, сегменты и подконтейнеры.

	О (...)	Описание
`bool T::empty()const` `bool is_empty(const T&)`	O(1)	Returns `true`, if the container is empty, `false` otherwise.
`bool contains(const T&, const P&)` `bool within(const P&, const T&)`	see below	Returns `true`, if `super` container contains object `sub`.
	where	n`= iterative_size(sub)`
		m`= iterative_size(super)`

// overload tables for 
bool contains(const T& super, const P& sub)
bool   within(const P& sub, const T& super)
element containers:   interval containers:
T\P| e b s m          T\P| e i b p S M
--------+---          --------+-------
 s | 1   1             S | 1 1     1
 m | 1 1 1 1           M | 1 1 1 1 1 1

При этом они различны<boolcontains(constT&super,constP&sup)>. Мы можем сгруппировать их в часть (1), которая проверяет, содержится ли элемент, сегмент или контейнертого же типав элементе или интервальном контейнере.

// (1) containedness of elements, segments or containers of same kind
T\P| e b s m          T\P| e i b p S M
---+--------          ---+------------
 s | 1   1             S | 1 1     1
 m |   1   1           M |     1 1   1

и другую часть (2), которая проверяет содержаниеключевых объектов, которые могут бытьэлементыинтервалыилинаборы.

// (2) containedness of key objects.
T\P| e b s m          T\P| e i b p S M
---+--------          ---+------------
 s | 1   1             S | 1 1     1
 m | 1   1             M | 1 1     1

(m::set_type) может быть ключевой объект. .

Для типа интервальной картыM, ключевым элементомM<::domain_type>, интерваломM<::interval_type>, а такжеинтервалом, установленным, могут бытьключевые объекты.

Характеристики сложности для функции<boolcontains(constT&super,constP&sub)const>приведены в следующих таблицах, где

n = iterative_size(super);
m = iterative_size(sub); //if P is a container type

Table 1.19. Time Complexity for function contains on element containers

	Тип домена	Картирование Тип	std::set	icl::map
`std::set`	O(log n)		O(m log n)
`icl::map`	O(log n)	O(log n)	O(m log n)	O(m log n)

Table 1.20. Time Complexity for functions contains and within on interval containers

		Тип домена	Тип интервала	Картирование Тип	Интервал отображение тип		интервал Карты
	`interval_set`	O(log n)	O(log n)			O(m log n)
	`separate_interval_set` `split_interval_set`	O(log n)	O(n)			O(m log n)
interval_maps	`interval_map`	O(log n)	O(log n)	O(log n)	O(log n)	O(m log n)	O(m log n)
	`split_interval_map`	O(log n)	O(n)	O(log n)	O(n)	O(m log n)	O(m log n)

Все перегрузки герметичности контейнеров в контейнерах

bool contains(const T& super, const P& sub)
bool   within(const P& sub, const T& super)

время:O(m log n). Если оба контейнера имеют одинаковые итеративные размеры, так чтом = nу нас самый худший случайO (n log n). Существует альтернативная реализация, которая имеетлинейнуюсложностьO(n+m). Выбрана логлайновая реализация, потому что она может быть быстрее, если аргумент контейнера мал. В этом случае логарифмическая реализация приближается к логарифмическому поведению, тогда как линейная реализация остается линейной.

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

<>Function Synopsis
Interface

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

Containedness

Boost , Chapter 1. Boost.Icl , Function Reference

Boost C++ Libraries

Containedness