list.h

#ifdef _WIN32
#pragma once
#endif

#ifndef LIST_H_
#define LIST_H_
#include <iterator>
#include <stdexcept>

template<typename Elem>
class Link
{
public:
	Link *prev;
	Link *succ;
	Elem val;
};

template<typename Elem>
class list
	// representation and implementation details
{
public:
	using size_type = std::size_t;
	using value_type = Elem;
	using iterator_category = std::bidirectional_iterator_tag;
	using pointer = Elem*;
	using const_pointer = const Elem*;
	using reference = Elem&;
	using const_reference = const Elem&;
	using difference_type = std::ptrdiff_t;
	class iterator : public std::iterator<iterator_category, value_type, difference_type, pointer, reference>	                                
	{
		Link<Elem> *curr;	// current link
	public:
		iterator(Link<Elem> *p)
			: curr{ p } { }
		iterator()
			: curr{ nullptr } {}

		auto &operator++();		// forward
		auto &operator--();		// backword
		auto operator++(int);
		auto operator--(int);
		Elem &operator*() 
		{ 
			if (!curr)
			{
				throw std::out_of_range{ "current link is nullptr" };
			}
			return curr->val; 
		}

		bool operator==(const iterator &b) { return curr == b.curr; }
		bool operator!=(const iterator &b) { return curr != b.curr; }

		Link<Elem> *current_link() 
		{ 
			if (!curr)
			{
				throw std::out_of_range{ "current link is nullptr" };
			}
			return curr;
		}
	};

	class const_iterator : public std::iterator<iterator_category, value_type, difference_type, const_pointer, const_reference>
	{
		Link<Elem> *curr;	// current link
	public:
		const_iterator(Link<Elem> *p)
			: curr{ p } { }
		const_iterator()
			: curr{ nullptr } {}

		auto &operator++();		// forward
		auto &operator--();		// backword
		auto operator++(const int);
		auto operator--(const int);
		const Elem &operator*() const 
		{ 
			if (!curr)
			{
				throw std::out_of_range{ "current link is nullptr" };
			}
			return curr->val; 
		}

		bool operator==(const const_iterator &b) { return curr == b.curr; }
		bool operator!=(const const_iterator &b) { return curr != b.curr; }

		const Link<Elem> *current_link() const 
		{ 
			if (!curr)
			{
				throw std::out_of_range{ "current link is nullptr" };
			}
			return curr; 
		}
	};

	class reverse_iterator : public std::reverse_iterator<iterator>
	{
		Link<Elem> *curr;	// current link
		iterator iter;
	public:
		reverse_iterator(Link<Elem> *p)
			: curr{ p }, iter { curr } { }

		auto &operator++();		// forward
		auto &operator--();		// backword
		auto operator++(int);
		auto operator--(int);
		iterator base() const { return iter; }
		Elem &operator*() 
		{ 
			if (!curr)
			{
				throw std::out_of_range{ "current link is nullptr" };
			}
			return curr->val; 
		}

		bool operator==(const reverse_iterator &b) { return curr == b.curr; }
		bool operator!=(const reverse_iterator &b) { return curr != b.curr; }

		Link<Elem> *current_link() 
		{
			if (!curr)
			{
				throw std::out_of_range{ "current link is nullptr" };
			}
			return curr; 
		}
	};

	class const_reverse_iterator : public std::reverse_iterator<const_iterator>
	{
		Link<Elem> *curr;	// current link
		const_iterator iter;
	public:
		const_reverse_iterator(Link<Elem> *p)
			: curr{ p }, iter{ curr } { }

		auto &operator++();		// forward
		auto &operator--();		// backword
		auto operator++(int);
		auto operator--(int);
		const_iterator base() const { return iter; }
		const Elem &operator*() const
		{
			if (!curr)
			{
				throw std::out_of_range{ "current link is nullptr" };
			}
			return curr->val;
		}

		bool operator==(const const_reverse_iterator &b) { return curr == b.curr; }
		bool operator!=(const const_reverse_iterator &b) { return curr != b.curr; }

		const Link<Elem> *current_link() const
		{
			if (!curr)
			{
				throw std::out_of_range{ "current link is nullptr" };
			}
			return curr;
		}
	};

	list(const Elem &v);

	list()
		: first{ nullptr }, last{ nullptr }, num_nodes{ 0 } { }

	list(std::initializer_list<Elem> lst);

	list(const list<Elem> &other);

	explicit list(size_type count);

	~list()
	{
		while (last)
		{
			auto temp = last->prev;
			delete last;
			last = temp;
		}
		first = nullptr;
		last = first;
	}

	iterator begin() noexcept { return iterator(first); }
	iterator end() noexcept { return iterator(last->succ); }
	const_iterator cbegin() const noexcept { return const_iterator(first); }
	const_iterator cend() const noexcept { return const_iterator(last->succ); }
	reverse_iterator rbegin() noexcept { return reverse_iterator(last); }
	reverse_iterator rend() noexcept { return reverse_iterator(first->prev); }
	const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator(last); }
	const_reverse_iterator crend() const noexcept { return const_reverse_iterator(first->prev); }

	size_type size() const { return num_nodes; }

	auto insert(iterator p, const Elem &v);		// insert v into list before p
	auto erase(iterator p);						// remove v at p from list
	const_iterator erase(const_iterator p);

	void push_back(const Elem &v);					// insert v at end
	void push_front(const Elem &v);					// insert v at front
	void pop_front();		// remove the first element
	void pop_back();		// remove the last element

	bool empty();

	Elem &front() { return first->val; }		// the first element
	Elem &back() { return last->val; }			// the last element

	list &operator=(const list &other);

