【C++】STL--List使用及其模拟实现

1. list的介绍及使用

1.1. list的介绍 list官方文档

• list是能够在常数范围内任意位置进行插入和删除的序列容器，并且能够进行双向迭代
• list的底层是双向链表，双向链表中的每一个元素都储存在独立的节点中，每个节点通过指针进行前后联系
• list和forward_list相似，不同的地方在于forward_list是单链表，只能够向前迭代
• 与其他容器相比（vector、array、deque），list通常在任意位置插入和删除的执行效率更好
• 与其他序列式容器相比，list、forward_list的最大缺陷在于不能够做到对任意位置的随机访问。例如：我要访问第六个元素，那就必须要从已知的位置（头或尾）开始，迭代到这个位置，这一操作需要线性的开销。并且list中的每一个节点还需要额外的空间来存储关联的信息（这一点在小数据的大链表中体现的比较多）

1.2. list的常见接口 list中接口比较多，我们学习常见的接口并且了解它的底层原理即可：

2. list的迭代器

在开始讲解list的常见接口之前，我们先来了解一下list中的迭代器：list中的指针是一个自定义类型的指针，该指针指向list中的某一个节点。

这里补充一个知识，迭代器的实现有两种方式：

• 直接使用原生指针，如：vector
• 对原生指针进行封装，然后重载原生指针需要用到的运算符

list迭代器：

• 因为指针支持解引用，所以自定义的类中需要重载operator*()
• 可以通过->来访问成员，所以需要重载operator->()
• 指针可以++向后移动，所以需要重载operator++()/operator(int)；至于向前移动，需要根据需要选择呢是否重载operator--()/operator(int)，因为如果是forward_list就不需要这个操作
• 迭代器需要进行是否相等的比较，所以需要重载operator==()和operator!=()

我们首先实现一个简单的list的iterator：

注意：

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

//节点类
template <class T>
struct ListNode
{
	ListNode(const T& val = T())
		:_pre(nullptr)
		,_next(nullptr)
		,_val(val)
	{ }

	ListNode<T>* _pre;
	ListNode<T>* _next;
	T _val;
};

//迭代器类
template <class T,class Ref,class Ptr>
struct ListIterator
{
	typedef ListNode<T>* PNode;
	//下面不需要用指针，因为我们要的就是迭代器本身，而并不是迭代器指针
	typedef ListIterator<T, Ref, Ptr> Self;
	/*typedef  T& Ref;
    typedef  T* Ptr;*/

	PNode _node;

	ListIterator(PNode node)
		:_node(node)
	{ }

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

	Ptr operator -> ()
	{
		//返回的节点数据的地址
		return &_node->_val;
	}

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

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

	Self& operator -- ()
	{
		_node = _node->_pre;
		return *this;
	}

	Self operator -- ()
	{
		Self tmp(*this);
		_node = _node->_pre;
		return tmp;
	}

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

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

};

3. list的构造

• 构造空的list：

//构造空的list list() { _head = new Node(); _head->_next = _head; _head->_pre = _head; }

• 拷贝构造函数

//拷贝构造 list(const list<T>& it) { _head = new Node(); _head->_next = _head; _head->_pre = _head; for (auto i : it) { push_back(i); } }

• 使用first、last区间构造

//使用first、last区间构造 template <class InputIterator> list(InputIterator first, InputIterator last) { _head = new Node(); _head->_next = _head; _head->_pre = _head; while (first != last) { push_back(*first); ++first; } }

• 析构函数

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

4. list capacity

5. list常见接口

5.1. insert

步骤：

• 先创建一个newnode来接收x
• 然后创建两个指针pre（指向pos位置的前一个结点），cur（指向pos位置）
• 然后进行newnod、cur、pre三个结点的连接

iterator insert(iterator pos, const T& x)
{
	Node* newnode = new Node(x);
	Node* cur = pos._node;
	Node* pre = cur->_pre;

	//连接
	pre->_next = newnode;
	newnode->_pre = pre;
	newnode->_next = cur;
	cur->_pre = newnode;

	return newnode;
}

5.2. push_front、push_back

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

//push_back
void push_back()
{
	insert(end(), x);
}

5.3. earse

步骤：

• 首先创建三个指针cur（pos位置）、pre（pos前一个位置）、next（pos后一个位置）
• 然后连接pre和next
• 释放掉cur指针，然后返回next指向结点的迭代器

//earse
iterator earse(iterator pos)
{
	assert(pos != end());

	Node* cur = pos->_node;
	Node* pre = cur->_pre;
	Node* next = cur->_next;

	//连接pre、next
	pre->_next = next;
	next->_pre = pre;
	delete cur;

	return iterator(next);
}

5.4. pop_front、pop_back

//头删
void pop_front()
{
	earse(begin());
}

//尾删
void pop_back()
{
	earse(end());
}

5.5. swap

其实list的交换非常简单，因为我们发现，list类中只有一个成员变量_head，所以我们只需要交换_head的值即可：

void Swap(list<T>& l)
{
	std::swap(_head, l->_head);
}

5.6. clear

将链表的每一个节点释放掉即可，可是使用迭代器然后earse：

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

6. list的迭代器失效

之前和大家讲过，我们可以将迭代器粗浅地先看做指针，而迭代器失效是因为是迭代器指向的空间被释放了。但是list的底层是一个包含头结点的双向链表，所以在插入元素的时候不存在扩容的操作，所以是不会导致迭代器失效的。只有在删除结点的时候才会导致迭代器失效，并且失效的只有被删除的一个结点，其他迭代器不会受到影响。

来看一下这段代码：

void TestListIterator1()
{
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	list<int> l(array, array + sizeof(array) / sizeof(array[0]));
	auto it = l.begin();
	while (it != l.end())
	{
		// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值
			l.erase(it);
		++it;
	}
}

会出现访问异常：

修改之后的代码：

void TestListIterator1()
{
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	list<int> l(array, array + sizeof(array) / sizeof(array[0]));
	auto it = l.begin();
	while (it != l.end())
	{
		// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值
		l.erase(it++);
		//++it;
	}
}

7.list和vector的对比

vectorlist 底 层 结 构 动态顺序表，一段连续空间 带头结点的双向循环链表 随 机 访 问支持随机访问，访问某个元素效率 O(1)不支持随机访问，访问某个元素 效率 O(N) 插 入 和 删 除 任意位置插入和删除效率低，需要搬移元素，时间复杂 度为 O(N) ，插入时有可能需要增容，增容：开辟新空 间，拷贝元素，释放旧空间，导致效率更低 任意位置插入和删除效率高，不 需要搬移元素，时间复杂度为 O(1) 空 间 利 用 率 底层为连续空间，不容易造成内存碎片，空间利用率 高，缓存利用率高 底层节点动态开辟，小节点容易 造成内存碎片，空间利用率低，缓存利用率低 迭 代 器 原生态指针 对原生态指针 ( 节点指针 ) 进行封装 迭 代 器 失 效 在插入元素时，要给所有的迭代器重新赋值，因为插入 元素有可能会导致重新扩容，致使原来迭代器失效，删 除时，当前迭代器需要重新赋值否则会失效 插入元素不会导致迭代器失效， 删除元素时，只会导致当前迭代 器失效，其他迭代器不受影响 使 用 场 景 需要高效存储，支持随机访问，不关心插入删除效率 大量插入和删除操作，不关心随 机访问

（本篇完）