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

Для обеспечения этого можно: а)унаследовать его от существующего класса итератора, б) унаследовать от какого-либо iterator_traits, либо в)написать нужные характеристики самим. Первый путь применим, когда требуется частично или полностью сохранить функциональность наследуемого класса итератора, второй – когда схожей функциональности не требуется, но требуется удовлетворение какому-либо стандартному набору характеристик (traits), третий – когда набор характеристик не совпадает ни с одним из существующих вSTL.

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

Это, очевидно, итератор ввода (input iterator).

using namespace std;

classDeviceIterator :public input_iterator

Итератор на C++

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

Благодаря Итератору, клиент может обходить разные коллекции одним и тем же способом, используя единый интерфейс итераторов.

Сложность:

Популярность:

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

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

Концептуальный пример

Этот пример показывает структуру паттерна Итератор, а именно — из каких классов он состоит, какие роли эти классы выполняют и как они взаимодействуют друг с другом.

main.cc: Пример структуры паттерна

/** * Паттерн Итератор * * Назначение: Даёт возможность последовательно обходить элементы составных * объектов, не раскрывая их внутреннего представления. */ #include #include #include /** * C++ has its own implementation of iterator that works with a different * generics containers defined by the standard library. */ template class Iterator < public: typedef typename std::vector::iterator iter_type; Iterator(U *p_data, bool reverse = false) : m_p_data_(p_data) < m_it_ = m_p_data_->m_data_.begin(); > void First() < m_it_ = m_p_data_->m_data_.begin(); > void Next() < m_it_++; >bool IsDone() < return (m_it_ == m_p_data_->m_data_.end()); > iter_type Current() < return m_it_; >private: U *m_p_data_; iter_type m_it_; >; /** * Конкретные Коллекции предоставляют один или несколько методов для получения * новых экземпляров итератора, совместимых с классом коллекции. */ template class Container < friend class Iterator; public: void Add(T a) < m_data_.push_back(a); >Iterator *CreateIterator() < return new Iterator(this); > private: std::vector m_data_; >; class Data < public: Data(int a = 0) : m_data_(a) <>void set_data(int a) < m_data_ = a; >int data() < return m_data_; >private: int m_data_; >; /** * The client code may or may not know about the Concrete Iterator or Collection * classes, for this implementation the container is generic so you can used * with an int or with a custom class. */ void ClientCode() < std::cout cont; for (int i = 0; i < 10; i++) < cont.Add(i); >Iterator> *it = cont.CreateIterator(); for (it->First(); !it->IsDone(); it->Next()) < std::cout Current() Container cont2; Data a(100), b(1000), c(10000); cont2.Add(a); cont2.Add(b); cont2.Add(c); std::cout << "________________Iterator with custom Class______________________________" << std::endl; Iterator *it2 = cont2.CreateIterator(); for (it2->First(); !it2->IsDone(); it2->Next()) < std::cout Current()->data() delete it; delete it2; > int main()

Output.txt: Результат выполнения

________________Iterator with int______________________________________ 0 1 2 3 4 5 6 7 8 9 ________________Iterator with custom Class______________________________ 100 1000 10000

Как создать свой итератор для вектора в шаблонном классе?

Есть задание, написать шаблонный класс контейнер, в котором данные должны храниться в виде одной из STL коллекций. Я выбрал хранить их в std::vector.
Мне нужно написать свой двунаправленный итератор, в котором будет перегружен оператор инкремента (++), так, чтобы итератор пробегался по вектору и брал каждый третий элемент. Проблема заключается в том, что как бы я не пробовал его написать, ничего не получается с моим уже написанным классом.
Там у меня есть метод printEachThirdElement, который как раз занимается выводом каждого третьего элемента вектора, но это нужно реализовать как свой итератор. Прошу помощи.

Код шаблонного класса

