File Iterators.h

↰ Parent directory (ADS)

The iterators that the containers of the library have in common, beyond the book: they give a container the interface of the standard library (begin(), end(), the categories of the iterators), so that the range-for, the algorithms of std and of std::ranges, and those of Boost visit it.

Definition (ADS/Iterators.h)

Detailed Description

  • LinkedIterator walks cells linked by a pointer, the member Next, and reads the member Value of each, the end being nil: a forward iterator for the singly linked lists, queues and stacks.

  • IndexIterator walks cells of a vector linked by an index, the member Next, the end being -1: a forward iterator for the structures whose cells are a vector with a free list (the stacks sharing one space).

  • CircularIterator is the random-access iterator on the items of a circular vector, the item i from the head being at ( head + i ) mod capacity, so that the order of the items is that of the queue and not that of the places.

  • IndirectIterator reads through an iterator on pointers (smart or not), with its category: a random-access view of a vector of pointers to the items, as the heaps of handles keep them.

  • SlotIterator walks the places 0 , … , m - 1 of a table, skipping those that a policy P declares empty (or deleted, for the open addressing with lazy deletion), and reads each through P: P::size(), P::occupied() and P::read() take the owner and the place, so that a policy nested in the owner reads its private fields; the reading may build its result (a pair of references, a key computed from the place), in which case the iterator is a forward iterator of C++20 and only an input iterator for the older algorithms, as the views of std are.

  • KeyIterator reads the member first of what another iterator reads, the keys of a dictionary as the items of a set.

  • PathIterator visits a binary tree in symmetric order keeping the path from the root to the current node, so that it needs no link to the parent and goes both ways; a policy P gives the root, the children and the reading of a node, as for SlotIterator. A step costs O( 1 ) amortized and O( h ) at most, the path O( h ) space.

  • WalkIterator follows the nodes of a tree (pointers or indices) by a policy P whose next( o , n , root ), o a pointer to the owner (nil if the nodes need none), gives the node after n in the walk below root, or P::none: the children of a node, the preorder and the symmetric order by the links to the parents, with no stack.

Each has a constant and a mutable form, by the parameter Const, and the mutable one converts to the constant one. An iterator stays valid as long as the cells (or the vector) it refers to do; the containers that keep an invariant on their items (a heap, a set) expose only the constant form. These are adaptors with no contracts of their own: the containers check theirs.

  1. Stroustrup, The C++ Programming Language, 4th ed., Addison-Wesley, 2013, chapter 33 (the iterators)

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

  • compare

  • cstddef

  • iterator

  • type_traits

  • utility

  • vector

Included By

Namespaces

Classes