Предыдущий пост -
Следующий пост -

Прямые и обратные итераторы.

Рубрика: C++, Дата: 4 May, 2013, Автор:

Отталкиваясь от класса Itor, подумайте, как обеспечить прямые и обратные итераторы, итераторы для контейнера, содержимое которого может меняться в процессе итерации и итераторы для работы поверх контейнеров с неизменным содержимым. Организуйте этот набор итераторов так, чтобы пользователь мог взаимозаменяемо использовать итераторы, обеспечивающую достаточную для алгоритма функциональность. Какие еще типы итераторов могут потребоваться пользователю? Перечислите достоинства и недостатки вашего подхода.

Опять тяжелая задачка, но никуда не деться. Будем идти по порядку. В общем сложно мне что то говорить. Как нам обеспечить прямые и обратные итераторы? Что это вообще такое прямые и обратные итераторы? Я вам просто сейчас приведу маленький пример, потом приведу, сейчас я пока вам просто скажу, что прямые итераторы это когда мы просто идем от начала допустим вектора к его концу, а обратные я думаю здесь имеется в веду реверсивные – это когда мы просто идем от конца вектора к его началу. Ну что ж вроде бы все ясно.

Еще здесь интересно итераторы для работы с контейнерами содержимое которых может меняться и для работы с контейнерами с неизменным содержимым, что это? Я так думаю возможно здесь имеется в веду для работы с const контейнерами  и не const обычные итераторы которые меняют содержимое контейнеров. В принципе так оно и есть тут без вариантов.

“Организуйте этот набор итераторов так, чтобы пользователь мог взаимозаменяемо использовать итераторы, обеспечивающую достаточную для алгоритма функциональность.” Отето от не сильно ясно, взаимозаменяемо использовать итераторы, что под этим подразумевается? Я честно говоря не сильно понимаю.

Ну что ж давайте пока попробуем сделать первую часть программы. Попробуем создать итераторы прямой и обратный и естественно const итератор прямой и обратный. Будем наверно создавать для нашего класса List и класса Vector из предыдущей задачи: http://www.kselax.ru/2013/05/klassy-vector-list-i-itor. Так что же нам нужно? Попытаемся сделать так как у нас в реале работает прямой итератор, от допустим для того что бы создать прямой итератор для вектора, что мы делаем? Мы просто прописываем vector<int>::iterator It; и все мы создали итератор для типа вектор int. Что сама запись означает vector<int>::iterator? Похоже на то, что Iterator находится в классе vector. А у нас, что происходит? А у нас просто как мы видим Vector_itor – это класс который наследуется от Itor так же само и List_itor наследуется от Itor. Вообщем Vector_itor и List_itor это и есть прямые итераторы я уже это реализовал как мог. По ссылке выше можно посмотреть выводятся как вектор так и список. Значит нам остается только сделать для обратного итератора и для константного.

Как же обратный итератор создается в реалии? Каким вызовом? Какой синтаксис? Я вам просто покажу как нужно записать, чтобы создать обратный итератор в общем следующая строчка vector<int>::reverse_iterator It; создает реверсивный итератор. Хотя я могу и ошибаться, я просто щас пишу без проверок. Что думаю, то и пишу. Из этого похоже нам нужно создавать два новых класса наследника Itor, допустим reverse_Vector_itor и reverse_List_itor. Так в реализацию классов я думаю вникать не будем. Там я думаю с вектором проблем не будет, а от с List придется чуток видимо повозиться.

А как же const – итераторы вызываются? Я конечно точно не помню, но мне кажется нужно прописать vector<int>::const_iterator It; и у нас создастся константный итератор. Ну это не сложная задачка как мне кажется. Похоже еще нужно будет создать для const – итераторов 4 класса наследников от It. Я думаю что задачка не такая уж и сложная, в сумме нужно добавить новых 6 классов и это только для Vector и для List также добавляется. И того получается 12 классов. Да уж. Конечно не сложно, но кода будет много и чото у меня щас как то силы нету делать.

Вот код который у меня получился. Долгувато конечно я его делал, вроде бы простой код ну и фиг с ним:

//dorabotka klaccov Vector List i Itor
#include <iostream>
using std::cout;
using std::endl;
#include <cstdlib>
using std::exit;

template<class T>
class Vector//optimal6nui
{
public:
	T mass[30];
	int size;
	explicit Vector(size_t n):size(n){}//inicializaci9 n ob6ektami co znacheniem T()

	T& operator[](size_t n)//indekcaci9
	{
		if(n<=size&&n>=0)
			return mass[n];
	}
	
	T getSize(){return size;}
	//...
};

template<class T>
class List//optimal6nui
{
public:
	class Link
	{
	public:
		Link* prev;
		Link* next;
		T data;
		Link(T val):data(val),prev(0),next(0){}
	};
	
	Link* tek;

	List():tek(0){}//pervonachal6no pyctoi
	void put(T a)//pomectit6 pered tekychim elementov
	{
		if(tek==0)
		{
			cout <<"cpicok pyct"<<endl;
			//dobavl9em element
			tek=new Link(a);
		}
		else
		{
			cout <<"ect6 elementu"<<endl;
			//dobavl9em element
			Link* prom=tek;//adrec tekychego elementa
			tek=new Link(a);
			prom->next=tek;
			tek->prev=prom;			
		}
	}
	T* get()//polychit6 tekychii element
	{
		return &tek->data;
	}
	//...
	
};

template<class T> class Itor //obchii interfaic (abctraktnui klacc paragraf 2.5.4. paragraf 12.3)
{
public:
//return 0 dl9 indikacii cocto9ni9 "elementov bol6we net"

	virtual T* first()=0;//ykazatel6 na pervui element
	virtual T* next()=0;//ykazatel6 na cledyyuchii element
	virtual ~Itor(){};//virtyal6nui dectryktor
};

template<class T>
class Vector_itor : public Itor<T>//realizaci9 Vector
{
public:
	Vector<T>&v;//ccukla na vektor
	size_t index;//index tekychego elementa

	Vector_itor(Vector<T>&vv):v(vv),index(0){}
	T* first(){return (v.getSize())?&v[index=0]:0;}
	T* next(){return (++index<v.getSize())?&v[index]:0;}
	bool end(){return (index<v.getSize())?1:0;}
	//razumenovanie
	virtual T& operator*(){return v[index];}
};
//const iterator vector
template<class T>
class const_Vector_itor : public Vector_itor<T>//realizaci9 Vector
{
public:
	//konctryktor preobrazovani9
	const_Vector_itor(Vector<T>&vv)
		:Vector_itor(vv)
	{}

	//peregryzka fynkcii
	T& operator*(){T a=v[index];return a;}
};

template<class T>
class List_itor : public Itor<T>//realizaci9 List
{
public:
	List<T> &lst;
	typename List<T>::Link* p;//ykazuvaet na tekychii element
	int flag;

	List_itor(List<T>& l):lst(l),flag(1){}
	T* first()
	{
		p=lst.tek;
		flag=1;
		//cout <<"p->data= "<<p->data<<endl;
		return &p->data;
	}
	T* next()
	{
		if(p->prev!=0)
		{
			p=p->prev;
			//cout <<"p->data= "<<p->data<<endl;
			return &p->data;
		}
		else
		{
			//p=0;
			flag=0;
			return 0;
		}
	}

	//peregryzka operator*()
	virtual T& operator*()
	{
		return p->data;
	}

	//end
	bool end()
	{
		//cout <<"flag= "<<flag<<endl;
		if(flag!=0)
			return true;

		return false;
	}
};
//const verci9
template<class T>
class const_List_itor : public List_itor<T>//realizaci9 List
{
public:
	//konctryktor preobrazovani9
	const_List_itor(List<T>& l)
		:List_itor(l)//vuzov konctryktora po ymolch.
	{}
	T& operator*()
	{
		T a=p->data;
		return a;
	}
};

template<class T>
class revers_List_itor : public Itor<T>//realizaci9 List
{
public:
	List<T> &lst;
	typename List<T>::Link* p;//ykazuvaet na tekychii element
	int flag;
	
	void rfirstHelper(typename List<T>::Link* ptr)
	{
		cout <<"mu chas tyt"<<endl;
		if(ptr->prev==0)
		{
			cout <<"ptr->prev= 0"<<endl;
			cout <<"ptr->data= "<<ptr->data<<endl;
			p=ptr;//ykazuvaet na pervui element
		}
		else
		{
			cout <<"ptr->prev ne 0"<<endl;
			rfirstHelper(ptr->prev);
		}
		//exit(1);
	}

	//konctryktor preobrazovani9
	revers_List_itor(List<T>& l):lst(l),flag(1){}
	
	T* first()
	{
		if(lst.tek->prev==0)
		{
			cout <<"odin element"<<endl;
			p=lst.tek;
		}
		else
		{
			cout <<"ne odin element"<<endl;
			rfirstHelper(lst.tek->prev);
		}
		
		flag=1;
		//cout <<"p->data= "<<p->data<<endl;
		return &p->data;
	}

	T* next()
	{
		if(p->next!=0)
		{
			p=p->next;
			//cout <<"p->data= "<<p->data<<endl;
			return &p->data;
		}
		else
		{
			//p=0;
			flag=0;
			return 0;
		}
	}

	//peregryzka operator*()
	virtual T& operator*()
	{
		return p->data;
	}

	//end
	bool end()
	{
		//cout <<"flag= "<<flag<<endl;
		if(flag!=0)
			return true;

		return false;
	}

};
//const revers_List
template<class T>
class const_revers_List_itor : public revers_List_itor<T>//realizaci9 List
{
public:
	const_revers_List_itor(List<T>& l)
	:revers_List_itor(l){}

	T& operator*()const
	{
		T a=p->data;
		return a;
	}
};

//reverse_Vector_itor
template<class T>
class reverse_Vector_itor : public Itor<T>//realizaci9 Vector
{
public:
	Vector<T>&v;//ccukla na vektor
	size_t index;//index tekychego elementa
	reverse_Vector_itor(Vector<T>&vv):v(vv),index(0){}
	T* first()
	{
		return (v.getSize())?&v[index=v.getSize()-1]:0;
	}
	
	T* next()
	{
		return (--index>=0)?&v[index]:0;
	}

	bool end()
	{
		return (index+1>0)?1:0;
	}

	//razumenovanie
	virtual T& operator*(){return v[index];}
};
//const-verci9
template<class T>
class const_reverse_Vector_itor : public reverse_Vector_itor<T>
{
public:
	//cozdadim konctryktor preobrazovani9
	const_reverse_Vector_itor(Vector<T>&vv)
	:reverse_Vector_itor(vv){}
	//pereopredel9em fynkciyu
	T& operator*()const
	{
		T a=v[index];
		return a;
	}
};

