C++STL容器 list——双向带头循环链表的实现

list简介

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

结点类定义

代码如下：

template <class T>
struct ListNode  //定义结点内容
{
	ListNode<T>* _prev;  // 前指针
	ListNode<T>* _next;  // 后指针
	T _data;  //模板类型数据

	ListNode(const T& n)  //结点的构造函数
		: _prev(0)
		, _next(0)
		, _data(n)
	{}
};

这里我们用struct来定义结点类，因为struct默认所有成员均为public。然后双向链表每个结点包含三项，分别是向前指针，向后指针和要存放的内容。最后还需要实现结点的构造函数以方便后面new结点时进行调用。

迭代器类定义

我们知道，前面两个容器string和vector他们存放数据的内存都是连续的，因此支持随机存取，也就可以重载[]来进行访问，而解引用(*)就可以直接访问对应内存里的内容。但是到了链表这里，我们就不能再简单的使用解引用符号来访问数据元素了，因为内存不再连续，数据在内存上的前后关系也不确定。因此我们想要统一迭代器的使用方式，就需要对list的迭代器进行封装，代码如下：

template <class T, class Ref, class Ptr>
struct __list_iterator
{
	typedef ListNode<T> Node; //将刚才定义好的链表节点进行重命名，命名为Node
	typedef __list_iterator<T, Ref, Ptr> Self;
	Node* _pnode;  // 在迭代器里创建一个指向结点的指针

	__list_iterator(Node* p)  //迭代器的构造函数，需要传入一个指向结点的指针
		:_pnode(p)  //用传入的指针来初始化迭代器
	{}

	Ref operator*()  // 迭代器结构体的解引用运算符重载，返回指针指向的结构体里面存储的data
	{
		return _pnode->_data;
	}
	Ptr operator->()
	{
		return &_pnode->_data;
	}
	Self& operator  () //前置  ，返回一个迭代器对象，并且让指向结点的指针指向其next
	{
		_pnode = _pnode->_next;
		return *this;
	}
	Self operator  (int)
	{
		Self tmp(*this);
		_pnode = _pnode->_next;
		return tmp;
	}
	Self& operator--() //前置--，返回一个迭代器对象，并且让指向结点的指针指向其next
	{
		_pnode = _pnode->_prev;
		return *this;
	}
	Self operator--(int)
	{
		Self tmp(*this);
		_pnode = _pnode->_prev;
		return tmp;
	}
	bool operator!=(const Self& it) const
	{
		return _pnode != it._pnode;
	}
	bool operator==(const Self& it) const
	{
		return _pnode == it._pnode;
	}

};

整个迭代器唯一的成员变量就是一个指向结点的指针，在这个类里面我们实现了以下这些函数：

1. 构造函数：因为类中只包含一个指针，所以构造函数就是通过传入指针进行初始化
2. 解引用重载函数：返回指针指向结点的数据，这样在外界看来就和解引用直接获得数据一样了
3. 类成员访问运算符重载函数：因为STL容器可以装各种类型的数据，因此也当然可以存储结构体类型的数据，因此迭代器里面存放的自然就是结构体的指针，但迭代器自己作为类，他并不能直接使用此运算符，所以必须对此运算符进行重载。我们看到重载后函数会返回对应的地址，而我们想通过地址进行数据访问是需要再用一次类成员访问运算符的，就比如it->->类成员，但是这样虽然好理解但是可读性很差，所以在这里编译器替我们进行了处理，只要进行了重载，用一个运算符即可，也就是it->类成员
4. 前后置 和- -，就是重载成将指针指向前一个结点或后一个结点，前置返回修改后的，后置返回修改前的
5. 相等和不相等就是返回两个迭代器内的指针值是否相等

这里还涉及到后续const迭代器的实现，主要是借助模板的功能，我们后面会提到。

链表类成员及其方法定义

私有类成员

private:
	Node* _head;
	size_t _size;

正常来讲一个链表有个哨兵位就够了，这里增加一个size变量主要是为了能够降低调用size()方法的代价。如果没有这个成员变量，那么每次调用此方法都会遍历一次链表，代价较高。

几个重命名

typedef ListNode<T> Node; 
typedef __list_iterator<T, T&, T*> iterator; 
typedef __list_iterator<T, const T&,const T*> const_iterator; 

