| Document number: | N1672=04-0112 |
| Date: | September 10, 2004 |
| Project: | Programming Language C++ |
| Reference: | ISO/IEC IS 14882:2003(E) |
| Reply to: | Pete Becker |
| Dinkumware, Ltd. | |
| petebecker@acm.org |
Introduction
· Changes to Iterator Categories
· Changes to Algorithms
· Changes to Containers
· Impact on Existing Code
The underlying idea in the paper New Iterator Concepts (N1640=04-0080) is fairly simple: separating dereferencing of iterators from traversing them provides more flexibility for programmers who implement and use iterators. The details in the paper are somewhat complicated, however, because the paper creates a new set of iterator requirements while attempting to make these new requirements compatible with the existing iterator requirements. Applying the underlying idea directly to the existing iterator requirements is much simpler.
The current iterator categories look like this:
| Category | Traversal Properties | Access | Tag |
|---|---|---|---|
| output iterator | destructive increment | writable | output_iterator_tag |
| input iterator | destructive increment, compare | readable | input_iterator_tag |
| forward iterator | increment, compare | readable or writable | forward_iterator_tag |
| bidirectional iterator | forward iterator properties plus decrement | readable or writable | bidirectional_iterator_tag |
| random access iterator | bidirectional iterator properties plus random access | readable or writable | random_access_iterator_tag |
N1640 proposes adding the following categories:
| Category | Traversal Properties | Tag |
|---|---|---|
| incrementable iterator | destructive increment | incrementable_traversal_tag |
| single pass iterator | destructive increment, compare | single_pass_traversal_tag |
| forward traversal iterator | increment, compare | forward_traversal_tag |
| bidirectional traversal iterator | forward traversal iterator properties plus decrement | bidirectional_traversal_tag |
| random access traversal iterator | bidrectional traversal iterator properties plus random access | random_access_traversal_tag |
This paper proposes removing the access properties from the current iterator categories, as proposed in N1640, but for the most part keeping the names and tag types from the current categories:
| Category | Traversal Properties | Tag | Tag Typedef |
|---|---|---|---|
| incrementable iterator | destructive increment | incremental_iterator_tag |
output_iterator_tag |
| single pass iterator | destructive increment, compare | single_pass_iterator_tag |
input_iterator_tag |
| forward iterator | increment, compare | forward_iterator_tag |
|
| bidirectional iterator | forward iterator properties plus decrement | bidirectional_iterator_tag |
|
| random access iterator | bidirectional iterator properties plus random access | random_access_iterator_tag |
As in N1640, each of the tags is derived from the tag in the row above it.
The tags output_iterator_tag and input_iterator_tag
become typedefs for incremental_iterator_tag and
single_pass_iterator_tag, respectively.
As discussed in N1640, changing the iterator categories so that they no longer reflect access properties means that algorithms can no longer be specified solely in terms of the iterator categories that they accept. Algorithms must also specify the access properties that they require for each of the iterator types that they take.
Obversely, changing the iterator categories means that member functions that return iterators into containers can no longer be specified solely in terms of the iterator categories of the iterators that they return. They must also specify the access properties of those iterators.
None.
Okay, that's a bit glib. But these changes affect only the way that we describe iterators, algorithms, and containers, not the way any of them are currently implemented. So all existing valid code remains valid.
At first glance there does appear to be a possible problem from the reduced guarantees that the new iterator categories make. Algorithms often have multiple implementations, chosen according to the properties of the types of the iterators that they are called with. Reducing the guarantees for an iterator category means that algorithms that rely on properties that are no longer required for a particular category will no longer work correctly.
However, removing access properties from iterator categories has no such impact. An algorithm's requirements for readability and writability of iterators are absolute requirements, not iterator properties whose absence can be worked around. Algorithms do not provide alternate formulations depending on whether the iterator they are called with is readable. They simply fail to compile.