Для получения триального ключа
заполните форму ниже
Team License (базовая версия)
Enterprise License (расширенная версия)
* Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

Запросите информацию о ценах
Новая лицензия
Продление лицензии
--Выберите валюту--
USD
EUR
GBP
RUB
* Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

Бесплатная лицензия PVS-Studio для специалистов Microsoft MVP
* Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

Для получения лицензии для вашего открытого
проекта заполните, пожалуйста, эту форму
* Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

Мне интересно попробовать плагин на:
* Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

Ваше сообщение отправлено.

Мы ответим вам на


Если вы так и не получили ответ, пожалуйста, проверьте папку
Spam/Junk и нажмите на письме кнопку "Не спам".
Так Вы не пропустите ответы от нашей команды.

Итераторы

20 Окт 2021

Под итераторами понимают объекты, реализующие интерфейс доступа к элементам контейнера. Их основное предназначение – это предоставление возможности работать с разными контейнерами единым способом, что позволяет использовать одни и те же функции и алгоритмы. С помощью итераторов можно перебирать объекты внутри любого контейнера. Это бывает полезно, когда сами контейнеры не могут предоставить быстрый доступ к произвольному элементу.

Итератор – легковесный объект, который хранит только указатель на тип объектов контейнера и определяется 5 шаблонными параметрами, два из которых являются обязательными: категория итератора и тип значения, которое может быть получено путем разыменовывания итератора. Для каждой категории итератора перегружены операции префиксного и постфиксного инкрементов (++), сравнения (==, !=) и разыменования (*). После выполнения оператора ++ итератор будет указывать на следующий в коллекции элемент, если он существует. Операторы == и != вернут true или false в зависимости от того, указывают ли итераторы на один и тот же объект. Как и при работе с указателями, для получения объекта используется операция разыменования. Также как для указателей, для них применимы операции разыменования (*,->), инкремента (++) и сравнения (==, !=).

Для каждого типа контейнера существуют свои итераторы. Это связано с особенностями расположения элементов в памяти и доступа к ним. Итераторы делятся на следующие категории:

  • ввода (InputIterator);
  • однонаправленные (ForwardIterator);
  • двунаправленные (BidirectionalIterator);
  • произвольного доступа (RandomAccessIterator);
  • непрерывные (ContiguousIterator, начиная с C++17);
  • вывода (OutputIterator).

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

  • it, it1, it2 – итераторы;
  • a – поле или метод базового типа, на который указывает итератор;
  • n – число элементов или индекс.
Iterators_ru/image1.png

Ячейка со значением ± означает, что операция выполнима только если итератор не является константным.

В зависимости от категории итераторов, их можно использовать в разных стандартных алгоритмах. Так, например, алгоритм подсчета числа элементов (std::count) применим ко всем типам итераторов, кроме итераторов вывода, а алгоритм сортировки (std::sort) только к итераторам произвольного доступа и непрерывным итераторам.

В следующем примере продемонстрировано использование итераторов для подсчета суммы в разных контейнерах:

#include <vector>
#include <deque>
#include <forward_list>
#include <set>
#include <string>
#include <iostream>

template <typename InputIt, typename T>
constexpr T sum(InputIt first, InputIt last, T init)
{
  while (first != last)
  {
    init = std::move(init) + *first;
    ++first;
  }

  return init;
}

int main()
{
  std::forward_list<int> flist { 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1 };
  std::deque<int>        deque { 1, 1, 2, 3, 5, 8, 13 };
  std::vector<float>    vector { 0.3, 0.5 ,0.7 ,0.9 ,1.1 };
  std::set<std::string>    set { "One", "Two", "Three", "Four" };

  auto  flist_sum = sum(flist.begin(), flist.end(), 0);
  auto  deque_sum = sum(deque.begin(),  deque.end(), 0);
  auto vector_sum = sum(vector.begin(), vector.end(), 0.0f);
  auto    set_sum = sum(set.begin(), set.end(), std::string {});

  std::cout << " flist_sum = " << flist_sum  << "\n";
  std::cout << " deque_sum = " << deque_sum  << "\n";
  std::cout << "vector_sum = " << vector_sum << "\n";
  std::cout << "   set_sum = " << set_sum    << std::endl;


  // flist_sum = 7
  // deque_sum = 33
  // vector_sum = 3.5
  // set_sum = FourOneThreeTwo

  return 0;
}

Для подсчета суммы используется шаблон функции, принимающей два итератора и начальное значение. Функция использует такие операции над итераторами, как сравнение (!=), разыменование для чтения (*) и префиксный инкремент (++). Эти операции выполнимы для всех категорий, начиная с InputIterator (кроме OutputIterator). Эта категория самая низкая из пяти, поэтому функция может работать со всеми пятью категориями итераторов. Для определения типа возвращаемого значения используется третий аргумент функции.

Для того, чтобы получить итератор на начало и конец последовательности элементов, у любого контейнера существуют методы begin и end. Контейнер forward_list использует однонаправленные итераторы, deque и set – двунаправленные, а vector – итераторы произвольного доступа. Вызов функций для разных контейнеров приводит к инстанцированию шаблона с соответствующим типом итератора и типом хранимого значения.

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

Для более удобной работы с итераторами существуют операции:

  • std::distance – возвращает расстояние (число переходов) между двумя итераторами;
  • std::advance – модифицирует переданный итератор, сдвигая его на n позиций вперед или назад. Сдвиг на положительное число доступен для любых типов итераторов. Сдвиг на отрицательное число доступен для итераторов, начиная с категории BidirectionalIterator;
  • std::prev – возвращает n-ый по счету предыдущий итератор;
  • std::next – возвращает n-ый по счету следующий итератор.

Для изменения поведения итератора или добавления дополнительного функционала, используются итераторы-адаптеры. Например, адаптер reverse_iterator позволяет обходить контейнер в обратном направлении, а back_insert_iterator вставлять элементы в конец контейнера.

Итераторы часто упрощают программирование, однако их неправильное использование не всегда отслеживается компилятором и может приводить к ошибкам. Например, можно сравнить итераторы от разных контейнеров (V662) или разыменовать невалидный итератор (V783). PVS-Studio позволяет детектировать эти и некоторые другие паттерны ошибок связанные с итераторами с помощью диагностик V803, V789 и V738.

Библиографический список

Популярные статьи по теме
Как и почему статические анализаторы борются с ложными срабатываниями

Дата: 20 Мар 2017

Автор: Андрей Карпов

В своей предыдущей статье я писал, что мне не нравится подход, при котором статические анализаторы кода оцениваются с помощью синтетических тестов. В статье приводился пример, воспринимаемый анализат…
PVS-Studio для Java

Дата: 17 Янв 2019

Автор: Андрей Карпов

В седьмой версии статического анализатора PVS-Studio мы добавили поддержку языка Java. Пришло время немного рассказать, как мы начинали делать поддержку языка Java, что у нас получилось и какие дальн…
Статический анализ как часть процесса разработки Unreal Engine

Дата: 27 Июн 2017

Автор: Андрей Карпов

Проект Unreal Engine развивается - добавляется новый код и изменятся уже написанный. Неизбежное следствие развития проекта - появление в коде новых ошибок, которые желательно выявлять как можно раньш…
Эффект последней строки

Дата: 31 Май 2014

Автор: Андрей Карпов

Я изучил множество ошибок, возникающих в результате копирования кода. И утверждаю, что чаще всего ошибки допускают в последнем фрагменте однотипного кода. Ранее я не встречал в книгах описания этого …
Как PVS-Studio оказался внимательнее, чем три с половиной программиста

Дата: 22 Окт 2018

Автор: Андрей Карпов

PVS-Studio, как и другие статические анализаторы кода, часто выдаёт ложные срабатывания. Но не стоит спешить считать странные срабатывания ложными. Это короткая история о том, как PVS-Studio вновь ок…
Технологии, используемые в анализаторе кода PVS-Studio для поиска ошибок и потенциальных уязвимостей

Дата: 21 Ноя 2018

Автор: Андрей Карпов

Краткое описание технологий, используемых в инструменте PVS-Studio, которые позволяют эффективно обнаруживать большое количество паттернов ошибок и потенциальных уязвимостей. Статья описывает реализа…
Любите статический анализ кода!

Дата: 16 Окт 2017

Автор: Андрей Карпов

Я в шоке от возможностей статического анализа кода, хотя сам участвую в разработке инструмента PVS-Studio. На днях я был искренне удивлён тому, что анализатор оказался умнее и внимательнее меня.
Бесплатный PVS-Studio для тех, кто развивает открытые проекты

Дата: 22 Дек 2018

Автор: Андрей Карпов

В канун празднования нового 2019 года команда PVS-Studio решила сделать приятный подарок всем контрибьюторам open-source проектов, хостящихся на GitHub, GitLab или Bitbucket. Им предоставляется возмо…
Главный вопрос программирования, рефакторинга и всего такого

Дата: 14 Апр 2016

Автор: Андрей Карпов

Вы угадали, ответ - "42". Здесь приводится 42 рекомендации по программированию, которые помогут избежать множества ошибок, сэкономить время и нервы. Автором рекомендаций выступает Андрей Карпов - тех…
Характеристики анализатора PVS-Studio на примере EFL Core Libraries, 10-15% ложных срабатываний

Дата: 31 Июл 2017

Автор: Андрей Карпов

После большой статьи про проверку операционной системы Tizen мне было задано много вопросов о проценте ложных срабатываний и о плотности ошибок (сколько ошибок PVS-Studio выявляет на 1000 строк кода)…

Комментарии (0)

Следующие комментарии
Этот сайт использует куки и другие технологии, чтобы предоставить вам более персонализированный опыт. Продолжая просмотр страниц нашего веб-сайта, вы принимаете условия использования этих файлов. Если вы не хотите, чтобы ваши данные обрабатывались, пожалуйста, покиньте данный сайт. Подробнее →
Принять