шаблоны, используемые в итераторах

Question

Я знаком с использованием итераторов C++ STL, например.

for(map<pair<int,int>>::iterator it=m.begin(); it!=m.end(); ++it) 
    int a = it->first; 
    int b = it->second; 

Но я не знаю внутренних деталей. Могли бы некоторые объяснить мне? Либо в C++, Java, C# или Python.

Answer 1

Заканчивать итератор шаблон http://www.dofactory.com/patterns/PatternIterator.aspx

Answer 2

Помимо: код Вы отправили не будет работать - вы упускаете брекеты - ни C#, ни C++, ни Java есть волшебный пробел (и этот код действительно Безразлично 't выглядят как Python).

Также >> будет интерпретироваться как оператор правой смены (спасибо Prasoon Saurav). Я думаю, что вы хотите:

for(map<pair<int,int> >::iterator it=m.begin(); it!=m.end(); ++it) { // <- here 
    int a = it->first; 
    int b = it->second; 
} // <- and here 

Answer 3

Одна точки использования итераторов является то, что вам не нужно знать о «внутренних деталях».

Тем не менее, всегда полезно понять основные принципы, стоящие за ним, и на всех упомянутых вами языках одинаково: у вас есть функция (или функция языка), которая должна что-то делать с целым рядом объектов. Функция может затем взять объект итератора, и сделать что-то вроде этого (с помощью Python):

def DoSomething(start_iter, end_iter): 
    while (start_iter != end_iter): 
     calculate(start_iter.get_data()) 
     start_iter = start_iter.next() 

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

В C++, например, итератор для STL :: vector очень близок к простому целому числу, и итерация через него выполняется под капотом, так же, как итерация чистого массива.

Answer 4

Проверьте ссылку на wiki для Iterator. Это довольно объяснительный (и, как упоминается другой ответ и ссылка) намерение этого шаблона состоит в том, чтобы обеспечить доступ к элементам совокупного объекта без раскрытия внутренних деталей.

Например, в Java итератор для AbstractList реализован во внутреннем классе, экземпляр которого создан для итерации списка. Проверьте здесь code.

Answer 5

Итератор - это абстрактное понятие, для которого определено, что разыменование его с помощью оператора * даст вам определенный элемент из последовательности, связанной с итератором, и приращение его даст вам итератор, связанный со следующим элементом в некоторая последовательность. Это означает, что конкретный итератор определяется последовательностью и не является отдельно определенным классом, т. Е. Почему вам нужно использовать тип map<pair<int,int> >::iterator, а не только iterator. Тип итератора для каждой последовательности STL имеет собственную реализацию, для которой оператор ++ перегружен, чтобы обеспечить итератор, указывающий на следующий элемент в последовательности.

Это означает, что простой указатель на массив символов также является итератором, поскольку разыменование указателя даст вам объект, связанный с итератором (указатель) и увеличивающий его, даст вам новый итератор (указатель), связанный с следующий элемент в последовательности.

Неполный пример дважды связанный список, (примечание: тестировался, просто писал выше, может потребоваться добавить некоторые другу положения и прочее):

class doubly_linked_list { 
    class node { 
    node* prev; 
    node* next; 
    int data; 
    node(const int data, node* prev, node* next) : data(data), prev(prev), next(next) {} 
    }; 
    static const node nil; // = node(0, 0, 0) 
    node* head; 
    node* tail; 
public: 
    class iterator { 
    node* current; 
    iterator(node* n) : current(n) {} 
    public: 
    int& operator*() const { 
     return current->obj; 
    } 
    iterator& operator++() { 
     current = current->next; 
     return *this; 
    } 
    iterator& operator--() { 
     current = current->prev; 
     return *this; 
    } 
    }; 
    double_linked_list() : head(nil), tail(nil) {} 
    iterator begin() const { 
    return iterator(head); 
    } 
    iterator end() const { 
    return iterator(tail); 
    } 
}; 

И, чтобы проиллюстрировать, как различные структуры данных будут иметь различные итераторы вектор пример (как непроверенная)

class vector { 
    int* data; 
    size_t len; 
public: 
    typedef int* iterator; 
    vector(const size_t len) : len(len) { 
    data = new int[len]; 
    } 
    int& operator[](int i) const { 
    return data[i]; 
    } 
    iterator begin() const { 
    return data; 
    } 
    iterator end() const { 
    return data + len; 
    } 
}; 

Answer 6

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

Важная часть - это не реализация, а концепция. Вам не нужно знать, как внедряется итератор в список или вектор (или как они отличаются во многих случаях), только то, что он предоставляет. Итераторы в разных контейнерах будут иметь разные реализации (для списка он будет следовать указателю next в узле, для карты он будет следовать либо ребенку right, либо указателю parent сбалансированного дерева. Фактически итераторы в один и тот же контейнер могут быть реализованы по-разному (и некоторые компиляторы имеют более одной реализации для любого данного контейнера) в зависимости от флагов или режима компиляции. Но тем не менее важная часть состоит в том, что вам действительно все равно, как они, именно то, что они позволяют вам делать .

в качестве простого примера, в г реализация 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; 
}; 

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

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

В Java и C# на самом деле они объекты, реализующие несколько простых операций (в Java hasNext(), next() и remove()), которые позволяют секущей целого контейнера Hidding, как реализуется контейнер.Они очень похожи в том, что намерение заключается в инкапсулировании операций, выполняемых на конкретном контейнере из кода пользователя.

Важным отличием является то, что в обоих случаях вы можете использовать их для итерации по всему контейнеру, но в C++ они сопоставимы, и вы можете перебирать любые два итератора в один и тот же контейнер. Например, на карте, содержащей вашу телефонную книгу города, вы можете использовать операции, чтобы получить итератор в первое имя, начинающееся с ac, и другой поиск, чтобы получить первый элемент, имя которого начинается с «d» (при условии упорядочения имен), и вы может использовать любой STL (или ваш собственный) алгоритм с этими двумя итераторами для выполнения операции только для этого подмножества людей.

Answer 7

Хороший example в C# из MSDN.

Существует стандартный интерфейс IEnumerable. Если ваш класс перечислим, то вы просто реализуете метод GetEnumerator этого интерфейса.

Но, как вы знаете, у другого класса может быть другой метод для перечисления, для массива вы просто перемещаете указатель на 1 для дерева, вам нужен метод обхода дерева. Но в целом, перечислитель имеет тот же интерфейс, например. методы в IEnumerator в C#.

Итак, помимо класса, реализующего IEnumerable, вам все равно нужно реализовать класс, который реализует IEnumerator, в частности, MoveNext, Reset. Метод GetEnumerator возвращает экземпляр класса перечислителя.