【C++】list的使用与模拟实现

世间是否此山最高 2023-06-15 原文

一、list介绍

list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

二、list的使用

1、list的构造

构造函数（ (constructor)）	接口说明
list (size_type n, const value_type& val = value_type())	构造的list中包含n个值为val的元素
list()	构造空的list
list (const list& x)	拷贝构造函数
list (InputIterator first, InputIterator last)	用[first, last)区间中的元素构造list

2、list capacity

函数声明	接口说明
empty	检测list是否为空，是返回true，否则返回false
size	返回list中有效节点的个数

3、list element access

函数声明	接口说明
front	返回list的第一个节点中值的引用
back	返回list的最后一个节点中值的引用

4、list iterator

此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点。

函数声明	接口说明
begin + end	返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin + rend	返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的 reverse_iterator,即begin位置

注意：

begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动

5、list modifiers

函数声明	接口说明
push_front	在list首元素前插入值为val的元素
pop_front	删除list中第一个元素
push_back	在list尾部插入值为val的元素
pop_back	删除list中最后一个元素
insert	在list position 位置中插入值为val的元素
erase	删除list position位置的元素
swap	交换两个list中的元素
clear	清空list中的有效元素

5.1、insert

使用方法如下：

6、list Operations

函数声明	接口说明
splice	将元素从一个列表传输到另一个列表
remove	删除具有特定值的元素
unique	删除重复值
merge	合并排序列表
sort	对容器中的元素进行排序
reverse	反转元素的顺序

6.1、sort

list无法使用算法库里的 sort 函数，因为算法库里的 sort 函数底层实现如下图所示：

这里使用了减法运算，而list各个节点的地址都是不连续的，于是就发生了错误。除此之外，算法库里的 sort 函数底层使用快排实现，而快排有一个重要的组成部分：三数取中，也不适用于list。

文档里关于 sort 函数的说明，也暗示使用算法库里的 sort 函数时要传随机迭代器：

list中的 sort 用法如下：

功能没有任何问题，但是list的 sort 函数我们很少使用，因为它的效率非常的低。

我们使用如下代码进行证明：

可以看到，把相同的数据先拷贝到 vector 中排序，排好了之后再拷贝回来，都要比直接使用 list 排序要快。

7、list的迭代器失效

前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

三、list模拟实现

我们先来搭一个list的基本框架：

namespace bin
{
	template<class T>
	struct list_node
	{
		list_node<T>* _next;
		list_node<T>* _prev;
		T _data;
		
		list_node(const T& x = T())
			:_next(nullptr)
			,_prev(nullptr)
			,_data(x)
		{}
	};

	template<class T>
	class list
	{
		typedef list_node<T> node;
	public:
		list()
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
		}
	private:
		node* _head;
	};
}

需要注意：在 list 类中定义私有成员变量时，一定要注意成员变量类型为类名 + 模板参数。

1、push_back

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

	tail->_next = new_node;
	new_node->_prev = tail;
	new_node->_next = _head;
	_head->_prev = new_node;
}

具体底层逻辑可以参照文章《双向链表》。

2、iterator

list的底层物理空间是不连续的，所以模拟实现迭代器时，就不能直接让指针 "++" 或 "--" 了，而应该实现迭代器 "++" 或 "--" 的重载：

template<class T>
struct __list_iterator
	{
	typedef list_node<T> node;
	typedef __list_iterator<T> self;
	node* _node;

	__list_iterator(node* n)
		:_node(n)
	{}

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

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

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

因为我们模拟实现的list类中的迭代器是使用原生指针实现的，且原生指针的类型为 _node* ，没办法直接实现，所以又定义了一个 __list_iterator 类进行封装。

实验运行结果正确：

红框框起的部分调用了一次拷贝构造，由于我们没有自己实现拷贝构造函数，所以这里是一次浅拷贝，而我们想要的就是浅拷贝。

这里浅拷贝之所以没有报错，是因为我们封装的迭代器类中没有实现析构函数，因为迭代器仅仅是使用list对象节点，而不是拥有list对象节点，它没有权利释放list的对象。

我们再来完善一下迭代器的其他功能：

template<class T>
	struct __list_iterator
	{
		typedef list_node<T> node;
		typedef __list_iterator<T> self;
		node* _node;

		__list_iterator(node* n)
			:_node(n)
		{}

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

		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;
		}

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

3、const iterator

先来看一下错误的写法：

直接在list类中定义 const 类型的成员函数。这种写法的错误之处在于，这些 const 类型成员函数所针对的是list类中的成员变量 _head ，虽然 _head 被 const 限制无法更改，但是 _head 所指向的 _data 仍然可以更改，即数据仍然可以被更改，不符合我们的预期。

我们较为容易想到的写法是直接再另外定义一个类，在这个新类中封装 const 类型的迭代器：

虽然这种写法可以实现功能且完全满足需求，但是代码太过于冗余，接下来我们来学习一种新的写法：

在迭代器模板中多增加了一个模板参数 Ref ，用于满足不同的调用需求。

4、Ptr

观察如下代码：

编译器报错，因为我们没有为自定义类型 AA 实现流插入重载，所以需要写成这种形式：

但是我们在写 C++ 代码时，一般没有写成这种形式的习惯，大多数都是通过 "->" 来实现解引用操作的，所以我们可以改变写法：

这种写法乍一看非常难以理解，这时因为为了增强可读性的缘故，在这里少写了一个 "->" ：

大家看一下完整版的写法就一定能够理解：

同理，为了满足不同的调用需求，应该为list类重载一个 const 类型的成员函数，为了不造成代码冗余，同样只需要为list类模板增加一个模板参数就可以了：

5、insert 及其复用

具体实现如下：

list的 insert 不会导致迭代器失效。

可以使用 insert 函数的复用来实现 push_back 与 push_front ：

6、erase 及其复用

具体实现如下：

list的 erase 会导致迭代器失效。

为了在使用 erase 函数后仍然可以找到该节点的下一个节点，我们使用返回值来返回需要的信息：

可以使用 erase 函数的复用来实现 pop_back 与 pop_front ：

7、clear

具体实现方法如下：

也可以使用下面这种写法：

8、构造函数

8.1、默认构造

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

list()
{
	empty_init();
}

8.2、迭代器构造

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

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

扩展内容：

const 类型的对象是无法调用 empty_init() 函数的，因为这属于权限放大。那么为什么我们写如下 const 类型对象的实例化不会报错呢？

这是因为该 const 对象在定义的时候并没有 const 属性，在该对象定义完成后，才被赋予了 const 属性，否则就没有办法对对象进行初始化操作了。

9、拷贝构造函数

传统写法如下：

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

list(const list<T>& lt)
{
	empty_init();
	for ( auto e : lt)
	{
		push_back(e);
	}
}

这里再提供一份现代写法：

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

list(const list<T>& lt)
{
	empty_init();

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

10、析构函数

实现代码如下：

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

11、operator=