![cover](https://img-blog.csdnimg.cn/direct/26329bc9f2e64d72ba613d6143f4dca4.gif)
C++第二十四弹---从零开始模拟STL中的list(上)
list基本结构,默认构造函数,尾插函数,普通迭代器类的封装,迭代器与list进行关联,链表的增删函数~~~
✨个人主页: 熬夜学编程的小林
💗系列专栏: 【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位置结点
}
总结
本篇博客就结束啦,谢谢大家的观看,如果公主少年们有好的建议可以留言喔,谢谢大家啦!
更多推荐
所有评论(0)