Collection

Boost , ,

Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. — Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

Collection

Description

Коллекция — это концепция, аналогичная концепции STLКонтейнер. Коллекция предоставляет итераторы для доступа к ряду элементов и предоставляет информацию о количестве элементов в коллекции. Однако у коллекции меньше требований, чем у контейнера. Мотивация концепции «Коллекция» заключается в том, что существует множество полезных типов контейнеров, которые не соответствуют полным требованиям контейнера, и множество алгоритмов, которые могут быть написаны с помощью этого сокращенного набора требований. Резюмируя сокращение потребностей:

Не требуется «владеть» его элементами: срок службы элемента в Коллекции не должен соответствовать сроку службы объекта Коллекции, хотя срок службы элемента должен охватывать срок службы объекта Коллекции.
Семантика копирования объекта Коллекции не определена (это может быть глубокая или неглубокая копия или даже не поддерживать копирование).
Связанный тип ссылки на Сборник не обязательно должен быть реальным С++.

Because of the reduced requirements, some care must be taken when writing code that is meant to be generic for all Collection types. In particular, a Collection object should be passed by-reference since assumptions can not be made about the behaviour of the copy constructor.

Associated types

Value type	`X::value_type`	The type of the object stored in a Collection. If the Collection is mutable then the value type must be Assignable. Otherwise the value type must be CopyConstructible.
Iterator type	`X::iterator`	The type of iterator used to iterate through a Collection's elements. The iterator's value type is expected to be the Collection's value type. A conversion from the iterator type to the const iterator type must exist. The iterator type must be an InputIterator.
Const iterator type	`X::const_iterator`	A type of iterator that may be used to examine, but not to modify, a Collection's elements.
Reference type	`X::reference`	A type that behaves like a reference to the Collection's value type. [1]
Const reference type	`X::const_reference`	A type that behaves like a const reference to the Collection's value type.
Pointer type	`X::pointer`	A type that behaves as a pointer to the Collection's value type.
Distance type	`X::difference_type`	A signed integral type used to represent the distance between two of the Collection's iterators. This type must be the same as the iterator's distance type.
Size type	`X::size_type`	An unsigned integral type that can represent any nonnegative value of the Collection's distance type.

Notation

`X`	A type that is a model of Collection.
`a`, `b`	Object of type `X`.
`T`	The value type of `X`.

Valid expressions

Следующие выражения должны быть действительными.

Name	Expression	Return type
Beginning of range	`a.begin()`	`iterator` if `a` is mutable, `const_iterator` otherwise
End of range	`a.end()`	`iterator` if `a` is mutable, `const_iterator` otherwise
Size	`a.size()`	`size_type`
Empty Collection	`a.empty()`	Convertible to `bool`
Swap	`a.swap(b)`	`void`

Expression semantics

Name	Expression	Semantics	Postcondition
Beginning of range	`a.begin()`	Returns an iterator pointing to the first element in the Collection.	`a.begin()` is either dereferenceable or past-the-end. It is past-the-end if and only if `a.size() == 0`.
End of range	`a.end()`	Returns an iterator pointing one past the last element in the Collection.	`a.end()` is past-the-end.
Size	`a.size()`	Returns the size of the Collection, that is, its number of elements.	`a.size() >= 0`
Empty Collection	`a.empty()`	Equivalent to `a.size() == 0`. (But possibly faster.)
Swap	`a.swap(b)`	Equivalent to `swap(a,b)`

Complexity guarantees

Начало()иконецПостоянная амортизация.

Размер()является самым линейным в размере коллекции.пустой()является постоянным временем амортизации.

swap()является максимально линейным в размере двух коллекций.

Invariants

Valid range	For any Collection `a`, `[a.begin(), a.end())` is a valid range.
Range size	`a.size()` is equal to the distance from `a.begin()` to `a.end()`.
Completeness	An algorithm that iterates through the range `[a.begin(), a.end())` will pass through every element of `a`.

Models

массив
array_ptr
vector

Collection Refinements

Существует довольно много концепций, которые уточняют концепцию Коллекции, аналогично концепциям, которые уточняют концепцию Контейнера. Вот краткий обзор усовершенствованных концепций.

ForwardCollection

Элементы расположены в некотором порядке, который не меняется спонтанно от одной итерации к другой. В результате, ForwardCollectionEqualityComparableиLessThanComparable. Кроме того, тип итератора ForwardCollection представляет собой мультипассажирский итератор ввода, который является просто итератором ввода с дополнительными требованиями, что итератор может использоваться для выполнения нескольких проходов через диапазон, и что еслиit1 == it2иit1является приемлемым, то++it1 == ++it2. Надстройка также имеетпереднюю часть.Метод.

Name	Expression	Return type	Semantics
Front	`a.front()`	`reference` if `a` is mutable, `const_reference` otherwise.	Equivalent to `*(a.begin())`.

ReversibleCollection

Контейнер обеспечивает доступ к итераторам, которые проходят в обоих направлениях (вперед и назад). Тип итератора должен соответствовать всем требованиямДвунаправленного итератора, за исключением того, что эталонный тип не должен быть реальной ссылкой на C++. ReversibleCollection добавляет следующие требования к ForwardCollection:

Name	Expression	Return type	Semantics
Beginning of range	`a.rbegin()`	`reverse_iterator` if `a` is mutable, `const_reverse_iterator` otherwise.	Equivalent to `X::reverse_iterator(a.end())`.
End of range	`a.rend()`	`reverse_iterator` if `a` is mutable, `const_reverse_iterator` otherwise.	Equivalent to `X::reverse_iterator(a.begin())`.
Back	`a.back()`	`reference` if `a` is mutable, `const_reference` otherwise.	Equivalent to `*(--a.end())`.

SequentialCollection

Элементы расположены в строгом линейном порядке. Никаких дополнительных методов не требуется.

RandomAccessCollection

Итераторы RandomAccessCollection удовлетворяют всем требованиямRandomAccessIterator, за исключением того, что эталонный тип не должен быть реальной ссылкой на C++. Кроме того, RandomAccessCollection предоставляет оператора доступа к элементам.

Name	Expression	Return type	Semantics
Element Access	`a[n]`	`reference` if `a` is mutable, `const_reference` otherwise.	Returns the nth element of the Collection. `n` must be convertible to `size_type`. Precondition: `0 <= n < a.size()`.

Notes

Тип ссылки не обязательно должен быть реальным C++. Требования эталонного типа зависят от контекста, в котором используется Сборник. В частности, это зависит от требований, которые контекст помещает на тип ценности коллекции. Тип ссылки на Сборник должен соответствовать тем же требованиям, что и тип значения. Кроме того, объекты отсчета должны быть эквивалентны объектам типа значения в коллекции (что тривиально верно, если они являются одним и тем же объектом). Кроме того, в изменяемом Собрании присвоение объекту ссылки должно привести к присвоению объекту в Собрании (опять же, что тривиально верно, если они являются одним и тем же объектом, но нетривиально, если тип ссылки является классом прокси).

Collection

Boost , ,

Boost C++ Libraries

Collection

Description

Associated types

Notation

Valid expressions

Expression semantics

Complexity guarantees

Invariants

Models

Collection Refinements

ForwardCollection

ReversibleCollection

SequentialCollection

RandomAccessCollection

Notes

See also