Random access iterator

Итераторы

Итераторы — это обобщение указателей, которые позволяют программисту работать с различными структурами данных (контейнерами) единообразным способом. Чтобы создать шаблонные алгоритмы, которые правильно и эффективно работают с различными типами структур данных, нам нужно формализовать не только интерфейсы, но также семантику и предположения сложности итераторов. Итераторы — это объекты, которые имеют operator*, возвращающий значение некоторого класса или встроенного типа T, называемого значимым типом (value type) итератора. Для каждого типа итератора X, для которого определено равенство, имеется соответствующий знаковый целочисленный тип, называемый типом расстояния (distanсe type) итератора.

Так как итераторы — обобщение указателей, их семантика — обобщение семантики указателей в C++. Это гарантирует, что каждая шаблонная функция, которая использует итераторы, работает с обычными указателями. Есть пять категорий итераторов в зависимости от операций, определённых для них: ввода (input iterators), вывода (output iterators), последовательные (forward iterators), двунаправленные (bidirectional iterators) и произвольного доступа (random access iterators.) Последовательные итераторы удовлетворяют всем требованиям итераторов ввода и вывода и могут использоваться всякий раз, когда определяется тот или другой вид. Двунаправленные итераторы удовлетворяют всем требованиям последовательных итераторов и могут использоваться всякий раз, когда определяется последовательный итератор. Итераторы произвольного доступа удовлетворяют всем требованиям двунаправленных итераторов и могут использоваться всякий раз, когда определяется двунаправленный итератор. Имеется дополнительный атрибут, который могли быть иметь последовательные, двунаправленные и произвольного доступа итераторы, то есть они могут быть модифицируемые (mutable) или постоянные (constant) в зависимости от того, ведёт ли себя результат operator* как ссылка или как ссылка на константу. Постоянные итераторы не удовлетворяют требованиям итераторов вывода.

Таблица 1. Отношения среди категорий итераторов

Точно также, как обычный указатель на массив гарантирует, что имеется значение указателя, указывающего за последний элемент массива, так и для любого типа итератора имеется значение итератора, который указывает за последний элемент соответствующего контейнера. Эти значения называются законечными (past-the-end) значениями. Значения итератора, для которых operator* определён, называются разыменовываемыми (dereferenceable). Библиотека никогда не допускает, что законечные значения являются разыменовываемыми. Итераторы могут также иметь исключительные (singular) значения, которые не связаны ни с каким контейнером. Например, после объявления неинициализированного указателя x (например, int* x;), всегда должно предполагаться, что x имеет исключительное значение указателя. Результаты большинства выражений не определены для исключительных значений. Единственное исключение — присваивание неисключительного значения итератору, который имеет исключительное значение. В этом случае исключительное значение перезаписывается таким же образом, как любое другое значение. Разыменовываемые и законечные значения всегда являются неисключительными.

Итератор j называется доступным (reachable) из итератора i, если и только если имеется конечная последовательность применений operator++ к i, которая делает i==j. Если i и j относятся к одному и тому же контейнеру, тогда или j доступен из i, или i доступен из j, или оба доступны (i==j).

Большинство алгоритмических шаблонов библиотеки, которые работают со структурами данных, имеют интерфейсы, которые используют диапазоны. Диапазон — это пара итераторов, которые указывают начало и конец вычисления. Интервал [i,i) — пустой диапазон; вообще, диапазон [i,j) относится к элементам в структуре данных, начиная с элемента, указываемого i, и до элемента, но не включая его, указываемого j. Диапазон [i,j) допустим, если и только если j доступен из i. Результат применения алгоритмов библиотеки к недопустимым диапазонам не определён.

Все категории итераторов требуют только те функции, которые осуществимы для данной категории со сложностью постоянного времени (амортизированные). Поэтому таблицы требований для итераторов не имеют столбца сложности.

В следующих разделах мы принимаем: a и b — значения X, n — значение типа расстояния Distance, u, tmp и m — идентификаторы, r и s — леводопустимые (lvalues) значения X, t — значение значимого типа T.

Итераторы ввода (Input iterators)

