В C ++ итераторы в контейнере напоминают указатели в массив (я предполагаю, что вы знакомы с указателями). Существуют разные разновидности итераторов, но в конце они представляют собой просто способ ссылки на элементы в контейнере (через операторы разыменования * и ->) и прохождение элементов в контейнере.
Важной частью является не реализация, а концепция. Вам не нужно знать, как реализован итератор в списке или векторе (или как они различаются во многих случаях), только какие операции он предоставляет. Итераторы в разных контейнерах будут иметь разные реализации (для списка он будет следовать некоторому указателю next в узле, для карты он будет следовать либо за right дочерним, либо parent указателем сбалансированного дерева. Фактически итераторы в один и тот же контейнер может быть реализован по-разному (и некоторые компиляторы имеют несколько реализаций для каждого данного контейнера) в зависимости от флагов или режима компиляции. Но, тем не менее, важной частью является то, что вам действительно все равно, какие они есть, просто что они позволяют вам делать.
В качестве простого примера, в реализации g ++ STL std::vector содержит три указателя, что-то вроде:
//...
class vector {
T * _b; // beginning of allocated memory
T * _e; // one past the last inserted element
T * _c; // one past the end of the allocated memory
//...
}
такой, что size() = (_e - _b) / sizeof(T) и capacity = (_c - _b) / sizeof(T). В этой реализации вектора вы можете использовать необработанный указатель в качестве итератора:
//...
class vector {
public:
typedef T* iterator;
T* begin() { return _b; }
T* end() { return _e; }
//...
}
но вы также можете создавать более сложные (более медленные, но более безопасные) реализации итераторов, такие как проверенные итераторы, которые будут запускать утверждение, если итератор признан недействительным (этот код упрощен только для примера):
template <typename T>
class checked_iterator {
public:
checked_iterator( std::vector<T> & v, std::size_t e )
: _check_begin(v._b), _vector(v), _pos( v._b + e )
{}
T& operator*() {
assert( _check_begin == _vector._b && "Dereferencing an invalidated iterator");
return *_pos;
}
// ...
private:
T * _pos;
T const * const _check_begin;
std::vector<T>& _vector;
};
Эта реализация итератора обнаружит разыменование недействительного итератора (только в случае перемещения целого вектора, но при сохранении большего количества данных может выполнить полную проверку) и прервет выполнение неверной программы, пока она еще находится в разработке. С пользовательской точки зрения это был бы обычный RandomAccessIterator (это должно быть, это требование для векторных итераторов), но за кулисами он предоставит механизм для выявления в противном случае трудно обнаруживаемых ошибок.
Это подход в компиляторах VS: в то время как в режиме отладки (и в зависимости от флагов компилятора) он будет использовать медленные безопасные итераторы, которые помогут обнаружить доступ через недействительные итераторы (для вектора итератор становится недействительным, когда элемент добавлен в контейнер). В то же время, изменяя флаги компилятора, вы можете получить реализацию простого необработанного указателя, которая будет намного быстрее для производственных систем, но будет намного сложнее отлаживать использование недопустимого итератора.
В Java и C # они на самом деле являются объектами, которые реализуют пару простых операций (в Java hasNext(), next() и remove()), которые допускают трансверсальный перенос целого контейнера, скрывая способ реализации контейнера. Они очень похожи в том, что целью является инкапсуляция операций, выполняемых над конкретным контейнером, из пользовательского кода.
Одно важное отличие состоит в том, что в обоих случаях вы можете использовать их для итерации по всему контейнеру, но в c ++ они сравнимы, и вы можете итерировать любые два итератора в одном и том же контейнере. Например, на карте, содержащей телефонную книгу вашего города, вы можете использовать операции, чтобы получить итератор для имени, начинающегося с ac, и другой поиск, чтобы получить первый элемент, имя которого начинается с «d» (при условии упорядочения имен), и вы может использовать любой алгоритм STL (или ваш собственный) с этими двумя итераторами для выполнения операции только над этим подмножеством людей.