C++ list 模拟实现

 

目录

1. 基本结构的实现

2.  list()

3. void push_back(const T& val)

4. 非 const 迭代器

4.1 基本结构 

4.2 构造函数 

4.3 T& operator*()

4.4  __list_iterator& operator++()

4.5 bool operator!=(const __list_iterator& it)

4.6 T* operator->()

5. const 迭代器 

6. begin() && end()

​编辑

7. iterator insert(iterator pos, const T& val)

8. iterator erase(iterator pos)

9. void push_front(const T& val)

10. void pop_front()

11. void pop_back()

12. size_t size() const

13. void clear()

14. ~list()

---

1. 基本结构的实现

在 list 的使用部分，我们已经知道了 list 其实就是一个带头的双向循环链表 (以下简称双链表)。结合我们在 C 语言写过的双链表的实现：C语言数据结构初阶(4)----带头双向循环链表_姬如祎的博客-CSDN博客

第一步要做的就是定义出链表的节点。和 C 语言不一样的是，list 可以存储任意类型的数据，因此必须定义成模板。 老规矩为了与库中的 list 做区分，我们还是会把自己模拟实现的 list 放到一个命名空间里面。

namespace Tchey
{
    template<class T>
    struct ListNode
    {
    	T _val;
    	ListNode* _prev;
    	ListNode* _next;
    
    	ListNode(const T& val = T())
    		:_val(val)
    		,_prev(nullptr)
    		,_next(nullptr)
    	{}
    };
}

在 C++ 中结构体被提升成了类，因此在定义双链表的节点的时候，我们可以写一个节点的构造函数，这样在堆上申请节点的时候，就能够直接初始化节点的 val 值啦！

OK，既然双链表的节点定义好了，list 类中的成员变量应该如何定义呢？起始很简单，list 类想要维护一个双链表只需要维护头结点的指针就可以了。因为 list 是带头的双链表，因此，list 的成员变量就是那个哨兵位的头结点的指针。

namespace Tchey
{
    template<class T>
    class list
    {
    private:
	    ListNode* _head;
    };
}

2.  list()

这个是 list 的无参构造函数，他的任务就是做好初始化哨兵位的头结点的工作。你还记得双向带头循环链表的初始化应该怎么做吗？看下面的图你应该就会记得了吧！

因为哨兵位的头结点是不需要存储任何有效的数据的，他的 val 值填多少都无所谓！索性就不填了，用默认的 val 就行。

list()
{
	_head = new ListNode;
	_head->_next = _head;
	_head->_prev = _head;
}

3. void push_back(const T& val)

这个是双链表的尾插，双链表的尾节点，就是哨兵位的头结点的 _prev。开辟新节点，找到尾节点，做好链接工作就行啦！不知道如何链接，请看 C 语言实现的双向链表中的 push_back 函数：

C语言数据结构初阶(4)----带头双向循环链表_姬如祎的博客-CSDN博客

void push_back(const T& val)
{
	ListNode* newNode = new ListNode(val);
	ListNode* tail = _head->_prev;
 
	tail->_next = newNode;
	newNode->_prev = tail;
 
	_head->_prev = newNode;
	newNode->_next = _head;
}

4. 非 const 迭代器

list 的迭代器是我们遇到的第一个不是原生指针的迭代器，我们来看看他的迭代器和 vector 迭代器的差别：

对于 vector 来说，他的迭代器是 int 类型的指针 (假设vector存储 int 数据)，解引用就直接能访问到真实的数据。如果 list 也是原生指针，那只能是结构体的指针，解引用得到的就是一个结构体，无法拿到真实的数据。list 拿到数据需要通过访问结构体的 _val 成员得到。

对于 vector 来说，他的迭代器是 int 类型的指针 (假设vector存储 int 数据)，并且 vector 的存储空间是连续的。迭代器加加就能直接跳过一个整形的空间，直接指向下一个有效的数据。

list 呢，物理空间不连续，如果 list 迭代器是结构体指针，加加之后访问到的空间并一定不属于你，可能会发生内存错误。实际上 list 的迭代加加之后，应该是指向节点的下一个节点，即需要通过 _next 找到下一个节点。

综上所述，list 的迭代器不可能是原生指针，需要对节点的指针进行封装。封装时，我们需要重载 *，++，等运算符，这样才能正确实现迭代器的效果。

4.1 基本结构 

我们已经知道了，list 的迭代器就是对原生的结构体指针进行封装。然后通过运算符重载实现迭代器应有的功能。那这个迭代器的成员变量当然就是一个节点的指针啦！

namespace Tchey
{
	template<class T>
	struct __list_iterator
	{
	public:
 
	private:
		ListNode* _node;
	};
}

4.2 构造函数 

在 list 类里面，有 begin()，end() 之类的函数，用来返回一个迭代器对象，那么我们实现的迭代器就需要提供构造函数，支持使用节点的指针构造出来一个迭代器对象。

__list_iterator(ListNode* node)
	:_node(node)
{}

4.3 T& operator*()

我们都使用过迭代器遍历一个容器，知道了迭代器的解引用解释返回真实有效的数据，因此 operator 就是返回节点的 _val 值。

T& operator*()
{
	return _node->_val;
}

4.4  __list_iterator& operator++()

对于 list 来说迭代器加加实际上就是让迭代器的成员变量 _node 指向当前节点的下一个节点。

__list_iterator& operator++()
{
	_node = _node->_next;
	return *this;
}

4.5 bool operator!=(const __list_iterator& it)

这个函数就是判断两个迭代器是否是一样的嘛，判断的逻辑就是判断两个迭代成员的节点指针是否相同。不能不写 const 因为 list 中的 begin()，end() 返回的都是一个迭代器的拷贝，当我们自己定义的迭代器变量与 end() 的返回值做 != 判断时就会调用 operator!= 如果没有 const，因为 end 的返回值具有常性，是无法用非 const 的迭代器类型来接收的。

bool operator!=(__list_iterator& it)
{
	return _node != it._node;
}

4.6 T* operator->()

为什么要重载这种解引用的方式呢？emm，如果 list 容器存储的是一个结构体类型，或者其他自定义类型，那么重载了 -> 就能较为方便拿到我们的数据！

如果我没有重载 -> 那么当我们用迭代器区访问一个存储自定义类型的 list 的时候，你就需要这么写：

struct info
{
	int a;
	int b;
};
 
int main()
{
	info in = { 10,20 };
	list lt;
	lt.push_back(in);
 
	auto it = lt.begin();
	while (it != lt.end())
	{
		cout << (*it).a << " " << (*it).b << endl;
		it++;
	}
	return 0;
}

但是如果你重载了 -> 这个运算符，你就可以这么写： 

struct info
{
	int a;
	int b;
};
 
int main()
{
	info in = { 10,20 };
	list lt;
	lt.push_back(in);
 
	auto it = lt.begin();
	while (it != lt.end())
	{
		cout << it->a << " " << it->b << endl;
		it++;
	}
	return 0;
}

 我们下来看看怎么重载 -> 这个吧，其实重载 -> 就是返回 list 中的成员变量的 _val 的地址：

T* operator->()
{
	return &(_node->_val);
}

上面的例子中在使用迭代器遍历 list 的时候，it->a，本质上应该是先调用 operator-> 得到结构体的指针，再通过 -> 拿到数据，因此实际上应该这么写的：it->->a。但是这样写着实奇怪， 因此编译器会进行处理，我们只需要这么写就可以：it->a。 

5. const 迭代器 

首先，我们要理解 const 迭代器和非 const 迭代器的区别：

在 const 迭代器中解引用返回的数据是不能够更改的。

在 const 迭代器中 operator-> 返回的指针解引用得到的数据也是不能修改的！

也就是说在 const 迭代器中 operator* 的返回值应该是 const T&，operator-> 的返回值应该是 const T* 。然后，你一拍脑袋说，这好办哇！我们把非 const 迭代器的代码 copy 一份，改成 const 迭代器不就行了嘛！是的这样做完全没问题，但是，既然我们学了模板，这样的脏活累活自然得交给我们的编译器去做啦！

我们来看看怎么把 const 迭代器和非 const 迭代器融合成一个模板吧！const 迭代器和非 const 迭代器的不同就是右两个函数的返回值类型不同嘛，因此我们可以将函数的返回值的类型参数化，通过外部实例化的传递来决定是 const 迭代器还是非 const 迭代器！

因为有两个函数的返回值不相同，所以我们需要为我们封装的迭代器增加两个模板参数！

当我们传入 T&，T* 就是非 const 的 iterator，当我们传入 const T&，const T* 就是 const 的 iterator。是不是美妙绝伦！

__list_iterator 的模板参数改了，其他的函数也相应地改改嘛！因为给 __list_iterator 加上模板参数之后呢，这个类型写起来就比较复杂，我们可以使用 typedef 给他重新去一个名字

template<class T, class Ref, class Ptr>
struct __list_iterator
{
public:
 
typedef __list_iterator self;
 
__list_iterator(ListNode* node)
	:_node(node)
{}
 
self& operator++()
{
	_node = _node->_next;
	return *this;
}
 
bool operator!=(const self& it)
{
	return _node != it._node;
}
 
 
Ref operator*()
{
	return _node->_val;
}
 
Ptr operator->()
{
	return &(_node->_val);
}
 
private:
ListNode* _node;
};

6. begin() && end()

上面的那张图已经解释了如何定义 const 迭代器和非 const 迭代器啦！那么 begin() 与 end() 的 const 版本和 非 const 版本就是信手拈来了！

begin 对应的迭代器起始就是用 _head->_next 构造一个迭代器返回！

typedef __list_iterator iterator;
typedef __list_iteratorconst T&, const T*> const_iterator;
 
iterator begin()
{
	return _head->_next;
}
 
iterator end()
{
	return _head;
}
 
const_iterator begin() const
{
	return _head->_next;
}
 
const_iterator end() const
{
	return _head;
}

为啥可以直接返回节点的指针呢 ？因为单参数的构造函数支持隐式类型转化嘛！

其实 list 的模拟实现，难的就是迭代器的部分，好的，我们的迭代器就已经实现完毕了！懂的都懂嘛！ 

7. iterator insert(iterator pos, const T& val)

我们先通过 pos 拿到节点的指针，申请节点，链接就行了，相当简单呢！最后返回新插入的节点的迭代器。

void insert(iterator pos, const T& val)
{
	ListNode* cur = pos._node;
	ListNode* prev = cur->_prev;
	ListNode* newNode = new ListNode(val);
 
	prev->_next = newNode;
	newNode->_prev = prev;
			
	newNode->_next = cur;
	cur->_prev = newNode;
    return newNode;
}

8. iterator erase(iterator pos)

 在 list 的使用哪一节，我们观察到了，erase 是不能删除 end() 位置的节点的，即不能删除哨兵位的头结点。我们可以使用断言检查。为了解决迭代器失效的问题呢，我们可以给 erase 增加一个返回值。

iterator erase(iterator pos)
{
	ListNode* cur = pos._node;
 
	ListNode* prev = cur->_prev;
	ListNode* next = cur->_next;
 
	delete cur;
	prev->_next = next;
	next->_prev = prev;
 
	return next;
}

9. void push_front(const T& val)

在我们完成了 insert 接口和 erase 接口的实现之后，下面的插入删除可以完全复用啦！

void push_front(const T& val)
{
	insert(begin(), val);
}

10. void pop_front()

void pop_front()
{
	erase(begin());
}

11. void pop_back()

这里的 -- 需要在迭代器里面重载，原理和 ++ 差不多，就交给你来实现啦！

void pop_back()
{
	erase(--end());
}

12. size_t size() const

遍历一遍出结果，或者呢，你也可以在 list 里面维护一个表示 list 长度的变量。

size_t size() const
{
	int sz = 0;
	auto it = begin();
	while (it != end())
	{
		sz++;
		++it;
	}
	return sz;
}

13. void clear()

这个函数是清空 list 存储有效数据的节点，也就是说 clear 之后呢，哨兵位的头结点还在！

切记不可以 ++it，因为迭代器失效的问题嘛！我们通过 erase 的返回值来清除节点就行啦。

void clear()
{
	auto it = begin();
	while (it != end())
	{
		it = erase(it);
	}
}

14. ~list()

主打的就是一个复用。我们写完 clear 之后析构函数直接复用，然后再释放掉 _head 就可以啦！

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