C++: Iterator Types

Yao Yao on April 22, 2015
  • Published in category
  • C++


  • 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.

blog comments powered by Disqus