[数据结构与算法]带头节点的双向循环链表的模拟实现以及链表内部算法的实现（排序、逆置）和内部迭代器的封装

#include<iostream>
using namespace std;
//定义链表节点
template<class T>
struct CBListNode {
	CBListNode(const T& x=T())//链表节点构造函数
		:data(x)
		, next(nullptr)
		, prev(nullptr)
	{}
	T data;//数据域
	CBListNode<T>* next;
	CBListNode<T>* prev;
};
//封装迭代器
template<class T>
class CBListIterator {
public:
	typedef CBListNode<T> Node;
	typedef CBListIterator<T> Self;
public:
	CBListIterator( Node* node)
		:_node(node)
	{}
	T& operator*() {
		return _node->data;
	}
	T* operator->() {
		return &(operator*());
	}
	bool operator==(const Self& s) {
		return _node == s._node;
	}
	bool operator!=(const Self& s) {
		return _node != s._node;
	}
	Self& operator++() {
		_node = _node->next;
		return *this;
	}
	Self& operator++(int) {
		Self temp = *this;
		_node = _node->next;
		return temp;
	}
	Self& operator--() {
		_node = _node->prev;
		return this;
	}
	Self& operator--(int) {
		Self temp = this;
		_node = _node->prev;
		return temp;
	}
private:
	Node* _node;
};
//带头结点的双向循环链表的实现

template<class T>
class CBList {
public:
	typedef CBListNode<T> Node;
	typedef CBListIterator<T> iterator;
public:
	//构造函数
	CBList()
		:_head(new Node)//构造头节点
		,_size(0)//计数器，记录链表中元素个数
	{
		//双向循环链表初始哈是头节点的两个指针指向自身
		_head->next = _head;
		_head->prev = _head;
	}
	//下面是两个两个位置的迭代器，依靠这两个迭代器可以实现范围for
	iterator begin() {
		return iterator(_head->next);
	}
	iterator end() {
		return iterator(_head);
	}
	//尾插
	void push_back(const T& val) {
		Node* newnode = new Node(val);
		newnode->next = _head;
		newnode->prev = _head->prev;
		_head->prev->next = newnode;
		_head->prev = newnode;
		_size++;
	}
	//头插
	void push_front(const T& val) {
		Node* newnode = new Node(val);
		newnode->next = _head->next;
		_head->next->prev = newnode;
		newnode->prev = _head;
		_head->next = newnode;
		_size++;
	}
	//尾删
	void pop_back() {
		if (_size == 0) {
			return;//表示链表为空
		}
		Node* delnode = _head->prev;
		delnode->prev->next = _head;
		_head->prev = delnode->prev;
		delete delnode;
		delnode = nullptr;
		_size--;
	}
	//头删
	void pop_front() {
		if (_size == 0) {
			return;//链表为空不做删除
		}
		Node* delnode = _head->next;
		_head->next = delnode->next;
		delnode->next->prev = _head;
		delete delnode;
		delnode = nullptr;
		_size--;
	}
	//打印链表
	void show_list() {
		Node* p = _head->next;
		while (p != _head && p!=nullptr) {
			cout << p->data << " ";
			p = p->next;
		}
	}
	//按值删除
	void pop_list_by_val(const T& key) {
		if (_size == 0) {
			return;//链表为空不做删除操作
		}
		Node* delnode = _head->next;
		while(delnode != _head && delnode->data != key)
			delnode = delnode->next;//查找待删除元素位置

		if (delnode->data == key) {
			delnode->prev->next = delnode->next;
			delnode->next->prev = delnode->prev;
			delete delnode;
			delnode = nullptr;
			_size--;
		}
		else//可能元素不存在
			return;
	}
	//按值查找，返回所在链表第几个位置上的元素
	int find_by_val(const T& key) {
		Node* cur = _head->next;
		size_t count = 1;
		while (cur != _head) {
			if (cur->data == key) {
				return count;
			}
			count++;
			cur = cur->next;
		}
		//如果没有找到，返回-1
		return -1;
	}
	//修改元素
	void modifiy_val(const T& key,const T& val) {
		Node* cur = _head->next;
		//按key值查找待修改元素位置
		while (cur != _head && cur->data != key) {
			cur = cur->next;
		}
		if (cur->data == key) {
			cur->data = val;
		}
	}
	//清空链表中元素，但不删除头节点
	void clear() {
		Node* cur = _head->next;
		while (cur != _head) {
			Node* p = cur->next;
			free(cur);
			cur = p;
		}
		_head->next = _head->prev = _head;
		_size = 0;
	}
	//按值插入，按升序插入，较大元素插入较小元素后面
	void List_insert_byval(const T& val) {
		Node* cur = _head->next;
		//查找待插入位置
		while (cur != _head && val > cur->data) {
			cur = cur->next;
		}

		Node* newnode = new Node(val);
		newnode->next = cur;
		newnode->prev = cur->prev;
		cur->prev->next = newnode;
		cur->prev = newnode;

		_size++;
	}
	//链表排序
	void List_sort() {
		if (_size == 1 || _size == 0) {
			return;
		}//如果元素为0或1不做排序
		Node* p = _head->next;
		Node* q = p->next;
		//根据标记元素位置拆分链表
		p->next = _head;
		_head->prev = p;
		//将后段元素依次按升序插入
		while (q != _head) {
			p = q;
			q = p->next;
			Node* tmp = _head->next;
			//查找带插入位置
			while (tmp!=_head&&p->data > tmp->data) {
				tmp = tmp->next;
			}
			p->next = tmp;
			p->prev = tmp->prev;
			tmp->prev->next = p;
			tmp->prev = p;
		}
	}
	//链表逆置
	void List_reverse() {
		//如果链表元素个数为0或1，不做操作
		if (_size == 1 || _size == 0) {
			return;
		}
		Node* p = _head->next;
		Node* q = p->next;
		//拆链表
		p->next = _head;
		_head->prev = p;
		//将拆下来元素依次使用头插法插入链表
		while (q != _head) {
			p = q;
			q = p->next;

			p->next = _head->next;
			p->prev = _head;
			_head->next->prev = p;
			_head->next = p;
		}
	}
	//返回链表中元素个数
	size_t size() {
		return _size;
	}
	//返回第一个元素的值
	T& first_val(){
		return _head->next->data;
	}
	//返回最后一个元素的值
	T& Last_val() {
		return _head->prev->data;
	}
	//析构函数
	~CBList()
	{
		_destory();
	}
private:
	Node* _head;
	size_t _size;
private:
	void _destory() {
		//清空链表之后回收头节点
		clear();
		free(_head);
		_head = nullptr;

	}
};