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

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

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

Свой итератор для класса

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

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

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

#include #include #include template typename T> class MyVector { public: MyVector() : vector() { } MyVector(const T& value) : vector() { vector.push_back(value); } void info() const { std::cout  <"[ "; for (auto &v : vector) { std::cout   <" "; } std::cout  <"]"  ::endl; } 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  <*i  <" "; } std::cout  ::endl; } private: std::vectorT> vector; };

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

int main() { MyVectorint> vInt; 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  <"Each 3 element"  ::endl; vInt.printEachThirdElement(); return 0; }

Итераторы в C++: введение

Всем привет! Изучая контейнеры STL, мы использовали новый вид переменных - итераторы. Так давайте узнаем, зачем ими пользуются?

Что такое итератор

Итератор - это такая структура данных, которая используется для обращения к определенному элементу в контейнерах STL. Обычно из используют с контейнерами set , list , а у вектора для этого применяют индексы.

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

Как создать итератор

Для создания итератора мы должны с самого начала программы подключить библиотеку .

#include 

Далее для его создании нам потребуется использовать вот эту схему:

контейнер> его тип> :: iterator имя итератора>;

• - указываем требуемый контейнер, на который и будет ссылаться итератор. Например map , vector , list .
• - указываем тип контейнера.

Вам нужно помнить! Если вы создали итератор и случайно ввели не тот тип данных, который указали при создании контейнера, то ваша программа будет работать неправильно и вообще может сломается.

Методы начала и конца контейнеров

У каждого контейнера имеются два метода, которые, как указатели передают итератору начало или конец контейнера - begin() и end().

• Метод begin() отправит итератор на начала контейнера.
• А метод end() отправит на конец. А если точнее, то на одну ячейку больше последней. Если мы попытаемся вывести эту ячейку у нас появятся проблемы с компилятором 🙂 .

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

Также при инициализации итератора мы можем с самого начала написать, куда он будет указывать:

vector int> i_am_vector; vector int> :: iterator it = i_am_vector.begin();

Итератор на vector

Для итератора на vector вы можете:

• Выполнять операцию разыменования (обращаться к значению элемента на которое указывает итератор), как мы это делали с указателем.

int x = *it;

• Использовать инкремент ( it++, ++it ) и декремент ( it--, --it ).
• Применять арифметические операции. Так например мы можем сместить итератор на пять ячеек в право, вот так:

it += 5;

• Сравнивать на равенства.

if (it == it2)  ...

• Передать переменной разницу итераторов.

int x = it - it2;

Использовать выше сказанные операции можно только с идентичными итераторами, которые указывают на одинаковый контейнер и тип.

Есть исключение из правил - если вы создадите два одинаковых итератора на map то при сравнивании они не будут одинаковы.

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

vector int> vector_first; vector double> vector_second; vector int> :: iterator it = vector_first.begin(); vector double> :: iterator it2 = vector_second.begin(); if (it == it2)  // ошибка! cout  <"it == it2"; >

Итератор на list, set, map

Для итераторов на list , set , map немного урезан функционал. Так вы не можете:

• Использовать арифметические операции.

it += 5; // it *= 2; // it /= 3; // ошибка it -= 5; //

• Применять операции сравнения ( > и < ):

if (it > it_second)  ... // // ошибка if (it  it_second)  ... //

Все остальное можно использовать:

• Применять инкремент и декремент.

it--; // все it++; // нормально!

• Использовать операцию разыменования.

cout  *it; *it += 5;

• Сравнивать два итератора на равенство и неравенства:

if (it == it_second)  ... // // правильно if (it != it_second)  ... //

Кстати использовать арифметические операции, чтобы увеличить итератор на один, как это делает инкремент - нельзя.

Но вы можете сказать: “Так что мы можем двигать итератор только на один элемент? Это же неудобно!“. Да было бы совсем не гибко со стороны C++ делать вот такое, но они позаботились и создали функцию - advanсe() , она заменяет операции увеличения и уменьшения над итераторами.

Вот как она работает:

advance(итератор>, значение>);

• - сюда мы должны указать итератор, который и нужно изменить.
• - тут мы должны вписать число на которое должны увеличить или уменьшить итератор.

Если мы увеличиваем итератор, то используем оператор + к числу. Но можно и просто записать число без оператора + .

Если же нужно уменьшить итератор, то мы добавляем оператор - .

advanсe(it, 5); // сместили на 5 ячеек

Как работают итераторы

Чтобы понять, как работают итераторы, давайте разберем их использование на практике. В примере ниже с помощью итератора мы выводим содержимое вектора на экран:

#include #include #include using namespace std; int main()  setlocale(0, ""); vector name_vector; name_vector.push_back(3); name_vector.push_back(4); name_vector.push_back(6); vector int> :: iterator it; for (it = name_vector.end() - 1; it >= name_vector.begin(); it--)  cout  <*it  <" "; > system("pause"); return 0; >

• В строке 10: создали вектор name_vector .
• Дальше в последующих трех строках занимаемся его заполнением.
• В строке 16: создали итератор под именем it .
• В цикле for мы написали, что итератор указывает на последнюю ячейку вектора. С помощью вот такой не замысловатой конструкции :

it = name_vector.end() - 1;

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

• Используя операцию разыменования, в теле цикла, мы вывели все элементы.

cout  *it;

Вы наверняка заметили, что мы выводим элеме