Класс или встроенный тип X удовлетворяет требованиям итератора ввода для значимого типа T, если справедливы следующие выражения:

Таблица 2. Требования итератора ввода

Итераторы произвольного доступа (Random access iterators)

Класс или встроенный тип X удовлетворяет требованиям итераторов произвольного доступа, если к таблице, которая определяет двунаправленные итераторы, мы добавим следующие строки:

Таблица 6: Требования итератора произвольного доступа (в дополнение к двунаправленному итератору)

STL Iterators

This section describes STL iterators and introduces central ideas of generic programming.

Iterator Basics

Sequential Search

Consider a simple algorithm find

Find a particular value in a sequence (linear collection of elements).
Search from beginning until value is found or end is reached.

As an abstract algorithm this is clear, but can we implement it without specifying what kind of sequence we are dealing with?

Any implementation has to answer the following questions:

How is the start of the sequence specified?
How to move forward in the sequence?
How to recognize the end of the sequence?
How to access an element of the sequence?
What is the return value in success?
What is the return value in failure?

Iterators provide an elegant answer to all these questions.

Iterators

Iterator is a generalized pointer identifying a position in a container.

Allows moving in the container ( operator++ ) and accessing elements ( operator* )

Answers to the questions:

How is the start of the sequence specified?

iterator to the beginning of the sequence

How to move forward in the sequence?

operator++

How to recognize the end of the sequence?

iterator to the end of the sequence

How to access an element of the sequence?

operator*

What is the return value in success?

iterator pointing to the found position

What is the return value in failure?

iterator to the end (see below)

Ranges

A range is the standard STL way to specify a sequence. Most STL algorithms take a range as an argument.

A range is a pair of iterators pointing to the beginning and to the end of the sequence.
The former points to the first element but the latter to the position one step beyond the last element.

Range is often denoted as a half-open range [begin,end) or [first,last) or [first,beyond)
A range [begin,end) is valid if end is reachable from begin by repeated application of operator++ .

The asymmetry of begin and end has many nice features:

[iter,iter) is the empty range.
The length of [begin,end) is end-begin .
[A,A+N) is the range for array int A[N];
end can be used to signal failure of search.
Loops over all elements are clean:

If mid is in range [begin,end] , then [begin,end) is the concatenation of [begin,mid) and [mid,end) .
- The different choices of mid result exactly the different ways to divide a sequence into two parts.

When inserting at position iter , the new element is placed just before the element pointed by iter .
- The resulting sequence is [begin,iter)[new][iter,end) .
- Insertion at begin and end work as expected.

Iterators can have three kinds of values:

A dereferenceable iterator points to an element.
A past the end iterator points to the one-step-beyond-last position of a container.
A singular iterator does not point anywhere. It corresponds to null pointers.

The operator* is legal only for dereferenceable iterators.

Algorithm `find`

We can now give the implementation of the find algorithm.

If the returned iterator is end , the value was not found. Otherwise, the iterator points to the value.

This implementation works for any sequence with suitable iterators:

STL containers (and std::string ) have their own iterators:
- vector ::iterator , string::iterator
- A container C is [C.begin(),C.end()) as an iterator range.
Pointers are iterators for primitive arrays.

input streams

subrange of a sequence

customized iterators
- skip elements
- apply a transformation to elements
- .

Example: Simple List

A very bare-bones singly-linked list can be defined as follows:

We can build a simple list [1, 2, 3] like this

Now define an iterator for the list.

We can now search the list:

Note: node::iterator is not quite full STL iterator, yet.

Iterator Categories

The algorithm find uses the following operators of the iterator

preincrement operator++
dereference operator*
comparison operator!=
copy constructor

The algorithm works for any iterator type that defines the operators properly. Such a list of requirements is sometimes called a concept.

Concepts

A concept is a set of requirements on a type:

Syntactic requirements state the expressions that should be legal.
Semantic requirements state what the effects of the expressions should be.

A full description of the requirements can be complicated, especially for semantic requirements. It is often more intuitive to think concepts in terms of related algorithms and types:

Algorithms that make no assumptions about the type of their template argument except that it satisfies the requirements.
- Usually several algorithms.
- Some of the algorithms might have weaker requirements but it may not be worth having a separate concept for them.
Types that satisfy the requirement. Such a type models the concept, or is a model of the concept.
- A type can model several concepts.

The models are valid template arguments for the algorithms.

Concepts are central to generic programming. Their role is analogous to virtual base classes in object-oriented programming, with models corresponding to derived classes. An important difference is that concepts are not language structures; they are part of the documentation. One consequence is that built-in types can be models, too.

Analogous to class hierarchies, concepts can form hierarchies, too. If the requirements of a concept A are a superset of the requirements of a concept B:

A is said to refine B.
All models of A are also models of B.

Итераторы

Итераторы — это обобщение указателей, которые позволяют программисту работать с различными структурами данных (контейнерами) единообразным способом. Чтобы создать шаблонные алгоритмы, которые правильно и эффективно работают с различными типами структур данных, нам нужно формализовать не только интерфейсы, но также семантику и предположения сложности итераторов. Итераторы — это объекты, которые имеют operator* , возвращающий значение некоторого класса или встроенного типа T , называемого значимым типом (value type) итератора. Для каждого типа итератора X , для которого определено равенство, имеется соответствующий знаковый целочисленный тип, называемый типом расстояния (distanсe type) итератора.

Читать еще: Iif access пример

Точно также, как обычный указатель на массив гарантирует, что имеется значение указателя, указывающего за последний элемент массива, так и для любого типа итератора имеется значение итератора, который указывает за последний элемент соответствующего контейнера. Эти значения называются законечными (past-the-end) значениями. Значения итератора, для которых operator* определён, называются разыменовываемыми (dereferenceable). Библиотека никогда не допускает, что законечные значения являются разыменовываемыми. Итераторы могут также иметь исключительные (singular) значения, которые не связаны ни с каким контейнером. Например, после объявления неинициализированного указателя x (например, int* x; ), всегда должно предполагаться, что x имеет исключительное значение указателя. Результаты большинства выражений не определены для исключительных значений. Единственное исключение — присваивание неисключительного значения итератору, который имеет исключительное значение. В этом случае исключительное значение перезаписывается таким же образом, как любое другое значение. Разыменовываемые и законечные значения всегда являются неисключительными.

Итератор j называется доступным (reachable) из итератора i , если и только если имеется конечная последовательность применений operator++ к i , которая делает i==j . Если i и j относятся к одному и тому же контейнеру, тогда или j доступен из i , или i доступен из j , или оба доступны ( i == j ).

Большинство алгоритмических шаблонов библиотеки, которые работают со структурами данных, имеют интерфейсы, которые используют диапазоны. Диапазон — это пара итераторов, которые указывают начало и конец вычисления. Интервал [i,i) — пустой диапазон; вообще, диапазон [i,j) относится к элементам в структуре данных, начиная с элемента, указываемого i , и до элемента, но не включая его, указываемого j . Диапазон [i,j) допустим, если и только если j доступен из i . Результат применения алгоритмов библиотеки к недопустимым диапазонам не определён.

В следующих разделах мы принимаем: a и b — значения X , n — значение типа расстояния Distance , u, tmp и m — идентификаторы, r и s — леводопустимые (lvalues) значения X , t — значение значимого типа T .

Итераторы ввода (Input iterators)

Класс или встроенный тип X удовлетворяет требованиям итератора ввода для значимого типа T , если справедливы следующие выражения:

Random access iterator

2.2 Varieties of Iterators

As shown in Table 3, there are five basic forms of iterators used in the C++ Standard Library:

Read only, forward moving

Write only, forward moving

Both read and write, forward moving

Read and write, forward and backward moving

random access iterator

Read and write, random access

Iterator categories are hierarchical. Forward iterators can be used wherever input or output iterators are required, bidirectional iterators can be used in place of forward iterators, and random access iterators can be used in situations requiring bidirectionality.

