[数据结构与算法]list容器模拟实现及使用——C++

一、list容器基本概念

• list容器使用链表存储，链表是由一系列节点构成，每个节点都有自己的存储空间。
• list容器中的链表是双向环状链表链表，其尾节点指向头节点
  

二、链表节点结构体

template<typename T>
	struct ListNode
	{
		ListNode<T>*_prev;
		ListNode<T>*_next;
		T _data;
	};

使用模板，包含一个前指针，一个后指针，和一个数据域

三、迭代器构建

//Ref指T&引用，Ptr指T*指针，采用三个参数是为了便于const迭代器构建，只需在后两个参数前加上const限定即可，不必重写一个
template<typename T, typename Ref, typename Ptr>
	class ListIterator
	{
	public:
		ListNode<T>*_node;
		typedef ListNode<T> Node;
		typedef ListIterator<T, Ref, Ptr> self;
		ListIterator(Node*node)//构造函数
		{
			this->_node = node;
		}
		Ref operator*()//解引用
		{
			return this->_node->_data;
		}
		Ptr &operator->()//指针访问
		{
			return &(this->_node->_data);
		}
		self&operator++()//前置++
		{
			this->_node = this->_node->_next;
			return *this;
		}
		self&operator++(int)//后置++
		{
			self temp(*this);
			this->_node = this->_node->_next;
			return temp;
		}
		self&operator--()//前置--
		{
			this->_node = this->_node->_prev;
			return *this;
		}
		self&operator--(int)//后置--
		{
			self temp(*this);
			this->_node = this->_node->_prev;
			return temp;
		}
		bool operator!=(const self&it)
		{
			return this->_node != it._node;
		}
		bool operator==(const self&it)
		{
			return this->_node == it._node;
		}
	};

这是一个双向迭代器，即可正向访问，也可反向访问，因为重载了++和–

四、list类成员、命名及构造函数

public:
		typedef ListNode<T> Node;
		typedef ListIterator<T, T&, T*> iterator;
		typedef ListIterator<T, const T&, const T*> const_iterator;
	private:
		Node*_head;
		void CreatHead()
		{
			this->_head = new Node;
			this->_head->_prev = this->_head->_next = this->_head;
		}

私有成员为一个头指针，简化模板迭代器命名，CreatHead在构造函数中多次用到，简化为一个函数，避免重复代码
以下函数均在类外实现

template<typename T>
	mlist<T>::mlist()//无参构造
	{
		this->CreatHead();
	}
	template<typename T>
	mlist<T>::mlist(iterator begin, iterator end)//迭代器构造
	{
		this->CreatHead();
		while (begin != end)
		{
			this->push_back(*begin);//采用类内函数调用实现，减少代码量
			++begin;
		}
	}
	template<typename T>
	mlist<T>::mlist(size_t n, const T & elmn)//传入n个elmn
	{
		this->CreatHead();
		for (size_t i = 0; i < n; i++)
			this->push_back(elmn);
	}
	template<typename T>
	mlist<T>::mlist(mlist<T> & list)//拷贝构造
	{
		this->CreatHead();
		this->assign(list.begin(), list.end());
	}

五、assign()函数

赋值函数

template<typename T>
	void mlist<T>::assign(iterator begin, iterator end)
	{
		this->CreatHead();
		this->insert(this->begin(), begin, end);
	}
	template<typename T>
	void mlist<T>::assign(size_t n, const T & elmn)
	{
		this->CreatHead();
		for (size_t i = 0; i < n; i++)
			this->push_back(elmn);
	}

迭代器的赋值函数还可以有const的版本，这里就不在多写，过于麻烦，这样，insert函数也要写const版本，很多函数都要在写个const版本，这就是个只读限定，防止数据被修改

六、重载=号运算符

template<typename T>
	mlist<T> & mlist<T>::operator=(mlist<T> & list)
	{
		this->CreatHead();
		this->assign(list.begin(),list.end());
		return*this;
	}

用assign赋值，返回本身

七、swap()交换函数

