Как написать свой итератор c

Свой итератор для своего шаблона

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

Кликните здесь для просмотра всего текста

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75

#include "stdafx.h" #include templatetypename T, std::size_t N> class Array { T *_array; std::size_t count; public: // Конструкторы Array(); // инициализируем объект нулями // Геттеры T get_begin(void); // получаем первый элемент // Деструктор ~Array(); // удаляем объект }; template typename T, std::size_t N> ArrayT, N>::Array() { this->count = N; this->_array = new T[N]; for (int i(0); i  N; i++) this->_array[i] = 0; } templatetypename T, std::size_t N> T ArrayT, N>::get_begin(void) { return this->_array; } templatetypename T, std::size_t N> ArrayT, N>::~Array() { delete[] this->_array; this->_array = nullptr; this->count = 0; } //---------------------------------------------------------------// templatetypename T> class Iterator { T* value; // значение Iterator(); // закрыл, ибо не нужен public: // Конструкторы template typename T, std::size_t N> Iterator(ArrayT, N> & arr) // инициализируем итератор первым элементом шаблона { this->value = arr.get_begin(); } // Методы T operator*() // получаем текущий элемент { return *this->value; } // остальное пока не реализовано }; //------------------------------------------------------------------------// int main() { Arrayint, 10> _arr1; Iteratorint> iter(_arr1); std::cout  <*iter  ::endl; return 0; }

Ошибка в строке 55.

Делаем свой итератор

Не часто возникает необходимость создать свой итератор и хотелось бы иметь под рукой небольшой HowTo. В этой заметка хочу рассказать как создать простейший итератор, который можно использовать в стандартных алгоритмах типа std::copy, std::find. Какие методы и определения типов нужны в классе контейнере, чтобы его можно было обходить в циклах for из c++11 и BOOST_FOREACH.

Контейнер

В классе контейнере необходимо определить типы iterator и const_iterator (типы нужны во-первых для удобства, а во-вторых без них не будет работать обход при помощи BOOST_FOREACH), а также методы begin и end (тут в зависимости от требований, можно добавить только константные методы возвращающие const_iterator):
Для примера возьмем контейнер хранящий массив целых чисел.

class OwnContainer < public: typedef OwnIteratoriterator; typedef OwnIterator const_iterator; OwnContainer(std::initializer_list values); iterator begin(); iterator end(); const_iterator begin() const; const_iterator end() const; private: const size_t size; std::unique_ptr data; >; 

Реализация методов OwnContainer

OwnContainer::OwnContainer(std::initializer_list values) : size(values.size()), data(new int[size]) < std::copy(values.begin(), values.end(), data.get()); >OwnContainer::iterator OwnContainer::begin() < return iterator(data.get()); >OwnContainer::iterator OwnContainer::end() < return iterator(data.get() + size); >OwnContainer::const_iterator OwnContainer::begin() const < return const_iterator(data.get()); >OwnContainer::const_iterator OwnContainer::end() const

Естественно, ничто не мешает определить iterator и const_iterator как псевдонимы одного и того же типа.

Итератор

Итератор следует наследовать от класса std::iterator. Сам по себе этот класс не реализует никаких методов, но объявляет необходимые типы, которые используются в стандартных алгоритмах.

std::iterator
Как он определе в g++ 4.9

 template struct iterator < /// One of the @link iterator_tags tag types@endlink. typedef _Category iterator_category; /// The type "pointed to" by the iterator. typedef _Tp value_type; /// Distance between iterators is represented as this type. typedef _Distance difference_type; /// This type represents a pointer-to-value_type. typedef _Pointer pointer; /// This type represents a reference-to-value_type. typedef _Reference reference; >; 

Это шаблонный класс, первый параметр шаблона — тип итератора, так как собираемся использовать со стандартной библиотекой, то тип выбирается из следующих типов: input_iterator_tag, output_iterator_tag, forward_iterator_tag, bidirectional_iterator_tag, random_access_iterator_tag. Второй параметр тип значения которое хранится и возвращается операторами * и ->, теретий параметр — тип который может описывать растояние между итераторами, четвртый шаблонный параметр — тип указателя на значение, пятый — тип ссылки на значения. Обязательными являются первые два параметра.

