•  与其他序列式容器相比，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：

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

注意：

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

代码语言：javascript

AI代码解释

//节点类
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的构造

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

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

---

5. list常见接口

函数声明	接口说明
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

步骤：

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