Iterator Concepts

Boost , ,

Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. — Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

Iterator Concepts

Итератор - это ограниченный указатель-подобный объект, указывающий в векторный или матричный контейнер.

Indexed Bidirectional Iterator

Description

Индексированный двунаправленный итератор - это итератор контейнера, который может быть удален, увеличен, уменьшен и несет информацию об индексе.

Refinement of

Приемлемое, сопоставимое по равенству, конструктивное по умолчанию.

Associated types

Тип значения	Тип значения, полученного путем отсчета индексированного двунаправленного итератора
Тип контейнера	Тип контейнера, в который указывает индексированный двунаправленный итератор.

Notation

<`I`>	Тип, который является моделью индексированного двунаправленного итератора
<`T`>	Тип величины<`I`>
<`C`>	Тип контейнера<`I`>
<`it`><`itt, it1`><`it2`>	Объекты типа<`I`>
<`t`>	Объект типа<`T`>
<`c`>	Объект типа<`C`>

Definitions

Индексированный двунаправленный итератор может бытьизменчивым, что означает, что значения, указанные объектами этого типа, могут быть изменены, илипостоянным, что означает, что они не могут. Если тип итератора является изменчивым, это означает, что его тип значения является моделью подлежащего присвоению; однако обратное не обязательно верно.

Индексированный двунаправленный Итератор может иметьединственноезначение, то есть результаты большинства операций, включая сравнение для равенства, не определены. Единственная операция, которая гарантированно поддерживается, это назначение несингулярного итератора единственному итератору.

Индексированный двунаправленный Итератор может иметьотносимоезначение, что означает, что отнесение к нему дает четко определенное значение. Относительные итераторы всегда несингулярны, но обратное неверно.

Индексированный двунаправленный итераторпроходит конец, если он указывает за пределы последнего элемента контейнера. Прошлые конечные значения являются несингулярными и неотносительными.

Valid expressions

В дополнение к выражениям, определенным для Assignable, Equality Comparable и Default Constructible, следующие выражения должны быть действительными.

Name	Expression	Type requirements	Return type
Разработчик Default	<`I it`>
Отсчетное назначение	<`*it`>		Преобразуется в<`T`>.
Отсчетное назначение	<`*it = t`>	<`I`>Неподвижно.
Доступ к члену	<`it->m`>	<`T`>— тип, для которого<`t.m`>определено.
Прирост	<`++ it`>		<`I &`>
Постприрост	<`it ++`>		<`I`>
Предварительное определение	<`-- it`>		<`I &`>
Постдекрет	<`it --`>		<`I`>
Индекс	<`it.index ()`>		<`C::size_type`>

Expression Semantics

Семантика выражения определяется только в тех случаях, когда она отличается или не определена в Assignable, Equality Comparable и Default Constructible.

Name	Expression	Precondition	Semantics	Postcondition
Разработчик Default	<`I it`>			<`it`>является единственным.
Отсчетное назначение	<`*it`>	<`it`>Недопустимо.
Отсчетное назначение	<`*it = t`>	Так же, как и<`*it`>.		<`*it`>является копией п.
Доступ к члену	<`it->m`>	<`it`>Недопустимо.	эквивалентно<`(*it).m`>
Прирост	<`++ it`>	<`it`>Недопустимо.	<`it`>изменяется, чтобы указать на следующий элемент.	<`it`>является прелюдией или концом.<`&it == &++ it`> Если<`it1 == it2`>, тогда<`++ it1 == ++ it2`>.
Постприрост	<`it ++`>	Так же, как и<`++ it`>.	Эквивалентно <`{ I itt = it; ++ it; return itt; }`>	<`it`>является сносным или прошедшим концом.
Предварительное определение	<`-- it`>	<`it`>является сносным или прошедшим концом. There exists a dereferenceable iterator `itt` such that `it == ++ itt`.	<`it`>изменяется, чтобы указать на предыдущий элемент.	<`it`>Недопустимо. `&it = &-- it`. If `it1 == it2`, then `-- it1 == -- it2`. If `it2` is dereferenceable and `it1 == ++it2`, then `--it1 == it2`.
Постдекрет	<`it --`>	То же самое, что и<`it`>.	эквивалентно <`{ I itt = it; -- it; return itt; }`>	<`it`>Недопустимо.
Индекс	<`it.index ()`>	<`it`>Недопустимо.	<`it.index () >= 0`> и <`it.index () < it ().size ()`>	Если<`it1 == it2`>, , то<`it1.index () == it2.index ()`>. Если<`it1 == it2`>, тогда<`it1.index () < (++ it2).index ()`>. Если<`it1 == it2`>, тогда<`it1.index () > (-- it2).index ()`>.

