C++第二十四弹---从零开始模拟STL中的list(上)

list基本结构，默认构造函数，尾插函数，普通迭代器类的封装，迭代器与list进行关联，链表的增删函数~~~

小林熬夜学编程

1706人浏览 · 2024-06-06 12:03:46

小林熬夜学编程 · 2024-06-06 12:03:46 发布

✨个人主页：熬夜学编程的小林

💗系列专栏：【C语言详解】【数据结构详解】【C++详解】

1、基本结构

namespace lin
{
	template<class T>
	struct ListNode//双向循环链表的基本结构
	{
		ListNode<T>* _prev;//前驱指针
		ListNode<T>* _next;//后继指针
		T _data;//数据值
        
        //不传值时使用T()默认值构造，传值则传值构造
		ListNode(const T& val = T())//默认构造 + 传值构造
			:_prev(nullptr)
			,_next(nullptr)
			,_data(val)
		{}
	};

    template<class T>
    struct ListIterator//迭代器封装类，成员都会被调用，因此使用struct
    {
	    typedef ListNode<T> Node;
        Node* _node;//结点指针
    }

    template<class T>
    class list//链表模板类，成员变量定义及函数封装
    {
	    typedef ListNode<T> Node;//将链表结构取别名，简化代码
    public:
        typedef ListIterator<T> iterator;//迭代器重命名
    private:
	    Node* _head;//链表头指针
        size_t size;//链表长度
    }
}

上述代码实现了双向循环链表的基本结构，其中包含了四个部分：

1.namespace lin，命令空间 lin 是用于封装代码，避免同名类型和函数冲突。

2.在命名空间中，定义了模板类ListNode(双向循环链表基本结构)，该类包含三个成员变量：

_prev : 存储指向前一个结点的指针
_next : 存储指向后一个结点的指针
_data : 存储数据

ListNode类还实现一个有缺省值(T())的构造函数，如果构造函数没有提供参数，则使用T类型的默认构造来初始化_data，如果传值则使用该值来初始化_data，该构造函数也会将_prev和_next指针指向nullptr。

3.模板类ListIterator(迭代器封装)，该类包含一个成员变量，即链表的结点指针：

为什么链表需要封装一个迭代器的类呢？？？

链表的物理空间是不连续的，是通过结点的指针依次链接。
不能像string和vector一样直接解引用去访问其数据。
结点的指针解引用还是结点，结点指针++还是结点指针。
在string和vector的物理空间是连续的，所以这俩不需要实现迭代器类，可以直接使用。

4.模板类list(链表的基本成员变量及其函数接口)，该类包含两个成员变量：

_head : 链表的头结点指针
_size : 链表的长度

2、基本函数实现

注意：我们实现的是带头双向循环链表。

2.1、默认构造函数

list()

默认构造的函数功能是构造一个没有元素的空容器。

思路：我们实现的是带头双向循环链表，因此默认构造时我们需要创建(new)一个头结点，并将链表长度初始化为0。

//构造头结点函数
void empty_init()
{
	_head = new Node;//创建新结点
	_head->_next = _head;
	_head->_prev = _head;
    _size = 0;
}

//默认构造 构造一个头结点
list()
{
	empty_init();
}

为了后序使用方便，我们将构造头结点封装成了一个函数。

2.2、尾插数据

为什么在第二个函数就写尾插呢？因为后面的函数会大量用到尾插函数。

push_back()

思想：

先找到尾结点，即头结点的前一个结点。
然后将尾结点，新结点以及头结点进行链接。

void push_back(const T& val)
{
	//tail _head->_prev
	Node* tail = _head->_prev;

	Node* newnode = new Node(val);//创建一个值为val的新结点
	//tail newnode _head //链接关系的顺序
	tail->_next = newnode;
	newnode->_prev = tail;
	newnode->_next = _head;
	_head->_prev = newnode;

	_size++;//尾插之后长度要++
}

我们尾插完数据之后，想要遍历整个链表怎么遍历呢？？？

我们在使用链表的时候是通过迭代器进行遍历，如下代码：

void test_list1()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);

	list<int>::iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	cout << lt.size() << endl;
}

此时我们就需要对链表的迭代器进行封装！！！

3、迭代器的封装

此时的迭代器是一个结点指针(Node*)。

3.1、迭代器的基本结构

template<class T>
struct ListIterator
{
    typedef ListNode<T> Node;//类型起别名
    Node* _node;//成员变量
    ListIterator(Node* node)//构造函数
        :_node(node)
    {}
};

但是我们使用迭代器时，是在list内部进行使用的，且类型名称为iterator，因此需要在list内部重命名迭代器类型(公有的，因为我们需要在类外访问)。

template<class T>
class list 
{
public:  
    typedef ListIterator<T> iterator;//迭代器重命名
};