int main()
{
	Vector<int> v(5);
	for(int i=0;i<5;i++)
	{
		v[i]=i;
		cout <<v[i]<<' ';
	}
	cout <<endl;

	List<int> L;
	int s;
	L.put(3);
	L.put(4);
	L.put(5);
	s=*(L.get());
	cout <<"s= "<<s<<endl;

	Vector_itor<int> it(v);

	//vuvod vektora v cikle c pomochyu iteratorov
	for(it.first();it.end();it.next())
		cout <<*it<<' ';
	cout <<endl;

	List_itor<int> itl(L);
	cout <<"itl.first()= "<<*(itl.first())<<endl;
	cout <<"itl.next()= "<<*itl.next()<<endl;
	cout <<"itl.next()= "<<itl.next()<<endl;
	cout <<"itl.next()= "<<itl.next()<<endl;
	//vuvod v cikle znacheni9 cpicka
	for(itl.first();itl.end();itl.next())
	{
		cout <<"*itl= "<<*itl<<endl;
	}
	cout <<endl;

	//cozdaem obratnui iterator dl9 cpicka
	revers_List_itor<int> rItl(L);
	cout <<"rItl.first()= "<<*rItl.first()<<endl;
	cout <<"rItl.next()= "<<*rItl.next()<<endl;
	cout <<"rItl.next()= "<<*rItl.next()<<endl;
	//cout <<"rItl.next()= "<<*rItl.next()<<endl;
	//cout <<"rItl.next()= "<<*rItl.next()<<endl;
	
	//putaemc9 vuvecti c pomochyu pr9mogo iteratora
	for(rItl.first();rItl.end();rItl.next())
	{
		cout <<"*rItl= "<<*rItl<<endl;
	}

	//cozdaem obratnui iterator dl9 vektora
	reverse_Vector_itor<int> rItv(v);
	cout <<"rItv.first()= "<<*rItv.first()<<endl;
	cout <<"rItv.next()= "<<*rItv.next()<<endl;
	cout <<"rItv.next()= "<<*rItv.next()<<endl;
	cout <<"rItv.next()= "<<*rItv.next()<<endl;
	cout <<"rItv.next()= "<<*rItv.next()<<endl;
	//vuvod v cikle
	for(rItv.first();rItv.end();rItv.next())
	{
		//*rItv=30;
		cout <<"*rItv= "<<*rItv<<endl;
	}
	
	//ecli mu rackomentiryem ctroky mu legko izmenim znachenie vektora, poetomy cozdaem konctantnue iteratoru chtobu nel6z9 bulo izmenit6 znachenie.
	
	//cozdanie konctantnogo revers iteratora Vector
	const_reverse_Vector_itor<int> rItv_con(v);
	for(rItv_con.first();rItv_con.end();rItv_con.next())
	{
		*rItv_con=30;//nichego ne proicxodit tak kak pereopredelena
		cout <<"*rItv_con= "<<*rItv_con<<endl;
	}
	cout <<endl<<endl;

	//cozdanie const revers iterator list
	const_revers_List_itor<int> rItl_c(L);
	for(rItl_c.first();rItl_c.end();rItl_c.next())
	{
		*rItl_c=40;
		cout <<"*rItl_c= "<<*rItl_c<<endl;
	}
	cout <<endl<<endl;

	//cozdanie const iterator List
	const_List_itor<int> Itl_c(L);
	for(Itl_c.first();Itl_c.end();Itl_c.next())
	{
		*Itl_c=40;
		cout <<"*Itl_c= "<<*Itl_c<<endl;
	}
	cout <<endl<<endl;

	//cozdanie const iterator Vector
	const_Vector_itor<int> Itv_con(v);
	for(Itv_con.first();Itv_con.end();Itv_con.next())
	{
		*Itv_con=40;
		cout <<"*Itv_con= "<<*Itv_con<<endl;
	}

	return 0;
}

По коду я комментировать не буду. Код похож на гамнокод но зато работает. Что касается вот этого “Какие еще типы итераторов могут потребоваться пользователю? Перечислите достоинства и недостатки вашего подхода.” , то на вопрос какие типы еще могут потребоваться у меня как бы то нету ответа, по моему это и все итераторы которые мне известны. Достоинства? Ну какие достоинства, я думаю главное, что все работает, ну это для меня главное так как у меня уровень не сильно высокий и я над этими вопросами даже не задумываюсь. Наверно достоинства в том, что код не такой большой получился. А недостатки? да наверно, то что я все члены классов сделал public, просто время неохота тратить на переработку. Я просто взял по быстрому шлепнул. Ладно давайте попробуем следующую задачку решать. Я думаю со временем осознаю достоинства и недостатки, не все сразу.

[youtube]http://www.youtube.com/watch?v=GKvWWrp6q9Q[/youtube]

rss