STL: итераторы

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

Чаще всего итератор это просто ООП-обёртка над указателем. Но обычно эта обёртка несёт более высокий уровень абстракции, чем простой указатель. Звучит несколько странно, правда? Давайте разберёмся получше.

Назначение итераторов

Чем же занимаются итераторы и в чём их основное назначение? Итераторы служат для доступа к элементам контейнера. Естественно, они повсеместно используются как внутри самой STL, так и при её использовании программистами.

Типы итераторов

Итераторы бывают нескольких разных видов, которые отличаются по своему назначению и возможностям, которые они предоставляют. В STL существует четыре типа итераторов: iterator, reverse_iterator, bidirectional_iterator и random access iterator. Соответственно, обычный итератор (iterator или forward iterator) используется для обхода (перебора) элементов в контейнере от начала к концу. Обратный итератор (reverse_iterator) позволяет делать это в обратном направлении – от конца к началу. Двунаправленный итератор (bidirectional_iterator), как следует из его названия, позволяет осуществлять перебор в обе стороны. И итератор произвольного доступа (random access iterator) даёт доступ к любому элементу контейнера (непоследовательный, произвольный доступ).

Получение итераторов

Любой контейнер предоставляет функции для получения итераторов. Например, конейнер вектор, предоставляет для этого такие функции, как:

• begin() – получение итератора, указывающего на первый элемент контейнера
• end() – получение итератора, указывающего на конец контейнера
• rbegin() – получение итератора (обратного), указывающего на первый элемент контейнера с конца
• rend() – получение итератора (обратного), указывающего на конец контейнера… тоже с конца )

Создание собственных итераторов

Пользовательские итераторы создать очень просто – надо просто унаследовать свой собственный итератор от шаблона класса iterator. Для указания типа итератора надо будет передать в шаблон одну из структур-параметров, которые определяют, какой тип итератора мы в итоге получим. Вот эти варианты:

struct output_iterator_tag {};
struct input_iterator_tag {};
struct forward_iterator_tag: public input_iterator_tag {};
struct bidirectional_iterator_tag: public forward_iterator_tag {};
struct random_access_iterator_tag: public bidirectional_iterator_tag {};

Для понятности, пример:

#include <iterator>
 
// type - имя типа элементов с которыми будет работать итератор
class MyIterator: 
  public std::iterator 
     <std::forward_iterator_tag, type> {
        ...
};

И ещё покажу совсем уж практический пример использования итераторов, который позволяет работать с регионами внутри массива. В с++ часто вместо двумерного массива применяют одномерный, а индексы вычисляют по форуме: индекс = x + y*ширина. Как же будет выглядеть итератор для работы с регионами в таком вот массиве:

#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
 
// T - тип объекта, содержащего элементы
// Tval - тип элементов
template <typename T,typename Tval>
class It2Grid: public std::iterator
	<std::forward_iterator_tag, T> {
protected:
	T& m_data;   // объект с элементами, и с операцией[]
	int m_posbeg; // с какого элемента
	int m_width;  // ширина поля
	int m_w;      // ширина региона
	int m_i;      // текущая позиция
 
public:
	It2Grid(T& data, int posbeg, int width, int w, int pos=0)
		: m_data(data),
		m_width(width),
		m_w(w),
		m_posbeg(posbeg),
		m_i(pos)
	{
	}
 
	It2Grid(const It2Grid<T,Tval>& a)
		: m_data(a.m_data),
		m_width(a.m_width),
		m_w(a.m_w),
		m_posbeg(a.m_posbeg),
		m_i(a.m_i)
	{}
 
	//----------------------------------
	Tval& operator *()
	{
		return m_data[m_posbeg+(m_i%m_w)+(m_i/m_w)*m_width];
	}
 
	It2Grid<T,Tval>&operator ++()
	{
		++m_i;
		return *this;
	}
 
	It2Grid<T,Tval>& operator ++(int a)
	{
		++m_i;
		return *this;
	}
 
	bool operator ==(It2Grid<T,Tval> &it)
	{
		return (m_data==it.m_data) && (m_i==it.m_i) &&
			(m_w==it.m_w) && (m_width==it.m_width);
	}
 
	bool operator !=(It2Grid<T,Tval>&it)
	{
		return !(*this==it);
	}
};
 
void out(int*data)
{
	for(int i=0;i<16;i++)
	{
		for(int j=0;j<16;j++)
			cout<<data[j+i*16];
		cout<<endl;
	}
}
 
int main()
{
	int *data=new int[16*16];
	std::fill(data,data+256,0);
	out(data);
	It2Grid<int*,int> begin(data,16*3+3,16,3);
	It2Grid<int*,int> end(data,16*3+3,16,3,9);
	std::fill(begin,end,1);
	cout<<"================"<<endl;
	out(data);
	return 0;
}

Остаётся только надеяться на то, что я объяснил всё понятно. Попробуйте скомпилировать этот исходник и посмотреть что получится. Урок про итераторы закончен.