#include #include #include template class MyVector < public: MyVector() : vector() < >MyVector(const T& value) : vector() < vector.push_back(value); >void info() const < std::cout std::cout std::int32_t size() const < return vector.size(); >void addElement(const T& value) < vector.push_back(value); >void removeElements(const T& value) < vector.erase(std::remove(vector.begin(), vector.end(), value), vector.end()); >void printEachThirdElement() const < for (auto i = vector.begin() + 2; i < vector.end(); i+=3) < std::cout std::cout private: std::vector vector; >;

Код функции main()

int main() < MyVectorvInt; vInt.addElement(5); vInt.addElement(6); vInt.addElement(7); vInt.addElement(5); vInt.addElement(15); vInt.addElement(12); vInt.addElement(5); vInt.addElement(51); vInt.addElement(666); vInt.addElement(5); vInt.addElement(15); vInt.addElement(12); vInt.addElement(5); vInt.addElement(51); vInt.addElement(666); std::cout

• Вопрос задан более двух лет назад
• 326 просмотров

Реализация итераторов для собственного контейнера

Пытаюсь первый раз реализовать итераторы для своего контейнера, вроде бы все работает хорошо, но вот std::rbegin(test), std::rend(test) не выводят первый элемент (последний с конца). Не могу понять в чем у меня заключается проблема, если не сложно подскажите как решить данную проблему. main.cpp для тестов

#include #include #include #include "deque.h" int main() < Dequetest; test.push_back(123); test.push_back(77); test.push_back(1); test.push_back(777); test.push_back(321); test.push_back(111); test.push_back(12); test.push_back(1000); auto [min_it2, max_it2] = std::minmax_element(std::rbegin(test), std::rend(test)); std::cout << *min_it2 << " - " << *max_it2 << '\n'; Deque::reverse_iterator rvIter; std::cout std::cout

Deque.h (Реализация)

#ifndef _DEQUE_H_ #define _DEQUE_H_ #include #include #include #include //------------------------------------------------------------------------------------------------- template class Node < public: Type element; Node* prev; Node* next; public: Node() : element<>, prev(nullptr), next(nullptr) <>; Node(const Node & node) : Node(node.element, node.prev, node.next) <>; >; //------------------------------------------------------------------------------------------------- template class Iterator < public: using difference_type = std::ptrdiff_t; using value_type = std::remove_cv_t; using pointer = Type*; using reference = Type&; using iterator_category = std::random_access_iterator_tag; using iterator_concept = std::contiguous_iterator_tag; public: explicit Iterator(Node* ptr = nullptr); Iterator(const Iterator& iterator); ~Iterator() = default; bool operator==(const Iterator& lhs) const; bool operator!=(const Iterator& lhs) const; Iterator operator++(); // Iterator operator++(int post); Iterator operator--(); // Iterator operator--(int post); Type& operator*(); protected: Node* date; >; //------------------------------------------------------------------------------------------------- template Iterator::Iterator(Node* ptr) : date(ptr) < >//------------------------------------------------------------------------------------------------- template Iterator::Iterator(const Iterator& iter) : Iterator(iter.date) < >//------------------------------------------------------------------------------------------------- template bool Iterator::operator==(const Iterator& lhs) const < return (date == lhs.date); >//------------------------------------------------------------------------------------------------- template bool Iterator::operator!=(const Iterator& lhs) const < return (date != lhs.date); >//------------------------------------------------------------------------------------------------- template Iterator Iterator::operator++() < date = date->next; return *this; > //------------------------------------------------------------------------------------------------- //template //Iterator Iterator::operator++(int post) // < // Iteratortemp(date); // date = date->next; // return temp; //> //------------------------------------------------------------------------------------------------- template Iterator Iterator::operator--() < date = date->prev; return *this; > //------------------------------------------------------------------------------------------------- //template //Iterator Iterator::operator--(int post) // < // Iteratortemp(date); // date = date->prev; // return temp; //> //------------------------------------------------------------------------------------------------- template Type& Iterator::operator*() < return date->element; > //------------------------------------------------------------------------------------------------- template class Deque < public: //Using using iterator = Iterator; using const_iterator = Iterator; using reverse_iterator = std::reverse_iterator; using const_reverse_iterator = std::reverse_iterator; private: //Member size_t count <>; Node* head; Node* tail; public: //Member functions Deque(); Deque(const Deque & deq); Deque(Deque && deq) noexcept; Deque & operator = (const Deque & deq); Deque & operator = (Deque && deq); ~Deque(); //Element access //const Type & at(Deque pos) const; Not implemented //template //const Type & operator[](size_type pos) const; Not implemented const Type & front() const; const Type & back() const; //Iterators iterator begin() < return iterator(head); >iterator end() < return iterator(tail->next); > iterator begin() const < return iterator(head); >iterator end() const < return iterator(tail->next); > const_iterator cbegin() const < return head; >const_iterator cend() const < return tail->next; > reverse_iterator rbegin() < return std::make_reverse_iterator(tail); >reverse_iterator rend() < return std::make_reverse_iterator(head); >// // reverse_iterator rbegin() const < return std::make_reverse_iterator(rbegin()); >// reverse_iterator rend() const < return std::make_reverse_iterator(rend()); >// // const_reverse_iterator crbegin() const < return rend(); >// const_reverse_iterator crend() const < return rbegin(); >//Capacity bool empty() const; size_t size() const; //size_t max_size() const noexcept; Not implemented //Modifiers void push_front(const Type & tp); void push_back(const Type & tp); //void emplace_front(); Not implemented //void emplace_back(); Not implemented void pop_front(); void pop_back(); void clear() noexcept; void swap(Deque & deq) noexcept; >; //------------------------------------------------------------------------------------------------- template Deque::Deque() : count(0), head(nullptr), tail(nullptr) < //Body of the constructor class >//------------------------------------------------------------------------------------------------- template Deque::Deque(const Deque & deq) : count(deq.count), head(nullptr), tail(nullptr) < for (const Node* n_ptr = deq.head; n_ptr != nullptr; n_ptr = n_ptr->next) < auto* n_ptr_new = new Node; n_ptr_new->element = n_ptr->element; if (head == nullptr && tail == nullptr) < head = n_ptr_new; tail = head; >else < tail->next = n_ptr_new; n_ptr_new->prev = tail; n_ptr_new->next = nullptr; tail = n_ptr_new; > > > //------------------------------------------------------------------------------------------------- template Deque::Deque(Deque && deq) noexcept : count(deq.count), head(deq.head), tail(deq.tail) < deq.count = 0; deq.head = nullptr; deq.tail = nullptr; >//------------------------------------------------------------------------------------------------- template Deque & Deque::operator = (const Deque & deq) < if (this == &deq) < return *this; >Deque tmp(deq); std::swap(count, tmp.count); std::swap(head, tmp.head); std::swap(tail, tmp.tail); return *this; > //------------------------------------------------------------------------------------------------- template Deque & Deque::operator = (Deque && deq) < if (this == &deq) < return *this; >std::swap(count, deq.count); std::swap(head, deq.head); std::swap(tail, deq.tail); return *this; > //------------------------------------------------------------------------------------------------- template Deque::~Deque() < while (head) < Node* n_ptr_del = head; head = head->next; delete n_ptr_del; > count = 0; > //------------------------------------------------------------------------------------------------- template void Deque::push_front(const Type & tp) < auto* n_ptr_new = new Node; n_ptr_new->element = tp; if (head == nullptr && tail == nullptr) < head = n_ptr_new; tail = head; >else < n_ptr_new->next = head; n_ptr_new->prev = nullptr; head->prev = n_ptr_new; head = n_ptr_new; > ++count; > //------------------------------------------------------------------------------------------------- template void Deque::push_back(const Type & tp) < auto* n_ptr_new = new Node; n_ptr_new->element = tp; if (head == nullptr && tail == nullptr) < head = n_ptr_new; tail = head; >else < tail->next = n_ptr_new; n_ptr_new->prev = tail; n_ptr_new->next = nullptr; tail = n_ptr_new; > ++count; > //------------------------------------------------------------------------------------------------- template void Deque::pop_front() < if (empty()) < throw std::out_of_range("Can't pop from empty list"); >if (head == tail) < delete head; --count; head = nullptr; tail = nullptr; return; >Node* n_ptr_del = head; head = head->next; head->prev = nullptr; --count; delete n_ptr_del; > //------------------------------------------------------------------------------------------------- template void Deque::pop_back() < if (empty()) < throw std::out_of_range("Can't pop from empty list"); >if (head == tail) < delete head; --count; head = nullptr; tail = nullptr; return; >Node* n_ptr_del = tail; tail = tail->prev; tail->next = nullptr; --count; delete n_ptr_del; > //------------------------------------------------------------------------------------------------- template bool Deque::empty() const < return head == nullptr; >//------------------------------------------------------------------------------------------------- template const Type & Deque::front() const < if (empty()) < throw std::out_of_range("List::top: empty stack"); > return head->element; > //------------------------------------------------------------------------------------------------- template const Type & Deque::back() const < if (empty()) < throw std::out_of_range("List::top: empty stack"); > return tail->element; > //------------------------------------------------------------------------------------------------- template size_t Deque::size() const < return count; >//------------------------------------------------------------------------------------------------- template void Deque::clear() noexcept < while (count) < pop_back(); >> //------------------------------------------------------------------------------------------------- template void Deque::swap(Deque & deq) noexcept < Deque temp(deq); deq = std::move(*this); *this = std::move(temp); >//------------------------------------------------------------------------------------------------- #endif // _DEQUE_H_ 

Если оставить как сейчас

 reverse_iterator rbegin() < return std::make_reverse_iterator(tail); >reverse_iterator rend()

То в выводе я получаю The deque reversed is: ( 12 111 321 777 1 77 123 ). А если я делаю

 reverse_iterator rend() < return std::make_reverse_iterator(head->prev); > 

Как написать свой итератор 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 (то есть по предпоследний элемент включительно). Консольный вывод:

C++: создание своего итератора

Подскажите пожалуйста, как нормально создать свой класс итераторов c рандомным доступом.
Насколько я понял (а возможно я понял неправильно) необходимо и достаточно создать класс с переопределенными операторами ==,<,++,--,* и &. Однако обычно все делается через наследование базовых классов. Или этот метод используется только при небольшом объеме изменений?

anonymous
29.09.08 13:02:12 MSD

Re: C++: создание своего итератора

Если тебе STL совместимый итератор нуден, то наверно будет достаточно. Наследование не нужно.

Reset ★★★★★
( 29.09.08 13:11:54 MSD )

Re: C++: создание своего итератора

Можно наследовать от std::iterator, которые определяет серию typedef, которые, быть может, где-нибудь да и пригодятся. Оператор & не перегружают. Вместо него перегружают * и ->. Вообще, эта тема хорошо описана у Страуструпа.

dave ★★★★★
( 29.09.08 13:22:07 MSD )

Re: C++: создание своего итератора

Открой СТЛ да почитай коды

placement_new ★★
( 29.09.08 14:39:30 MSD )

Re: C++: создание своего итератора

>Однако обычно все делается через наследование базовых классов

тут статический полиморфизм, неявный интерфейс (концепт) итератора. наследование тут ни к чему, а явная поддержка в языке обещается только с C++0x - пока же просто аккуратно следуй инструкциям

jtootf ★★★★★
( 29.09.08 15:11:31 MSD )

Re: C++: создание своего итератора

Для работы с алгоритмами STL в классе итератора потребуется ряд typedef-ов. Помню точно, что нужно определить типы:

difference_type
iterator_category (в твоем случае это std::random_access_iterator_tag)
pointer
reference
value_type