迭代器实质是一个结点指针，因此类的成员是_node(结点指针)，此处我们使用一个结点的指针对其初始化。

typedef ListNode<T> Node;//类型起别名
    Node* _node;//成员变量
    ListIterator(Node* node)//构造函数
        :_node(node)
    {}

3.2、迭代器重载函数的实现

前置++

先++，再使用，返回的是++后的结点，用引用返回。

//前置++
typedef ListIterator<T> Self//对返回迭代器类型重命名，因为原类型较长
Self& operator++()
{
	_node = _node->_next;
	return *this;
}

后置++

先使用，再++，返回的是++前的结点，传值返回。

typedef ListIterator<T> Self
Self operator++(int)
{
	Self tmp(*this);//构造一个临时变量存储之前的结点
	_node = _node->_next;
	return tmp;//返回临时对象
}

注意：前置和后置的区别是，后置需要在形参中传一个占位符，一般使用int类型。

前置--

先--，再使用，返回的是--后的结点，用引用返回。

Self& operator--()
{
	_node = _node->_prev;
	return *this;
}

后置--

先使用，再++，返回的是++前的结点，传值返回。

Self operator--(int)
{
	Self tmp(*this);
	_node = _node->_prev;
	return tmp;
}

为什么前置++返回的是类对象引用，而后置++返回的是结点类型呢？？？

因为在前置++中，我们返回的是类本身，而后置++，我们返回的是一个局部的类对象，局部的类对象出了函数会自动销毁。

operator*

对该迭代器位置的数据进行解引用，类似与指针解引用。

T& operator*()//遍历及修改
{
	return _node->_data;//访问链表的data数据
}

operator!=

重载两个迭代器不相等，指针不相等则返回true，相等则返回false。

bool operator!=(const Self& lt)
{
	return _node != lt._node;//两个迭代器不相等即指针不相等
}

operator==

bool operator==(const Self& lt)
{
	return _node == lt._node;
}

注意：比较迭代器是否相等比较的是的地址。

4、迭代器与list进行关联

4.1、使用迭代器打印链表数据

void test_list1()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);

	list<int>::iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	cout << lt.size() << endl;
}

根据打印的测试函数我们可以知道，我们需要获取链表的第一个结点的迭代器（即第一个结点的地址），但是这个地址只有在list类中有，因此我们需要在list类中封装一个获取第一个结点的迭代器(begin)，获取end()也是同理。

begin()

第一个结点的迭代器，即头结点的下一个位置(_head->next)。

iterator begin() 
{
	return iterator(_head->_next);//调用迭代器类的构造函数
    //return _head->next;//单参数的隐式类型转换
}

end()

最后一个结点的下一个位置，即_head位置。

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

封装完迭代器之后我们就可以进行打印了。

list类代码：

template<class T>
class list
{
	typedef ListNode<T> Node;
public:
	typedef ListIterator<T> iterator;
	iterator begin() //打印链表时，只能访问数据，不能修改内容及指向的内容
	{
		return iterator(_head->_next);
	}
	iterator end()
	{
		return iterator(_head);
	}
private:
	Node* _head;//链表头指针
	size_t _size;//链表大小
};

测试结果：

4.2、其他相关函数

insert()

在pos位置之前插入val。

思路：

先获取当前结点的地址
然后通过前驱指针找到前面一个结点的地址
再创建一个新的结点
最后将前驱结点，新结点，当前结点构成链接关系

void insert(iterator pos, const T& val)//在pos位置前面插入val
{
	Node* cur = pos._node;//当前结点指针
	Node* prev = cur->_prev;

	Node* newnode = new Node(val);
	//prev newnode cur
	prev->_next = newnode;
	newnode->_prev = prev;
	newnode->_next = cur;
	cur->_prev = newnode;

	_size++;
}

erase()

删除pos位置的值，并返回删除前的下一个结点的地址。

思路：

先获取当前结点的地址
然后通过前驱指针找到前一个结点地址，通过后继指针找到后一个结点的地址
将prev 前驱指针与后继指针建立链接关系
释放当前结点
返回next结点

iterator erase(iterator pos)//删除pos位置值，迭代器失效问题
{
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* next = cur->_next;

	//prev next
	prev->_next = next;
	next->_prev = prev;

	delete cur;
	_size--;

	return iterator(next);//返回迭代器中结点指针
}

头插尾插头删尾删

复用insert()函数和erase()函数实现。

void push_back(const T& val)
{
	insert(end(), val);//end()之前插入
}
void push_front(const T& val)
{
    insert(begin(),val);//begin()之前插入
}
void pop_back()
{
	erase(--end());//删除end前面一个结点
}
void pop_front()
{
    erase(begin());//删除begin位置结点
}