What are iterators and why are they needed


I can't understand the main purpose of iterators. Googling, I did not understand everything equal.

Explain, please:

  1. What is an iterator?
  2. Why is it needed?
  3. Benefits on the signpost
  4. How to describe it programmatically in code? (that is, make your iterator similar to the library one).


Look. You have a container. It doesn't matter what: map , vector , set . It contains a collection of elements. And you do not want to refer to the entire container, but to some place in this set of elements. So that from this place you can go forward / backward, and do something in this place: change an element, insert an element, delete an element.

How to do it? For an array, you use an index in such cases. set internally a red-black tree, so you need a reference to a node in that tree. unordered_map uses a hash table, so you need a hash index and a pointer to the item inside the bucket.

To avoid having to write algorithms specific to each container, iterators were invented.

An iterator is a data structure that “points” to a certain element of the container, and (for some containers) can move to the previous / next element.

If you want to implement an iterator, remember that there are different types of iterators, depending on the operations they provide. Here is a list of possible types.

If you, for example, want to implement RandomAccessIterator , you have to define a copy constructor, assignment operator, destructor, operations == RandomAccessIterator != , * , -> , no-argument constructor, ++ , -- , += , + (2 pcs. ), -= , - (2 pcs.), < , > , <= , >= . (Other types of iterators are simpler.)

In addition, you have to specify std::iterator_traits<It> , where It is the type of your iterator.

Here's a template for your own container on SO. A lot, right?

Scroll to Top