Как итераторы и указатели связаны?
Код с итераторами в значительной степени походит на код с указателями. Итераторы имеют некоторый неясный тип (как std::vector<int>::iterator например).
То, что я не получаю, - то, как итераторы и указатель связаны друг с другом - действительно ли итератор является оберткой вокруг указателя с перегруженными операциями для усовершенствования к смежным элементам или является им что-то еще?
4 ответа
Итераторы - это обобщение указателей.
Итератор (в зависимости от вариантов) должен реализовывать * и ++
Итак, указатель ЯВЛЯЕТСЯ итератором. Но не обязательно наоборот.
Если вы хотите перебрать сложную структуру (дерево, граф ...), итератор будет намного больше, чем указатель, и не будет ссылаться на какое-либо реальное место в оперативной памяти.
Итератор - это просто тип, который предоставляет требуемый интерфейс. для итераторов - они различны для разных типов итераторов и указаны в разделе 24.1 стандарта C ++ (Требования к итераторам).
Как реализуются итераторы, зависит от того, что они повторяют - для векторов они обычно являются оболочкой вокруг единственного указателя на массив (в любом случае в сборках релизов), для более сложных контейнеров они имеют более сложную реализацию. Для открытых диапазонов они будут содержать состояние любого алгоритма, который используется для генерации элементов.
Обратите внимание, что указатель на элемент в массиве соответствует требованиям итератора с произвольным доступом, поэтому до некоторой степени они взаимозаменяемы.
Концептуально да - но они не обязательно должны быть указателями. Их внутреннее устройство и возможности будут зависеть от структуры данных, которую они «оборачивают».
Поэтому существуют разные «классы» итераторов . Например. Однонаправленный, двунаправленный, случайный доступ и т. Д.
Некоторые из них могут иметь несколько классов.
Например. если внутренняя структура представляет собой красно-черное дерево или связанный список, итераторы могут быть двунаправленными, но не случайным доступом. Если они оборачивают вектор (реализованный как массив), у вас будет RandomAccess и Bidirectional.
Итераторы - это объекты, которые перегружают определенные операторы, поэтому их использование будет выглядеть так, как если бы они были указателями. Это в пределах возможностей данной категории итераторов. Итераторы произвольного доступа полностью похожи на указатели, другие типы итераторов не предоставляют некоторых операций (например, list , который является двунаправленным, не имеет оператора + = среди многие другие, для которых потребуется произвольный доступ).
Что касается «непонятных имен», то использование простого указателя для итератора не совсем немыслимо:
template <class T>
class MyContainer
{
...
typedef T* iterator;
}
MyContainer<int>::iterator it; //the type is really int*