Complexity guarantees

Сложность операций на индексированных двунаправленных итераторах гарантированно амортизируется постоянным временем.

Invariants

Идентичность	<`it1 == it2`>Если и только если<`&it1 == &it2`>.
Симметрия приращения и декреции	Если же<`it`>— неуместно, то<`++ it; --it;`>— нулевая операция.<`-- it; ++ it;`>— это нулевая операция.
Связь между индексом итератора и оператором контейнерных элементов	Если же<`it`>— то<`*it == it () (it.index ())`>.

Models

sparse_vector::iterator

Indexed Random Access Iterator

Description

Индексированный итератор случайного доступа - это итератор контейнера, который может быть отнесен, перемещен вперед, перемещен назад и несет информацию об индексе.

Refinement of

Несравненный,Индексированный двунаправленный итератор.

Associated types

Тип значения	Тип значения, полученного путем отсчета индексированного итератора случайного доступа
Тип контейнера	Тип контейнера, в который указывает индексированный итератор случайного доступа.

Notation

<`I`>	Тип, который является моделью индексированного итератора случайного доступа
<`T`>	Тип величины<`I`>
<`C`>	Тип контейнера<`I`>
<`it`><`itt, it1`><`it2`>	Объекты типа<`I`>
<`t`>	Объект типа<`T`>
<`n`>	Объект типа<`C::difference_type`>

Definitions

Индексированный итератор случайного доступа<it1>доступениз индексированного итератора случайного доступа<it2>, если после применения<operator ++>к<it2>конечное число раз<it1 == it2>.

Valid expressions

В дополнение к выражениям, определенным дляИндексированного двунаправленного итератора, следующие выражения должны быть действительными.

Name	Expression	Type requirements	Return type
Движение вперед	<`it += n`>		<`I &`>
Добавление итератора	<`it + n`>		<`I`>
Движение назад	<`i -= n`>		<`I &`>
Вычитание итератора	<`it - n`>		<`I`>
Разница	<`it1 - it2`>		<`C::difference_type`>
Оператор элемента	<`it [n]`>		Преобразуется в<`T`>.
Задание элементов	<`it [n] = t`>	<`I`>является мутабельным	Преобразуется в<`T`>.

Expression Semantics

Семантика выражения определяется только там, где она отличается или не определена вИндексированный двунаправленный итератор.

Name	Expression	Precondition	Semantics	Postcondition
Движение вперед	<`it += n`>	Включая сам<`it`>, должны быть<`n`>реферативные или прошлые конечные итераторы, следующие или предшествующие<`it`>, в зависимости от того, является ли<`n`>положительным или отрицательным.	Если<`n > 0`>, то<`n`><`++ it`><`n`>. Если<`n < 0`>, то<`-- it`><`n`>раз. Если<`n == 0`>, то это нулевая операция.	<`it`>является сносным или прошедшим концом.
Добавление итератора	<`it + n`>	Так же, как и<`i += n`>.	эквивалентно <`{ I itt = it; return itt += n; }`>	Результат является достойным уважения или прошедшим концом.
Движение назад	<`it -= n`>	Включая сам<`it`>, должны быть<`n`>сносные или прошлые конечные итераторы, предшествующие или следующие<`it`>, в зависимости от того, является ли<`n`>положительным или отрицательным.	Это эквивалентно<`it += (-n)`>.	<`it`>является сносным или прошедшим концом.
Вычитание итератора	<`it - n`>	Так же, как и<`i -= n`>.	эквивалентно <`{ I itt = it; return itt -= n; }`>	Результат является достойным уважения или прошедшим концом.
Разница	<`it1 - it2`>	Или<`it1`>достижимо от<`it2`>, или<`it2`>достижимо от<`it1`>, или оба.	Возвращает число<`n`>так, что<`it1 == it2 + n`>
Оператор элемента	<`it [n]`>	<`it + n`>существует и заслуживает уважения.	эквивалентно<`*(it + n)`>
Задание элементов	<`i[n] = t`>	Так же, как и<`it [n]`>.	эквивалентно<`*(it + n) = t`>

Complexity guarantees

Сложность операций на индексированных итераторах случайного доступа гарантированно амортизируется постоянным временем.

Invariants