Самый просто итератор — это InputIterator (input_iterator_tag), он должен поддерживать префиксную форму инкремента, оператор !=, оператор* и оператор -> (его реализовывать не буду, так как в примере итератор используется для типа int, и в этом случае operator-> бессмысленен). Помимо этого понадобится конструктор и конструктор копирования. В примере не предполагается создание итератора кроме, как методами begin и end класса контейнера, поэтому конструктор итератора будет приватным, а класс контейнера объявлен как дружественный. И добавим оператор ==, во-первых хорошая практика добавлять поддержку != и == вместе, а во-вторых без этого не будет работать BOOST_FOREACH.

const_iterator не сильно отличается от iterator, поэтому объявим iterator как шаблонный класс с одним параметром — тип возвращаемого значения для операторов * и ->.

В конструктор будем передавать указатель на элемент массива хранящийся в OwnContainer.

template class OwnIterator: public std::iterator < friend class OwnContainer; private: OwnIterator(ValueType* p); public: OwnIterator(const OwnIterator &it); bool operator!=(OwnIterator const& other) const; bool operator==(OwnIterator const& other) const; //need for BOOST_FOREACH typename OwnIterator::reference operator*() const; OwnIterator& operator++(); private: ValueType* p; >; 

Реализация методов OwnIterator

template OwnIterator::OwnIterator(ValueType *p) : p(p) < >template OwnIterator::OwnIterator(const OwnIterator& it) : p(it.p) < >template bool OwnIterator::operator!=(OwnIterator const& other) const < return p != other.p; >template bool OwnIterator::operator==(OwnIterator const& other) const < return p == other.p; >template typename OwnIterator::reference OwnIterator::operator*() const < return *p; >template OwnIterator &OwnIterator::operator++()

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

Итератор унаследованный от boost::iterator_facade

Контейнер отличается только типами на которые ссылаются iterator и const_iterator:

class OwnContainerBBI < public: typedef OwnIteratorBBiterator; typedef OwnIteratorBB const_iterator; OwnContainerBBI(std::initializer_list values); iterator begin(); iterator end(); const_iterator begin() const; const_iterator end() const; private: const size_t size; std::unique_ptr data; >; 

Реализация методов OwnContainerBBI

OwnContainerBBI::OwnContainerBBI(std::initializer_list values) : size(values.size()), data(new int[size]) < std::copy(values.begin(), values.end(), data.get()); >OwnContainerBBI::iterator OwnContainerBBI::begin() < return iterator(data.get()); >OwnContainerBBI::iterator OwnContainerBBI::end() < return iterator(data.get() + size); >OwnContainerBBI::const_iterator OwnContainerBBI::begin() const < return const_iterator(data.get()); >OwnContainerBBI::const_iterator OwnContainerBBI::end() const

Итератор наследуется от шаблонного типа boost::iterator_facade. Это шаблонный класс, первый параметр — тип наследника, второй тип значения, третий тип итератора. В качестве типа итератора может выступать тип используемый в std::iterator, так и специфичные для boost (в описании такой вариант обозначен как old-style), я возьму тот же тип, что и для std::iterator. boost::iterator_facade реализует необходимые методы: operator*, operator++, operator-> и т.д. Но их реализация базируется на вспомогательных методах, которые нужно реализовать в нашем итераторе, а именно dereference, equal, increment, decrement, advance, distance. В простом случе (как наш) потребуются только equal, increment и dereference. Так как эти методы используются для релизации интерфейса итератора, то разместим их в секции privat, а класс их использующий (boost::iterator_core_access) объявим другом.

template class OwnIteratorBB: public boost::iterator_facade< OwnIteratorBB, ValueType, boost::single_pass_traversal_tag > < friend class OwnContainerBBI; friend class boost::iterator_core_access; private: OwnIteratorBB(ValueType* p); public: OwnIteratorBB(const OwnIteratorBB& it); private: bool equal(OwnIteratorBB const& it) const; void increment(); typename OwnIteratorBB::reference dereference() const; ValueType* p; >; 

Реализация методов OwnIteratorBB

template OwnIteratorBB::OwnIteratorBB(ValueType *p) : p(p) < >template OwnIteratorBB::OwnIteratorBB(const OwnIteratorBB &it) : p(it.p) < >template bool OwnIteratorBB::equal(const OwnIteratorBB &it) const < return p == it.p; >template void OwnIteratorBB::increment() < ++p; >template typename OwnIteratorBB::reference OwnIteratorBB::dereference() const

Заключение

