文章目录

• 接口总览
• list结点的模拟实现
• list迭代器的模拟实现
• • 迭代器类的模板参数说明
  • 构造函数
  • ++运算符的重载
  • - - 运算符的重载
  • ==运算符的重载
  • !=运算符的重载
  • *运算符的重载
  • ->运算符的重载
• list的模拟实现
• • 默认成员函数
  • • 构造函数
    • 拷贝构造函数
    • 赋值运算符重载函数
    • 析构函数
  • 迭代器相关函数
  • 访问容器相关函数
  • 插入、删除函数
  • • insert
    • erase
    • push_front和push_back
    • pop_front和pop_back
  • 其他函数
  • • size
    • empty
    • clear
    • swap

接口总览

namespace NZB
{
	// 模拟实现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 clear();
		bool empty() const;
		void swap(list<T>& lt);

	private:
		node* _head; //指向链表头结点的指针
	};
}

list结点的模拟实现

list底层实际上就是一个带头双向循环链表

实现list首先要实现它的结点类，从图中我们可以看出每个结点的成员变量为：存储数据的变量，指向前一个结点的指针和指向后一个结点的指针。

为了方便新结点的创建，还需要成员函数用于构造结点。

template<class T>
struct _list_node
{
	_list_node(const T& val = T()) // 构造结点
		:_next(nullptr)
		, _prev(nullptr)
		, _data(x)
	{}

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

注意：当构造结点没有传入数据时，使用list默认构造函数构造出来的值

list迭代器的模拟实现

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

list迭代器不同与string和vector迭代器，string类和vector类储存的数据是连续的，它们的迭代器类似指针，但是list类存储的数据是随机的，不能间单的用指针加减来进行访问。

为了使list满足迭代器的要求，我们对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迭代器对象。

构造函数

迭代器中成员变量就只有一个，那就是结点指针，构造时直接给指针构造一个迭代器对象即可

_list_iterator(node* node)
:_node(node)
{}

++运算符的重载

前置++：

将结点指针指向下一个结点，再返回自增后的结点

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

后置++：

先记录当前指针指向的结点，再将结点指针指向下一个结点，返回自增前的结点

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

- - 运算符的重载

前置 - -：

将结点指针指向前一个结点，再返回自减后的结点

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

后置 - -：

先记录当前指针指向的结点，再将结点指针指向前一个结点，返回自减前的结点

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

==运算符的重载

判断两个迭代器指针指向的结点是否相同即可
（这里不会对两个结点修改，最好用const迭代器）

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

!=运算符的重载

!=和==写法类似，一个是判断迭代器指针指向的结点是否不同，一个是判断迭代器指针指向的结点是否相同

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

*运算符的重载

这里类似指针的解应用操作，直接返回迭代器指针指向的结点，因为可能会对解引用的数据进行修改所以返回引用类型。

Ref operator*()
{
	return _node->_data;
}

->运算符的重载

当结点储存为自定义类型时，例如结点储存也为结构体，这时再用*运算符就不太合适了，为了更好访问结点储存这里我们引入了->运算符。

->返回结点中所存储数据的地址即可

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

list的模拟实现

默认成员函数

构造函数

list是一个带头双向循环链表，构造时创建一个头结点，让其前向指针和后向都指向自己

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

拷贝构造函数

新建一个结点，让其前向指针和后向指针都指向自己，再将要拷贝的数据遍历尾插到该结点中。

list(const list<T>& it)
{
	_head = new Node;
	_head->_next = _head;
	_head->_prev = _head;

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

赋值运算符重载函数

传统写法

先用clear函数清理原链表留下头结点，再将新数据遍历尾插

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

现代写法

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

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

析构函数

先调用clear函数清理结点留下头结点，再将头结点释放并置空

~list()
{
	clear();
	delete _head;
	_head = nullptr;
}

迭代器相关函数

begin和end

从string和vector类中我们知道，begin函数返回的是第一个数据的迭代器，end函数返回的是最后一个数据的下一个位置的迭代器，在list类中，begin函数返回的是头指针的下一个结点的迭代器，end函数返回的是头结点的迭代器（最后一个结点的下一个结点就是头结点）

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

我们还需要构造一对用于const对象的迭代器

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

访问容器相关函数

front和back函数分别用于获取第一个有效数据和最后一个有效数据，返回第一个有效数据和最后一个有效数据即可

T& front()
{
	return *begin(); 
}
T& back()
{
	return *(--end()); 
}

不要忘了再写一份const版本用于const类型链表

const T& front() const
{
	return *begin(); 
}
const T& back() const
{
	return *(--end());
}

插入、删除函数

insert

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

iterator insert(iterator pos, const T& x)
{
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* newnode = new Node(x);
			
	// 建立新结点与cur，prev之间的双向关系
	prev->_next = newnode;
	newnode->_prev = prev;
	newnode->_next = cur;
	cur->_prev = newnode;
	return iterator(newnode);
}

erase

作用：删除指定位置的数据。
实现思路：先根据所给迭代器得到该位置处的结点指针cur，然后通过cur指针找到前一个位置的结点指针prev，以及后一个位置的结点指针next，紧接着释放cur结点，最后建立prev和next之间的双向关系。

iterator erase(iterator pos)
{
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* next = cur->_next;

	delete cur;
	// 建立next，prev之间的双向关系
	prev->_next = next;
	next->_prev = prev;
	return iterator(next);
}

push_front和push_back

作用：头插，尾插
实现思路：套用先前实现的insert函数，利用迭代器相关函数begin和end进行头插和尾插

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

void push_back(const T& x)
{
	insert(end(), x);
}

pop_front和pop_back

作用：头删，尾删
实现思路：套用先前实现的erase函数，利用迭代器相关函数begin和end进行头删和尾删（注意：尾删是删除最后一个数据，用end迭代器时需要它的前一个结点）。

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

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

其他函数

size

作用：获取当前容器有效数据的个数
实现思路：设置变量，遍历容器，记录有效数据的个数

size_t size()
{
	int n = 0;
	iterator it = begin();
	// 遍历容器
	while (it != begin())
	{
		++it;
		++n;
	}
	return n;
}

empty

作用：判断容器是否为空
实现思路：判断它的begin和end迭代器是否指向同一块空间

bool empty()
{
	return begin() == end();
}

clear

作用：清空容器
实现思路：遍历删除结点只保留头结点

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

swap

作用：交换链表
实现思路：list容器当中存储的实际上就只有链表的头指针，我们将这两个容器当中的头指针交换即可。

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