A second characteristic of iterators is whether or not they can be used to modify the values held by their associated container. A constant iterator is one that can be used for access only, and cannot be used for modification. Output iterators are never constant, and input iterators always are. Other iterators may or may not be constant, depending upon how they are created. There are both constant and non-constant bidirectional iterators, both constant and non-constant random access iterators, and so on.

Table 4 summarizes specific ways that various categories of iterators are generated by the containers in the C++ Standard Library.

random access iterator

In the following sections we describe the capabilities and construction of each form of iterator.

2.2.1 Input Iterators

Input iterators are the simplest form of iterator. To understand their capabilities, consider an example algorithm:

This algorithm, which is similar to the std::find() generic algorithm (Section 13.3.1), performs a simple linear search, looking for a specific value being held within a container. The contents of the container are described using two iterators, first and last . While first is not equal to last , the element denoted by first is compared to the test value. If this element is equal to the test value, the iterator, which now denotes the located element, is returned. If it is not equal, the first iterator is incremented and the loop cycles once more. If the entire region of memory is examined without finding the desired value, then the algorithm returns the end-of-range iterator.

This algorithm illustrates three features of an input iterator:

An input iterator can be compared for equality to another iterator. They are equal when they point to the same position, and not equal otherwise.

An input iterator can be dereferenced, using operator*() to obtain the value being denoted by the iterator.

An input iterator can be incremented, so that it refers to the next element in sequence, using operator++() .

Notice that these features can all be provided with new meanings in a C++ program, since the behavior of the given functions can all be modified by overloading the appropriate operators. Because of this overloading, iterators are possible.

2.2.1.1 Kinds of Input Iterators

There are three main kinds of input iterators: ordinary pointers, container iterators, and input streams iterators.

Ordinary pointers. Ordinary pointers can be used as input iterators. In fact, since we can subscript and add to ordinary pointers, they are random access values, and thus can be used either as input or output iterators. The end-of-range pointer describes the end of a contiguous region of memory, and the dereference and increment operators have their conventional meanings. For example, the following code searches for the value 7 in an array of integers:

Note that constant pointers, which do not permit the underlying array to be modified, can be created by simply placing the keyword const in a declaration:

Because ordinary pointers have the same functionality as random access iterators, most of the generic algorithms in the C++ Standard Library can be used with conventional C++ arrays, as well as with the containers provided by the C++ Standard Library.

Container iterators. All of the iterators constructed for the various containers provided by the C++ Standard Library are at least as general as input iterators. The iterator for the first element in a collection is always constructed by the member function begin() , while the iterator that denotes the past-the-end location is generated by the member function end() . For example, the following iterator searches for the value 7 in a list of integers:

Each container that supports iterators provides a type with the name iterator within the class declaration. Using this type, iterators can uniformly be declared in the fashion shown. If the container being accessed is constant, or if the description const_iterator is used, then the iterator is a constant iterator.

Читать еще: Control access ru

Input stream iterators. The C++ Standard Library provides a mechanism to operate on an input stream using an input iterator. This ability is provided by the class istream_iterator, described in more detail in Section 2.3.1.

2.2.2 Output Iterators

An output iterator has the opposite function of an input iterator. Output iterators can be used to assign values in a sequence, but cannot be used to access values. For example, we can use an output iterator in a generic algorithm that copies values from one sequence into another:

A number of the generic algorithms manipulate two parallel sequences. Frequently the second sequence is described using only a beginning iterator, rather than an iterator pair. It is assumed, but not checked, that the second sequence has at least as many elements as the first.

In the algorithm shown here, two ranges are being manipulated: the range of source values specified by a pair of input iterators, and the destination range. The latter, however, is specified by only a single argument. It is assumed that the destination is large enough to include all values, and errors will ensue if this is not the case.

As illustrated by this algorithm, an output iterator can modify the element to which it points by being used as the target for an assignment. Output iterators can use the dereference operator only in this fashion; they cannot be used to return or to access the elements they denote.

As we noted earlier, ordinary pointers, like all iterators constructed by containers in the C++ Standard Library, can be used as output iterators. (Ordinary pointers are random access iterators, which are a superset of output iterators.) For example, in this code fragment elements from an ordinary C-style array are copied into a C++ Standard Library vector:

