Here I can not understand the main purpose of iterators. Googling, all the same did not understand.

Please explain:

  1. What is an iterator?
  2. Why is it needed?
  3. Advantages on the pointer
  4. How to describe it programmatically in code? (i.e., make your iterator look like a library).

    2 answers 2

    See it. Let you have a container. No matter what: map , vector , set . It contains a set of items. And you want to refer not to the entire container, but to some place in this set of elements. So that from this place it was possible to go forward / back, and to do something in this place: change the element, insert the element, delete the element.

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

    That it was not necessary to write the algorithms specific to each container, and iterators were thought up.

    An iterator is a data structure that “points” to some element of the container, and (for some containers) can navigate 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 a RandomAccessIterator , you have to define a copy constructor, an assignment operator, a destructor, == RandomAccessIterator != , * , -> operations, a constructor without arguments, ++ , -- , += , + (2 pcs. ), -= , - (2 pcs.), < , > , <= , >= . (Other types of iterators are simpler.)

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

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

    • 7
      That is, an iterator is like an extended pointer, that is, I suppose I don’t need to know how the iterator works to use it, but to use generally accepted rules. Although inside for each specific container, the iterator may be the same pointer, for example, as in an array, and in other situations, the elements may be out of sync in memory, but the iterator knows how to get to a specific element. Right ? - CROSP
    • @Alexandr Crospov: Absolutely! - VladD

    An iterator is an object that allows you to move (iterate) through the elements of a sequence.
    The use of such objects is classified as an Iterator programming pattern.

    A sequence can be either a ready-made set of objects in memory or it can consist of objects that are created on the fly when an iterator is moved (for example, read from a file).

    Unlike various sequences of elements (arrays, lists, files), iterators have the same interface: getting the current element, moving to the next. This allows you to write more general algorithms that work with any iterators that support this minimal set of functions.

    Iterators of the standard C ++ library repeat the pointer interface. This allows you to use pointers to array elements as iterators. At the same time, most algorithms use only some minimal set of operations, for example, only moving forward. This set of operations is called a category ; a list of all categories of iterators is listed here .

    Variants of writing your iterator are in the answers to this question .