private:
	Link<Elem> *first;
	Link<Elem> *last;
	size_type num_nodes;
};

#endif

template<typename Elem>
list<Elem>::list(const Elem &v)
	: first{ nullptr }, last{ nullptr }, num_nodes{ 0 }
{
	Link<Elem> *new_node = new Link<Elem>;
	new_node->prev = nullptr;
	new_node->succ = last;
	new_node->val = v;
	first = new_node;
	last = first;
	num_nodes++;
}

template<typename Elem>
list<Elem>::list(typename list<Elem>::size_type count)
	: first{ nullptr }, last{ nullptr }, num_nodes{ 0 }
{
	for (size_type i = 0; i < count; ++i)
	{
		Link<Elem> *new_node = new Link<Elem>;
		new_node->prev = nullptr;
		new_node->succ = nullptr;
		new_node->val = Elem{};
		push_back(new_node);
	}
}

template<typename Elem>
auto &list<Elem>::iterator::operator++()
{ 
	if (curr == nullptr)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->succ;
	return *this; 
}

template<typename Elem>
auto &list<Elem>::iterator::operator--()
{ 
	if (curr == nullptr)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->prev;
	return *this; 
}

template<typename Elem>
auto &list<Elem>::const_iterator::operator++()
{
	if (curr == nullptr)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->succ;
	return *this;
}

template<typename Elem>
auto &list<Elem>::reverse_iterator::operator++()
{
	if (curr == nullptr)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->prev;
	return *this;
}

template<typename Elem>
auto &list<Elem>::reverse_iterator::operator--()
{
	if (curr == nullptr)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->succ;
	return *this;
}

template<typename Elem>
auto &list<Elem>::const_reverse_iterator::operator++()
{
	if (curr == nullptr)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->prev;
	return *this;
}

template<typename Elem>
auto &list<Elem>::const_reverse_iterator::operator--()
{
	if (curr == nullptr)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->succ;
	return *this;
}

template<typename Elem>
auto &list<Elem>::const_iterator::operator--()
{
	if (curr == nullptr)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->prev;
	return *this;
}

template<typename Elem>
auto list<Elem>::iterator::operator++(int)
{ 
	auto ret = *this; 
	if (curr == nullptr)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->succ;
	return ret; 
}

