C++: Iterator Types

整理自：

• Thinking in C++, Volume 2
• Apache C++ Standard Library User’s Guide: 2.2 Varieties of Iterators
• Header: iterator
• SGI: Iterators
• C++ concepts: Iterator

---

• InputIterator:
  • Reads elements of its sequence in a single, forward pass using operator++ and operator*.
  • Can also be tested with operator== and operator!= (a.k.a EqualityComparable).
  • 比如:
    • istream_iterator
• OutputIterator:
  • Writes elements to a sequence in a single, forward pass using operator++ and operator*.
  • CANNOT be tested with operator== and operator!=
  • 比如：
    • ostream_iterator
    • inserter()
    • front_inserter()
    • back_inserter()
• ForwardIterator:
  • Only moves forward using operator++,
    • but you can both write and read, (所以 replace 操作需要 ForwardIterator)
    • and you can compare such iterators in the same range for equality.
  • ALL standard containers support at least forward iterator types.
    • Ordinary pointers, like all iterators produced by containers in the C++ Standard Library, can be used as forward iterators.
  • 比如：
    • vector::begin()
• BidirectionalIterator:
  • Effectively, this is a ForwardIterator that can also go backward.
    • That is, it supports all the operations that a ForwardIterator does,
    • but in addition it has an operator--. (所以 reverse_copy 操作需要 BidirectionalIterator)
  • 比如：
    • list::begin()
• RandomAccessIterator
  • This type of iterator supports all the operations that a regular pointer does:
    • you can add and subtract integral values to move it forward and backward by jumps (rather than just one element at a time),
    • you can subscript it with operator[],
    • you can subtract one iterator from another,
    • and you can compare iterators to see which is greater using operator<, operator>, and so on.
    • If you’re implementing a sorting routine or something similar, random access iterators are necessary to be able to create an efficient algorithm.
  • 比如：
    • vector::iterator()

在继承关系上我们有：

struct output_iterator_tag {};

struct input_iterator_tag {};
	struct forward_iterator_tag : public input_iterator_tag {};
		struct bidirectional_iterator_tag : public forward_iterator_tag {};
			struct random_access_iterator_tag : public bidirectional_iterator_tag {};

---

最后说几个描述 class 的概念，也可以用来描述 iterator：

• LessThanComparable:
  • A class that has a operator<.
• Assignable:
  • A class that has a operator= for its own type.
• EqualityComparable:
  • A class that has an operator== for its own type.

以下这两个概念应该只能用来描述 iterator：

• Dereferenceable:
  • Iterator i for which the behavior of the expression *i is defined is called dereferenceable.
  • Iterators are not dereferenceable if
    • they are past-the-end iterators (including pointers past the end of an array) or before-begin iterators.
      • Such iterators may be dereferenceable in a particular implementation, but the library never assumes that they are.
      • 比如 vector::end() 就是个 past-the-end iterator，你可以对它 dereference，不会报错但是这是一个 undefined behavior
    • they are singular iterators, that is, iterators that are not associated with any sequence.
      • A null pointer, as well as a default-constructed pointer (holding an indeterminate value) is singular
    • they were invalidated by one of the iterator-invalidating operations on the sequence to which they refer.
• incrementable:
  • Iterator i for which the behavior of the expression ++i is defined is called incrementable.