Симметрия сложения и вычитания	Если<`it + n`>хорошо определено, то<`it += n; it -= n;`>и<`(it + n) - n`>являются нулевыми операциями. Если<`it - n`>хорошо определено, то<`it -= n; it += n;`>и<`(it - n) + n`>являются нулевыми операциями.
Отношение между расстоянием и сложением	Если<`it1 - it2`>хорошо определен, то<`it1 == it2 + (it1 - it2)`>.
Достижимость и расстояние	Если<`it1`>достижимо от<`it2`>, то<`it1 - it2 >= 0`>.

Models

vector::iterator

Indexed Bidirectional Column/Row Iterator

Description

Индексированный двунаправленный колонный / рядовой итератор - это итератор контейнера, который может быть удален, увеличен, уменьшен и несет информацию об индексе.

Refinement of

Приемлемое, сопоставимое по равенству, конструктивное по умолчанию.

Associated types

Тип значения	Тип значения, полученного путем отсчета индексированной двунаправленной колонны / итератора строки
Тип контейнера	Тип контейнера, в который указывает индексированная двунаправленная колонна / рядовой итератор.

Notation

<`I1`>	Тип, который является моделью индексированной двунаправленной колонки / итератора строки
<`I2`>	Тип, который является моделью индексированного двунаправленного итератора рядов / колонн
<`T`>	Типы значений<`I1`>и<`I2`>
<`C`>	Тип контейнера<`I1`>и<`I2`>
<`it1`>,<`it1t, it11`>,<`it12`>	Типовые объекты<`I1`>
<`it2`>,<`it2t`>	Типовые объекты<`I2`>
<`t`>	Объект типа<`T`>
<`c`>	Объект типа<`C`>

Definitions

Valid expressions

Name	Expression	Type requirements	Return type
Разработчик Default	<`I1 it`>
Отсчетное назначение	<`*it`>		Преобразуется в<`T`>.
Отсчетное назначение	<`*it = t`>	<`I1`>Неподвижно.
Доступ к члену	<`it->m`>	<`T`>— тип, для которого<`t.m`>определено.
Прирост	<`++ it`>		<`I1 &`>
Постприрост	<`it ++`>		<`I1`>
Предварительное определение	<`-- it`>		<`I1 &`>
Постдекрет	<`it --`>		<`I1`>
Индекс Row	<`it.index1 ()`>		<`C::size_type`>
Индекс столбца	<`it.index2 ()`>		<`C::size_type`>
Колонна / Колонна начинается	<`it.begin ()`>		<`I2`>
Окончание колонны / Colun End	<`it.end ()`>		<`I2`>
Обратный ряд / Колонна начинается	<`it.rbegin ()`>		<`reverse_iterator<I2>`>
Обратный Row/Column End	<`it.rend ()`>		<`reverse_iterator<I2>`>

Expression Semantics

