【C++初阶】第十篇：list模拟实现

一、list的模拟实现

三个类及其成员函数接口总览

namespace wyt
{
	//模拟实现list当中的结点类
	template<class T>
	struct _list_node
	{
		//成员函数
		_list_node(const T& val = T()); //构造函数

		//成员变量
		T _val;                 //数据域
		_list_node<T>* _next;   //后继指针
		_list_node<T>* _prev;   //前驱指针
	};

	//模拟实现list迭代器类
	template<class T, class Ref, class Ptr>
	struct _list_iterator
	{
		typedef _list_node<T> node;
		typedef _list_iterator<T, Ref, Ptr> self;

		_list_iterator(node* pnode);  //构造函数

		//各种运算符重载函数
		self operator++();
		self operator--();
		self operator++(int);
		self operator--(int);
		bool operator==(const self& s) const;
		bool operator!=(const self& s) const;
		Ref operator*();
		Ptr operator->();

		//成员变量
		node* _pnode; //一个指向结点的指针
	};

	//模拟实现list
	template<class T>
	class list
	{
	public:
		typedef _list_node<T> node;
		typedef _list_iterator<T, T&, T*> iterator;
		typedef _list_iterator<T, const T&, const T*> const_iterator;

		//默认成员函数
		list();
		list(const list<T>& lt);
		list<T>& operator=(const list<T>& lt);
		~list();

		//迭代器相关函数
		iterator begin();
		iterator end();
		const_iterator begin() const;
		const_iterator end() const;

		//访问容器相关函数
		T& front();
		T& back();
		const T& front() const;
		const T& back() const;

		//插入、删除函数
		void insert(iterator pos, const T& x);
		iterator erase(iterator pos);
		void push_back(const T& x);
		void pop_back();
		void push_front(const T& x);
		void pop_front();

		//其他函数
		size_t size() const;
		void resize(size_t n, const T& val = T());
		void clear();
		bool empty() const;
		void swap(list<T>& lt);

	private:
		node* _head; //指向链表头结点的指针
		size_t _size;//统计节点个数
	};
}

结点类的模拟实现

我们经常说list在底层实现时就是一个链表，更准确来说，list实际上是一个带头双向循环链表。

因此，我们若要实现list，则首先需要实现一个结点类。而一个结点需要存储的信息有：数据、前一个结点的地址、后一个结点的地址，于是该结点类的成员变量也就出来了（数据、前驱指针、后继指针）。

而对于该结点类的成员函数来说，我们只需实现一个构造函数即可。因为该结点类只需要根据数据来构造一个结点即可，而结点的释放则由list的析构函数来完成。

//结点类
template<class T>
struct list_node
{
	//成员变量
	list_node<T>* _next;//后继指针
	list_node<T>* _prev;//前驱指针
	T _data;//数据域
	
	//成员函数
	list_node(const T& val = T())//构造函数
		:_next(nullptr)
		, _prev(nullptr)
		, _data(val)
	{}
};

注意： 若构造结点时未传入数据，则默认以list容器所存储类型的默认构造函数所构造出来的值为传入数据。

迭代器类的模拟实现

迭代器类存在的意义：
之前模拟实现string和vector时都没有说要实现一个迭代器类，为什么实现list的时候就需要实现一个迭代器类了呢？

因为string和vector对象都将其数据存储在了一块连续的内存空间，我们通过指针进行自增、自减以及解引用等操作，就可以对相应位置的数据进行一系列操作，因此string和vector当中的迭代器就是原生指针。

但是对于list来说，其各个结点在内存当中的位置是随机的，并不是连续的，我们不能仅通过结点指针的自增、自减以及解引用等操作对相应结点的数据进行操作。

而迭代器的意义就是，让使用者可以不必关心容器的底层实现，可以用简单统一的方式对容器内的数据进行访问

既然list的结点指针的行为不满足迭代器定义，那么我们可以对这个结点指针进行封装，对结点指针的各种运算符操作进行重载，使得我们可以用和string和vector当中的迭代器一样的方式使用list当中的迭代器。例如，当你使用list当中的迭代器进行自增操作时，实际上执行了p = p->next语句，只是你不知道而已。

总结： list迭代器类，实际上就是对结点指针进行了封装，对其各种运算符进行了重载，使得结点指针的各种行为看起来和普通指针一样。（例如，对结点指针自增就能指向下一个结点）

迭代器类的模板参数说明

这里我们所实现的迭代器类的模板参数列表当中为什么有三个模板参数？

template<class T, class Ref, class Ptr>

在list的模拟实现当中，我们typedef了两个迭代器类型，普通迭代器和const迭代器。

typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;

这里我们就可以看出，迭代器类的模板参数列表当中的Ref和Ptr分别代表的是引用类型和指针类型。

当我们使用普通迭代器时，编译器就会实例化出一个普通迭代器对象；当我们使用const迭代器时，编译器就会实例化出一个const迭代器对象。

若该迭代器类不设计三个模板参数，那么就不能很好的区分普通迭代器和const迭代器。

迭代器operator->的重载

某些情景下，我们使用迭代器的时候可能会用到->运算符。

//*的重载：返回节点的数据
Ref operator*()
{
    return _pnode->_data;
}
//->的重载：返回数据的指针
T* operator->()
{
    return &_pnode->_data;
}

例如：

但是operator->使用T*做返回值类型，这样无论是普通迭代器和const迭代器都能修改，所以operator->的返回值类型应该改为泛型：

template <class T, class Ref,class Ptr>
Ptr operator->()
{
    return &_pnode->_data;
}
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;

迭代器模拟实现代码

//用类封装迭代器
// 同一个类模板实例化出的两个类型
// typedef __list_iterator<T, T&, T*> iterator;
// typedef __list_iterator<T, const T&, const T*> const_iterator;
template<class T, class Ref, class Ptr>
struct __list_iterator
{
	typedef list_node<T> node;
	node* _pnode;
	typedef __list_iterator<T, Ref, Ptr> Self; //self是当前迭代器对象的类型：
	//Ref就表示当我需要使用*it时，我们返回的是const T&，还是T&，即支持两种迭代器
	//Ptr支持我们像指针一样使用->
	
	//迭代器类实际上就是对结点指针进行了封装，
	//其成员变量就只有一个，那就是结点指针，其构造函数直接根据所给结点指针构造一个迭代器对象即可。
	__list_iterator(node* p)
		:_pnode(p)
	{}

	Ptr operator->()
	{
		return &_pnode->_data;
	}

	// iterator it
	// *it
	// ++it;
	//当我们使用解引用操作符时，是想得到该位置的数据内容。
	//因此，我们直接返回当前结点指针所指结点的数据即可，但是这里需要使用引用返回，因为解引用后可能需要对数据进行修改。
	Ref operator*()
	{
		return _pnode->_data;
	}

	// ++it
	//前置++原本的作用是将数据自增，然后返回自增后的数据。
	//我们的目的是让结点指针的行为看起来更像普通指针，
	//那么对于结点指针的前置++，我们就应该先让结点指针指向后一个结点，然后再返回“自增”后的结点指针即可。
	Self& operator++()
	{
		_pnode = _pnode->_next;
		return *this;
	}

	// it++
	//对于后置++，我们则应该先记录当前结点指针的指向，然后让结点指针指向后一个结点，最后返回“自增”前的结点指针即可。
	Self operator++(int)
	{
		Self tmp(*this);
		_pnode = _pnode->_next;		
		return tmp;
	}
	