template<typename Elem>
auto list<Elem>::iterator::operator--(int)
{ 
	auto ret = *this; 
	if (curr == nullptr)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->prev;
	return ret; 
}

template<typename Elem>
auto list<Elem>::reverse_iterator::operator++(int)
{
	auto ret = *this;
	if (curr == nullptr)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->prev;
	return ret;
}

template<typename Elem>
auto list<Elem>::const_reverse_iterator::operator++(int)
{
	auto ret = *this;
	if (curr == nullptr)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->prev;
	return ret;
}

template<typename Elem>
auto list<Elem>::const_reverse_iterator::operator--(int)
{
	auto ret = *this;
	if (curr == nullptr)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->succ;
	return ret;
}

template<typename Elem>
auto list<Elem>::reverse_iterator::operator--(int)
{
	auto ret = *this;
	if (curr == nullptr)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->succ;
	return ret;
}

template<typename Elem>
auto list<Elem>::const_iterator::operator++(const int)
{ 
	auto ret = *this; 
	if (curr == nullptr)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->succ;
	return ret; 
}

template<typename Elem>
auto list<Elem>::const_iterator::operator--(const int)
{ 
	auto ret = *this; 
	if (curr == nullptr)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->prev;
	return ret; 
}

template<typename Elem>
list<Elem>::list(const list<Elem> &other)
	: first{ nullptr }, last{ nullptr }, num_nodes{ 0 }
{
	Link<Elem> *temp = other.first;
	num_nodes = 0;
	for (auto iter = other.cbegin(); iter != other.cend(); ++iter)
	{
		push_back(temp->val);
		temp = temp->succ;
	}
}

template<typename Elem>
list<Elem>::list(std::initializer_list<Elem> lst)
	: first{ nullptr }, last{ nullptr }, num_nodes{ 0 }
{
	std::copy(lst.begin(), lst.end(), std::back_inserter(*this));
}

template<typename Elem>
list<Elem> &list<Elem>::operator=(const list<Elem> &other)
{
	list<Elem> temp{ other };
	std::swap(temp.first, first);
	return *this;
}

template<typename Elem>
auto list<Elem>::insert(iterator p, const Elem &v)
{
	Link<Elem> *new_node = new Link<Elem>;
	new_node->val = v;
	new_node->prev = nullptr;
	new_node->succ = nullptr;
	
	if (first == nullptr)
	{
		first = new_node;
		last = first;
		num_nodes++;
		return iterator(new_node);
	}
	else if (p.current_link())
	{
		new_node->succ = p.current_link();
		if (p.current_link()->prev)
		{
			p.current_link()->prev->succ = new_node;
		}
		new_node->prev = p.current_link()->prev;
		p.current_link()->prev = new_node;
		if (!new_node->prev)
		{
			first = new_node;
		}
		num_nodes++;
		return iterator(new_node);
	}
	return p;
}

template<typename Elem>
auto list<Elem>::erase(iterator p)
{
	if (p.current_link())
	{
		if (p.current_link()->succ)
		{
			p.current_link()->succ->prev = p.current_link()->prev;
		}
		if (p.current_link()->prev)
		{
			p.current_link()->prev->succ = p.current_link()->succ;
		}
		if (p.current_link()->succ == nullptr)
		{
			last = p.current_link()->prev;
		}
		if (!p.current_link()->prev)
		{
			first = p.current_link()->succ;
		}
		Link<Elem> *next = p.current_link()->succ;
		delete p.current_link();
		num_nodes--;
		return iterator(next);
	}
	return p;
}

template<typename Elem>
typename list<Elem>::const_iterator list<Elem>::erase(const_iterator p)
{
	if (p.current_link())
	{
		if (p.current_link()->succ)
		{
			p.current_link()->succ->prev = p.current_link()->prev;
		}
		if (p.current_link()->prev)
		{
			p.current_link()->prev->succ = p.current_link()->succ;
		}
		if (p.current_link()->succ == nullptr)
		{
			last = p.current_link()->prev;
		}
		if (!p.current_link()->prev)
		{
			first = p.current_link()->succ;
		}
		Link<Elem> *next = p.current_link()->succ;
		delete p.current_link();
		num_nodes--;
		return const_iterator(next);
	}
	return p;
}

