CD46.【C++ Dev】list的模拟实现(1)

zhangcoder

已于 2025-07-08 21:51:09 修改

阅读量603

点赞数 10

CC 4.0 BY-SA版权

分类专栏： C++ Develop 文章标签： c++ 开发语言 list 算法数据结构

于 2025-07-08 11:14:30 首次发布

本文链接：https://blog.csdn.net/2401_85828611/article/details/148772998

C++ Develop 专栏收录该内容

44 篇文章

订阅专栏

1.STL库的list

模拟实现list之前,先看看STL库里的list是怎么做的

STL v3.0版本代码一览:

先看链表的结构体和构造函数

结构体:

template <class T>
struct __list_node {
  typedef void* void_pointer;
  void_pointer next;//后指针
  void_pointer prev;//前指针
  T data;//数据域
};

看到next和prev,显然是双向链表,复习双向链表的参见:

96.【C语言】数据结构之双向链表的初始化,尾插,打印和尾删
 97.【C语言】数据结构之双向链表的头插,头删,查找,中间插入,中间删除和销毁函数

CC32.【C++ Cont】静态实现双向链表及STL库的list

构造函数:

list() { empty_initialize(); }//调用空链表的构造函数

void empty_initialize() { 
  node = get_node();//调用空间配置器
  node->next = node;
  node->prev = node;
}

//......
protected:
  link_type node;

2.模拟实现

定义节点结构体next和prev成员变量,不建议用void_pointer,因为void*需要强制类型转换,比较麻烦

节点结构体

仿照STL:

namespace mystl
{
	template<class T>
	struct __list_node
	{
		typedef __list_node<T>* link_type;
		link_type next;
		link_type prev;
		T data;
	};

	//......
}

list类

框架:

template<class T>
class list
{
	typedef __list_node<T> list_node;
public:
private:
};

发现STL库中的成员变量只有一个

node为__list_node<T>的指针,显然是双向链表的哨兵位,如下图

照葫芦画瓢写:

template<class T>
class list
{
	typedef __list_node<T> list_node;
	typedef __list_node<T>* link_type;
public:
private:
	link_type node;
};

无参构造函数

生成哨兵位,让next和prev都指向自己

list()
{
	node = new list_node;
	node->next = node;
	node->prev = node;
}

测试代码:

#include "list.h"
int main()
{
	mystl::list<int> ls;
	return 0;
}

下断点到return 0,看看无参构造函数是否能正常工作

可以正常工作

尾插函数

void push_back(const T& x)
{
	link_type tmp = new list_node;
	tmp->data = x;
	//先找尾
	link_type tail = node->prev;
	tail->next = tmp;
	tmp->prev = tail;
	tmp->next = node;
	node->prev = tmp;
}

测试代码:

#include "list.h"
using namespace std;
int main()
{
	mystl::list<int> ls;
	ls.push_back(1);
	ls.push_back(2);
	ls.push_back(3);
	return 0;
}

运行结果:

当然上面的代码可以简写

link_type tmp = new list_node(x);

new list_node(x)会自动调用list_node的构造函数,需要提前准备,将list_node构造函数写在struct list_node中即可

struct __list_node
{
	typedef __list_node<T>* link_type;

	__list_node(const T& x = T())//写成缺省参数的形式
		:next(nullptr)
		, prev(nullptr)
		, data(x)
	{}

	link_type next;
	link_type prev;
	T data;
};

迭代器★

迭代器的本质:自定义类型的封装

list迭代器不能像模拟vector一样是指针,因为list不是连续区间,因此迭代器需要重新定义,能让迭代器++能直接指向下一个节点

即封装自定义指针成对象,符合C++面向对象的思想

//it是迭代器,本质上都是调用类的成员函数
it.operator++();
it.operator++(0);
it.operator--();
it.operator--(0);
it.operator*();
it.operator!=(...);
it.operator==(...);

STL库的解决方法:写成结构体,存储节点的指针

struct __list_iterator
{
    link_type node;
};

(省略了成员函数和typedef)

再自定义成iterator

typedef __list_iterator<T> iterator;

可以发现迭代器定义成了实例化的类

注意:__list_iterator定义成类时不要定义到list里面,嵌套类(可参见文章)是有限制的!

