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.

Чтобы реализовать алгоритмы только в терминах итераторов, часто необходимо определить типы значений и различий, которые соответствуют конкретному типу итератора. Соответственно, требуется, чтобы if Iterator - тип итератора, типы

iterator_traits<Iterator>::difference_type
iterator_traits<Iterator>::value_type
iterator_traits<Iterator>::iterator_category

быть определенным как тип различия итератора, тип значения и категория итератора соответственно. Кроме того, типы

iterator_traits<Iterator>::reference
iterator_traits<Iterator>::pointer

должен быть определен как тип ссылки и указателя итератора, то есть для объекта итератора a, тот же тип, что и тип *a и a->, соответственно. В случае итератора вывода типы

iterator_traits<Iterator>::difference_type
iterator_traits<Iterator>::value_type
iterator_traits<Iterator>::reference
iterator_traits<Iterator>::pointer

можно определить как void.

Если Iterator есть действительные ([temp.deduct]) типы элементов difference_­type, value_­type, pointer, reference, и iterator_­category, iterator_­traits<Iterator> должны иметь следующие в качестве публично доступных членов:

  using difference_type   = typename Iterator::difference_type;
  using value_type        = typename Iterator::value_type;
  using pointer           = typename Iterator::pointer;
  using reference         = typename Iterator::reference;
  using iterator_category = typename Iterator::iterator_category;

В противном случае не iterator_­traits<Iterator> будет иметь членов ни с одним из вышеуказанных имен.

Он специализируется на указателях как

namespace std {
  template<class T> struct iterator_traits<T*> {
    using difference_type   = ptrdiff_t;
    using value_type        = T;
    using pointer           = T*;
    using reference         = T&;
    using iterator_category = random_access_iterator_tag;
  };
}

а для указателей на const как

namespace std {
  template<class T> struct iterator_traits<const T*> {
    using difference_type   = ptrdiff_t;
    using value_type        = T;
    using pointer           = const T*;
    using reference         = const T&;
    using iterator_category = random_access_iterator_tag;
  };
}

[  Example: Чтобы реализовать универсальную reverse функцию, программа на C ++ может делать следующее:

template <class BidirectionalIterator>
void reverse(BidirectionalIterator first, BidirectionalIterator last) {
  typename iterator_traits<BidirectionalIterator>::difference_type n =
    distance(first, last);
  --n;
  while(n > 0) {
    typename iterator_traits<BidirectionalIterator>::value_type
     tmp = *first;
    *first++ = *--last;
    *last = tmp;
    n -= 2;
  }
}

 — end example ]

Часто бывает желательно, чтобы специализация шаблона функции определяла наиболее конкретную категорию аргумента итератора, чтобы функция могла выбрать наиболее эффективный алгоритм во время компиляции. Чтобы облегчить это, в библиотеке представлены category tag классы, которые используются в качестве тегов времени компиляции для выбора алгоритма. Они являются input_­iterator_­tag, output_­iterator_­tag, forward_­iterator_­tag, bidirectional_­iterator_­tag и random_­access_­iterator_­tag. Для каждого итератора типа Iterator, iterator_­traits<Iterator>​::​iterator_­category должны быть определены наиболее конкретной категории тег , который описывает поведение итератора.

namespace std {
  struct input_iterator_tag { };
  struct output_iterator_tag { };
  struct forward_iterator_tag: public input_iterator_tag { };
  struct bidirectional_iterator_tag: public forward_iterator_tag { };
  struct random_access_iterator_tag: public bidirectional_iterator_tag { };
}

[  Example: Для программного итератора BinaryTreeIteratorон может быть включен в категорию двунаправленных итераторов путем специализации iterator_­traits шаблона:

template<class T> struct iterator_traits<BinaryTreeIterator<T>> {
  using iterator_category = bidirectional_iterator_tag;
  using difference_type   = ptrdiff_t;
  using value_type        = T;
  using pointer           = T*;
  using reference         = T&;
};

 — end example ]

[  Example: Если evolve() это хорошо определено для двунаправленных итераторов, но может быть реализовано более эффективно для итераторов с произвольным доступом, то реализация выглядит следующим образом:

template <class BidirectionalIterator>
inline void
evolve(BidirectionalIterator first, BidirectionalIterator last) {
  evolve(first, last,
    typename iterator_traits<BidirectionalIterator>::iterator_category());
}

template <class BidirectionalIterator>
void evolve(BidirectionalIterator first, BidirectionalIterator last,
  bidirectional_iterator_tag) {
  // more generic, but less efficient algorithm
}

template <class RandomAccessIterator>
void evolve(RandomAccessIterator first, RandomAccessIterator last,
  random_access_iterator_tag) {
  // more efficient, but less generic algorithm
}

 — end example ]