Name	Expression	Precondition	Semantics	Postcondition
Разработчик Default	<`I1 it`>			<`it`>является единственным.
Отсчетное назначение	<`*it`>	<`it`>Недопустимо.
Отсчетное назначение	<`*it = t`>	Так же, как и<`*it`>.		<`*it`>является копией п.
Доступ к члену	<`it->m`>	<`it`>Недопустимо.	эквивалентно<`(*it).m`>
Прирост	<`++ it`>	<`it`>Недопустимо.	<`it`>модифицируется для указания следующего элемента столбца/ряда, т.е. для итераторов столбцов удерживает <`it.index1 () < (++ it).index1 ()`>и <`it.index2 () == (++ it).index2 ()`>, для итераторов строк удерживает <`it.index1 () == (++ it).index1 ()`>и <`it.index2 () < (++ it).index2 ()`>.	<`it`>является прелюдией или концом.<`&it == &++ it`> Если<`it1 == it2`>, тогда<`++ it1 == ++ it2`>.
Постприрост	<`it ++`>	Так же, как и<`++ it`>.	Эквивалентно <`{ I1 itt = it; ++ it; return itt; }`>	<`it`>является сносным или прошедшим концом.
Предварительное определение	<`-- it`>	<`it`>является сносным или прошедшим концом. There exists a dereferenceable iterator `itt` such that `it == ++ itt`.	<`it`>изменяется, чтобы указать на предыдущий элемент столбца/ряда, т.е. для итераторов столбцов удерживает <`it.index1 () > (-- it).index1 ()`>и <`it.index2 () == (-- it).index2 ()`>, для итераторов строк удерживает <`it.index1 () == (-- it).index1 ()`>и <`it.index2 () > (-- it).index2 ()`>.	<`it`>Недопустимо. `&it = &-- it`. If `it1 == it2`, then `-- it1 == -- it2`.
Постдекрет	<`it --`>	То же самое, что и<`it`>.	Эквивалентно <`{ I1 itt = it; -- it; return itt; }`>	<`it`>Недопустимо.
Индекс Row	<`it.index1 ()`>	Если<`it`>является итератором, то<`it`>должен быть уважительным.	<`it.index1 () >= 0`>и <`it.index1 () < it () .size1 ()`>	Если<`it1 == it2`>, , то<`it1.index1 () == 12.index1 ()`>. Если<`it1`>,<`it2`>являются рядовыми итераторами с<`it1 == it2`>, , то<`it1.index1 () < (++ it2`>.<`index1 ()`>. и<`it1.index1 () > (-- it2`>.<`index1 ()`>.
Индекс столбца	<`it.index2 ()`>	Если<`it`>является итератором колонки, то<`it`>должен быть уважительным.	<`it.index2 () >= 0`>и <`it.index2 () < it () .size2 ()`>	Если<`it1 == it2`>, , то<`it1.index2 () == it2`>.<`index2 ()`>. Если<`it1`>,<`it2`>итераторы колонок с<`it1 == i12`>, , то<`it1.index2 () < (++ it2`>.<`index2 ()`>. конец<`it1.index2 () > (-- it2`>.<`index2 ()`>.
Колонна / Колонна начинается	<`it.begin ()`>	<`it`>Недопустимо.	Если<`it`>является итератором колонки, то<`it2 = it.begin ()`>является итератором колонки с<`it2.index1 () == it.index1 ()`>. Если<`it`>является итератором колонки, то<`it2 = it.begin ()`>является итератором колонки с<`it2.index2 () == it.index2 ()`>.
Окончание колонны / Colun End	<`it.end ()`>	<`it`>Недопустимо.	Если<`it`>является итератором колонки, то<`it2 = it.end ()`>является итератором колонки с<`it2.index1 () == it.index1 ()`>. Если<`it`>является итератором колонки, то<`it2 = it.end ()`>является итератором колонки с<`it2.index2 () == it.index2 ()`>.
Обратный ряд / Колонна начинается	<`it.rbegin ()`>	<`it`>Недопустимо.	Это эквивалентно<`reverse_iterator<I2> (it.end ())`>.
Обратный Row/Column End	<`it.rend ()`>	<`it`>Недопустимо.	Это эквивалентно<`reverse_iterator<I2> (it.begin ())`>.

Complexity guarantees

Сложность операций на индексированных двунаправленных колонках/рядовых итераторах гарантированно логарифмическая в зависимости от размера контейнера. Сложность одного итератора (в зависимости от компоновки хранилища) может быть увеличена до амортизированного постоянного времени. Сложность другого итератора (в зависимости от компоновки хранилища и контейнера) может быть увеличена до амортизированного постоянного времени для первой строки/первой колонки соответственно.

Invariants

Идентичность	<`it1 == it2`>Если и только если<`&it1 == &it2`>.
Симметрия приращения и декреции	Если же<`it`>— неуместно, то<`++ it; --it;`>— нулевая операция.<`-- it; ++ it;`>— это нулевая операция.
Связь между индексом итератора и оператором контейнерных элементов	Если<`it`>является уважительным,<`*it == it () (it.index1 (), it.index2 ())`>
Связь между столбцом / началом строки и индексом итератора	Если<`it`>является итератором колонки и<`it2 = it.begin ()`>, то<`it2.index2 () < it2t.index2 ()`>для всех<`it2t`>с<`it2t () == it2 ()`>и<`it2t ().index1 () == it2 ().index1 ()`>. Если<`it`>является итератором рядов и<`it2 = it.begin ()`>, то<`it2.index1 () < it2t.index1 ()`>для всех<`it2t`>с<`it2t () == it2 ()`>и<`it2t ().index2 () == it2 ().index2 ()`>.
Связь между столбцом и концом строки и индексом итератора	Если<`it`>является итератором колонки и<`it2 = it.end ()`>, то<`it2.index2 () > it2t.index2 ()`>для всех<`it2t`>с<`it2t () == it2 ()`>и<`it2t ().index1 () == it2 ().index1 ()`>. Если<`it`>является итератором рядов и<`it2 = it.end ()`>, то<`it2.index1 () > it2t.index1 ()`>для всех<`it2t`>с<`it2t () == it2 ()`>и<`it2t ().index2 () == it2 ().index2 ()`>.

Models

sparse_matrix::iterator1
sparse_matrix::iterator2

Indexed Random Access Column/Row Iterator

Description

Indexed Random Access Column/Row Iterator - это итератор контейнера, который может быть удален, увеличен, уменьшен и нести информацию об индексе.

Refinement of

Индексированная двунаправленная колонна / рядовой итератор.

