Skip to content

ООП Лекция 10. Итераторы.

Jump to bottom
Vladislav Mansurov edited this page May 2, 2022 · 1 revision

Итераторы. Работа с итераторами

image

struct List
{
    Node *first, *lsat;
};

Идея: выделить текущий указатель в структуру и создавать по надобности.

struct Iterator
{
    Node *curent;
};

Стоит задача унификации работы с контейнерными данными. Можно идти по пути унификации интерфейса, чтобы разные контейнерные классы имели один и тот же интерфейс. Но нормальной работы с вот этими понятиями не будет. Желательно, чтобы каждая сущность имела свой интерфейс.

Идея простая: унифицировать работу с разными контейнерами засчёт итератора. А у итератора будет унифицированный интерфейс.

Стандартная библиотека предоставляет 5(6) видов итераторов.

Идея: есть базовый шаблон - итератора, и уже конкретный итератор - специализация. 5 видов специализации. Специализация определяется тэгом. Тэг - простейшая структура.

struct input_iterator_tag {}; // итератор ввода
struct output_iterator_tag {}; // итератор вывода
struct forward_iterator_tag {}; // однонаправленный итератора на чтение-апись
struct bi_directional_iterator_tag {}; // двунаправленный итератор на чтение-запись
struct random_access_iterator_tag {}; // произвольный доступ
  • ->, *, bool
  • ++ (префиксный, постфиксный инкременты)
  • !=, ==

Отличие двунаправленного от однонаправленного: добавление оператора декремента --

Random access iterator добавляет +=, -=, +, -, [], !=, ==, <, <=, >, >=

Раньше мы вынуждены были любой итератор порождает от этих базовых итераторов. В принципе, в современных стандартах можно свой итератор не порождать от этих стандартных итераторов.

В языке C++ появился цикл foreach

for (auto elem: obj)
    cout << elem;
// Цикл выше разворачивается в
for (Iterator<Type> It = obj.begin(); It != obj.end(); ++It) {
    auto elem = *It;
	cout << elem;
}

Мы обязаны в контейнерный класс добавить методы: begin, end, cbegin, cend (c - const), rbegin, rend, crbegin, crend. Также добавить операторы: !=, ++, * (++ - префиксный инкремент).

Контейнер может быть хранитель, но есть проблема. Мы на контейнеры можем создавать итераторы. По этой причины "голенький" указатель в контейнере хранить нельзя. То есть итератор должен хранить weak_ptr. Контейнер должен оборачивать данные в shared_ptr.

Существуют классы, которые содержат в себе другие классы. Например, множество, вектор и т. п. Такие классы называются контейнерными - они включают в себя другие классы.

Для работы с контейнерными классами, нам во-первых необходимо абстрагироваться от внутренней структуры организации контейнера - нас это не должно интересовать, а во-вторых мы можем обрабатывать контейнер вне зависимости от типа объекта внутри контейнера. Для этого были придуманы классы-итераторы. Существуют стандартные итераторы, поэтому задача программиста - задавать общий механизм работы с итераторами. Классы, которые отвечают за просмотр содержимого в других объектах, называют итераторами.

Чтобы работать со стандартными итераторами, нужно подключить <iterator>.

Есть стандартный итератор - шаблон класса Iterator. У него есть специализации под разные виды работы с итераторами. Итераторы делятся на итераторы ввода (мы можем менять то, на что итератор указывает) и итераторы вывода (мы НЕ можем менять то, на что итератор указывает, то есть мы можем только читать, но не записывать).

Специализация ввода или вывода задаётся при наследовании пользовательского итератора от стандартного итератора (пример смотри ниже).

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

С помощью итератора можно просматривать содержимое контейнера.

Благодаря итераторам в C++ стало возможным создать оператор foreach. Для работы с этим оператором контейнерный класс должен содержать два метода: метод begin(), указывающий на начало последовательности, и метод end(), указывающий на конец последовательности. Конец - это не последний элемент, а ЗА последним элементом.

Для итератора должны быть определены операции сравнения (!=) и обход (++, *).

Оператор foreach:

for (<тип>& <имя> : <объект>)
{
	...
}

Следует предусмотреть итераторы для работы как с константным контейнерным классом, так и с неконстантным.

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

# include <iostream>
# include <memory>
# include <iterator>
# include <initializer_list>

using namespace std;

template <typename Type>
class Iterator;

class BaseArray
{
public:
	BaseArray(size_t sz = 0) { count = shared_ptr<size_t>( new size_t(sz) ); }
	virtual ~BaseArray() = default;
	size_t size() { return bool(count) ? *count : 0; }
	operator bool() { return size(); }
protected:
	shared_ptr<size_t> count;
};

template <typename Type>
class Array final : public BaseArray // Создание контейнера
{
public:
	Array(initializer_list<Type> lt);
	virtual ~Array() {}

	// Итератор - интерфейс для этого контейнера
	Iterator<Type> begin() const { return Iterator<Type>(arr, count); }
	Iterator<Type> end() const { return Iterator<Type>(arr, count, *count);	}
private:
	shared_ptr<Type[]> arr{ nullptr };
};

template <typename Type>
class Iterator : public std::iterator<std::input_iterator_tag, Type>  // В данном случае используется итератор ввода
{
	friend class Array<Type>;
private:
	Iterator(const shared_ptr<Type[]>& a, const shared_ptr<size_t>& c, size_t ind = 0) : arr(a), count(c), index(ind) {}
public:
	Iterator(const Iterator &it) = default;

	// Сравнивать итераторы
	bool operator!=(Iterator const& other) const;
	bool operator==(Iterator const& other) const; 
	
	// Получать доступ к содержимому итератора
	Type& operator*();
	const Type& operator*() const;
	Type* operator->();
	const Type* operator->() const;

	// Итерировать контейнерные элементы
	Iterator<Type>& operator++();
	Iterator<Type> operator++(int);
private:
	weak_ptr<Type[]> arr;
	weak_ptr<size_t> count;
	size_t index = 0;
};

#pragma region Method Array

template <typename Type>
Array<Type>::Array(initializer_list<Type> lt)
{
	if (!(*count = lt.size())) return;
	arr = shared_ptr<Type[]>(new Type[*count]);
	size_t i = 0;
	for (Type elem : lt)
		arr[i++] = elem;
}

#pragma endregion

#pragma region Methods Iterator

template <typename Type>
bool Iterator<Type>::operator!=(Iterator const& other) const { return index != other.index; }

template <typename Type>
Type& Iterator<Type>::operator*()
{
	shared_ptr<Type[]> a(arr);
	return a[index];
}

template <typename Type>
Iterator<Type>& Iterator<Type>::operator++()
{
	shared_ptr<size_t> n(count);
	if (index < *n)
		index++;
	return *this;
}

template <typename Type>
Iterator<Type> Iterator<Type>::operator++(int)
{
	Iterator<Type> it(*this);
	++(*this);
	return it;
}

#pragma endregion

template <typename Type>
ostream& operator<<(ostream& os, const Array<Type>& arr)
{
	for (auto elem : arr)
		cout << elem << " ";
	return os;
}

int main()
{
	Array<int> arr{ 1, 2, 3, 4, 5 };
	cout << " Array: " << arr << endl;
}
Clone this wiki locally