	//--it
	//对于前置- -，我们应该先让结点指针指向前一个结点，然后再返回“自减”后的结点指针即可。
	Self& operator--()
	{
		_pnode = _pnode->_prev;
		return *this;
	}
	//it--
	//对于后置- -，我们则应该先记录当前结点指针的指向，然后让结点指针指向前一个结点，最后返回“自减”前的结点指针即可。
	Self operator--(int)
	{
		Self tmp(*this);
		_pnode = _pnode->_prev;
		return tmp;
	}
	//判断这两个迭代器当中的结点指针的指向是否不同即可。
	bool operator!=(const Self& it) const
	{
		return _pnode != it._pnode;
	}
	//当使用==运算符比较两个迭代器时，
	//我们实际上想知道的是这两个迭代器是否是同一个位置的迭代器，也就是说，我们判断这两个迭代器当中的结点指针的指向是否相同即可。
	bool operator==(const Self& it) const
	{
		return _pnode == it._pnode;
	}
};

list的模拟实现

无参构造函数

list是一个带头双向循环链表，在构造一个list对象时，直接申请一个头结点，并让其前驱指针和后继指针都指向自己即可。

//构造函数
list()
{
	_head = new node(T()); //申请一个头结点，给一个缺省值，调用结点类的默认构造
	_head->_next = _head;//头结点的后继指针指向自己
	_head->_prev = _head; //头结点的前驱指针指向自己

	_size = 0;//结点个数为0
}

带参构造

list还提供一个迭代区间构造，首先创建一个头节点，然后循环遍历依次尾插到后面即可

template <class InputIterator>  
list(InputIterator first, InputIterator last)
{
	_head = new node(T()); //申请一个头结点，给一个缺省值，调用结点类的默认构造
	_head->_next = _head;//头结点的后继指针指向自己
	_head->_prev = _head; //头结点的前驱指针指向自己
	while (first != last)
	{
		push_back(*first);
		++first;
	}
}

拷贝构造函数

拷贝构造函数就是根据所给list容器，拷贝构造出一个对象。对于拷贝构造函数，我们先申请一个头结点，并让其前驱指针和后继指针都指向自己，然后将所给容器当中的数据，通过遍历的方式一个个尾插到新构造的容器后面即可。

//拷贝构造函数
list(const list<T>& lt)
{
	_head = new node(T()); //申请一个头结点，给一个缺省值，调用结点类的默认构造
	_head->_next = _head; //头结点的后继指针指向自己
	_head->_prev = _head; //头结点的前驱指针指向自己
	for (const auto& e : lt)
	{
		push_back(e); //将容器lt当中的数据一个个尾插到新构造的容器后面
	}
}

赋值运算符重载函数

对于赋值运算符的重载，这里提供两种写法：

写法一：传统写法
这是比较容易理解的一种写法，先调用clear函数将原容器清空，然后将容器lt当中的数据，通过遍历的方式一个个尾插到清空后的容器当中即可。

//传统写法
list<T>& operator=(const list<T>& lt)
{
	if (this != &lt) //避免自己给自己赋值
	{
		clear(); //清空容器
		for (const auto& e : lt)
		{
			push_back(e); //将容器lt当中的数据一个个尾插到链表后面
		}
	}
	return *this; //支持连续赋值
}

写法二：现代写法
现代写法的代码量较少，首先利用编译器机制，故意不使用引用接收参数，通过编译器自动调用list的拷贝构造函数构造出来一个list对象，然后调用swap函数将原容器与该list对象进行交换即可。

//现代写法
list<T>& operator=(list<T> lt) //编译器接收右值的时候自动调用其拷贝构造函数
{
	swap(lt); //交换这两个对象
	return *this; //支持连续赋值
}

这样做相当于将应该用clear清理的数据，通过交换函数交给了容器lt，而当该赋值运算符重载函数调用结束时，容器lt会自动销毁，并调用其析构函数进行清理。

析构函数

对对象进行析构时，首先调用clear函数清理容器当中的数据，然后将头结点释放，最后将头指针置空即可

