Document number: |
J16/01-0011 = WG21 N1297 |
Date: |
March 21, 2001 |
Author: |
Jeremy Siek, |
Output Iterator | *i = a |
Input Iterator | *i is convertible to T |
Forward Iterator | *i is T& (or const T& once issue 200 is resolved) |
Random Access Iterator | i[n] is convertible to T (which is odd because the operational semantics say i[n] is equivalent to *(i + n) which would have a return type of T&) |
Because of the mixing of iterator traversal and dereference return type, many useful iterators can not be appropriately categorized. For example, vector<bool>::iterator is almost a random access iterator, but the return type is not bool& (see issue 96 and Herb Sutter's paper J16/99-0008 = WG21 N1185). Therefore, the iterators only meet the requirements of input iterator and output iterator. This is so nonintuitive that at least one implementation erroneously assigns random_access_iterator_tag as its iterator_category. Also, vector<bool> is not the only example of useful iterators that do not return true references: there is the often cited example of disk-based collections.
Another example is a counting iterator, an iterator the returns a sequence of integers when incremented and dereferenced (see boost::counting_iterator). There are two ways to implement this iterator, 1) make the reference type be a true reference (a reference to an integer data member of the counting iterator) or 2) make the reference type be the same as the value_type. Option 1) runs into the problems discussed in Issue 198, the reference will not be valid after the iterator is destroyed. Option 2) is therefore a better choice, but then we have a counting iterator that cannot be a random access iterator.
Yet another example is a transform iterator, an iterator adaptor that applies a unary function object to the dereference value of the wrapped iterator (see boost::transform_iterator). For unary functions such as std::times the return type of operator* clearly needs to be the result_type of the function object, which is typically not a reference. However, with the current iterator requirements, if you wrap int* with a transform iterator, you do not get a random access iterator as expected, but an input iterator.
A fourth example is found in the vertex and edge iterators of the Boost Graph Library. These iterators return vertex and edge descriptors, which are lightweight handles created on-the-fly. They must be returned by-value. As a result, their current standard iterator category is std::input_iterator_tag, which means that, strictly speaking, you could not use these iterators with algorithms like std::min_element(). As a temporary solution, we introduced the concept Multi-Pass Input Iterator to describe the vertex and edge descriptors, but as the design notes for concept suggest, a better solution is needed.
In short, there are many useful iterators that do not fit into the current standard iterator categories. As a result, the following bad things happen:
Note: we considered defining a Single-Pass Iterator, which could be combined with Readable or Writable Iterator to replace the Input and Output Iterator requirements. We rejected this idea because there are several differences between Input and Output Iterators that make it hard to merge them: Input Iterator requires Equality Comparable while Output Iterator does not and Input Iterator requires Assignable while Output Iterator does not.
namespace std { // Return Type Categories struct readable_iterator_tag { }; struct writable_iterator_tag { }; struct swappable_iterator_tag { }; struct mutable_lvalue_iterator_tag : virtual public writable_iterator_tag, virtual public readable_iterator_tag { }; struct constant_lvalue_iterator_tag : public readable_iterator_tag { }; // Traversal Categories struct forward_traversal_tag { }; struct bidirectional_traversal_tag : public forward_traversal_tag { }; struct random_access_traversal_tag : public bidirectional_traversal_tag { }; }And there will need to be a way to access these category tags using a traits mechanism. Adding new typedefs to std::iterator_traits is not an acceptable solution because that would break every existing iterator. Instead, we propose two new traits classes. It is important that these traits classes are backward compatible, that is, they should work with any iterator for which there is a valid definition of std::iterator_traits. This can be accomplished by making the default behavior of the traits classes map the iterator_category of the iterator to the appropriate return or traversal category. For new iterators, either specializations of these traits classes can be defined, or the iterator can provide nested typedefs, and inherit from new_iterator_base (which is just a signal to the traits class that it is a new iterator). As with std::iterator_traits, specializations for T* are provided.
namespace std { struct new_iterator_base { }; template <typename Iterator> struct return_category { // Pseudo-code if (Iterator inherits from new_iterator_base) { typedef typename Iterator::return_category type; } else { typedef std::iterator_traits<Iterator> OldTraits; typedef typename OldTraits::iterator_category Cat; if (Cat inherits from std::forward_iterator_tag) if (is-const(T)) typedef boost::constant_lvalue_iterator_tag type; else typedef boost::mutable_lvalue_iterator_tag type; else if (Cat inherits from std::input_iterator_tag) typedef boost::readable_iterator_tag type; else if (Cat inherits from std::output_iterator_tag) typedef boost::writable_iterator_tag type; } }; template <typename T> struct return_category<T*> { // Pseudo-code if (is-const(T)) typedef boost::constant_lvalue_iterator_tag type; else typedef boost::mutable_lvalue_iterator_tag type; }; template <typename Iterator> struct traversal_category { // Pseudo-code if (Iterator inherits from new_iterator_base) { typedef typename Iterator::traversal_category type; } else { typedef std::iterator_traits<Iterator> OldTraits; typedef typename OldTraits::iterator_category Cat; if (Cat inherits from std::random_access_iterator_tag) typedef boost::random_access_traversal_tag type; else if (Cat inherits from std::bidirectional_iterator_tag) typedef boost::bidirectional_traversal_tag type; else if (Cat inherits from std::forward_iterator_tag) typedef boost::forward_traversal_tag type; } }; template <typename T> struct traversal_category<T*> { typedef boost::random_access_traversal_tag type; }; }
Algorithm | Requirement Change |
---|---|
find_end | Forward Iterator -> Forward Traversal Iterator and Readable Iterator |
find_first_of | |
adjacent_find | |
search | |
search_n | |
rotate_copy | |
lower_bound | |
upper_bound | |
equal_range | |
binary_search | |
min_element | |
max_element | |
iter_swap | Forward Iterator -> Swappable Iterator |
fill | Forward Iterator -> Forward Traversal Iterator and Writable Iterator |
generate | |
swap_ranges | Forward Iterator -> Forward Traversal Iterator and Swappable Iterator |
rotate | |
replace | Forward Iterator -> Forward Traversal Iterator and Readable Iterator and Writable Iterator |
replace_if | |
remove | |
remove_if | |
unique | |
reverse | Bidirectional Iterator -> Bidirectional Traversal Iterator and Swappable Iterator |
partition | |
copy_backwards | Bidirectional Iterator -> Bidirectional Traversal Iterator and Readable Iterator Bidirectional Iterator -> Bidirectional Traversal Iterator and Writable Iterator |
next_permutation | Bidirectional Iterator -> Bidirectional Traversal Iterator and Swappable Iterator and Readable Iterator |
prev_permutation | |
stable_partition | Bidirectional Iterator -> Bidirectional Traversal Iterator and Readable Iterator and Writable Iterator |
inplace_merge | |
reverse_copy | Bidirectional Iterator -> Bidirectional Traversal Iterator and Readable Iterator |
random_shuffle | Random Access Iterator -> Random Access Traversal Iterator and Swappable Iterator |
sort | |
stable_sort | |
partial_sort | |
nth_element | |
push_heap | |
pop_heap | |
make_heap | |
sort_heap |
X | The iterator type. |
T | The value type of X, i.e., std::iterator_traits<X>::value_type. |
x, y | An object of type X. |
t | An object of type T. |
Value type | std::iterator_traits<X>::value_type | The type of the objects pointed to by the iterator. |
Reference type | std::iterator_traits<X>::reference | The return type of dereferencing the iterator. This type must be convertible to T. |
Return Category | std::return_category<X>::type | A type convertible to std::readable_iterator_tag |
Name | Expression | Type requirements | Return type |
---|---|---|---|
Dereference | *x | std::iterator_traits<X>::reference | |
Member access | x->m | T is a type with a member named m. | If m is a data member, the type of m. If m is a member function, the return type of m. |
Return Category | std::return_category<X>::type | A type convertible to std::writable_iterator_tag |
Name | Expression | Return type |
---|---|---|
Dereference assignment | *x = a | unspecified |
Note: the requirements for Swappable Iterator are dependent on the issues surrounding std::swap() being resolved. Here we assume that the issue will be resolved by allowing the overload of std::swap() for user-defined types.
Note: Readable Iterator and Writable Iterator combined implies Swappable Iterator because of the fully templated std::swap(). However, Swappable Iterator does not imply Readable Iterator nor Writable Iterator.
Return Category | std::return_category<X>::type | A type convertible to std::swappable_iterator_tag |
Name | Expression | Return type |
---|---|---|
Iterator Swap | std::iter_swap(x, y) | void |
Dereference and Swap | std::swap(*x, *y) | void |
Reference type | std::iterator_traits<X>::reference | The return type of dereferencing the iterator, which must be const T&. |
Return Category | std::return_category<X>::type | A type convertible to std::constant_lvalue_iterator_tag |
Reference type | std::iterator_traits<X>::reference | The return type of dereferencing the iterator, which must be T&. |
Return Category | std::return_category<X>::type | A type convertible to std::mutable_lvalue_iterator_tag |
Difference Type | std::iterator_traits<X>::difference_type | A signed integral type used for representing distances between iterators that point into the same range. |
Traversal Category | std::traversal_category<X>::type | A type convertible to std::forward_traversal_tag |
Name | Expression | Type requirements | Return type |
---|---|---|---|
Preincrement | ++i | X& | |
Postincrement | i++ | convertible to const X& |
Traversal Category | std::traversal_category<X>::type | A type convertible to std::bidirectional_traversal_tag |
Name | Expression | Type requirements | Return type |
---|---|---|---|
Predecrement | --i | X& | |
Postdecrement | i-- | convertible to const X& |
Traversal Category | std::traversal_category<X>::type | A type convertible to std::random_access_traversal_tag |
Name | Expression | Type requirements | Return type |
---|---|---|---|
Iterator addition | i += n | X& | |
Iterator addition | i + n or n + i | X | |
Iterator subtraction | i -= n | X& | |
Iterator subtraction | i - n | X | |
Difference | i - j | std::iterator_traits<X>::difference_type | |
Element operator | i[n] | X must also be a model of Readable Iterator. | std::iterator_traits<X>::reference |
Element assignment | i[n] = t | X must also be a model of Writable Iterator. | unspecified |