template<typename Elem>
void list<Elem>::push_back(const Elem &v)
{
	Link<Elem> *new_node = new Link<Elem>;
	new_node->val = v;
	new_node->prev = nullptr;
	new_node->succ = nullptr;

	if (first == nullptr)
	{
		last = new_node;
		first = last;
		num_nodes++;
	}
	else
	{
		last->succ = new_node;
		new_node->prev = last;
		last = new_node;
		num_nodes++;
	}
}

template<typename Elem>
void list<Elem>::push_front(const Elem &v)
{
	Link<Elem> *new_node = new Link<Elem>;
	new_node->val = v;
	new_node->prev = nullptr;
	new_node->succ = nullptr;

	if (first == nullptr)
	{
		first = new_node;
		last = first;
		num_nodes++;
	}
	else
	{
		first->prev = new_node;
		new_node->succ = first;
		first = new_node;
		num_nodes++;
	}
}

template<typename Elem>
void list<Elem>::pop_back()
{
	iterator iter = iterator{ last };
	iter.current_link()->prev->succ = iter.current_link()->succ;
	last = iter.current_link()->prev;
	Link<Elem> *temp = iter.current_link()->prev;
	delete iter.current_link();
	temp->succ = nullptr;
	num_nodes--;
}

template<typename Elem>
void list<Elem>::pop_front()
{
	iterator iter = begin();
	iter.current_link()->succ->prev = iter.current_link()->prev;
	first = iter.current_link()->succ;
	Link<Elem> *temp = iter.current_link()->succ;
	delete iter.current_link();
	temp->prev = nullptr;
	num_nodes--;
}

template<typename Elem>
bool list<Elem>::empty()
{
	if (first != nullptr)
	{
		return false;
	}
	return true;
}

template<typename Iter>
void advance(Iter &p, int n)
{
	if (n > 0)
	{
		while (n > 0)
		{
			++p;
			--n;
		}
	}
	else if (n < 0)
	{
		while (n < 0)
		{
			--p;
			++n;
		}
	}
}

main.cpp

// Osman Zakir
// 11 / 11 / 2017
// Bjarne Stroustrup: Programming: Principles and Practice Using C++ 2nd Edition
// Chapter 20 Section 20.4: Linked Lists

#include "../../cust_std_lib_facilities.h"
#include <stdexcept>
#include <iostream>
#include "list.h"
#include <vld.h>

template<typename Iter>
Iter high(Iter first, Iter last);
void f();

int main()
{
	f();
	std::cin.ignore(32767, '\n');
	std::cin.clear();
	keep_window_open();
}

template<typename Iter>
Iter high(Iter first, Iter last)
// return an iterator to the element in [first,last) that has the highest value
{
	Iter high = first;
	for (Iter p = first; p != last; ++p)
	{
		if (*high < *p)
		{
			high = p;
		}
	}
	return high;
}

void f()
{
	list<int> lst;
	for (int x; std::cin >> x;)
	{
		lst.push_back(x);
	}
	std::cin.ignore(32767, '\n');
	std::cin.clear();

	list<int>::iterator iter = lst.begin();
	iter = lst.insert(iter, 0);
	std::cout << "lst:\n";
	for (auto it = lst.begin(); it != lst.end(); ++it)
	{
		std::cout << *it << '\n';
	}

	std::cout << "lst in reverse:\n";
	try
	{
		for (auto it = lst.crbegin(); it != lst.crend(); ++it)
		{
			std::cout << *it << '\n';
		}
	}
	catch (const std::out_of_range &oor)
	{
		std::cerr << "Exception caught: " << oor.what() << '\n';
	}
	catch (...)
	{
		std::cerr << "Structural exception caught\n";
	}

	list<int>::iterator p2 = high(lst.begin(), lst.end());
	std::cout << "The highest value was " << *p2 << '\n';
}