template<typename T>
	void mlist<T>::swap(mlist<T> & list)
	{
		std::swap(this->_head, list._head);
	}

调用std的swap交换对象中的头节点即可实现交换

八、size()函数和empty()函数

template<typename T>
	size_t mlist<T>::size()
	{
		size_t count = 0;
		for (mlist<T>::iterator it = this->begin(); it != this->end(); it++)
			count++;
		return count;
	}
	template<typename T>
	bool mlist<T>::empty()
	{
		return this->begin() == this->end();
	}

遍历链表计数
头尾相等为空

九、resize()函数

指定链表长度

template<typename T>
	void mlist<T>::resize(size_t n, const T & elmn)
	{
		size_t len = this->size();
		if (n <= len)//缩小删除
		{
			for (size_t i = n; i < len; i++)
				this->pop_back();
		}
		else
			this->insert(this->end(), n - len, elmn);//增大插入元素
	}

现在想想不用写两个，用一个默认值（声明与定义只能标明一处，这里默认为0）实现，避免函数重载

十、头尾的删除、增添、取值

template<typename T>
	void mlist<T>::push_back(const T & elmn)
	{
		insert(this->end(), elmn);
	}
	template<typename T>
	void mlist<T>::pop_back()
	{
		this->erase(--this->end());
	}
	template<typename T>
	void mlist<T>::push_front(const T & elmn)
	{
		this->insert(this->begin(), elmn);
	}
	template<typename T>
	void mlist<T>::pop_front()
	{
		this->erase(this->begin());
	}

template<typename T>
	T & mlist<T>::front()
	{
		return this->begin()._node->_data;
	}

	template<typename T>
	T & mlist<T>::back()
	{
		return (--this->end())._node->_data;
	}

	template<typename T>
	const T & mlist<T>::front() const
	{
		return this->begin()._node->_data;
	}

	template<typename T>
	const T & mlist<T>::back() const
	{
		return (--this->end())._node->_data;
	}