Итератор можно создать и использовать без контейнера, а иногда контейнер не нужен вовсе. Итераторы могут служить обертками над другими итераторами и модифицировать их поведение, например выдавать элементы через один. Или отдельно хранятся данные, а отдельно контейнер с некоторыми ключами или значениями полей. И можно организовать итератор, который будет проходится по всем желементам, но возвращать только те что соответвуют некотрому условию основанному на значениях второго контейнера. Еще идеи можно почерпнуть в статье Недооценённые итераторы написанной k06a.

Для простых итераторов использование boost::iterator_facade не очень актуально, но для более сложных позволяет сократить количество кода, естественно, если библиотека boost уже используется, тянуть её только ради iterator_facade смысла нет.

Ссылки

1. Описание Iterator library на cppreference,com.
2. Описание boost::iterator_facade
3. Репозиторий c примером на github. Проект использует Qt5 (для тестов), так как используется boost, то нужно объявить переменную окружения BOOST с путем к каталогу с boost.

• итератор
• std::iterator
• boost::iterator_facade

Как написать свой итератор c

Итераторы обеспечивают доступ к элементам контейнера и представляют реализацию распространенного паттерна объектно-ориентированного программирования «Iterator». С помощью итераторов очень удобно перебирать элементы. В C++ итераторы реализуют общий интерфейс для различных типов контейнеров, что позволяет использовать единой подход для обращения к элементам разных типов контейнеров.

Стоит отметить, что итераторы имеют только контейнеры, адаптеры контейнеров — типы std::stack , std::queue и std::priority_queue итераторов не имеют.

Итератор описывается типом iterator . Для каждого контейнера конкретный тип итератора будет отличаться. Так, итератор для контейнера list представляет тип list::iterator , а итератор контейнера vector представляет тип vector::iterator и так далее. Однако общий функционад, который применяется для доступа к элементам, будет аналогичен.

Для получения итераторов контейнеры в C++ обладают такими функциями, как begin() и end() . Функция begin() возвращает итератор, который указывает на первый элемент контейнера (при наличии в контейнере элементов). Функция end() возвращает итератор, который указывает на следующую позицию после последнего элемента, то есть по сути на конец контейнера. Если контейнер пуст, то итераторы, возвращаемые обоими методами begin и end совпадают. Если итератор begin не равен итератору end, то между ними есть как минимум один элемент.

Обе этих функции возвращают итератор для конкретного типа контейнера:

#include #include int main() < std::vectornumbers< 1,2,3,4 >; std::vector::iterator iter = numbers.begin(); // получаем итератор >

В данном случае создается вектор — контейнер типа vector, который содержит значения типа int. И этот контейнер инициализируется набором . И через метод begin() можно получить итератор для этого контейнера. Причем этот итератор будет указывать на первый элемент контейнера.

С итераторами можно проводить следующие операции:

• *iter : получение элемента, на который указывает итератор
• ++iter : перемещение итератора вперед для обращения к следующему элементу
• —iter : перемещение итератора назад для обращения к предыдущему элементу. Итераторы контейнера forward_list не поддерживают операцию декремента.
• iter1 == iter2 : два итератора равны, если они указывают на один и тот же элемент
• iter1 != iter2 : два итератора не равны, если они указывают на разные элементы
• iter + n : возвращает итератор, который смещен от итератора iter на n позиций вперед
• iter — n : возвращает итератор, который смещен от итератора iter на n позиций назад
• iter += n : перемещает итератор на n позиций вперед
• iter -= n : перемещает итератор на n позиций назад
• iter1 — iter2 : возвращает количество позиций между итераторами iter1 и iter2
• >, >=,

Стоит отметить, что итераторы не всех контейнеров поддерживают все эти операции.

Итераторы для типов std::forward_list , std::unordered_set и std::unordered_map не поддерживают операции —, -= и -. (поскольку std::forward_list — однонаправленный список, где каждый элемент хранит указатель только на следующий элемент)

Итераторы для типа std::list поддерживают операции инкремента и декремента, но не поддерживаются операции +=, -=, + и -. Те же ограничения имеют итераторы контейнеров std::map и std::set .

Операции +=, -=, +, -, , >= и поддерживаются только итераторами произвольного доступа (итераторы контейнеров std::vector , array и deque )

Получение и изменение элемента контейнера

Поскольку итератор по сути представляет указатель на определенный элемент, то через этот указатель мы можем получить текущий элемент итератора и изменить его значение:

#include #include int main() < std::vectornumbers< 1,2,3,4 >; auto iter < numbers.begin() >; // получаем итератор // получаем элемент, на который указывает итератор std::cout 

После получения итератора он будет указывать на первый элемент контейнера. То есть при выражение *iter возвратит первый элемент вектора.

Прибавляя или отнимая определенное число, можно переместить итератор вперед или назад на определенное количество элементов:

#include #include int main() < std::vectornumbers< 10, 20, 30, 40 >; auto iter < numbers.begin() >; // получаем итератор // переходим на 1 элемент вперед ко 2-му элементу ++iter; std::cout 

Опять же повторю, что стоит учитывать, что не все операции поддерживаются итераторами всех контейнеров.

Перебор контейнера

Например, используем итераторы для перебора элементов вектора:

#include #include int main() < std::vectornumbers< 10, 20, 30, 40 >; auto iter < numbers.begin() >; // получаем итератор while(iter!=numbers.end()) // пока не дойдем до конца < std::cout // аналогичный пример с циклом for for(auto start; start !=numbers.end(); start++ ) < std::cout >

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

Константные итераторы

Если контейнер представляет константу, то для обращения к элементам этого контейнера можно использовать только константный итератор (тип const_iterator ). Такой итератор позволяет считывать элементы, но не изменять их:

const vector numbers; for(auto iter ; iter != numbers.end(); ++iter) < std::cout 

В данном случае итератор iter будет представлять тип std::vector::const_iterator .

Для получения константного итератора также можно использовать функции cbegin() и cend . При этом даже если контейнер не представляет константу, но для его перебора используется константный итератор, то опять же нельзя изменять значения элементов этого контейнера:

#include #include int main() < std::vectornumbers < 1, 2, 3, 4, 5 >; for (auto iter ; iter != numbers.cend(); ++iter) < std::cout >

Стоит отметить, что для типов std::set (множество) и std::map (словарь) доступны только константные итераторы.

Реверсивные итераторы

Реверсивные итераторы позволяют перебирать элементы контейнера в обратном направлении. Для получения реверсивного итератора применяются функции rbegin() и rend() , а сам итератор представляет тип reverse_iterator :

#include #include int main() < std::vectornumbers < 1, 2, 3, 4, 5 >; for (auto iter ; iter != numbers.rend(); ++iter) < std::cout std::cout

В данном случае итератор будет представлять тип std::vector::reverse_iterator . Консольный вывод программы:

5 4 3 2 1

Если надо обеспечить защиту от изменения значений контейнера, то можно использовать константный реверсивный итератор, который представлен типом const_reverse_iterator и который можно получить с помощью функций crbegin() и crend() :

#include #include int main() < std::vectornumbers < 1, 2, 3, 4, 5 >; for (auto iter ; iter != numbers.crend(); ++iter) < std::cout >

Итераторы для массивов

Для массивов в C++ также имеется поддержка итераторов. Для этого в стандартной библиотеке С++ определены функции std::begin() (возвращает итератор на начало массива) и std::end() (возвращает итератор на конец массива):

int data[]; // получаем итератор на начало массива auto iter = std::begin(data); // получаем итератор на конец массива auto end = std::end(data);

Как и контейнеры, массив можно перебрать с помощью итераторов:

#include int main() < int data[]; // перебор массива с помощью итераторов for(auto iter ; iter != std::end(data); iter++) < std::cout >

Но перебор массива вполне можно сделать и другими способами - через индексы, обычные указатели. Но итераторы на массивы могут быть полезны при манипуляции с контейнерами. Например, функция insert() , которая есть у ряда контейнеров, позволяет добавить в контейнер какую-то часть другого контейнера. Для выделения добавляемой части могут применяться итераторы. И таким образом, с помощью итераторов можно добавить в контейнер, например, в вектор какую-то часть контейнера:

#include #include int main() < int data[]; std::vector numbers < 1, 2, 3, 4>; // добавляем в конец вектора numbers из массива data элементы со 2-го по предпоследний (включительно) numbers.insert(numbers.end(), std::begin(data) + 1, std::end(data)-1); for (auto iter ; iter != numbers.end(); ++iter) < std::cout std::cout

numbers.insert(numbers.end(), std::begin(data) + 1, std::end(data)-1);

Добавляет в вектор numbers, начиная с позиции, на которую указывает итератор numbers.end() (то есть в самый конец вектора), диапазон элементов массива data. Начало этого диапазона задается выражением std::begin(data) + 1 (то есть со 2-го элемента), а конуц — выражением std::end(data)-1 (то есть по предпоследний элемент включительно). Консольный вывод: