Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

STL для новичков. Реализация класса-контейнера

Anna | 25.06.2014 | нет комментариев

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

Статья будет увлекательна только новичкам, которые начинают постигать стандартную библиотеку, специалисты не обнаружат тут для себя ничего новго.

Ну что ж, начнем. Что собой представляет list из стандартной библиотеки? Это ступенчатый контейнер, тот, что оптимизирован для вставки и удаления элементов. Для работы с этим контейнером в STL применяется двунаправленный итератор, тот, что мы испробуем реализовать. Также мы реализуем функцию вставки на предисловие и в конец списка, вставку позже элемента на тот, что указывает iterator, удаление элементов и еще несколько функций.

А теперь будет много кода с комментариями.
файл «dlist.h»

#ifndef DLIST_H_
#define DLIST_H_
#include <iostream>

template <typename T>
class Double_list
{
public:
	class iterator; 
	friend class iterator; //класс итератора должен иметь доступ к полям класса Double_list

private:
	class Double_node; 
	friend class Double_node;

	class Double_node //
	{
	public:
		friend class Double_list<T>;
		friend class iterator;

		//Создать вузол с какимто значением типа T
		Double_node(T node_val): val(node_val) {}
		Double_node() {}
		~Double_node() {}

		void print_val() {std::cout << val << " "; }

		Double_node *next; //указывает на дальнейший узел списка
		Double_node *prev; //указывает на предшествующий узел. 
		T val; //данные.

	};

public:
	class iterator
	{
		friend class Double_list<T>; 

	public:

		// нулевой конструкрор
		iterator() :the_node(0) {}
		//здесь мы создаем итератор с указателя на узел Double_node
		iterator(Double_node *dn): the_node(dn) {}
		//конструктор копии
		iterator(const iterator &it): the_node(it.the_node) {}

		iterator& operator=(const iterator &it)
		{
			the_node = it.the_node;
			return *this;
		}

		// в этом классе оператор == обозначает, что два итератора указывают на
		// один и тот же узел
		bool operator == (const iterator &it) const
		{
			return (the_node == it.the_node);
		}

		bool operator!=(const iterator &it) const
		{
			return !(it == *this);
		}

		//переводит итератор на дальнейший узел списка. 
		iterator& operator  ()
		{
			if (the_node == 0)
				throw "incremented an empty iterator";
			if (the_node->next == 0)
				throw "tried to increment too far past the end";

			the_node = the_node->next;
			return *this;
		}

		//переводит итератор на предідущий узел списка. 
		iterator & operator--()
		{
			if (the_node == 0)
				throw "decremented an empty iterator";
			if (the_node->prev == 0)
				throw "tried to decrement past the beginning";

			the_node = the_node->prev;
			return *this;
		}

		//Возвращает значение данных.
		T& operator*() const
		{
			if (the_node == 0)
				throw "tried to dereference an empty iterator";
			return the_node->val;
		}

	private:
		Double_node *the_node;

	};

private:
	Double_node *head;  //указывает на предисловие списка. 
	Double_node *tail;  //указывает на елемент, тот, что идет за последним

	iterator head_iterator; //итератор, тот, что неизменно указывает на предисловие списка
	iterator tail_iterator; //итератор, тот, что неизменно указывает на элемент, тот, что находится за последним.

public:
	Double_list()
	{
		head = tail = new Double_node;
		tail->next = nullptr;
		tail->prev = nullptr;

		//инициализирует итераторы
		head_iterator = iterator(head);
		tail_iterator = iterator(tail);
	}

	//Создать список, тот, что содержит один элемент. 
	Double_list(T node_val)
	{
		head = tail = new Double_node;
		tail->next  = nullptr;
		tail->prev = 0;

		head_iterator = iterator(head);
		tail_iterator = iterator(tail);
		add_front(node_val);
	}

	~Double_list()
	{
		Double_node *node_to_delete = head;
		for (Double_node *sn = head; sn != tail;)
		{
			sn = sn->next;
			delete node_to_delete;
			node_to_delete = sn;
		}

		delete node_to_delete;
	}

	bool is_empty() {return head == tail;}

	iterator front() {return head_iterator;}
	iterator rear() {return tail_iterator;}

	//вставляем узел в предисловие списка
	void add_front(T node_val)
	{
		Double_node *node_to_add = new Double_node (node_val);
		node_to_add->next =head;
		node_to_add->prev = nullptr;
		head->prev = node_to_add;
		head = node_to_add;
		//так как head изменился, необходимо изменить head_iterator
		head_iterator= iterator(head);
	}

	//вставляем узел в конец списка
	void add_rear(T node_val)
	{
		if (is_empty())
			add_front(node_val);
		else
		{
			Double_node *node_to_add = new Double_node(node_val);
			node_to_add->next = tail;
			node_to_add->prev = tail->prev;
			tail->prev->next = node_to_add;
			tail->prev =  node_to_add;
			//изменяем tail_iterator
			tail_iterator = iterator(tail);
		}
	}

	//вставляет в спсиок node_val позже итератора key_i
	bool insert_after(T node_val, const iterator &key_i)
	{
		for (Double_node *dn = head; dn != tail; dn = dn->next)
		{
			//Найден ли узел для заданного итератора
			if (dn == key_i.the_node)
			{
				Double_node *node_to_add = new Double_node(node_val);
				node_to_add->prev = dn;
				node_to_add->next = dn->next;
				dn->next->prev = node_to_add;
				dn->next = node_to_add;
				return true;
			}
		}
		return false;
	}

	//Удалить 1-й элемент списка. 
	T remove_front()
	{
		if (is_empty())
			throw "tried to remove from an empty list";
		Double_node *node_to_remove = head;
		T return_val = node_to_remove->val;
		head = node_to_remove->next;
		head->prev = 0;
		head_iterator = iterator(head);

		delete node_to_remove;
		return return_val;

	}

	T remove_rear()
	{
		if (is_empty())
			throw "tried to remove from an empty list";

		Double_node *node_to_remove = tail->prev;

		if(node_to_remove->prev == 0)
		{
			return remove_front();
		}
		else
		{
			T return_val = node_to_remove->val;
			node_to_remove->prev->next = tail;
			tail->prev = node_to_remove->prev;
			delete node_to_remove;
			return return_val;
		}
	}

	bool remove_it(iterator &key_i)
	{
		for (Double_node *dn =  head; dn != tail; dn = dn-next)
		{
			//Найден ли узел для заданного итератора
			if (dn == key i.the_node)
			{
				dn->prev->next = dn->next;
				dn->next->prev = dn->prev;
				delete dn;
				key_i.the_node =0;
				return true;
			}
		}

		return false;
	}

	//Возвращает 1-й итератор, указывающий на node_val
	iterator find(T node_val) const
	{
		for (double_node *dn = head; dn != tail; dn = dn->next)
		{
			if (dn->val == node_val)
				return iterator(dn);
		}

		//Если node_val нет в списке возвращает tail_iterator
		return tail_iterator;
	}

	//возвращает итератор, тот, что указывает на n-ый элемент списка
	iterator get_nth(const int element_num) const
	{
		if (element_num < 1)
			return tail_iterator;

		int count = 1;
		for(Double_node *dn = head; dn != tail; dn = dn->next)
		{
			if (count   == element_num)
				return iterator(dn);
		}

		return tail_iterator;
	}

	//Количество узлов в списке. 
	int size() const
	{
		int count = 0;
		for (Double_node *dn = head; dn != tail; dn = dn->next) 
			  count;
		return count;
	}

	void print() const
	{
		for (Double_node *dn = head; dn!= tail; dn = dn->next)
		{
			dn->print_val();
		}

		std::cout << std::endl;
	}

};

#endif	

Применение списка

#include "dlist.h"

int main()
{
	Double_list<int> the_list;

	Double_list<int>::iterator list_iter;

	for (int i=0; i<5;   i)
	{
		the_list.add_front(i);
	}

	the_list.print();

	the_list.remove_front();

	for (list_iter = the_list.front(); list_iter != the_list.rear();    list_iter)
	{
		std::cout << *list_iter << " ";
	}
	std::cout << std:: endl;

	//выводим в обратном порядке
	for (list_iter = the_list.rear(); list_iter != the_list.front();)
	{
		--list_iter;
		std::cout << *list_iter << " ";
	}

	std::cout << std::endl;

	system("PAUSE");
	return 0;
}
Обзор кода

Итератор реализован как открытый вложенный класс. Так как класс открытый, пользователи могут создавать объекты. Класс iterator должен знать о некоторых закрытых элементах класса Double_list, следственно мы объявляем класс iterator дружелюбным к классу Double_list и так же в классе iterator объявляем ином класс Double_list. 

Сейчас посмотрим на внутреннее устройство класса Double_list::iterator. У него есть исключительный элемент данных: Double_node* the_node. Именно это итератор и должен скрывать. Операции, объявляемые в классе iterator, разрешают пользователям манипулировать этим узлом определенным образом.

Конец

Вот на этом и все. Приблизительно так реализован класс списка в библиотек

 

Источник: programmingmaster.ru

 

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB