C++ High Performance

Iterator categories

If we think about a few basic algorithms, it becomes obvious that the requirements on the iterators vary between different algorithms:

• If an algorithm count the number of occurrences of a value, it requires is_end(), read() and step_fwd()
• If an algorithm fill a container with a value, it requires is_end(), write(), step_fwd()
• A binary search algorithm on a sorted range requires step() and read()
• An algorithm which rearrange the elements requires read(), write(), step_fwd() and step_bwd()

These requirements are categorized into four basic iterator categories in STL:

• forward_iterator: The iterator can step forward
• bidirectional_iterator: The iterator can step forward and backward
• random_access_iterator: The iterator ...