Ответ 1

В C++ Итератор - это понятие, а не конкретный (или абстрактный) тип, но любой тип, который подчиняется определенному итератору как правила.

Например, итераторы обычно могут увеличиваться ++i. К ним можно получить доступ (разыменованный) *i чтобы получить значение, на которое они указывают сейчас. Это, по сути, абстракции указателя.

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

https://en.cppreference.com/w/cpp/iterator

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

template<typename Iterator>
void my_algorithm(Iterator begin, Iterator end)
{
    for(; begin != end; ++begin)
        std::cout << *begin << '\n';
}

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

Замечания:

Хотя в настоящее время концепции, такие как Iterator, представляют собой всего лишь набор согласованных семантических свойств в стандарте, которым должны следовать программисты, более комплексное решение, которое будет формализовать такие понятия (в коде), предназначено для следующей версии стандарта [CN10 ] 20.

Ответ 2

Итераторы, как концепция, появились раньше C++.

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

Одна очень важная работа была названа STL - стандартной библиотекой шаблонов, первоначально написанной Степановым и Ли. в 1994 году в Hewlett-Packard, позже поддерживаемый SGI.

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

Итераторы - это концепция - более высокий тип типа

В нем итератор был концепцией. Концепция в C++ - это категория типов (тип типов, которые вы могли бы сказать). Концепции в C++ не выполняются компилятором (в это время).

Тип удовлетворяет концепции, если он имеет необходимые операции, и эти операции соответствуют правилам концепции.

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

Функции записи функций шаблона

Когда алгоритм шаблона запрашивает Iterator, они запрашивают тип, который удовлетворяет концепции Iterator (как описано в стандарте C++). Когда они запрашивают RandomAccessIterator, они просят тип, который удовлетворяет концепции RandomAccessIterator (которая также включает концепцию Iterator, концепцию ForwardIterator и некоторые другие).

Таким образом, template<class ForwardIterator> void std::sort( ForwardIterator, ForwardIterator ) - это функция шаблона, которая принимает два экземпляра одного типа, которые удовлетворяют концепции ForwardIterator.

ForwardIterators должны поддерживать несколько операций (*it, ++it, bool b = it != it ++it, bool b = it == it и т.д.), Поддерживать определенные черты (iterator_traits<it>::iterator_category, iterator_traits<it>::reference, iterator_traits<it>::value_type и т.д.), и эти операции должны следовать определенным правилам.

Если вы кормите его типом, который удовлетворяет RandomAccessIterator, std::sort гарантирует лучшую производительность, чем при передаче ForwardIterator.

Необработанный указатель удовлетворяет итератору Forward RandomAccess, не делая ничего. std::vector<?>::iterator также удовлетворяет обеим, но часто не является сырым указателем (библиотека std сделала некоторую работу).

Два типа - исходный указатель и std::vector<?>::iterator - обычно не связаны между собой. C++ система шаблонов и признаков позволяет несвязанным типам понимать один и тот же шаблонный алгоритм с нулевыми служебными данными.

В c++2a планируется внедрить концепты на языке, которые фактически проверяют некоторые требования для таких вещей, как RandomAccessIterator, и документировать внутри других требований, которые практически невозможно проверить.

C++ не является языком OO

Вы, возможно, сбиты с толку, будучи использованы для объектно-ориентированных языков. C++ поддерживает объектно-ориентированное программирование, но не является объектно-ориентированным языком. Он поддерживает полиморфизм - обработка нескольких типов одинакова - без объектного наследования несколькими способами.

В объектно-ориентированном языке каждый итератор наследует от абстрактного типа итератора. Алгоритмы будут взаимодействовать с итератором через этот абстрактный интерфейс, часто отправляя вызовы через таблицу виртуальных функций. Значения типа были бы невозможны, так как код алгоритма был бы скомпилирован, не зная, сколько байтов занимает итераторы, поэтому произойдет дополнительное косвенное обращение.

В C++ алгоритм не является функцией, пока вы не передадите ему тип итератора. В этот момент функция настраивается для этого итератора. Стандарт C++ гласит, что если итератор выполняет определенные вещи (подчиняется требованиям концепции), функция, написанная шаблоном, будет иметь определенное поведение.

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

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

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

TL; DR

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

C++ алгоритмы генерируют пользовательский код для каждого типа итератора, который вы передаете в std::sort; если вы сортируете вектор int и вектор строк, двоичный код не делится между ними (кроме возможности сложения комдата).

Концепции (тип типа) Iterator/ForwardIterator/RandomAccessIterator - это документированные требования к типам, переданным алгоритмам C++. Никакой принудительной реализации не выполняется, кроме того, что компилятор свободен делать буквально все, если вы не отвечаете требованиям.

Ответ 3

Итератор - это образец поведения, описанный как часть "Банда из четырех шаблонов дизайна". Он решает проблему с итерацией объектов в совокупном объекте, не зная внутренней структуры этого объекта.

Более подробную информацию о шаблоне итератора см. Ниже: http://www.blackwasp.co.uk/Iterator.aspx