template<class T>
struct __list_iterator//是类
{
	typedef __list_node<T>* link_type;
	link_type node;
};

当然list类里面要定义迭代器,这样利用访问

begin()

写在list类中,可以直接构造iterator对象返回

iterator begin()
{
	//返回哨兵位的下一个节点
    //或者写成return node->next;使用隐式类型转换
	return iterator(node->next);//构造对象返回
}

当然node->next是自定义类型,需要手动在__list_iterator类中添加构造函数,这个很容易忘

struct __list_iterator
{
	typedef __list_node<T>* link_type;
	__list_iterator(link_type x)
	{
		node = x;
	}
	link_type node;
};

或者写成初始化列表:

__list_iterator(link_type x)
	:node(x)
{}

测试代码:

#include <iostream>
#include "list.h"
int main()
{
	mystl::list<int> ls;
	ls.push_back(1);
	ls.push_back(2);
	ls.push_back(3);
    //::可以访问typedef的或者访问内部类
	mystl::list<int>::iterator it=ls.begin();
	return 0;
}

运行结果:

operator++

operator++是__list_iterator类的方法,不能写在list类中,因为list类中没有迭代器成员变量

前置++

返回++后的iterator

typedef __list_iterator<T> iterator;
iterator& operator++()
{
	node= node->next;
	return *this;
}

后置++

返回++前的iterator

iterator operator++(int)
{
	iterator tmp(*this);
	node= node->next;
	return tmp;
}

operator--

因为是双向链表,所以可以向前和向后移动迭代器

前置--

返回--后的iterator

iterator& operator--()
{
	node = node->prev;
	return *this;
}

后置--

返回--前的iterator

iterator& operator--(int)
{
	iterator tmp(*this);
	node = node->prev;
	return tmp;
}

operator!=

注意两个const修饰

const iterator& x防止权限放大,而且begin()和end()返回的是临时对象具有常性

operator!=末尾的const是防止修改node

bool operator!=(const iterator& x) const
{
	return node != x.node;
}

operator==

bool operator==(const iterator& x) const
{
	return node == x.node;
}

end()

写在list类中,由于是双向链表,因此返回哨兵位即可

iterator end()
{
	//返回哨兵位
	return node;//隐式类型转换,完整写法:iterator(node)
}

测试代码:用迭代器遍历

#include <iostream>
#include "list.h"
int main()
{
	mystl::list<int> ls;
	ls.push_back(1);
	ls.push_back(2);
	ls.push_back(3);
	mystl::list<int>::iterator it=ls.begin();
	while (it != ls.end())
	{	
		std::cout << it.node->data << " ";
		++it;
	}
	return 0;
}

运行结果:

operator*

虽然这里定义的迭代器是实例化的对象,但是迭代器任务是模拟指针行为,因此要有operator*

T& operator*()
{
	return node->data;
}

测试代码

#include <iostream>
#include "list.h"
int main()
{
	mystl::list<int> ls;
	ls.push_back(1);
	ls.push_back(2);
	ls.push_back(3);
	mystl::list<int>::iterator it = ls.begin();
	std::cout << *it;
	return 0;
}

注:mystl::list<int>::iterator it = ls.begin();会自动调用默认的拷贝构造,由于__list_iterator的成员变量是自定义类型的指针,浅拷贝没有问题,而且__list_iterator 不用写析构函数,节点应该是list类释放,迭代器只是借助节点访问

运行结果:

const修饰的迭代器的设计

能这样写吗?

typedef const __list_iterator<T> const_iterator;

不可以, const修饰的是 __list_iterator<T>这个类,类的成员函数不能被修改

一个简明的例子说明:

class myclass
{
public:
	int* node;
	int data;
};

int main()
{
	const myclass obj;
	obj.node++;
}

obj.node++是不被允许的,被const修饰的对象的成员变量是不能被修改的

要明确: 无论是否有const修饰,双向迭代器是要能用operator++和operator--进行修改来访问的,但const修饰的迭代器指向的内容是不能被修改的,非const修饰的迭代器指向的内容能被修改

(有关const修饰的基础问题参见38.【C语言】指针（重难点）（C)文章)

那const修饰的迭代器应该模拟类似const T* ptr的情况

在迭代器的成员函数中,只有operator*需要修改,其余都不变

下文将介绍两种处理方法