|
Note: This specification is a revised version based on the C++ Standard [C++98], which is available now. In particular, iterator traits are now assumed and required.
Iterators in the STL were tailored for linear sequences. The specialization for circular data structures leads to slightly different requirements which we will summarize in the circulators concept. The main difference is that a circular data structure has no natural past-the-end value. As a consequence, a container supporting circulators will not have an end()-member function. The semantic of a circulator range differs from the semantic of an iterator range. For a circulator c the range [c, c) denotes the sequence of all elements in the data structure. For iterators, this range defines the empty sequence. A separate test for an empty sequence has been added to the circulator requirements: A comparison c == NULL for a circulator c is true for an empty sequence. As for C++, we recommend the use of 0 instead of NULL.
Similar to STL iterators, we distinguish between forward, bidirectional, and random access circulators1. Most requirements for circulators are equal to those for iterators. We present the changes, please refer to [MS96, chapter 18] or [C++98] for the iterator requirements.
Past-the-end value: There is no past-the-end value for circulators.
Singular values: There are no singular values for circulators2
Empty sequence: The comparison c == NULL (or c == 0) for a circulator c is true if c denotes an empty sequence, and false otherwise.
Dereferenceable values: A circulator that does not denote an empty sequence is dereferenceable.
Reachability: Each dereferenceable circulator can reach itself with a finite and non-empty sequence of applications of operator++.
Ranges: For any circulator c the range [c, c) is a valid range. If the circulator refers to an empty sequence, the range [c, c) denotes the empty range. Otherwise the circulator is dereferenceable and the range [c, c) denotes the sequence of all elements in the data structure. Remark: When a circulator is used in a place of an iterator, as, for example, with an STL algorithm, it will work as expected with the only exception that, in STL algorithms, the range [c, c) denotes always the empty range. This is not a requirement, but a consequence of the requirements stated here and the fact that the STL requirements for iterator ranges are based on the operator++ and the operator==, which we use for circulators as well. In principle, we face here the difference between a while loop and a do-while loop.
Types: For a circulator of type C the following local types are required:
| C::value_type | value type the circulator refers to. |
| C::reference | reference type used for the return type of C::operator*(). |
| C::pointer | pointer type used for the return type of C::operator->(). |
| C::size_type | unsigned integral type that can hold the size of a sequence |
| C::difference_type | signed integral type that can hold the distance between two circulators. |
| C::iterator_category | circulator category. |
In the following, we assume that a and b are circulators of type C, r is of type C& (is assignable), and T denotes the value type of C. Let D be the distance type of C. As for C++, we recommend the use of 0 instead of NULL.
| C() | a circulator equal to NULL denoting an empty sequence. |
| a == NULL | Returns true if a denotes an empty sequence, false otherwise. |
| For simplicity, NULL == a is not required. The | |
| behavior for comparisons with pointer-like values different than NULL | |
| is undefined. A runtime assertion is recommended. | |
| a != NULL | Returns !(a == NULL). |
| ++r | Like for forward iterators, but a dereferenceable circulator r will always |
| be dereferenceable after ++r (no past-the-end value). Precondition: r | |
| does not denote an empty sequence. | |
| r++ | Same as for ++r. |
| C::iterator_category | circulator category CBP_Forward_circulator_tag. |
The same requirements as for the forward circulators hold for bidirectional iterators with the following change of the iterator category:
| C::iterator_category | circulator category CBP_Bidirectional_circulator_tag. |
The same requirements as for the bidirectional circulators hold for random access iterators with the following changes and extensions.
The idea of random access extends naturally to circulators using equivalence classes modulus the length of the sequence. With this in mind, the additional requirements for random access iterators hold also for random access circulators. The only exception is that the random access iterator is required to provide a total order on the sequence, which a circulator cannot provide3.
The difference of two circulators is not unique as for iterators. A reasonable requirement demands that the result is in a certain range [1-size, size-1], where size is the size of the sequence, and that whenever a circulator a is fixed that the differences with all other circulators of the sequence form a consistent ordering.
For the adaptor to iterators a minimal circulator dmin is required for which the difference c - dmin to all other circulators c is non negative.
| b - a | limited range and consistent ordering as explained above. |
| a.min_circulator() | returns the minimal circulator from the range [a,a). |
| C::iterator_category | circulator category CBP_Random_access_circulator_tag. |
As with iterators, we distinguish between circulators and const circulators. The expression *a = t with t of type T is valid for mutable circulators. It is invalid for const circulators.
For a container x of type X that supports circulators c the following naming convention is recommended:
| X::Circulator | the type of the mutable circulator. |
| X::Const_circulator | the type of the const circulator. |
| c = x.begin() | the start circulator of the sequence. It is of type X::Circulator for a |
| mutable container or X::Const_circulator for a const container. There | |
| must not be an end() member function. |
If a container will support iterators and circulators, the member function circulator_begin() is proposed. However, the support of iterators and circulators simultaneously is not recommended, since it would lead to fat interfaces. The natural choice should be supported, the other concept will be available through adaptors.
A generic contains function accepts a range of circulators and a value. It returns true if the value is contained in the sequence of items denoted by the range of circulators. As usual for circular structures, a do-while loop is preferable, such that for the specific input, c == d, all elements in the sequence are reached. Note that the example simplifies if the sequence is known to be non-empty, which is for example the common case in polyhedral surfaces where vertices and facets have at least one incident edge.
template <class Circulator, class T>
bool contains( Circulator c, Circulator d, const T& value) {
if (c != 0) {
do {
if (*c == value)
return true;
} while (++c != d);
}
return false;
}
| 1 | Input circulators are a contradiction, since any circulator is supposed to return once to itself. Output circulators are not supported since they would be indistinguishable from output iterators. |
| 2 | Since circulators must be implemented as classes anyway, there is no need to allow singular values for them. An un-initalized circulator does not have a singular value, but is supposed to refer to an empty sequence. |
| 3 | One might define an order by splitting the circle at a fixed point, e.g. the start circulator provided from the data structure. This is what the adaptor to iterators will do. Nonetheless, we do not require this for circulators. |