插入和删除都用insert和erase去实现(之前还傻呼呼都写一遍），这里有const版本的，如果直接传入常量，会调用const版，传入变量，会调用非const修饰的函数.注意end要先减1才能取得最后一个元素。

十一、insert()函数

template<typename T>
	typename mlist<T>::iterator mlist<T>::insert(iterator pos, const T & elmn)
	{
		Node*node = new Node, *Pos = pos._node;
		node->_data = elmn;
		node->_next = Pos;
		node->_prev = Pos->_prev;
		Pos->_prev->_next = node;
		Pos->_prev = node;
		return iterator(node);
	}

	template<typename T>
	void mlist<T>::insert(iterator pos, size_t n, const T & elmn)
	{
		while (n--)
		{
			this->insert(pos, elmn);
		}
	}

	template<typename T>
	void mlist<T>::insert(iterator pos, iterator begin, iterator end)
	{
		while (begin != end)
		{
			this->insert(pos, begin._node->_data);
			begin++;
		}
	}

这次终于明白迭代器返回类型的函数写在类外为啥会报错了，没有指明迭代器是模板名，如让面第一个函数，加个typename就好了。
因为是双向指针，插入有点麻烦，但很好理解，让插入位置的前一个节点的next指向node,node的前指针指向插入位置前一节点，node的next指向插入位置节点，插入位置节点的prev指向node，完成，但需要靠插入位置节点的前指针引导设置，要注意设置顺序。

十二、erase()、clear()和remove()函数

template<typename T>
	void mlist<T>::clear()
	{
		this->erase(this->begin(), this->end());
	}

	template<typename T>
	typename mlist<T>::iterator mlist<T>::erase(iterator begin, iterator end)
	{
		iterator it = begin;
		while (it != end)
		{
			it = this->erase(it);//这里erase的返回值派上了用场，更新i的值
		}
		return it;
	}

	template<typename T>
	typename mlist<T>::iterator mlist<T>::erase(iterator pos)
	{
		Node*Pos = pos._node;
		if (pos == this->end())//到尾部无需删除
			return this->end();
		Node*node = Pos->_next;
		Pos->_prev->_next = node;
		node->_prev = Pos->_prev;
		delete Pos;
		Pos = NULL;
		return iterator(node);
	}

	template<typename T>
	void mlist<T>::remove(const T & elmn)
	{
		for (mlist<T>::iterator i = this->begin(); i != this->end(); i++)
		{
			if (i._node->_data == elmn)
				i=this->erase(i);//这里也要注意更新i值
		}
	}

十三、sort()函数

template<typename T>
	void mlist<T>::sort()
	{
		for (iterator i = this->begin(); i != this->end(); i++)
		{
			iterator min = i, ret = i;
			for (iterator j =ret++; j != this->end(); j++)
				if (min._node->_data > j._node->_data)
					min = j;
			if (min != i)
				std::swap(min._node->_data, i._node->_data);
		}
	}

我实力有限，拿个选择排序糊弄一下，这里应该是个归并排序，有时间再来研究吧
因为没有重载+号，而又不能在内层循环中改变i的值，所以用个ret赋值

十四、迭代器访问函数

template<typename T>
	typename mlist<T>::iterator mlist<T>::begin()
	{
		return iterator(this->_head->_next);
	}
	template<typename T>
	typename mlist<T>::iterator mlist<T>::end()
	{
		return iterator(this->_head);
	}
	template<typename T>
	typename mlist<T>::const_iterator mlist<T>::begin() const
	{
		return const_iterator(this->_head->_next);
	}
	template<typename T>
	typename mlist<T>::const_iterator mlist<T>::end() const
	{
		return const_iterator(this->_head);
	}

返回头尾迭代器，这个环形链表的头是end，存的data的值为随机值，因此访问最后一个元素要–end,头指针的下一个节点是正真的头，为第一个元素

十五、析构函数

template<typename T>
	mlist<T>::~mlist()
	{
		this->clear();
		delete this->_head;
		this->_head = NULL;
	}

用clear()清空数据，再将头指针置为NULL

十六、完整模拟实现源码

#pragma once
#include<iostream>
using namespace std;
namespace mxylist
{
	template<typename T>
	struct ListNode
	{
		ListNode<T>*_prev;
		ListNode<T>*_next;
		T _data;
	};
	template<typename T, typename Ref, typename Ptr>
	class ListIterator
	{
	public:
		ListNode<T>*_node;
		typedef ListNode<T> Node;
		typedef ListIterator<T, Ref, Ptr> self;
		ListIterator(Node*node)
		{
			this->_node = node;
		}
		Ref operator*()
		{
			return this->_node->_data;
		}
		Ptr &operator->()
		{
			return &(this->_node->_data);
		}
		self&operator++()
		{
			this->_node = this->_node->_next;
			return *this;
		}
		self&operator++(int)
		{
			self temp(*this);
			this->_node = this->_node->_next;
			return temp;
		}
		self&operator--()
		{
			this->_node = this->_node->_prev;
			return *this;
		}
		self&operator--(int)
		{
			self temp(*this);
			this->_node = this->_node->_prev;
			return temp;
		}
		bool operator!=(const self&it)
		{
			return this->_node != it._node;
		}
		bool operator==(const self&it)
		{
			return this->_node == it._node;
		}
	};
	template<typename T>
	class mlist
	{
	public:
		typedef ListNode<T> Node;
		typedef ListIterator<T, T&, T*> iterator;
		typedef ListIterator<T, const T&, const T*> const_iterator;
	private:
		Node*_head;
		void CreatHead()
		{
			this->_head = new Node;
			this->_head->_prev = this->_head->_next = this->_head;
		}
	public:
		mlist();								//默认构造
		mlist(iterator begin, iterator end);	//构造函数将[begin，end]区间中的元素拷贝给本身
		mlist(size_t n, const T&elmn);			//构造函数将n个elmn拷贝给本身
		mlist(mlist<T>&list);				//拷贝构造函数
		void assign(iterator begin, iterator end);//将[begin，end]区间中的元素拷贝给本身
		void assign(size_t n, const T&elmn);	//将n个elmn拷贝给本身
		mlist&operator=(mlist<T>&list);		//重载=
		void swap(mlist<T>&list);						//将list的元素与本身的元素进行互换
		size_t size();								//返回容器元素个数
		bool empty();								//判断容器是否为空
		void resize(size_t n, const T&elmn = 0);		//重新指定容器长度，变成以默认指或传入值填充，变短，删除多余元素
		void push_back(const T&elmn);				//在容器尾部插入一个元素
		void pop_back();							//删除容器中最后一个元素
		void push_front(const T&elmn);				//在头部插入一个元素
		void pop_front();							//删除容器开头的一个元素
		iterator insert(iterator pos, const T&elmn);	//在pos处插入elmn元素，返回新数据的位置
		void insert(iterator pos, size_t n, const T&elmn);//在pos处插入n个elmn元素，无返回值
		void insert(iterator pos, iterator begin, iterator end);//在pos位置插入[begin，end]区间的数据，无返回值
		void clear();							//清除容器数据
		iterator erase(iterator begin, iterator end);//删除[begin，end]区间的数据，返回下一个数据的位置
		iterator erase(iterator pos);					//删除pos位置的数据，返回下一个数据的位置
		void remove(const T&elmn);					//删除容器中所有与elmn匹配的元素
		T&front();
		T&back();
		const T&front()const;						//返回第一个元素
		const T&back()const;						//返回最后一个元素
		void reverse();								//反转链表
		void sort();								//链表排序
		iterator begin();							//迭代器
		iterator end();
		const_iterator begin()const;
		const_iterator end()const;
		~mlist();									//析构函数
	};
	template<typename T>
	mlist<T>::mlist()
	{
		this->CreatHead();
	}
	template<typename T>
	mlist<T>::mlist(iterator begin, iterator end)
	{
		this->CreatHead();
		while (begin != end)
		{
			this->push_back(*begin);
			++begin;
		}
	}
	template<typename T>
	mlist<T>::mlist(size_t n, const T & elmn)
	{
		this->CreatHead();
		for (size_t i = 0; i < n; i++)
			this->push_back(elmn);
	}
	template<typename T>
	mlist<T>::mlist(mlist<T> & list)
	{
		this->CreatHead();
		this->assign(list.begin(), list.end());
	}
	template<typename T>
	void mlist<T>::assign(iterator begin, iterator end)
	{
		this->CreatHead();
		this->insert(this->begin(), begin, end);
	}
	template<typename T>
	void mlist<T>::assign(size_t n, const T & elmn)
	{
		this->CreatHead();
		for (size_t i = 0; i < n; i++)
			this->push_back(elmn);
	}
	template<typename T>
	mlist<T> & mlist<T>::operator=(mlist<T> & list)
	{
		this->CreatHead();
		this->assign(list.begin(),list.end());
		return*this;
	}
	template<typename T>
	void mlist<T>::swap(mlist<T> & list)
	{
		std::swap(this->_head, list._head);
	}
	template<typename T>
	size_t mlist<T>::size()
	{
		size_t count = 0;
		for (mlist<T>::iterator it = this->begin(); it != this->end(); it++)
			count++;
		return count;
	}
	template<typename T>
	bool mlist<T>::empty()
	{
		return this->begin() == this->end();
	}
	template<typename T>
	void mlist<T>::resize(size_t n, const T & elmn)
	{
		size_t len = this->size();
		if (n <= len)
		{
			for (size_t i = n; i < len; i++)
				this->pop_back();
		}
		else
			this->insert(this->end(), n - len, elmn);
	}
	template<typename T>
	void mlist<T>::push_back(const T & elmn)
	{
		insert(this->end(), elmn);
	}
	template<typename T>
	void mlist<T>::pop_back()
	{
		this->erase(--this->end());
	}
	template<typename T>
	void mlist<T>::push_front(const T & elmn)
	{
		this->insert(this->begin(), elmn);
	}
	template<typename T>
	void mlist<T>::pop_front()
	{
		this->erase(this->begin());
	}

	template<typename T>
	typename mlist<T>::iterator mlist<T>::insert(iterator pos, const T & elmn)
	{
		Node*node = new Node, *Pos = pos._node;
		node->_data = elmn;
		node->_next = Pos;
		node->_prev = Pos->_prev;
		Pos->_prev->_next = node;
		Pos->_prev = node;
		return iterator(node);
	}

	template<typename T>
	void mlist<T>::insert(iterator pos, size_t n, const T & elmn)
	{
		while (n--)
		{
			this->insert(pos, elmn);
		}
	}

	template<typename T>
	void mlist<T>::insert(iterator pos, iterator begin, iterator end)
	{
		while (begin != end)
		{
			this->insert(pos, begin._node->_data);
			begin++;
		}
	}

	template<typename T>
	void mlist<T>::clear()
	{
		this->erase(this->begin(), this->end());
	}

	template<typename T>
	typename mlist<T>::iterator mlist<T>::erase(iterator begin, iterator end)
	{
		iterator it = begin;
		while (it != end)
		{
			it = this->erase(it);
		}
		return it;
	}

	template<typename T>
	typename mlist<T>::iterator mlist<T>::erase(iterator pos)
	{
		Node*Pos = pos._node;
		if (pos == this->end())
			return this->end();
		Node*node = Pos->_next;
		Pos->_prev->_next = node;
		node->_prev = Pos->_prev;
		delete Pos;
		Pos = NULL;
		return iterator(node);
	}

	template<typename T>
	void mlist<T>::remove(const T & elmn)
	{
		for (mlist<T>::iterator i = this->begin(); i != this->end(); i++)
		{
			if (i._node->_data == elmn)
				i=this->erase(i);
		}
	}

	template<typename T>
	T & mlist<T>::front()
	{
		return this->begin()._node->_data;
	}

	template<typename T>
	T & mlist<T>::back()
	{
		return (--this->end())._node->_data;
	}

	template<typename T>
	const T & mlist<T>::front() const
	{
		return this->begin()._node->_data;
	}

	template<typename T>
	const T & mlist<T>::back() const
	{
		return this->end()._node->_data;
	}

	template<typename T>
	void mlist<T>::reverse()
	{
		iterator begin = this->begin();
		iterator end = --this->end();
		while (begin!=end)
		{
			std::swap(begin._node->_data, end._node->_data);
			++begin;
			if (begin == end)
				return;
			--end;
			if (begin == end)
				return;
		}
	}

	template<typename T>
	void mlist<T>::sort()
	{
		for (iterator i = this->begin(); i != this->end(); i++)
		{
			iterator min = i, ret = i;
			for (iterator j =ret++; j != this->end(); j++)
				if (min._node->_data > j._node->_data)
					min = j;
			if (min != i)
				std::swap(min._node->_data, i._node->_data);
		}
	}
	template<typename T>
	typename mlist<T>::iterator mlist<T>::begin()
	{
		return iterator(this->_head->_next);
	}
	template<typename T>
	typename mlist<T>::iterator mlist<T>::end()
	{
		return iterator(this->_head);
	}
	template<typename T>
	typename mlist<T>::const_iterator mlist<T>::begin() const
	{
		return const_iterator(this->_head->_next);
	}
	template<typename T>
	typename mlist<T>::const_iterator mlist<T>::end() const
	{
		return const_iterator(this->_head);
	}
	template<typename T>
	mlist<T>::~mlist()
	{
		this->clear();
		delete this->_head;
		this->_head = NULL;
	}
}

十七、使用测试用例

#include"mlist.hpp"
#include<list>
using namespace mxylist;
void printList(const mlist<int>&L)
{
	for (mlist<int>::const_iterator i = L.begin(); i != L.end(); i++)
		cout << *i << " ";
	cout << endl;
}
void test01()
{
	mlist<int>L1;
	L1.push_back(10);
	L1.push_back(20);
	L1.push_back(30);
	L1.push_back(40);
	printList(L1);
	mlist<int>L2(L1.begin(), L1.end());
	printList(L2);
	mlist<int>L3(L2);
	printList(L3);
	mlist<int>L4(7, 3);
	printList(L4);
}
void test02()
{
	mlist<int>L1;
	L1.push_back(10);
	L1.push_back(20);
	L1.push_back(30);
	L1.push_back(40);
	printList(L1);
	mlist<int>L2;
	L2 = L1;
	printList(L2);
	mlist<int>L3;
	L3.assign(L2.begin(), L2.end());
	printList(L3);
	mlist<int>L4;
	L4.assign(7, 3);
	printList(L4);
	L1.swap(L4);
	printList(L1);
	printList(L4);
}
void test03()
{
	mlist<int>L1;
	L1.push_back(10);
	L1.push_back(20);
	L1.push_back(30);
	L1.push_back(40);
	printList(L1);
	if (L1.empty())
		cout << "L1为空" << endl;
	else
		cout << "L1不为空，元素个数为:" << L1.size() << endl;
	L1.resize(10);
	printList(L1);
	L1.resize(15, 3);
	printList(L1);
	L1.resize(1);
	printList(L1);
}
void test04()
{
	mlist<int>L;
	L.push_back(10);
	L.push_back(20);
	L.push_back(30);
	L.push_front(-10);
	L.push_front(-20);
	L.push_front(-30);
	printList(L);
	L.pop_back();
	printList(L);
	L.pop_front();
	printList(L);
	L.insert(L.begin(), 999);
	printList(L);
	L.erase(++L.begin());
	printList(L);
	L.push_back(520025);
	L.push_front(520025);
	printList(L);
	L.remove(520025);
	printList(L);
	L.clear();
	printList(L);
}
void test05()
{
	mlist<int>L1;
	L1.push_back(10);
	L1.push_back(20);
	L1.push_back(30);
	L1.push_back(40);
	cout << "第一个元素:" << L1.front() << endl << "最后一个元素:" << L1.back() << endl;
}
void test06()
{
	mlist<int>L1;
	L1.push_back(30);
	L1.push_back(20);
	L1.push_back(100);
	L1.push_back(40);
	L1.push_back(10);
	printList(L1);
	L1.reverse();
	printList(L1);
	//我用的选择排序实现的list排序，还不支持自定义排序方式，实际库函数可以自定义比较函数传参
	L1.sort();
	printList(L1);
	L1.reverse();
	printList(L1);
}
int main()
{
	test01();
	test02();
	test03();
	test04();
	test05();
	test06();
	return 0;
}

十八、list排序使用案例

这里使用库的list容器

#include<list>
#include<string>
#include<iostream>
using namespace std;
class Person
{
public:
	string m_name;
	int m_age;
	int m_height;
	Person(string name, int age, int height)
	{
		this->m_age = age;
		this->m_height = height;
		this->m_name = name;
	}
};
void printPerson(list<Person>&p)
{
	for (auto i : p)
		cout << "姓名:" << i.m_name << "  年龄:" << i.m_age << "  身高:" << i.m_height << endl;
}
bool cmp(Person&p1,Person&p2)
{
	//按年龄 升序
	if (p1.m_age == p2.m_age)//年龄相同按身高降序
		return p1.m_height >p2.m_height;
	return p1.m_age <p2.m_age;
}
void test07()
{
	list<Person>L;
	Person p[6] =
	{
	{"刘备",35,165},
	{"曹操",45,180},
	{"孙权",40,170},
	{"诸葛亮",27,175},
	{"司马懿",50,173},
	{"周瑜",27,177}
	};
	for (int i = 0; i < 6; i++)
		L.push_back(p[i]);
	printPerson(L);
	cout << "----------------------------------------------------" << endl;
	cout << "排序后" << endl;
	L.sort(cmp);
	printPerson(L);
}
int main()
{
	test07();
	return 0;
}