//析构函数
~list()
{
	clear(); //清理容器
	delete _head; //释放头结点
	_head = nullptr; //头指针置空
}

begin和end

首先我们应该明确的是：begin函数返回的是第一个有效数据的迭代器，end函数返回的是最后一个有效数据的下一个位置的迭代器。

对于list这个带头双向循环链表来说，其第一个有效数据的迭代器就是使用头结点后一个结点的地址构造出来的迭代器，而其最后一个有效数据的下一个位置的迭代器就是使用头结点的地址构造出来的迭代器。（最后一个结点的下一个结点就是头结点）

iterator begin()
{
	//返回使用头结点后一个结点的地址构造出来的普通迭代器
	return iterator(_head->_next);
}
iterator end()
{
	//返回使用头结点的地址构造出来的普通迭代器
	return iterator(_head);
}

上方是普通的迭代器的begin和end函数，可读可写，我们还需实现const迭代器，只允许读操作

const_iterator begin() const
{
	//返回使用头结点后一个结点的地址构造出来的const迭代器
	return const_iterator(_head->_next);
}
const_iterator end() const
{
	//返回使用头结点的地址构造出来的普通const迭代器
	return const_iterator(_head);
}

insert

insert函数可以在所给迭代器之前插入一个新结点。

先根据所给迭代器得到该位置处的结点指针cur，然后通过cur指针找到前一个位置的结点指针prev，接着根据所给数据x构造一个待插入结点，之后再建立新结点与cur之间的双向关系，最后建立新结点与prev之间的双向关系即可。

iterator insert(iterator pos, const T& x)
{
	//创建一个新节点
	node* newnode = new node(x);//根据所给数据x构造一个待插入结点
	
	node* cur = pos._pnode;//迭代器pos处的结点指针
	node* prev = cur->_prev;//迭代器pos前一个位置的结点指针

	// prev newnode cur
	//建立newnode与prev之间的双向关系
	prev->_next = newnode;
	newnode->_prev = prev;
	//建立newnode与cur之间的双向关系
	newnode->_next = cur;
	cur->_prev = newnode;

	++_size;

	return iterator(newnode);
}

erase

erase函数可以删除所给迭代器位置的结点。

先根据所给迭代器得到该位置处的结点指针cur，然后通过cur指针找到前一个位置的结点指针prev，以及后一个位置的结点指针next，紧接着释放cur结点，最后建立prev和next之间的双向关系即可。

iterator erase(iterator pos)
{
	assert(pos != end());//删除的结点不能是头结点

	node* prev = pos._pnode->_prev;//迭代器pos前一个位置的结点指针
	node* next = pos._pnode->_next;//迭代器pos后一个位置的结点指针

	prev->_next = next;
	next->_prev = prev;

	delete pos._pnode;
	--_size;

	return iterator(next);//返回所给迭代器pos的下一个迭代器
}

list的迭代器失效问题

• insert，迭代器不失效
• earse失效（因为删除pos节点后，pos所指向的空间已经不在了，所以需要返回pos节点的下一个节点）

push_back和pop_back

push_back和pop_back函数分别用于list的尾插和尾删，在已经实现了insert和erase函数的情况下，我们可以通过复用函数来实现push_back和pop_back函数。

push_back函数就是在头结点前插入结点，而pop_back就是删除头结点的前一个结点。

void push_back(const T& x)
{
	//规范写法
	//node* newnode = new node(x);
	//node* tail = _head->_prev;
	 _head         tail   newnode
	//tail->_next = newnode;
	//newnode->_prev = tail;
	//newnode->_next = _head;
	//_head->_prev = newnode;
	
	//复用insert
	insert(end(), x);
}

void pop_back()
{
	erase(--end());//删除头结点的前一个结点
}

push_front和pop_front

当然，用于头插和头删的push_front和pop_front函数也可以复用insert和erase函数来实现。

