Как связаны итераторы и указатели?

Question

Код с итераторами очень похож на код с указателями. Итераторы относятся к неясному типу (например, std::vector<int>::iterator).

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

Answer 1

Итераторы являются обобщением указателей.

Итератор (в зависимости от вариантов) должен реализовывать * и ++

Таким образом, указатель является итератором. Но не обязательно наоборот.

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

Answer 2

Итераторы - это объекты, которые перегружают определенные операторы, поэтому использование будет выглядеть как указатели. Это в пределах возможностей данной категории итераторов. Итераторы произвольного доступа выглядят полностью как указатели, другие типы итераторов не предоставляют некоторые операции (например, list<X>::iterator, который является двунаправленным, не имеет оператора += среди многих других, которые требуют произвольного доступа).

Что касается "непонятных имен", то вполне возможно использовать простой указатель для итератора:

 template <class T>
 class MyContainer
 {
     ...
     typedef T* iterator;
 }

 MyContainer<int>::iterator it; //the type is really int*

Answer 3

Концептуально, да - но они не должны быть указателями. Их внутренние возможности и возможности будут зависеть от структуры данных, которую они «обертывают».

Именно поэтому существуют разные "классы" итераторов . Например. Однонаправленный, Двунаправленный, RandomAccess и т. Д.

Некоторые способны к нескольким классам.

например. если внутренняя структура представляет собой красно-черное дерево или связанный список, итераторы могут быть двунаправленными, но не RandomAccess. Если они переносят вектор (реализованный в виде массива), у вас будут RandomAccess и Bidirectional.

Answer 4

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

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

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