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

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

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

Ответ 1

Итераторы - это обобщение указателей.

Итератору (в зависимости от вариантов) необходимо реализовать * и ++

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

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

Ответ 2

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

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

Некоторые из них могут иметь несколько классов.

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

Ответ 3

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

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

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

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

Ответ 4

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

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

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