push_front函数就是在第一个有效结点前插入结点，而pop_front就是删除第一个有效结点。

//头插
void push_front(const T& x)
{
	insert(begin(), x); //在第一个有效结点前插入结点
}
//头删
void pop_front()
{
	erase(begin()); //删除第一个有效结点
}

clear

clear函数用于清空容器，我们通过遍历的方式，逐个删除结点，只保留头结点即可。

void clear()
{
	iterator it = begin();
	while (it != end())
	{
		it = erase(it);
	}
}

empty

empty函数用于判断容器是否为空，因为我们list的成员变量中有一个_size,所以我们只需判断_size是否为0即可

bool empty() const
{
	return _size == 0;
}

size

size函数用于统计容器中数据个数，我们直接返回_size即可

size_t size() const
{
	return _size;
}

swap

swap函数用于交换两个容器，list容器当中存储的实际上就只有链表的头指针，我们将这两个容器当中的头指针交换即可

void swap(list<T>& lt)
{
	std::swap(_head, lt._head); //交换两个容器当中的头指针即可
	std::swap(_size, lt._size);
}

二、list与vector之间的对比

vector优缺点：

优点：
1、支持下标的随机访问；

2、尾插尾删效率高（当然扩容的那一次尾插会较慢）；

3、CPU高速缓存命中高（数据从缓存加载至CPU中，会加载连续的一段数据，vector因为结构连续，高速缓存命中高）。

缺点
1、头部或中间插入删除数据效率低（O(N)）
2、 扩容有消耗，还存在一定的空间浪费

vector迭代器失效问题：

insert/erase均失效。（如果string的insert和erase形参是迭代器，那么也会失效，但是大部分接口是下标传参，不考虑失效问题，只有几个接口是迭代器传参，需要注意迭代器失效问题）

list优缺点

优点
1、按需申请释放，无需扩容；
2、任意位置插入删除时间O(1)；（这里说的是插入删除，不要加上查找的时间）

缺点
1、不支持下标的随机访问
2、CPU高速缓存命中率低；

list迭代器失效问题：

insert不失效，erase失效。文章来源地址https://www.toymoban.com/news/detail-416228.html