Just as the istream_iterator provides a way to operate on an input stream using the input iterator mechanism, the C++ Standard Library provides a datatype, ostream_iterator , that permits values to be written to an output stream in an iterator-like fashion (Section 2.3.2).

Yet another form of output iterator is an insert iterator (Section 2.4). An insert iterator changes the output iterator operations of dereferencing/assignment and increment into insertions into a container. This permits operations such as copy() to be used with variable length containers, such as lists and sets.

2.2.3 Forward Iterators

A forward iterator combines the features of an input iterator and an output iterator. It permits values to be both accessed and modified. One function that uses forward iterators is the replace() generic algorithm, which replaces occurrences of specific values with other values. This algorithm could be written as follows:

Ordinary pointers, like all iterators produced by containers in the C++ Standard Library, can be used as forward iterators. For example, in the following code instances of the value 7 are replaced with the value 11 in a vector of integers:

2.2.4 Bidirectional Iterators

Bidirectional iterators are similar to forward iterators, except that bidirectional iterators support the decrement operator, operator—() , permitting movement in either a forward or a backward direction through the elements of a container. For example, we can use bidirectional iterators in a function that reverses the values of a container, placing the results into a new container:

As always, the value initially denoted by the last argument is not considered part of the collection.

The reverse_copy() function could be used, for example, to reverse the values of a linked list, and place the result into a vector:

2.2.5 Random Access Iterators

Some algorithms require more functionality than simply accessing values in either a forward or backward direction. Random access iterators permit values to be accessed by subscript, subtracted one from another (to yield the number of elements between their respective values), or modified by arithmetic operations, all in a manner similar to conventional pointers.

With conventional pointers, arithmetic operations can be related to the underlying memory; that is, x+10 is the memory ten elements after the beginning of x . With iterators the logical meaning is preserved ( x+10 is the tenth element after x ), however different the physical addresses being described.

Algorithms that use random access iterators include generic operations like sorting and binary search. For example, the following algorithm randomly shuffles the elements of a container. This is similar to, although simpler than, the function std::random_shuffle() provided by the C++ Standard Library.

NOTE — The function randomInteger described here appears in a number of the example programs presented in later sections.

The program will cycle as long as first denotes a position that occurs earlier in the sequence than the one denoted by last . Only random access iterators can be compared using relational operators; all other iterators can be compared only for equality or inequality. On each cycle through the loop, the expression
last — first yields the number of elements between the two limits. The function randomInteger() is assumed to generate a random number between 0 and the argument. Using the standard random number generator, this function could be written as follows:

This random value is added to the iterator first , resulting in an iterator to a randomly selected value in the container. This value is then swapped with the element denoted by the iterator first .

2.2.6 Reverse Iterators

An iterator naturally imposes an order on an underlying container of values. For a vector or a map, the order is imposed by increasing index values; for a set, by the increasing order of the elements held in the container. For a list, the order is explicitly derived from the way values are inserted.

A reverse iterator yields values in exactly the reverse order of values given by the standard iterators. For a vector or a list, a reverse iterator generates the last element first, and the first element last. For a set it generates the largest element first, and the smallest element last. Strictly speaking, reverse iterators do not constitute a new category of iterator, but an adaptation of another iterator type. Consequently, we have reverse bidirectional iterators and reverse random access iterators. Any bidirectional or random access iterator can be adapted by the reverse_iterator template.

The list, set, and map datatypes provide a pair of member functions that produce reverse bidirectional iterators. The functions rbegin() and rend() generate iterators that cycle through the underlying container in reverse order. Increments to such iterators move backward, and decrements move forward through the sequence.

Similarly, the vector and deque datatypes provide functions, also named rbegin() and rend() , that produce reverse random access iterators. Subscript and addition operators, as well as increments to such iterators, move backward within the sequence.

Random access iterator

Итераторы

Итераторы ввода (Input iterators)

Итераторы произвольного доступа (Random access iterators)

Похожие главы из других книг: