C++ list容器模拟实现

何为list？

list是一个容器，list的底层是带头双向循环链表，支持在任意位置插入与删除，并且时间复杂度为O(1)。list的使用与vector类似，这里就不再赘述，这篇博客是对list的模拟实现，以提升对其理解。

list的模拟实现

节点

list的底层是带头双向循环链表，链表的节点单独作为一个类，节点有指针域和数据域，指向前节点的指针和指向后节点的指针，节点保存的数据，三个成员变量，需要写一个默认构造函数，根据形参创建节点，将两个指针置空。

template <class T>
struct list_node
{
	list_node(const T data = T());
	T _data;
	list_node* prev;
	list_node* next;
};

template <class T>
myList::list_node<T>::list_node(T data)
{
	_data = data;
	prev = nullptr;
	next = nullptr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

迭代器

之前模拟实现的string和vector的迭代器都是原生指针，使用起来很方便，但链表的物理结构是分散的，空间不连续导致不能像string和vector一样使用原生指针作为迭代器。list的迭代器需要对指针进行封装，使其成为一个类，重载++，–，*，等操作。所以list迭代器是一个类，该类只有一个成员变量，就是指向节点的指针，节点有数据域和指针域，对迭代器解引用要返回节点的数据域，++，–要使指针指向前或后的节点。

template <T, Ref, Ptr>
struct __list_iterator
{
	typedef list_node<T> Node;
	// 迭代器有三个模板参数，第一个是节点数据域中的数据类型，Ref是该数据的引用，Ptr是指向该数据的指针
	typedef __list_iterator<T, Ref, Ptr> self;
	
	self(Node* node)
	{
		_node = node;
	}

	self& operator++()
	{
		_node = _node->_next; // 将迭代器的成员，节点的指针指向下一个节点，再返回该指针
		return *this;
	}
	
	self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}
	
	self& operator++(int)
	{
		self tmp(_node);
		_node = _node->_next;
		return tmp;
	}

	self& operator--(int)
	{
		self tmp(_node);
		_node = _node->_prev;
		return tmp;
	}

	Ref operator*() // 对迭代器的解引用操作，返回数据的引用
	{
		return _node->_data;
	}
	
	// 如果数据域存储的数据是自定义的一个类，类的成员是内置类型的，此时可以对迭代器->操作，去访问自定义类型中的数据
	// 但重载的->返回的是数据域中数据的指针，需要再一次解引用(it->->xxx)
	// 但不用连续写两个操作符，编译器会自动优化
	Ptr operator->() // 对迭代器的解引用操作，返回数据的指针
	{
		return &(_node->_data);
	}

	bool operator==(const self& it)
	{
		return it._node == _node; // 判断两迭代器是否相等的操作，根据迭代器的成员_node是否相等为依据进行判断
	}

	bool operator!=(const self& it)
	{
		return it._node != _node;
	}
	
	Node* _node; // 迭代器唯一的成员，指向节点的指针
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

至于迭代器的拷贝构造，赋值要不要实现，答案是不用，因为迭代器不管理资源，因此编译器自动生成的浅拷贝就够用了。

list类

list类只有一个成员变量，就是链表的头节点，该头节点不存储任何数据，所以一个list对象创建后，需要对头节点分配空间

类的整体框架

template <class T>
class list
{
	typedef list_node<T> Node;
	typedef __list_iterator<T, T&, T*> iterator;
	typedef __list_iterator<T, const T&, const T*> const_iterator;
	// 迭代器有三个模板参数，根据创建的list对象是否有const修使，生成对应的模板类
	
	// 构造和析构
	list();
	template <class InputIterator>
	list(InputIterator first, InputIterator last); // 用迭代器指向的头尾区间构造list
	list(const list& x);
	void swap(list& x);
	list& operator=(list x);
	~list();

	// 修改
	iterator insert(iterator pos, T val);
	iterator erase(iterator pos);
	void push_back(T val);
	void push_front(T val);
	void pop_back();
	void pop_front();
	void clear();

	// 迭代器
	iterator begin();
	const_iterator begin() const;

	iterator end();
	const_iterator end() const;

private:
	Node* _head;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

构造和析构

list的构造：为头节点分配空间，并将前后指针指向自己

template <T>
myList::list<T>::list()
{
	_head = new Node;
	_head->_prev = _head;
	_head->_next = _head;
}
1
2
3
4
5
6
7

用迭代器区间构造list容器，用first迭代器遍历区间，将解引用迭代器得到的数据尾插到list容器中。但插入数据前头节点还没分配空间，没有头节点就进行尾插，程序会崩溃，所以在尾插前要为头节点开辟空间，并使其前后指针指向自己。

template <class T>
template <class InputIterator>
myList::list<T>::list(InputIterator first, InputIterator last)
{
	_head = new Node;
	_head->_prev = _head;
	_head->_next = _head;
	while (first != last)
	{
		push_back(*first);
		first++;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

拷贝构造：利用迭代器区间的构造函数，用拷贝对象的迭代器区间构造一个tmp临时对象，此时的tmp是拷贝对象的复制，只要交换当前容器和tmp容器就能完成拷贝构造，但前提是要对头节点分配空间，否则交换后tmp的释放会崩溃（不像vector和string的拷贝构造只要把指针置空就行，vector和string的析构是delete指针，对于空指针是不会进行释放的，但list要怎么判空？头节点的下一个节点还是头节点为空，所以要为头节点分配空间。

template <class T>
myList::list<T>::list(const list& x)
{
	_head = new Node;
	_head->next = _head;
	_head->prev = _head;

	list<T> tmp(x.begin(), x.end());
	swap(tmp);
}

void myList::list<T>::swap(list& x)
{
	std::swap(_head, x._head); // 交换两容器的头节点
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

赋值运算符的重载：形参不加引用，使得要形成形参就要调用拷贝构造函数，此时的形参是赋值对象的拷贝，将当前容器和形参交换，完成赋值

template <class T>
myList::list<T>& myList::list<T>::operator=(list x)
{
	swap(x);
	return *this;
}
1
2
3
4
5
6

析构：复用clear，clear函数的作用是释放所有节点，只留下头节点，所以调用完clear后只要删除释放头节点，将其置空就行

template <class T>
myList::list<T>::~list()
{
	clear();
	delete _head;
	_head = nullptr;
}
1
2
3
4
5
6
7

修改

实现了在任意位置的插入和删除，其他的修改复用这两个函数即可。

insert：在传入的迭代器位置处插入一个节点，先保存迭代器指向的节点和前一个节点，剩下就简单了，注意函数返回新插入节点的迭代器

template <class T>
typedefname myList::list<T>::iterator myList::list<T>::insert(iterator pos, T val)
{
	Node* curr = pos._node;
	Node* prev = curr->prev;
	Node* new_node = new Node(val);

	prev->_next = new_node;
	new_node->_prev = prev;
	new_node->_next = curr;
	curr->_prev = new_node;
	
	return iterator(new_node);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

erase：任意位置的删除，删除该迭代器指向的节点，这里有个迭代器失效的问题，因为从外面传入的迭代器指向的节点被释放了，外面无法继续使用这个迭代器了，所以erase的返回值是删除位置的下一个迭代器，这样外面就能更新迭代器了。

template <class T>
typedefname myList::list<T>::iterator myList::list<T>::erase(iterator pos)
{
	Node* curr = pos._node;
	Node* prev = curr->_prev;
	Node* next = curr->_next;
	
	prev->_next = next;
	next->_prev = prev;
	delete curr; // 最后别忘了释放当前节点
	
	return iterator(next);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

剩下的尾插头删啥的都是复用这两个接口，没啥好说的

template <class T>
void myList::list<T>::push_back(T val)
{
	insert(end(), val);
}

template <class T>
void myList::list<T>::pop_back()
{
	erase(end()->_prev);
}

template <class T>
void myList::list<T>::push_front(T val)
{
	insert(begin(), val);
}

template <class T>
void myList::list<T>::pop_front()
{
	erase(begin());
}

template <class T>
void myList::list<T>::clear()
{
	if (_head) // 头节点为nullptr不删除
	{
		iterator it = begin();
		while (it != end())
		{
			it = erase(it); // 注意迭代器失效
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

迭代器定义

begin函数返回头节点的下一个节点，end函数返回头节点，也没啥好说的

template <class T>
typename myList::list<T>::iterator myList::list<T>::begin()
{
	return iterator(_head->next);
}

template <class T>
typename myList::list<T>::const_iterator myList::list<T>::begin() const
{
	return const_iterator(_head->next);
}

template <class T>
typename myList::list<T>::iterator myList::list<T>::end()
{
	return iterator(_head);
}

template <class T>
typename myList::list<T>::const_iterator myList::list<T>::end() const
{
	return const_iterator(_head);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

总结：在学习过链表的基础上，模拟实现list就比较简单，有几个要注意的。

1.拷贝构造list需要对头指针进行初始化，否则交换后的析构会崩溃
2.erase的迭代器失效问题，外面需要更新迭代器
3.迭代器的设计需要时间理解，const对象需要用const迭代器，不是实现两个类模板，而是添加模板参数，const对象传const T*和const T&作为非const对象的区分
1
2
3