【C++练级之路】【Lv.8】【STL】list类的模拟实现

快乐的流畅：个人主页

个人专栏：《C语言》《数据结构世界》《进击的C++》

远方有一堆篝火，在为久候之人燃烧！

---

引言

因为list结构的特殊性，所以拆分为结点、迭代器和list本身进行学习。

一、结点

细节：

1. 使用struct，标明公有属性（这样从外部调用比较方便）
2. list是带头双向循环链表
3. 提供全缺省的默认构造函数

template<class T>
struct __list_node
{
	__list_node<T>* _prev;
	__list_node<T>* _next;
	T _data;

	__list_node(const T& x = T())
		: _prev(nullptr)
		, _next(nullptr)
		, _data(x)
	{}
};
1
2
3
4
5
6
7
8
9
10
11
12
13

二、迭代器

由于list的每个结点物理空间不连续，导致迭代器不能像之前string、vector那样简单的设计为指针，而是设计为一个类（进行封装），以此完成*、->、++、–等一系列操作。

2.1 成员变量与默认成员函数

细节：

1. 仍然使用struct，标明公有属性
2. 成员变量是一个结点的指针
3. 提供带参构造函数（其余的默认成员函数不用显式定义，浅拷贝即可）

template<class T, class Ref, class Ptr>
struct __list_iterator
{
	typedef __list_node<T> node;
	typedef __list_iterator<T, Ref, Ptr> self;
	node* _node;

	__list_iterator(node* n)
		: _node(n)
	{}
};
1
2
3
4
5
6
7
8
9
10
11

此时的迭代器设计，可以说是list乃至STL的精华，天才般地运用了类的优势。

2.2 operator*

细节：

• 返回引用，为了区别普通迭代器和const迭代器

Ref operator*()
{
	return _node->_data;
}
1
2
3
4

2.3 operator->

细节：

• 返回指针，为了区别普通迭代器和const迭代器

Ptr operator->()
{
	return &_node->_data;
}
1
2
3
4

2.4 operator++

细节：

1. 为了区分前置和后置，后置参数加上int（无实际意义，以示区分）
2. 前置传引用返回，后置传值返回

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

self operator++(int)//后置++
{
	self tmp(*this);
	_node = _node->_next;
	return tmp;
}
1
2
3
4
5
6
7
8
9
10
11
12

2.5 operator- -

细节：同上

self& operator--()//前置--
{
	_node = _node->_prev;
	return *this;
}

self operator--(int)//后置--
{
	self tmp(*this);
	_node = _node->_prev;
	return tmp;
}
1
2
3
4
5
6
7
8
9
10
11
12

2.6 relational operators

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

bool operator==(const self& s)
{
	return _node == s._node;
}
1
2
3
4
5
6
7
8
9

三、list

3.1 成员变量

list类包含了

• _head（指向哨兵位）

template<class T>
class list
{
public:
	typedef __list_node<T> node;
private:
	node* _head;
};
1
2
3
4
5
6
7
8

3.2 迭代器

typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
1
2

3.2.1 begin

细节：

1. begin()在_head->next
2. 使用匿名对象

iterator begin()
{
	return iterator(_head->_next);
}

const_iterator begin() const
{
	return const_iterator(_head->_next);
}
1
2
3
4
5
6
7
8
9

3.2.2 end

细节：

1. end()在_head
2. 使用匿名对象

iterator end()
{
	return iterator(_head);
}

const_iterator end() const
{
	return const_iterator(_head);
}
1
2
3
4
5
6
7
8
9

3.3 默认成员函数

3.3.1 constructor

空初始化：创建哨兵位

void empty_init()
{
	_head = new node;
	_head->_prev = _head;
	_head->_next = _head;
}
1
2
3
4
5
6

无参构造

list()
{
	empty_init();
}
1
2
3
4

迭代器区间构造

细节：使用类模板，可以传任意类型的迭代器

template <class InputIterator>
list(InputIterator first, InputIterator last)
{
	empty_init();

	while (first != last)
	{
		push_back(*first);
		++first;
	}
}
1
2
3
4
5
6
7
8
9
10
11

3.3.2 destructor

~list()
{
	clear();
	delete _head;
	_head = nullptr;
}
1
2
3
4
5
6

3.3.3 copy constructor

现代写法

细节：

1. 用迭代器区间构造，构造出临时对象
2. 再使用list中的swap，交换*this和tmp的值，完成拷贝构造

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

	list<T> tmp(lt.begin(), lt.end());
	swap(tmp);
}
1
2
3
4
5
6
7

3.3.4 operator=

现代写法

细节：

1. 传参变成传值，这样就会拷贝构造出一个临时对象
2. 再使用list中的swap，交换*this和tmp的值，完成赋值重载

list<T>& operator=(list<T> lt)
{
	swap(lt);
	return *this;
}
1
2
3
4
5

3.4 修改

3.4.1 insert

指定位置插入

细节：

1. 在pos之前插入
2. 迭代器不会失效

void insert(iterator pos, const T& x)
{
	node* cur = pos._node;
	node* prev = cur->_prev;
	node* new_node = new node(x);

	prev->_next = new_node;
	new_node->_prev = prev;
	cur->_prev = new_node;
	new_node->_next = cur;
}
1
2
3
4
5
6
7
8
9
10
11

3.4.2 push_front

头插

void push_front(const T& x)
{
	insert(begin(), x);
}
1
2
3
4

3.4.3 push_back

尾插

void push_back(const T& x)
{
	insert(end(), x);
}
1
2
3
4

---

3.4.4 erase

指定位置删除

细节：

1. assert断言，防止删除哨兵位
2. 返回删除节点的下一位，防止迭代器失效

iterator erase(iterator pos)
{
	assert(pos != end());
	
	node* cur = pos._node;
	node* prev = cur->_prev;
	node* next = cur->_next;

	prev->_next = next;
	next->_prev = prev;
	delete cur;

	return iterator(next);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.4.5 pop_front

void pop_front()
{
	erase(begin());
}
1
2
3
4

3.4.6 pop_back

void pop_back()
{
	erase(--end());
}
1
2
3
4

---

3.4.7 clear

清除所有结点（除哨兵位以外）

void clear()
{
	iterator it = begin();
	while (it != end())
	{
		erase(it++);
	}
}
1
2
3
4
5
6
7
8

3.4.8 swap

交换两个list类的值

细节：使用std库中的swap函数，交换各个成员变量的值

void swap(list<T>& lt)
{
	std::swap(_head, lt._head);
}
1
2
3
4

总结

学习完list类，对于STL中的精华——迭代器设计，有了更深一步的了解。同时，了解多参数模板的用途和方法，极大提高代码复用程度。

真诚点赞，手有余香