C++ STL 容器 list

本文测试环境为 gcc 13.1

1. list 对象

std::list 底层是一个双向循环链表

list 对象本身包含一个头节点，通过指针指向元素节点，节点定义如下

头节点 header 和元素节点 node 都继承于基类 node_base

list<int> l;

所以 sizeof(l) = 8 + 8 + 8 = 24，一个 list 对象本身是 24 字节大小，头节点分配在栈上，而元素节点则通过 new 分配在堆上

具体模型如下图所示

可以看出，只要得到其中某个节点的迭代器，就可以以常数时间来进行插入和删除，但因为空间不连续，不支持快速随机访问

2. list 迭代器

2.1 实现

list 中的元素是不连续存储的，可不能像 vector 那样使用一个普通指针就能实现

想要通过这个迭代器访问每个元素，当然就需要 next 和 prev 指针了

这样，就可以使用 node_base 来实现，和 vector 一样，对这个进行封装，提供迭代器需要的功能

list 迭代器实现为双向迭代器，需要满足以下功能

很容易想到，++ 和 - - 不就对应 next 和 prev 吗，所以实现起来还是很简单的

那么怎么构造这个迭代器呢

vector 的迭代器最终就是一个指针，可以通过 start 指针来构造 begin()，finish 指针构造 end()

现在 list 的迭代器是对 node_base 的封装，是头节点和元素节点的基类，所以可以通过多态来实现，我们可以使用 head->next ，即第一个元素来构造 list 的 begin() 了，迭代器是用来遍历元素节点的，所以头节点作为 end()，刚好 head->prev 是最后一个元素，即 end() - 1 是最后一个元素

实现如下

template<typename _Tp>
struct _List_iterator
{
	typedef _List_iterator<_Tp>		_Self;
	typedef _List_node<_Tp>			_Node;
	
	typedef ptrdiff_t				difference_type;
	typedef std::bidirectional_iterator_tag	iterator_category;
	typedef _Tp				value_type;
	typedef _Tp*				pointer;
	typedef _Tp&				reference;

	//...	

	// The only member points to the %list element.
	__detail::_List_node_base* _M_node;
};

对 node_base 进行封装

构造

 _List_iterator() _GLIBCXX_NOEXCEPT
 : _M_node() { }

 explicit
 _List_iterator(__detail::_List_node_base* __x) _GLIBCXX_NOEXCEPT
 : _M_node(__x) { }

解引用

// Must downcast from _List_node_base to _List_node to get to value.
_GLIBCXX_NODISCARD
reference
operator*() const _GLIBCXX_NOEXCEPT
{ return *static_cast<_Node*>(_M_node)->_M_valptr(); }

_GLIBCXX_NODISCARD
pointer
operator->() const _GLIBCXX_NOEXCEPT
{ return static_cast<_Node*>(_M_node)->_M_valptr(); }

++ 、–

_Self&
operator++() _GLIBCXX_NOEXCEPT
{
	_M_node = _M_node->_M_next;
	return *this;
}

_Self
operator++(int) _GLIBCXX_NOEXCEPT
{
	_Self __tmp = *this;
	_M_node = _M_node->_M_next;
	return __tmp;
}

_Self&
operator--() _GLIBCXX_NOEXCEPT
{
	_M_node = _M_node->_M_prev;
	return *this;
}

_Self
operator--(int) _GLIBCXX_NOEXCEPT
{
	_Self __tmp = *this;
	_M_node = _M_node->_M_prev;
	return __tmp;
}

比较

_GLIBCXX_NODISCARD
friend bool
operator==(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
{ return __x._M_node == __y._M_node; }

#if __cpp_impl_three_way_comparison < 201907L
_GLIBCXX_NODISCARD
friend bool
operator!=(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
{ return __x._M_node != __y._M_node; }
#endif

对迭代器的解引用就是获取元素节点的 data 了，如果是对头节点的迭代器解引用，那么就会出问题了，如果元素也是 size_t 之类的数值类型的话，可能就没啥问题

2.2 迭代器失效

list 迭代器失效的话，那就是看这个 node_base 指针指向的节点是否可以正常使用了

1.插入元素

插入新元素会影响其他节点的地址和 data 吗，显然不会

2.删除元素

删除一个元素会影响其他节点的地址吗，当然也不会，但是这个要删除的节点的地址就不能正常引用了

因为 vector 连续存储和重新分配特点，迭代器失效问题就多一点，而 list 节点不连续，互不影响