Поскольку только итераторы произвольного доступа обеспечивают + и - оператор, библиотека предоставляет два шаблона функции advance и distance. Эти шаблоны функций используют + и - для итераторов произвольного доступа (и, следовательно, являются для них постоянным временем); для входных, прямых и двунаправленных итераторов они используют ++ для реализации линейного времени.

Шаблон класса reverse_­iterator - это адаптер итератора, который выполняет итерацию от конца последовательности, определенной его базовым итератором, до начала этой последовательности. Фундаментальное соотношение между обратным итератором и его соответствующим итератор i устанавливается идентичностью: &*(reverse_­iterator(i)) == &*(i - 1).

Чтобы можно было обрабатывать вставку так же, как запись в массив,insert iteratorsв библиотеке предусмотрен специальный вид адаптеров итератора, называемый . С обычными классами итераторов

while (first != last) *result++ = *first++;

вызывает [first, last) копирование диапазона в диапазон, начинающийся с результата. Тот же код, result который является итератором вставки, вставит соответствующие элементы в контейнер. Это устройство позволяет всем алгоритмам копирования в библиотеке работать в режиме, insert mode а не в regular overwrite режиме.

Итератор вставки создается из контейнера и, возможно, одного из его итераторов, указывающих на место вставки, если он не находится ни в начале, ни в конце контейнера. Итераторы вставки удовлетворяют требованиям итераторов вывода. operator* возвращает сам итератор вставки. Назначение operator=(const T& x) определяется на итераторах вставки, чтобы разрешить запись в них, оно вставляется x прямо перед тем местом, куда указывает итератор вставки. Другими словами, итератор вставки подобен курсору, указывающему на контейнер, в котором происходит вставка. back_­insert_­iterator вставляет элементы в конец контейнера, front_­insert_­iterator вставляет элементы в начало контейнера и insert_­iterator вставляет элементы, на которые указывает итератор в контейнере. back_­inserter, front_­inserterИ inserter три функции , делающие вставки итераторы из контейнера.

Шаблон класса move_­iterator - это адаптер итератора с таким же поведением, что и базовый итератор, за исключением того, что его оператор косвенного обращения неявно преобразует значение, возвращаемое оператором косвенного обращения базового итератора, в rvalue. Некоторые общие алгоритмы можно вызывать с итераторами перемещения, чтобы заменить копирование перемещением.

[ Example:

list<string> s;
// populate the list s
vector<string> v1(s.begin(), s.end());          // copies strings into v1
vector<string> v2(make_move_iterator(s.begin()),
                  make_move_iterator(s.end())); // moves strings into v2

 — end example ]

Шаблон класса istream_­iterator - это объект, input iterator который считывает (использует operator>>) последовательные элементы из входного потока, для которого он был создан. После создания и каждый раз ++ использования итератор считывает и сохраняет значение T. Если итератору не удается прочитать и сохранить значение T (fail() в возвращаемом потоке true), итератор становится равным end-of-stream значению итератора. Конструктор без аргументов istream_­iterator() всегда создает объект итератора ввода конца потока, который является единственным допустимым итератором, который может использоваться для условия окончания. Результат operator* итератора в конце потока не определен. Для любого другого итератораconst T& возвращается значение a . Результат operator-> итератора в конце потока не определен. Для любого другого итератораconst T* возвращается значение a . Поведение программы, которая применяется operator++() к итератору конца потока, не определено. Невозможно хранить что-либо в итераторах istream. Тип T должен соответствовать DefaultConstructible, CopyConstructibleи CopyAssignable требованиям.

Два итератора конца потока всегда равны. Итератор конца потока не равен итератору конца потока. Два итератора без конца потока равны, если они построены из одного и того же потока.

namespace std {
  template <class T, class charT = char, class traits = char_traits<charT>,
      class Distance = ptrdiff_t>
  class istream_iterator {
  public:
    using iterator_category = input_iterator_tag;
    using value_type        = T;
    using difference_type   = Distance;
    using pointer           = const T*;
    using reference         = const T&;
    using char_type         = charT;
    using traits_type       = traits;
    using istream_type      = basic_istream<charT,traits>;

