27 Iterators library [iterators]

Итераторы - это обобщение указателей, которые позволяют программе на C ++ единообразно работать с различными структурами данных (контейнерами). Чтобы иметь возможность создавать шаблонные алгоритмы, которые правильно и эффективно работают с различными типами структур данных, библиотека формализует не только интерфейсы, но также семантику и предположения о сложности итераторов. Итератор ввода i поддерживает выражение *i, в результате чего получается значение некоторого типа объекта T, называемого value type итератором. Итератор выводаi имеет непустой набор типов, относящихся writable к итератору; для каждого такого типа допустимоTвыражение,*i = oгдеo - значение типаT. Итератор, i для которого выражение (*i).m четко определено, поддерживает выражение i->m с той же семантикой, что и (*i).m. Для каждого типа итератора, X для которого определено равенство, существует соответствующий целочисленный тип соdifference type знаком, называемый итератором.

Поскольку итераторы являются абстракцией указателей, их семантика является обобщением большей части семантики указателей в C ++. Это гарантирует, что каждый шаблон функции, который принимает итераторы, также работает с обычными указателями. Настоящий стандарт определяет пять категорий итераторов, в соответствии с операциями , определенными на них: input iterators, output iterators, forward iterators, bidirectional iterators и random access iterators, как показано в таблице93.

Прямые итераторы удовлетворяют всем требованиям итераторов ввода и могут использоваться всякий раз, когда указан итератор ввода; Двунаправленные итераторы также удовлетворяют всем требованиям прямых итераторов и могут использоваться всякий раз, когда указан прямой итератор; Итераторы произвольного доступа также удовлетворяют всем требованиям двунаправленных итераторов и могут использоваться всякий раз, когда указан двунаправленный итератор.

Вызываются итераторы, которые дополнительно удовлетворяют требованиям итераторов выводаmutable iterators. Неизменяемые итераторы называютсяconstant iterators.

В дополнение к требованиям этого подпункта для типа итератора должна быть предусмотрена вложенность, typedef-names указанная в[iterator.traits]. [  Note: Либо тип итератора должен предоставлять их typedef-names напрямую (в этом случае получать ихiterator_­traits автоматически), либоiterator_­traits специализация должна предоставлять их. ] — end note 

Итераторы, которые дополнительно удовлетворяют требованию о том, что для целочисленных значенийn и значений итераторов с возможностью разыменованияa и(a + n), *(a + n) эквивалентно*(addressof(*a) + n), вызываютсяcontiguous iterators. [  Note: Например, тип «указатель наint» является непрерывным итератором, ноreverse_­iterator<int *> это не так. Для допустимого диапазона итератора[a$,$b) с возможностью разыменованияaсоответствующий диапазон, обозначенный указателями, равен [addressof(*a)$,$addressof(*a) + (b - a)); b не может быть разыменован. ] — end note 

Так же, как обычный указатель на массив гарантирует, что существует значение указателя, указывающее за последним элементом массива, так и для любого типа итератора существует значение итератора, указывающее за последним элементом соответствующей последовательности. Эти значения называются past-the-end значениями. Значения итератора ,i для которых выражение *i определенно называется dereferenceable. Библиотека никогда не предполагает, что последние значения могут быть разыменованы. Итераторы также могут иметь особые значения, не связанные с какой-либо последовательностью. [  Example: После объявления неинициализированного указателя x (как в случае int* x;) x всегда следует предполагать, что он имеет единственное значение указателя. ] Результаты большинства выражений не определены для сингулярных значений; единственными исключениями являются уничтожение итератора, содержащего сингулярное значение, присвоение неособого значения итератору, содержащему сингулярное значение, и, для итераторов, удовлетворяющих требованиям, использование итератора с инициализированным значением в качестве источника копирование или перемещение. [ Эта гарантия не предоставляется для инициализации по умолчанию, хотя различие имеет значение только для типов с тривиальными конструкторами по умолчанию, такими как указатели или агрегаты, содержащие указатели. ] В этих случаях единственное значение перезаписывается так же, как и любое другое значение. Разыменяемые значения всегда не единственные. — end example DefaultConstructible  Note:  — end note 

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

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

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

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

invalid Итератора является итератор , который может быть вырожденной.261

В следующих разделах, a и b величины означают типа X илиconst X, difference_­type иreference относятся к типам ,iterator_­traits<X>​::​difference_­type и iterator_­traits<X>​::​reference, соответственно, n обозначает значение difference_­type, u, tmpи цветом,m обозначают идентификаторы, r обозначает значение X&, t обозначает значение типа значения T, o обозначает значение некоторого типа который доступен для записи итератору вывода. [  Note: Для типа итератораX должен быть экземплярiterator_­traits<X>. ] — end note 

ВIterator требования легли в основу концепции итератора систематики; каждый итератор удовлетворяетIterator требованиям. Этот набор требований определяет операции для разыменования и увеличения итератора. Большинство алгоритмов потребует дополнительных действий для read илиwrite значения, или обеспечить более богатый набор итератор движений ([forward.iterators], [bidirectional.iterators],[random.access.iterators]).

ТипX удовлетворяетIterator требованиям, если:

• (2.1)

  X удовлетворяетCopyConstructible,CopyAssignableи Destructible требования ([utility.arg.requirements]) и lvalues типаX являютсяswappable, и

• (2.2)

  выражения в таблице94 действительны и имеют указанную семантику.

Класс или указатель типа X удовлетворяет требования входного итератора для типа значения ,T если X удовлетворяютIterator и EqualityComparable требования и выражение , приведенные в таблице95 , действительны и имеют указанную семантику.

В Таблице95этот термин the domain of == используется в обычном математическом смысле для обозначения набора значений, для которых == (требуется) определение. Этот набор может меняться со временем. Каждый алгоритм предъявляет дополнительные требования к области == значений используемых итераторов. Эти требования могут быть выведены из использования алгоритма== и!=. [  Example: Вызовfind(a,b,x) определяется только в том случае, если значениеa имеет свойство,p определенное следующим образом: b имеет свойство,p а значениеi имеет свойствоp if (*i==x) или if (*i!=x и ++i имеет свойство p). ] — end example 

[  Note: Для итераторов ввода a == b не означает ++a == ++b. (Равенство не гарантирует свойство подстановки или ссылочную прозрачность.) Алгоритмы на итераторах ввода никогда не должны пытаться пройти через один и тот же итератор дважды. Это должны быть single pass алгоритмы. Тип значенияT не обязательно должен бытьCopyAssignable типом. Эти алгоритмы могут использоваться с istreams в качестве источника входных данных через istream_­iterator шаблон класса. ] — end note 

Тип класса или указателя X удовлетворяет требованиям итератора вывода, еслиX удовлетворяетIterator требованиям, а выражения в таблице96 действительны и имеют указанную семантику.

[  Note: Единственное допустимое использование - operator* находится в левой части оператора присваивания. Assignment through the same value of the iterator happens only once. Алгоритмы на итераторах вывода никогда не должны пытаться дважды пройти через один и тот же итератор. Это должны быть single pass алгоритмы. Равенство и неравенство нельзя определить. Алгоритмы, которые принимают итераторы вывода, могут использоваться с ostreams в качестве места назначения для размещения данных через ostream_­iterator класс, а также с итераторами вставки и указателями вставки. ] — end note 

Тип класса или указателя X удовлетворяет требованиям прямого итератора, если

• (1.1)

  X удовлетворяет требованиямinput iterator,

• (1.2)

  X удовлетворяетDefaultConstructible requirements,

• (1.3)

  еслиX изменяемый итератор,reference это ссылка наT; еслиX постоянный итератор,reference это ссылка наconst T,

• (1.4)

  выражения в таблице97 действительны и имеют указанную семантику, и

• (1.5)

  объекты типаX предлагают многопроходную гарантию, описанную ниже.

Область== прямых итераторов - это область итераторов той же базовой последовательности. Однако итераторы с инициализацией значения могут сравниваться и должны сравниваться наравне с другими итераторами с инициализацией значения того же типа. [  Note: Итераторы с инициализацией значения ведут себя так, как если бы они ссылались на конец одной и той же пустой последовательности. ] — end note 

Два разыменяемых итератораa иb типаX предлагают multi-pass guarantee if:

• (3.1)

  a == b подразумевает++a == ++b и

• (3.2)

  X является типом указателя или выражение (void)++X(a), *a эквивалентно выражению*a.

[  Note: Требование, которое a == b подразумевает ++a == ++b (что неверно для итераторов ввода и вывода) и снятие ограничений на количество назначений через изменяемый итератор (которое применяется к итераторам вывода), позволяет использовать многопроходные однонаправленные алгоритмы с прямыми итераторами. ] — end note 

Еслиa иb равны, то либоa и, либоb разыменуемы, либо ни один из них не разыменован.

Еслиa иb оба разыменованы, тоa == b тогда и только тогда, когда *a и*b привязаны к одному и тому же объекту.

Тип класса или указателя X удовлетворяет требованиям двунаправленного итератора, если, помимо удовлетворения требований для прямых итераторов, допустимы следующие выражения, как показано в таблице98.

[  Note: Двунаправленные итераторы позволяют алгоритмам перемещать итераторы вперед и назад. ] — end note 

Тип класса или указателя X удовлетворяет требованиям итератора с произвольным доступом, если, помимо удовлетворения требований для двунаправленных итераторов, допустимы следующие выражения, как показано в таблице99.