Associated types

Тип значения	Тип значения, полученного путем отсчета индексированной колонки случайного доступа / итератора строки
Тип контейнера	Тип контейнера, в который указывает индексированная колонка случайного доступа / рядовой итератор.

Notation

<`I`>	Тип, который является моделью индексированной случайной колонки доступа / строкового итератора
<`T`>	Тип величины<`I`>
<`C`>	Тип контейнера<`I`>
<`it`><`itt, it1`><`it2`>	Объекты типа<`I`>
<`t`>	Объект типа<`T`>
<`c`>	Объект типа<`C`>

Definitions

Valid expressions

В дополнение к выражениям, определенным дляIndexed Bidirectional Column/Row Iterator, следующие выражения должны быть действительными.

Name	Expression	Type requirements	Return type
Движение вперед	<`it += n`>		<`I &`>
Добавление итератора	<`it + n`>		<`I`>
Движение назад	<`i -= n`>		<`I &`>
Вычитание итератора	<`it - n`>		<`I`>
Разница	<`it1 - it2`>		<`C::difference_type`>
Оператор элемента	<`it [n]`>		Преобразуется в<`T`>.
Задание элементов	<`it [n] = t`>	<`I`>является мутабельным	Преобразуется в<`T`>.

Expression Semantics

Семантика выражения определяется только там, где она отличается или не определена вIndexed Bidirectional Column/Row Iterator.

Name	Expression	Precondition	Semantics	Postcondition
Движение вперед	<`it += n`>	Включая сам<`it`>, должны быть<`n`>реферативные или прошлые конечные итераторы, следующие или предшествующие<`it`>, в зависимости от того, является ли<`n`>положительным или отрицательным.	Если<`n > 0`>, то<`n`><`++ it`><`n`>. Если<`n < 0`>, то<`-- it`><`n`>раз. Если<`n == 0`>, то это нулевая операция.	<`it`>является сносным или прошедшим концом.
Добавление итератора	<`it + n`>	Так же, как и<`i += n`>.	эквивалентно <`{ I itt = it; return itt += n; }`>	Результат является достойным уважения или прошедшим концом.
Движение назад	<`it -= n`>	Включая сам<`it`>, должны быть<`n`>сносные или прошлые конечные итераторы, предшествующие или следующие<`it`>, в зависимости от того, является ли<`n`>положительным или отрицательным.	Это эквивалентно<`it += (-n)`>.	<`it`>является сносным или прошедшим концом.
Вычитание итератора	<`it - n`>	Так же, как и<`i -= n`>.	эквивалентно <`{ I itt = it; return itt -= n; }`>	Результат является достойным уважения или прошедшим концом.
Разница	<`it1 - it2`>	Или<`it1`>достижимо от<`it2`>, или<`it2`>достижимо от<`it1`>, или оба.	Возвращает число<`n`>так, что<`it1 == it2 + n`>
Оператор элемента	<`it [n]`>	<`it + n`>существует и заслуживает уважения.	эквивалентно<`*(it + n)`>
Задание элементов	<`i[n] = t`>	Так же, как и<`it [n]`>.	эквивалентно<`*(it + n) = t`>

Complexity guarantees

Invariants

Симметрия сложения и вычитания	Если<`it + n`>хорошо определено, то<`it += n; it -= n;`>и<`(it + n) - n`>являются нулевыми операциями. Если<`it - n`>хорошо определено, то<`it -= n; it += n;`>и<`(it - n) + n`>являются нулевыми операциями.
Отношение между расстоянием и сложением	Если<`it1 - it2`>хорошо определен, то<`it1 == it2 + (it1 - it2)`>.
Достижимость и расстояние	Если<`it1`>достижимо от<`it2`>, то<`it1 - it2 >= 0`>.

Models

matrix::iterator1
matrix::iterator2

Авторское право (©) 2000-2002 Йорг Уолтер, Матиас Кох
На использование, модификацию и распространение распространяется лицензия Boost Software License, Version 1.0. (См. сопроводительный файл LICENSE_1_0.txt или копию по адресу) http://www.boost.org/LICENSE_1_0.txt.

Статья Iterator Concepts раздела может быть полезна для разработчиков на c++ и boost.

Материалы статей собраны из открытых источников, владелец сайта не претендует на авторство. Там где авторство установить не удалось, материал подаётся без имени автора. В случае если Вы считаете, что Ваши права нарушены, пожалуйста, свяжитесь с владельцем сайта.

:: Главная :: ::

Время компиляции файла: 2024-08-30 11:47:00
2025-05-19 20:03:06/0.033547163009644/1