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

A Collection is a concept similar to the STL Container concept. A Collection provides iterators for accessing a range of elements and provides information about the number of elements in the Collection. However, a Collection has fewer requirements than a Container. The motivation for the Collection concept is that there are many useful Container-like types that do not meet the full requirements of Container, and many algorithms that can be written with this reduced set of requirements. To summarize the reduction in requirements:

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

The following expressions must be valid.

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

begin() and end() are amortized constant time.

size() is at most linear in the Collection's size. empty() is amortized constant time.

swap() is at most linear in the size of the two collections.

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

Collection Refinements

There are quite a few concepts that refine the Collection concept, similar to the concepts that refine the Container concept. Here is a brief overview of the refining concepts.

ForwardCollection

The elements are arranged in some order that does not change spontaneously from one iteration to the next. As a result, a ForwardCollection is EqualityComparable and LessThanComparable. In addition, the iterator type of a ForwardCollection is a MultiPassInputIterator which is just an InputIterator with the added requirements that the iterator can be used to make multiple passes through a range, and that if it1 == it2 and it1 is dereferenceable then ++it1 == ++it2. The ForwardCollection also has a front() method.

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

ReversibleCollection

The container provides access to iterators that traverse in both directions (forward and reverse). The iterator type must meet all of the requirements of BidirectionalIterator except that the reference type does not have to be a real C++ reference. The ReversibleCollection adds the following requirements to those of 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

The elements are arranged in a strict linear order. No extra methods are required.

RandomAccessCollection

The iterators of a RandomAccessCollection satisfy all of the requirements of RandomAccessIterator except that the reference type does not have to be a real C++ reference. In addition, a RandomAccessCollection provides an element access operator.

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

[1] The reference type does not have to be a real C++ reference. The requirements of the reference type depend on the context within which the Collection is being used. Specifically it depends on the requirements the context places on the value type of the Collection. The reference type of the Collection must meet the same requirements as the value type. In addition, the reference objects must be equivalent to the value type objects in the collection (which is trivially true if they are the same object). Also, in a mutable Collection, an assignment to the reference object must result in an assignment to the object in the Collection (again, which is trivially true if they are the same object, but non-trivial if the reference type is a proxy class).

See also

Container


Valid HTML 4.01 Transitional

Revised 05 December, 2006

Copyright © 2000 Jeremy Siek, Univ.of Notre Dame and C++ Library & Compiler Group/SGI (jsiek@engr.sgi.com)

Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)