三、总结：模拟实现list的整体代码

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

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

	// 同一个类模板实例化出的两个类型
	// typedef __list_iterator<T, T&, T*> iterator;
	// typedef __list_iterator<T, const T&, const T*> const_iterator;
	template<class T, class Ref, class Ptr>
	struct __list_iterator
	{
		typedef list_node<T> node;
		typedef __list_iterator<T, Ref, Ptr> Self;
		node* _pnode;

		__list_iterator(node* p)
			:_pnode(p)
		{}


		Ptr operator->()
		{
			return &_pnode->_data;
		}

		// iterator it
		// *it
		// ++it;
		Ref operator*()
		{
			return _pnode->_data;
		}

		// const iterator cit
		// *cit
		// ++cit 这样的话，可以解引用，但是不能++
		/*const T& operator*() const
		{
		return _pnode->_data;
		}*/

		// ++it
		Self& operator++()
		{
			_pnode = _pnode->_next;
			return *this;
		}

		// it++
		Self operator++(int)
		{
			Self tmp(*this);
			_pnode = _pnode->_next;
			return tmp;
		}

		Self& operator--()
		{
			_pnode = _pnode->_prev;
			return *this;
		}

		Self operator--(int)
		{
			Self tmp(*this);
			_pnode = _pnode->_prev;
			return tmp;
		}

		bool operator!=(const Self& it) const
		{
			return _pnode != it._pnode;
		}

		bool operator==(const Self& it) const
		{
			return _pnode == it._pnode;
		}
	};

	// 跟普通迭代器的区别：遍历，不能用*it修改数据
	/*template<class T>
	struct __list_const_iterator
	{
		typedef list_node<T> node;
		node* _pnode;

		__list_const_iterator(node* p)
			:_pnode(p)
		{}

		const T& operator*()
		{
			return _pnode->_data;
		}

		__list_const_iterator<T>& operator++()
		{
			_pnode = _pnode->_next;
			return *this;
		}

		__list_const_iterator<T>& operator--()
		{
			_pnode = _pnode->_prev;
			return *this;
		}

		bool operator!=(const __list_const_iterator<T>& it)
		{
			return _pnode != it._pnode;
		}
	};*/

	//vector<int>
	//vector<string>
	//vector<vector<int>>

	// 类名  类型
	// 普通类  类名 等价于 类型
	// 类模板  类名  不等价于  类型
	// 如：list模板 类名list  类型list<T> 
	// 类模板里面可以用类名代表类型，但是建议不要那么用
	template<class T>
	class list
	{
		typedef list_node<T> node;
	public:
		typedef __list_iterator<T, T&, T*> iterator;
		//typedef __list_const_iterator<T> const_iterator;
		typedef __list_iterator<T, const T&, const T*> const_iterator;

		const_iterator begin() const
		{
			return const_iterator(_head->_next);
		}

		const_iterator end() const
		{
			return const_iterator(_head);
		}

		iterator begin()
		{
			return iterator(_head->_next);
		}

		iterator end()
		{
			//iterator it(_head);
			//return it;
			return iterator(_head);
		}

		void empty_initialize()
		{
			_head = new node(T());
			_head->_next = _head;
			_head->_prev = _head;

			_size = 0;
		}

		list()
		{
			empty_initialize();
		}

		 lt2(lt1)
		//list(const list<T>& lt)
		//{
		//	empty_initialize();

		//	for (const auto& e : lt)
		//	{
		//		push_back(e);
		//	}
		//}

		 lt1 = lt3
		//list<T>& operator=(const list<T>& lt)
		//{
		//	if (this != &lt)
		//	{
		//		clear();
		//		for (const auto& e : lt)
		//		{
		//			push_back(e);
		//		}
		//	}

		//	return *this;
		//}

		template <class InputIterator>
		list(InputIterator first, InputIterator last)
		{
			empty_initialize();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		void swap(list<T>& lt)
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}

		// 现在写法
		// lt2(lt1)
		list(const list<T>& lt)
			//list(const list& lt) // 不建议
		{
			empty_initialize();

			list<T> tmp(lt.begin(), lt.end());
			swap(tmp);
		}

		// lt3 = lt1
		list<T>& operator=(list<T> lt)
			//list& operator=(list lt) // 不建议
		{
			swap(lt);
			return *this;
		}

		size_t size() const
		{
			return _size;
		}

		bool empty() const
		{
			return _size == 0;
		}

		~list()
		{
			clear();

			delete _head;
			_head = nullptr;
		}

		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

		void push_back(const T& x)
		{
			//node* newnode = new node(x);
			//node* tail = _head->_prev;
			 _head         tail   newnode
			//tail->_next = newnode;
			//newnode->_prev = tail;
			//newnode->_next = _head;
			//_head->_prev = newnode;

			insert(end(), x);
		}

		void push_front(const T& x)
		{
			insert(begin(), x);
		}

		void pop_front()
		{
			erase(begin());
		}

		void pop_back()
		{
			erase(--end());
		}

		iterator insert(iterator pos, const T& x)
		{
			node* newnode = new node(x);
			node* cur = pos._pnode;
			node* prev = cur->_prev;

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

			++_size;

			return iterator(newnode);
		}

		iterator erase(iterator pos)
		{
			assert(pos != end());

			node* prev = pos._pnode->_prev;
			node* next = pos._pnode->_next;

			prev->_next = next;
			next->_prev = prev;

			delete pos._pnode;
			--_size;

			return iterator(next);
		}

	private:
		node* _head;
		size_t _size;
	};
}

到了这里，关于【C++初阶】第十篇：list模拟实现的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！