В свое время, участвуя в собеседованиях (со стороны фирмы разумеется), любил соискателей на должность мучить вопросом «зачем, мол, в STL нужны итераторы?». Простой вроде бы вопрос, но многих ставил в тупик. Итераторы нужны для унифицированного доступа к элементам последовательности. Это даст возможность алгоритмам работать с произвольными последовательностями не задумываясь о способах хранения элементов. Достаточно чтобы эта последовательность была итерируемой. В STL итераторы просты как пять копеек и жестко привязаны к последовательности, которую итерируют. Все это я уже знал давно, но только недавно закралась мысль о том могут ли итераторы существовать отдельно от последовательности. В некотором смысле могут, так как с помощью итераторов можно получить исчерпывающую информацию о хранимых данных (но не о последовательности этих данных). То есть прямой доступ к последовательности уже как бы и не нужен.

    Что это даст? Ну, например, функцию высшего порядка — filter(), в которую мы будем передавать ту или иную последовательность, а на выходе получать объекты, позволяющие итерировать только по отфильтрованным элементам. Оверхед минимальный, так как ничто никуда не копируется, ну и удобство использования на высоте. Более того, мы сможем очень гибко (и что немаловажно удобно) настраивать условия фильтрации, какими бы сложными они не были. Смотрим код?

    Основных класса всего три. Вот они:

template< class seq_type , class predicate >class vsequence{
public:

	class iterator : public iterator_function< seq_type , abstract_iterator< seq_type > >{
	public:

		iterator( void );

		iterator( const iterator & Iter );

		iterator operator=( const iterator & Iter );

		virtual void	 operator++( void );

		virtual seq_type & operator*( void ) const;

		virtual bool	 operator==( const iterator & Iter ) const;

		virtual bool	 operator!=( const iterator & Iter ) const;

		virtual bool	 operator!=( iterator_function< seq_type , abstract_iterator< seq_type > > * Iter ) const;

		virtual ~iterator();

	private:

		/*
		* закрытые члены класса.
		*/

	};

	template< class Iter > vsequence( const Iter & theStartIter , const Iter & theEndIter );

	iterator & begin( void );

	iterator & end( void );

private:

	/*
	* закрытые члены класса.
	*/
};

template< class seq_type >class virtual_iterator{
public:
	virtual_iterator( void );

	template< class iter_type >virtual_iterator( iter_type & theIter );

	template< class iter_type >virtual_iterator( iterator_function< seq_type , abstract_iterator< seq_type > > * theIter );

	virtual void	 operator++( void );

	virtual seq_type & operator*( void ) const;

	virtual bool	 operator!=( virtual_iterator< seq_type > & theIter ) const;

private:

	/*
	* закрытые члены класса.
	*/
};

    Здесь vsequence это наша «виртуальная» последовательность, которую можно «пощупать», но которая не существует в реальности. iterator — однонаправленный, итератор чтения/записи, посредством которого можно получить доступ к элементам «виртуальной» последовательности. virtual_iterator — «виртуальный» итератор, принимающий указатель, на объект, чей класс реализует интерфейс iterator_function< seq_type , abstract_iterator< seq_type > >. Вот спецификация этого интерфейса:

template< class seq_type , class abstract_iter_type >class iterator_function{
public:
	virtual void	 operator++( void ) = 0;

	virtual seq_type & operator*( void ) const = 0;

	virtual bool	 operator!=( abstract_iter_type * abstract_iter ) const;

	virtual bool	 operator!=( iterator_function * iter_func ) const = 0;
};

    Где abstract_iter_type это некий абстрактный интерфейс итератора, с которым нам было бы удобно работать. То есть реализующий все методы iterator_function, но обладающий так же функцией копирования copy. Вот как он выглядит в коде:

template< class seq_type >class abstract_iterator : public clone_function< abstract_iterator > , public iterator_function< seq_type , abstract_iterator >
{
public:
	virtual ~abstract_iterator(){}
};

    Ну и до кучи еще один интерфейс:

template< class abstract_iter_type >class clone_function{
public:
	virtual abstract_iter_type * clone( void ) const = 0;
};

    Для тех кто не может поверить своим глазам, объясняю на пальцах: есть класс А (abstract_iterator), который наследуется от шаблонного класса В (clone_function) инстанциированного самим классом А (почти Уроборос )) ). Такой фокус стал возможен благодаря тому, что у компилятора не возникает проблем с определением размера объекта класса clone_function, так как последний не содержит полей с размером, зависящим от размера объектов класса abstract_iterator (указатель на этот класс возвращается функцией clone, но это ничего не меняет т.к. размер указателя в пределах одного компилятора имеет фиксированный и заранее определенный размер).

    Обращаю ваше внимание на то, что vsequence< … >::iterator так же унаследован от iterator_function, и , следовательно, объекты этого класса можно использовать в качестве параметров одного из конструкторов класса virtual_iterator.

    Ну а теперь примеры:

#include	

template< class seq_type >class ident{
public:
	bool									operator()( seq_type & )
	{
		return( true );
	}
};

template< class seq_type >class odd{
public:
	bool									operator()( seq_type & v )
	{
		return( v % 2 == 1 );
	}
};

// программа выведет только нечетные числа
int		main( int argc , char * argv[] )
{
	std::vector< int >		v;

	for( int i( 0 ) ; i <= 11 ; i++ )
	{
		v.push_back( i );
	}

	// последовательность аналогичная исходной v
	vsequence< int , ident< int > > vseq1( v.begin() , v.end() );

	// последовательность только из нечётных элементов vseq1
	vsequence< int , odd< int > > vseq2( vseq1.begin() , vseq1.end() );
	vsequence< int , odd< int > >::iterator i( vseq2.begin() );

	for( ; i != vseq2.end() ; ++i )
	{
		std::cout<<*i<

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

    PS Исходники к статье

Добавить комментарий


Защитный код
Обновить