    constexpr istream_iterator();
    istream_iterator(istream_type& s);
    istream_iterator(const istream_iterator& x) = default;
    ~istream_iterator() = default;

    const T& operator*() const;
    const T* operator->() const;
    istream_iterator& operator++();
    istream_iterator  operator++(int);
  private:
    basic_istream<charT,traits>* in_stream; // exposition only
    T value;                                // exposition only
  };

  template <class T, class charT, class traits, class Distance>
    bool operator==(const istream_iterator<T,charT,traits,Distance>& x,
            const istream_iterator<T,charT,traits,Distance>& y);
  template <class T, class charT, class traits, class Distance>
    bool operator!=(const istream_iterator<T,charT,traits,Distance>& x,
            const istream_iterator<T,charT,traits,Distance>& y);
}

ostream_­iterator записывает (использует operator<<) последовательные элементы в выходной поток, из которого он был построен. Если он был построен с charT* аргументом конструктора, эта строка, называемая a delimiter string, записывается в поток после каждой записи T . Невозможно получить значение из итератора вывода. Его единственное использование - как итератор вывода в таких ситуациях, как

while (first != last)
  *result++ = *first++;

ostream_­iterator определяется как:

namespace std {
  template <class T, class charT = char, class traits = char_traits<charT>>
  class ostream_iterator {
  public:
    using iterator_category = output_iterator_tag;
    using value_type        = void;
    using difference_type   = void;
    using pointer           = void;
    using reference         = void;
    using char_type         = charT;
    using traits_type       = traits;
    using ostream_type      = basic_ostream<charT,traits>;

    ostream_iterator(ostream_type& s);
    ostream_iterator(ostream_type& s, const charT* delimiter);
    ostream_iterator(const ostream_iterator& x);
    ~ostream_iterator();
    ostream_iterator& operator=(const T& value);

    ostream_iterator& operator*();
    ostream_iterator& operator++();
    ostream_iterator& operator++(int);
  private:
    basic_ostream<charT,traits>* out_stream;  // exposition only
    const charT* delim;                       // exposition only
  };
}

Шаблон класса istreambuf_­iterator определяет объект, input iterator который последовательно читает characters из streambuf, для которого он был создан. operator* обеспечивает доступ к текущему входному символу, если таковой имеется. Каждый раз при operator++ оценке итератор переходит к следующему входному символу. Если достигается конец потока (streambuf_­type​::​sgetc() возвращается traits​::​eof()), итератор становится равным end-of-stream значению итератора. Конструктор по умолчанию istreambuf_­iterator() и конструктор istreambuf_­iterator(0) создают объект-итератор конца потока, подходящий для использования в качестве конца диапазона. Все специализации istreambuf_­iterator должны иметь тривиальный конструктор копирования, конструктор по constexpr умолчанию и тривиальный деструктор.

Результат operator*() итератора конца потока не определен. Для любого другого значения итератора char_­type возвращается значение. Невозможно присвоить символ через итератор ввода.

namespace std {
  template<class charT, class traits = char_traits<charT>>
  class istreambuf_iterator {
  public:
    using iterator_category = input_iterator_tag;
    using value_type        = charT;
    using difference_type   = typename traits::off_type;
    using pointer           = unspecified;
    using reference         = charT;
    using char_type         = charT;
    using traits_type       = traits;
    using int_type          = typename traits::int_type;
    using streambuf_type    = basic_streambuf<charT,traits>;
    using istream_type      = basic_istream<charT,traits>;

    class proxy;                          // exposition only

    constexpr istreambuf_iterator() noexcept;
    istreambuf_iterator(const istreambuf_iterator&) noexcept = default;
    ~istreambuf_iterator() = default;
    istreambuf_iterator(istream_type& s) noexcept;
    istreambuf_iterator(streambuf_type* s) noexcept;
    istreambuf_iterator(const proxy& p) noexcept;
    charT operator*() const;
    istreambuf_iterator& operator++();
    proxy operator++(int);
    bool equal(const istreambuf_iterator& b) const;
  private:
    streambuf_type* sbuf_;                // exposition only
  };

  template <class charT, class traits>
    bool operator==(const istreambuf_iterator<charT,traits>& a,
            const istreambuf_iterator<charT,traits>& b);
  template <class charT, class traits>
    bool operator!=(const istreambuf_iterator<charT,traits>& a,
            const istreambuf_iterator<charT,traits>& b);
}

Шаблон класса ostreambuf_­iterator последовательно записывает characters в выходной поток, из которого он был построен. Невозможно получить символьное значение из итератора вывода.