Simple-Singly-Linked-List.cpp

#include <iostream>
#include <iterator>
#include <algorithm>
#include <cstddef>
#include <stdexcept>


template <typename T>
class List
{
	struct Node
	{
		Node* next;
		T	  value;
	};


public:
	template <typename U = T>
	struct Iterator : public std::iterator<std::forward_iterator_tag, U, ptrdiff_t, U*, U&>
	{
		using iterator_category = std::forward_iterator_tag;
		using value_type = U;
		using difference_type = ptrdiff_t;
		using pointer = U*;
		using reference = U&;


		explicit Iterator(Node* ptr = nullptr) : ptr(ptr) {}

		reference operator*() const
		{
			return ptr->value;
		}

		pointer operator->() const
		{
			return std::pointer_traits<pointer>::pointer_to(**this);
		}

		Iterator& operator++()
		{
			ptr = ptr->next;
			return *this;
		}

		Iterator operator++(int) const
		{
			auto previous = *this;
			++*this;
			return previous;
		}

		template<class Type>
		bool operator==(Iterator<Type> const& rhs) const
		{
			return ptr == rhs.ptr;
		}

		template<class Type>
		bool operator!=(Iterator<Type> const& rhs) const
		{
			return !(*this == rhs);
		}

		operator Iterator<const U>() const
		{
			return Iterator<const U>(ptr);
		}

		Node* ptr;
	};

	using const_iterator = Iterator<const T>;
	using iterator = Iterator<T>;


public:
	List();
	List(List const& other);
	List(List&& other) noexcept;
	List(std::initializer_list<T> list);

	template<class Iter>
	List(Iter begin, Iter end);

	List& operator=(List other);
	List& operator=(List&& other) noexcept;
	List& operator=(std::initializer_list<T> list);
	void swap(List& other) noexcept;

	~List();

	iterator begin();
	iterator end();

	const_iterator begin() const;
	const_iterator end() const;

	const_iterator cbegin() const;
	const_iterator cend() const;

	void insert_after(iterator where, T const& value);

	void push_back(T&& t);
	void push_back(T const& t);

	template<class... U>
	void emplace_back(U&&... u);

	void push_front(T&& t);
	void push_front(T const& t);

	template<class... U>
	void emplace_front(U&&... u);

	iterator erase_after(iterator it);

	void clear();
	void pop_front();

	std::size_t size() const;
	bool empty() const;


private:
	Node*		m_head;
	Node*		m_tail;
	std::size_t m_size;
};

template <typename T>
List<T>::List()
	: m_head(nullptr)
	, m_tail(nullptr)
	, m_size()
{
}

template <typename T>
List<T>::List(List const& other)
	: List()
{
	clear();

	for (const auto& i : other)
	{
		push_back(i);
	}
}

template <typename T>
List<T>::List(List&& other) noexcept
	: List()
{
	clear();

	for (auto&& i : other)
	{
		emplace_back(std::move(i));
	}
}

template <typename T>
List<T>::List(std::initializer_list<T> list)
	: List()
{
	clear();

	for (const auto& i : list)
	{
		push_back(i);
	}
}

template <typename T>
template<class Iter>
List<T>::List(Iter begin, Iter end)
	: List()
{
	clear();

	for (auto i = begin; i != end; ++i)
	{
		push_back(*i);
	}
}

template <typename T>
List<T>::~List()
{
	clear();
}

template <typename T>
typename List<T>::iterator List<T>::begin()
{
	return iterator(m_head);
}

template <typename T>
typename List<T>::iterator List<T>::end()
{
	return iterator(nullptr);
}

template <typename T>
typename List<T>::const_iterator List<T>::begin() const
{
	return const_iterator(m_head);
}

template <typename T>
typename List<T>::const_iterator List<T>::end() const
{
	return const_iterator(nullptr);
}

template <typename T>
typename List<T>::const_iterator List<T>::cbegin() const
{
	return const_iterator(m_head);
}

template <typename T>
typename List<T>::const_iterator List<T>::cend() const
{
	return const_iterator(nullptr);
}

template <typename T>
void List<T>::insert_after(typename List::iterator where, T const& value)
{
	Node* node = nullptr;
	try {
		node = new Node{ nullptr, value };
	}
	catch (...) {
		delete node;
		throw;
	}
	node->next = where.ptr->next;
	where.ptr->next = node;
	m_size++;

	if (!node->next)
	{
		m_tail = node;
	}
}

template <typename T>
void List<T>::push_back(T&& t)
{
	emplace_back(std::move(t));
}

template <typename T>
void List<T>::push_back(T const& t)
{
	emplace_back(t);
}

template<typename T>
template<typename... U>
void List<T>::emplace_back(U&&... u)
{
	if (!m_tail)
		return emplace_front(std::forward<U>(u)...);
	try {
		m_tail->next = new Node{ nullptr, std::forward<U>(u)... };
	}
	catch (...) {
		delete m_tail->next;
		throw;
	}
	m_tail = m_tail->next;
	++m_size;
}

template <typename T>
void List<T>::push_front(T&& t)
{
	emplace_front(std::move(t));
}

template <typename T>
void List<T>::push_front(T const& t)
{
	emplace_front(t);
}

template <typename T>
template <typename... U>
void List<T>::emplace_front(U&&... u)
{
	try {
		m_head = new Node{ m_head, std::forward<U>(u)... };
	}
	catch (...) {
		delete m_head;
		throw;
	}
	++m_size;

	if (!m_tail)
		m_tail = m_head;
}

template <typename T>
typename List<T>::iterator List<T>::erase_after(typename List::iterator it)
{
	if (!it.ptr)
		return iterator(nullptr);

	auto temp = it.ptr->next;

	it.ptr->next = temp->next;
	m_size--;

	if (!it.ptr->next)
	{
		m_tail = it.ptr;
	}

	delete temp;

	return iterator(it.ptr->next);
}

template <typename T>
void List<T>::clear()
{
	while (!empty())
	{
		pop_front();
	}
}

template <typename T>
void List<T>::pop_front()
{
	if (!m_head)
		return;

	auto temp = m_head;

	m_head = temp->next;

	if (!m_head)
		m_tail = nullptr;

	m_size--;

	delete temp;
}

template <typename T>
std::size_t List<T>::size() const
{
	return m_size;
}

template <typename T>
bool List<T>::empty() const
{
	return m_size == 0;
}

template <typename T>
List<T>& List<T>::operator=(List other)
{
	other.swap(*this);

	return *this;
}

template <typename T>
List<T>& List<T>::operator=(List&& other) noexcept
{
	other.swap(*this);
	return *this;
}

template <typename T>
List<T>& List<T>::operator=(std::initializer_list<T> list)
{
	clear();

	for (const auto& i : list)
	{
		push_back(i);
	}

	return (*this);
}

template <typename T>
void List<T>::swap(List& other) noexcept
{
	using std::swap;

	swap(m_head, other.m_head);
	swap(m_tail, other.m_tail);
	swap(m_size, other.m_size);
}

template <typename T>
void print(List<T> const& list)
{
	for (auto it = list.cbegin(); it != list.cend(); ++it)
		std::cout << *it << " ";

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

template <typename T>
List<T> f(List<T> a)
{
	return a;
}

int main()
{
	try
	{
		// testing contructor initialize list
		List<int> listin({ 100, 200, 300, 400 });

		for (const auto& i : listin)
			std::cout << i << ' ';std::cout << "\n\n";

		List<int> listina = { 111, 222, 333, 444 };
		for (const auto& i : listina)
			std::cout << i << ' ';std::cout << "\n\n";

		for (const auto& i : listin)
			std::cout << i << ' ';std::cout << "\n\n";

		List<int> listino = std::move(listin);// move-construct from xvalue
		std::fill(listino.begin(), listino.end(), 99);
		std::copy(listino.begin(), listino.end(), std::ostream_iterator<int>(std::cout, " "));

		std::cout << '\n';
		for (const auto& i : listin)
			std::cout << i << ' ';

		List<int> listino1 = f(List<int>()); // move-construct from rvalue temporary
		std::cout << "\n\n list size: " << listino1.size() << "\n\n";

		for (auto it = listin.begin(); it != listin.end(); ++it)
		{
			listin.erase_after(it);
		}

		for (const auto& i : listin)
			std::cout << i << ' ';

		std::cout << "\n\n list size: " << listin.size() << "\n\n";

		List<int> list;

		// testing push_back and push_front
		list.push_back(3);
		list.push_back(4);
		list.push_front(2);
		list.push_front(1);

		// testing assign n copy contructors
		List<int> list3(list.begin(), list.end());


		for (const auto& i : list)
			std::cout << i << ' ';

		std::cout << "\n\n list size: " << list.size() << "\n\n";

		// testing STL
		std::fill(list3.begin(), list3.end(), 100);
		std::copy(list3.begin(), list3.end(), std::ostream_iterator<int>(std::cout, " "));

		std::cout << "\n\n list size: " << list3.size() << "\n\n";
		List<int> list2;
		list2 = list;

		for (const auto& i : list)
			std::cout << i << ' ';

		std::cout << "\n\n list size: " << list.size() << "\n\n";

		// testing STL
		std::fill(list2.begin(), list2.end(), 100);
		std::copy(list2.begin(), list2.end(), std::ostream_iterator<int>(std::cout, " "));

		std::cout << "\n\n list size: " << list2.size() << "\n\n";
		// ITERATORS
		List<int>::iterator it = list.begin();
		List<int>::const_iterator cit = list.cbegin();

		// testing insert_after
		list.insert_after(it, 200);

		for (const auto& i : list)
			std::cout << i << ' ';

		std::cout << "\n\n list size: " << list.size() << "\n\n";

		// test comparison types
		if (it == cit)
			std::cout << " two-way comparison: pass, we are good!\n\n";

		// testing erase_after
		++it;
		list.erase_after(++it);
		print(list);

		// testing incr
		it = list.begin();
		++it;
		*it = 10;
		print(list);

		std::cout << "\n list size: " << list.size() << "\n\n";

		// testing clear
		list.clear();

		if (list.empty())
			std::cout << "list is empty and its size: " << list.size() << std::endl;
	}
	catch (std::exception& e)
	{
		std::cout << "\nEXCEPTION: " << e.what() << std::endl;
	}
	std::cout << std::endl;
}