C++
итераторы

C Итераторы (указатели)

// This creates an array with 5 values.
const int array[] = { 1, 2, 3, 4, 5 };

#ifdef BEFORE_CPP11

// You can use `sizeof` to determine how many elements are in an array.
const int* first = array;
const int* afterLast = first + sizeof(array) / sizeof(array[0]);

// Then you can iterate over the array by incrementing a pointer until
// it reaches past the end of our array.
for (const int* i = first; i < afterLast; ++i) {
    std::cout << *i << std::endl;
}

#else

// With C++11, you can let the STL compute the start and end iterators:
for (auto i = std::begin(array); i != std::end(array); ++i) {
    std::cout << *i << std::endl;
}

#endif

Этот код выводит числа от 1 до 5, по одному на каждую строку:

1
2
3
4
5

Нарушение этого

const int array[] = { 1, 2, 3, 4, 5 };

Эта строка создает новый целочисленный массив с 5 значениями. C - это просто указатели на память, где каждое значение хранится вместе в непрерывном блоке.

const int* first = array;
const int* afterLast = first + sizeof(array) / sizeof(array[0]);

Эти строки создают два указателя. Первому указателю присваивается значение указателя массива, который является адресом первого элемента в массиве. Оператор sizeof используемый в массиве C, возвращает размер массива в байтах. Разделенный на размер элемента, это дает количество элементов в массиве. Мы можем использовать это, чтобы найти адрес блока после массива.

for (const int* i = first; i < afterLast; ++i) {

Здесь мы создаем указатель, который мы будем использовать в качестве итератора. Он инициализируется адресом первого элемента, который мы хотим перебрать, и мы будем продолжать итерацию, пока i меньше, чем afterLast , что означает, что пока i afterLast на адрес внутри array .

    std::cout << *i << std::endl;

Наконец, в цикле мы можем получить доступ к значению, на которое указывает наш итератор i , разыменовывая его. Здесь оператор разыменования * возвращает значение по адресу в i .

обзор

Итераторы - это позиции

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

A B C

Последовательность содержит три элемента и четыре позиции

+---+---+---+---+
| A | B | C |   |
+---+---+---+---+

Элементы - это вещи в последовательности. Позиции - это места, где значительная операция может произойти с последовательностью. Например, один вставляет в позицию, до или после элемента A, а не в элемент. Даже удаление элемента ( erase(A) ) выполняется сначала, найдя его положение, а затем удаляя его.

От итераторов до значений

Чтобы преобразовать из позиции в значение, итератор разыменован :

auto my_iterator = my_vector.begin(); // position
auto my_value = *my_iterator; // value

Можно рассматривать итератор как разыменование значения, на которое он ссылается в последовательности. Это особенно полезно для понимания того, почему вы никогда не должны разыгрывать итератор end() в последовательности:

+---+---+---+---+
| A | B | C |   |
+---+---+---+---+
  ↑           ↑
  |           +-- An iterator here has no value. Do not dereference it!
  +-------------- An iterator here dereferences to the value A.

Во всех последовательностях и контейнерах, найденных в стандартной библиотеке C ++, begin() вернет итератор в первую позицию, а end() вернет итератор в прошлое ( не последнюю позицию!). Следовательно, имена этих итераторов в алгоритмах часто помечены как first и last :

+---+---+---+---+
| A | B | C |   |
+---+---+---+---+
  ↑           ↑
  |           |
  +- first    +- last

Также возможно получить итератор для любой последовательности , потому что даже пустая последовательность содержит по крайней мере одну позицию:

+---+
|   |
+---+

В пустой последовательности begin() и end() будут одинаковой позиции, и ни одно из них не может быть разыменовано:

+---+
|   |
+---+
  ↑
  |
  +- empty_sequence.begin()
  |
  +- empty_sequence.end()

Альтернативная визуализация итераторов заключается в том, что они отмечают позиции между элементами:

+---+---+---+
| A | B | C |
+---+---+---+
↑   ^   ^   ↑
|           |
+- first    +- last

и разыменование итератора возвращает ссылку на элемент, идущий после итератора. В некоторых ситуациях, когда это мнение особенно полезно,

• insert операции будут вставлять элементы в позицию , указанную итератора,
• операции erase возвращают итератор, соответствующий той же позиции, что и тот,
• итератор и его соответствующий обратный итератор расположены в одной и той же позиции между элементами

Недействительные итераторы

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

std::vector<int>::iterator first;
{
    std::vector<int> foo;
    first = foo.begin(); // first is now valid
} // foo falls out of scope and is destroyed
// At this point first is now invalid

Многие алгоритмы и функции членов последовательности в стандартной библиотеке C ++ имеют правила, определяющие, когда итераторы недействительны. Каждый алгоритм отличается тем, как они обрабатывают (и недействительны) итераторы.

Навигация с итераторами

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

auto first = my_vector.begin();
++first;                                             // advance the iterator 1 position
std::advance(first, 1);                              // advance the iterator 1 position
first = std::next(first);                            // returns iterator to the next element
std::advance(first, -1);                             // advance the iterator 1 position backwards
first = std::next(first, 20);                        // returns iterator to the element 20 position forward
first = std::prev(first, 5);                         // returns iterator to the element 5 position backward
auto dist = std::distance(my_vector.begin(), first); // returns distance between two iterators.

Обратите внимание, что второй аргумент std :: distance должен быть доступен с первого (или, другими словами, first должен быть меньше или равен second ).

Несмотря на то, что вы можете выполнять арифметические операции с итераторами, не все операции определены для всех типов итераторов. a = b + 3; будет работать для Итераторов случайного доступа, но не будет работать для форвардных или двунаправленных итераторов, которые все еще могут быть продвинуты на 3 позиции с чем-то вроде b = a; ++b; ++b; ++b; , Поэтому рекомендуется использовать специальные функции, если вы не уверены, что такое тип итератора (например, в функции шаблона, принимающей итератор).

Концепции итератора

Стандарт C ++ описывает несколько различных концепций итератора. Они группируются в соответствии с тем, как они ведут себя в последовательности, на которую они ссылаются. Если вы знаете концепцию, то итератор моделирует (ведет себя как), вы можете быть уверены в поведении этого итератора независимо от последовательности, к которой он принадлежит . Они часто описываются в порядке от максимального до наименее ограничительного (поскольку следующая концепция итератора на шаг лучше, чем его предшественник):

• Итераторы ввода: могут быть разыменованы только один раз для каждой позиции. Может только продвигаться и только по одной позиции за раз.
• Forward Iterators: Итератор ввода, который можно разыменовать сколько угодно раз.
• Двунаправленные итераторы: передний итератор, который также может перемещаться назад по одной позиции за раз.
• Итераторы случайного доступа: двунаправленный итератор, который может продвигать вперед или назад любое количество позиций за раз.
• Смежные итераторы (начиная с C ++ 17): Итератор с произвольным доступом, который гарантирует, что базовые данные смежны в памяти.

Алгоритмы могут варьироваться в зависимости от концепции, моделируемой итераторами, которые они задают. Например, хотя random_shuffle может быть реализован для форвардных итераторов, может быть предоставлен более эффективный вариант, требующий итераторов с произвольным доступом.

Итераторские черты

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

template<class Iter>
Iter find(Iter first, Iter last, typename std::iterator_traits<Iter>::value_type val)  {
    while (first != last) {
        if (*first == val)
            return first;
        ++first;
    }
    return last;
}

Категория итератора может использоваться для специализации алгоритмов:

template<class BidirIt>
void test(BidirIt a, std::bidirectional_iterator_tag)  {
    std::cout << "Bidirectional iterator is used" << std::endl;
}
 
template<class ForwIt>
void test(ForwIt a, std::forward_iterator_tag)  {
    std::cout << "Forward iterator is used" << std::endl;
}
 
template<class Iter>
void test(Iter a)  {
    test(a, typename std::iterator_traits<Iter>::iterator_category());
}

Категории итераторов - это, в основном, понятия итераторов, за исключением того, что Contiguous Iterators не имеют собственного тега, так как было обнаружено, что он нарушает код.

Обратные итераторы

Если мы хотим итерации назад через список или вектор, мы можем использовать reverse_iterator . Обратный итератор выполнен из двунаправленного или произвольного итератора доступа, который он хранит как элемент, к которому можно получить доступ через base() .

Чтобы rbegin() итерацию назад, используйте rbegin() и rend() как итераторы для конца коллекции и начало коллекции соответственно.

Например, для повторного итерационного использования:

std::vector<int> v{1, 2, 3, 4, 5};
for (std::vector<int>::reverse_iterator it = v.rbegin(); it != v.rend(); ++it)
{
    cout << *it;
} // prints 54321

Обратный итератор может быть преобразован в итератор вперед через функцию-член base() . Связь заключается в том, что обратный итератор ссылается на один элемент за base() итератором:

std::vector<int>::reverse_iterator r = v.rbegin();
std::vector<int>::iterator i = r.base();
assert(&*r == &*(i-1)); // always true if r, (i-1) are dereferenceable
                        // and are not proxy iterators

 +---+---+---+---+---+---+---+
 |   | 1 | 2 | 3 | 4 | 5 |   |
 +---+---+---+---+---+---+---+
   ↑   ↑               ↑   ↑
   |   |               |   |
rend() |         rbegin()  end()
       |                   rbegin().base()
     begin()
     rend().base()

При визуализации, где итераторы отмечают позиции между элементами, связь проще:

  +---+---+---+---+---+
  | 1 | 2 | 3 | 4 | 5 |
  +---+---+---+---+---+
  ↑                   ↑
  |                   |
  |                 end()
  |                 rbegin()
begin()             rbegin().base()
rend()
rend().base()

Векторный Итератор

begin возвращает iterator в первый элемент в контейнере последовательности.

end возвращает iterator в первый элемент за конец.

Если векторный объект является const , то begin и end возвращают const_iterator . Если вы хотите, чтобы const_iterator возвращался, даже если ваш вектор не const , вы можете использовать cbegin и cend .

Пример:

#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = { 1, 2, 3, 4, 5 };  //intialize vector using an initializer_list

    for (std::vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
        std::cout << *it << " ";
    }

    return 0;
}

Выход:

1 2 3 4 5

Итератор карты

Итератор к первому элементу в контейнере.

Если объект карты имеет const-квалификацию, функция возвращает const_iterator . В противном случае он возвращает iterator .

// Create a map and insert some values
std::map<char,int> mymap;
mymap['b'] = 100;
mymap['a'] = 200;
mymap['c'] = 300;

// Iterate over all tuples
for (std::map<char,int>::iterator it = mymap.begin(); it != mymap.end(); ++it)
    std::cout << it->first << " => " << it->second << '\n';

Выход:

a => 200
b => 100
c => 300

Итераторы потока

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

// Data stream. Any number of various whitespace characters will be OK.
std::istringstream istr("1\t 2     3 4");
std::vector<int> v;

// Constructing stream iterators and copying data from stream into vector.
std::copy(
    // Iterator which will read stream data as integers.
    std::istream_iterator<int>(istr),
    // Default constructor produces end-of-stream iterator.
    std::istream_iterator<int>(),
    std::back_inserter(v));

// Print vector contents.
std::copy(v.begin(), v.end(),
    //Will print values to standard output as integers delimeted by " -- ".
    std::ostream_iterator<int>(std::cout, " -- "));

Пример программы будет печатать 1 -- 2 -- 3 -- 4 -- до стандартного вывода.

Напишите свой собственный итератор с поддержкой генератора

Общепринятая модель на других языках имеет функцию, которая создает «поток» объектов и может использовать цикл цикла для его перебора.

Мы можем моделировать это на C ++ как

template<class T>
struct generator_iterator {
  using difference_type=std::ptrdiff_t;
  using value_type=T;
  using pointer=T*;
  using reference=T;
  using iterator_category=std::input_iterator_tag;
  std::optional<T> state;
  std::function< std::optional<T>() > operation;
  // we store the current element in "state" if we have one:
  T operator*() const {
    return *state;
  }
  // to advance, we invoke our operation.  If it returns a nullopt
  // we have reached the end:
  generator_iterator& operator++() {
    state = operation();
    return *this;        
  }
  generator_iterator operator++(int) {
    auto r = *this;
    ++(*this);
    return r;
  }
  // generator iterators are only equal if they are both in the "end" state:
  friend bool operator==( generator_iterator const& lhs, generator_iterator const& rhs ) {
    if (!lhs.state && !rhs.state) return true;
    return false;
  }
  friend bool operator!=( generator_iterator const& lhs, generator_iterator const& rhs ) {
    return !(lhs==rhs);
  }
  // We implicitly construct from a std::function with the right signature:
  generator_iterator( std::function< std::optional<T>() > f ):operation(std::move(f))
  {
    if (operation)
      state = operation();
  }
  // default all special member functions:
  generator_iterator( generator_iterator && ) =default;
  generator_iterator( generator_iterator const& ) =default;
  generator_iterator& operator=( generator_iterator && ) =default;
  generator_iterator& operator=( generator_iterator const& ) =default;
  generator_iterator() =default;
};

живой пример .

Мы сохраняем сгенерированный элемент раньше, чтобы мы могли легче обнаружить, если мы уже в конце.

Поскольку функция итератора конечного генератора никогда не используется, мы можем создать ряд итераторов генератора, только скопировав std::function один раз. По умолчанию построенный итератор генератора сравнивается с равным самому себе и всем другим итераторам конечных генераторов.