这里我们分别重命名了结点，通过给迭代器类传入两套不同的参数以实现非const迭代器和const迭代器并将他们进行重命名。

迭代器

迭代器包括const迭代器和非const迭代器，代码如下：

iterator begin()
{
	return iterator(_head->_next);  //返回begin迭代器，用哨兵位的next来传参生成匿名对象，因为哨兵位的下一个是第一个有效对象
}

iterator end()
{
	return iterator(_head);  //返回end迭代器，用哨兵位来传参生成匿名对象，因为哨兵位就是双向循环链表最后一个有效位置的下一个
}
const_iterator begin() const
{
	return const_iterator(_head->_next);
}

const_iterator end() const
{
	return const_iterator(_head);
}

构造函数

void empty_initialize()
{
	_head = new Node(T());
	_head->_next = _head;
	_head->_prev = _head;

	_size = 0;
}
List()
{
	empty_initialize();
}

默认构造的内容很简单，就是生成一个哨兵位，其前后指针均指向自己。

拷贝构造函数

template<class InputIterator>
List(InputIterator first, InputIterator last)
{
	empty_initialize();
	while (first != last)
	{
		push_back(*first);
		  first;
	}
}
void swap(List<T>& lt)
{
	std::swap(_head, lt._head);
	std::swap(_size, lt._size);
}
List(const List<T>& lt)
{
	empty_initialize();
	List<T> tmp(lt.begin(), lt.end());
	swap(tmp);
}

拷贝构造函数提供两种，第一种是迭代器区间的，比较好理解。第二种是我们常用的简洁写法，先将调用拷贝构造的对象初始化，然后借助第一个迭代器区间的构造初始化一个工具人，最后交换二者成员即可。

赋值运算符重载函数

List<T>& operator=(List<T> lt)
{
	swap(lt);
	return *this;
}

内容很简单，和前面两个容器的实现方式类似，都是通过传值调用来隐式调用拷贝构造，让临时对象来和调用赋值重载的对象进行成员变量交换以实现赋值。

size()

size_t size() const
{
	return _size;
}

因为我们增加了成员变量进行记录，所以可以直接返回变量值，否则就要对list进行遍历计数。

empty()

bool empty() const
{
	return _size == 0;
}

这里既可以使用_size，也可以判断头结点的前后指针是否指向自己。

clear()

void clear()
{
	iterator cur = begin();
	while (cur != end())
	{
		cur = erase(cur);
	}
	_size = 0;
}

此函数的主要功能就是清除掉所有非哨兵结点，然后将size置为0。

析构函数

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

因为我们前面实现了clear函数，所以这里直接调用即可，然后将哨兵结点释放、置空。

插入函数

iterator insert(iterator pos, const T& n)
{
	Node* newnode = new Node(n);

	Node* cur = pos._pnode;
	Node* prev = cur->_prev;
	//prev   newnode   cur
	newnode->_prev = prev;
	prev->_next = newnode;
	newnode->_next = cur;
	cur->_prev = newnode;

	  _size;
	return iterator(newnode);
}

先申请一个新结点，然后就是双向链表的插入操作，然后给size加一，最后以新结点为参数生成迭代器匿名对象做为返回值。

删除函数

iterator erase(iterator pos)
{
	assert(pos != iterator(_head));

	Node* next = pos._pnode->_next;
	Node* prev = pos._pnode->_prev;
	prev->_next = next;
	next->_prev = prev;

	delete[] pos._pnode;
	--_size;
	return iterator(next);
}

首先判断链表非空，然后将想要删除的结点从链表中摘出并将其delete掉，修改size后返回删除节点下一个位置的迭代器。

头删头插&尾删尾插

void push_back(const T& n)
{
	insert(end(), n);
}
void push_front(const T& n) 
{
	insert(begin(), n);
}
void pop_front()
{
	erase(begin());
}		
void pop_back()
{
	erase(--end());
}

复用实现好的插入和删除即可。

结束语

至此关于list类的简单实现的全部内容已呈现完毕，如本文有不足或遗漏之处还请大家指正，笔者感激不尽；同时也欢迎大家在评论区进行讨论，一起学习，共同进步！

这篇好文章是转载于：学新通技术网