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

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

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

Ну что ж, начнем. Что собой представляет 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;
	}

	//Удалить первый элемент списка. 
	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;
	}

	//Возвращает первый итератор, указывающий на 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, позволяют пользователям манипулировать этим узлом определенным образом.

Конец

Вот на этом и все. Примерно так реализован класс списка в библиотеке STL. Конечно, наш класс очень общий пример, в STL все сложнее, но общий принцип с этого кода понять можно.

Автор: Pein95

Источник