【C++进阶】深入STL之list：模拟实现深入理解List与迭代器

template<class T>
struct list_node
{
	T _data;
	list_node<T>* _next;
	list_node<T>* _prev;

	list_node(const T& x = T())
		:_data(x)
		,_next(nullptr)
		,_prev(nullptr)
	{}
};

template<class T>
struct list
{
	typedef list_node<T> Node;
public:
	// 构造函数等可能的其他成员函数... 
private:
	Node* _head;
};

void empty_init()
{
	_head = new Node;
	_head->_prev = _head;
	_head->_next = _head;
}

// 无参构造
list()
{
	empty_init();
}

void clear()
{
	// 依次清除节点
	itetator it = begin(); // 稍后会提到迭代器的模拟
	while(it != end())
	{
		it = erase(it);
	}	
}

~list()
{
	clear(); // 删除出头节点以外的所有节点
	delete _head; // 单独删除一下头节点
	_head = nullptr;
}

//list(const list<T>& lt)
list(list<T>& lt) // 还未实现const迭代器，先使用常规的
{
	empty_init();
	for (auto e : lt)
	{
		push_back(e); // push_back的实现其实是复用insert，文末有补充
	}
}

// 传统写法
list<T>& operator=(const list<T>& lt)
{
	clear(); // 先将原来的list清空
	for (auto e : lt)
	{
		push_back(e);
	}
	return *this;
}

// 现代写法
void swap(list<T>& tmp)
{
	std::swap(_head, tmp._head);
}

list<T>& operator=(list<T> lt)
{
	swap(lt);
	return *this;
}

template<class T>
struct __list_iterator
{
	typedef list_node<T> Node;
	typedef __list_iterator<T> self;
	Node* _node;
	
	// 构造函数
	__list_iterator(Node* node)
		:_node(node)
	{}
};

self& operator++() // 前置++
{
	_node = _node->_next;
	return *this;
}

self& operator--() // 前置--
{
	_node = _node->_prev;
	return *this;
}

self operator++(int) // 后置++
{
	self tmp(*this);
	_node = _node->_next;
	return &tmp;
}

self operator--(int) // 后置--
{
	self tmp(*this);
	_node = _node->_prev;
	return &tmp;
}

bool operator!=(const self& tmp)
{
	return _node != tmp._node; 
}

bool operator-=(const self& tmp)
{
	return _node -= tmp._node;
}

//可读写
T& operator*()
{
	return _node->_data;
}
//可读写
T* operator->()
{
	return &_node->_data;
}
// it.operator->()-> 编译器帮我们省略了一个箭头->  it->

template<class T>
struct list
{
	typedef list_node<T> Node;
public:
	typedef __list_iterator<T> iterator;
	
	iterator begin()
	{
		//return iterator(_head->_next); // 匿名对象
		return _head->next;
	}
	iterator end()
	{
		//return iterator(_head); // 匿名对象
		return _head;
	}
private:
	Node* _head;
};

template<class T>
struct __list_const_iterator
{
	typedef list_node<T> Node;
	typedef __list_const_iterator<T> self;
	Node* _node;
	
	// 构造函数
	__list_const_iterator(Node* node)
		:_node(node)
	{}

	//可读不可写
	const T& operator*()
	{
		return _node->_data;
	}
	//可读不可写
	const T* operator->()
	{
		return &_node->_data;
	}
	// 可能的其他成员函数... 
};

// 用一个模板来解决 const与非const
template<class T, class Ref, class Ptr>
struct __list_iterator
{
	typedef list_node<T> Node;
	// 会实例化成最匹配的
	typedef __list_iterator<T, Ref, Ptr> self;
	Node* _node;
	
	// 构造函数
	__list_iterator(Node* node)
		:_node(node)
	{}
	
	Ref operator*()
	{
		return _node->_data;
	}

	Ptr operator->()
	{
		return &_node->_data;
	}
	// 可能的其他成员函数... 
};
template<class T>
struct list
{
	typedef list_node<T> Node;
public:
	typedef __list_iterator<T, T&, T*> iterator;
	typedef __list_const_iterator<T, const T&, const T*>  const_iterator;
	
	iterator begin()
	{
		return _head->next;
	}
	iterator end()
	{
		return _head;
	}
	const_iterator begin() const
	{
		return _head->next;
	}
	const_iterator end() const
	{
		return _head;
	}
private:
	Node* _head;
};

void print_list(const list<int>& lt)
{
	// list<T>没有实例化话，就并不能去遍历寻找
	// 编译器不知道 list<T>::const_iterator 是内嵌类型，还是静态成员变量
	list<int>::const_iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << *it << " ";
		++it;
	}
}
void test_list()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	print_list(lt);
	cout << endl;
}

template<typename T>
void print_list(const list<T>& lt)
{
	......
	// typename 就是告诉编译器，这是一个类型，等list实例化之后再去取
	typename list<T>::const_iterator it = lt.begin();
	......
}

// 这里直接搞了一个Container来适配容器
template<typename Container>
void print_container(const Container& con)
{
	typename  Container::const_iterator it = con.begin();
	while (it != con.end())
	{
		cout << *it << " ";
		++it;
	}
}

// insert会返回插入位置的一个迭代器
iterator insert(iterator pos, const T& x)
{
	Node* newnode = new Node(x);
	Node* cur = pos._node;
	Node* prev = cur->_prev;

	prev->_next = newnode;
	newnode->_prev = prev;

	cur->_prev = newnode;
	newnode->_next = cur;

	return iterator(newnode); // 匿名对象
}
// erase会返回删除位置的next节点的迭代器
iterator erase(iterator pos)
{
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* next = cur->_next;
			
	delete cur;
	prev->_next = next->_prev;
	next->_prev = prev->_next;

	return iterator(next); // 匿名对象
}
// erase和insert的复用
void push_back(const T& x) // 尾插
{
	insert(end(), x);
}
void push_front(const T& x) // 头插
{
	insert(begin(), x);
}
void pop_back() // 尾删
{
	erase(end());
}
void pop_front() // 头删
{
	erase(begin());
}