C++从入门到起飞之——list模拟实现 全方位剖析！
秋风起，再归来～ 2024-09-09 16:35:01 阅读 73
🌈个人主页：秋风起，再归来~
🔥系列专栏：C++从入门到起飞
🔖克心守己，律己则安
目录
1、list的整体框架
2、list迭代器
>整体分析
>整体框架
>成员函数
>运算符->重载
>const迭代器
>迭代器类的一些问题的思考
3、成员函数
4、完结散花
1、list的整体框架
list就是我们所熟悉的数据结构链表，通过查看源码以及我们对链表的了解我们知道在类模版list中的成员变量一个是指向有效链表的哨兵卫头结点_head，另一个是记录有效元素个数的_size，而链表中的有效元素的存储地址空间不是连续的，所以并没有容量capacity的概念！
而我们又知道链表是由一个又一个的节点组成的，而我们要实现的是带头双向循环链表，所以每个节点里面都存储着数据val、前驱指针pre、后继指针next！
所以我们可以先大概写出list的整体框架！
<code>//链表的节点
template<class T>
struct list_node
{
list_node(const T& val = T())
:data(val)
,pre(nullptr)
,next(nullptr)
{}
T data;//数据
list_node<T>* pre;//前驱指针
list_node<T>* next;//后继指针
};
/双向循环带头链表
template<class T>
class list
{
public:
typedef list_node<T> node;//给节点取别名
//成员函数
//………………
private:
node* _head=nullptr;//带哨兵卫的头结点
size_t _size = 0;//记录节点个数
};
2、list迭代器
>整体分析
为了后续方便遍历容器打印结果检测我们程序的正确性，我们先来实现list的迭代器！
我们知道我们之前模拟的string和vector的迭代器都是原生的指针，那是因为他们底层结构的优越性允许他们这样实现。但是，list如果我们还是使用原生指针的话就完全做不到迭代器的效果，因为我们对节点指针*取到的是节点本身，而不是节点里面的数据，对节点++或--，因为链表不是连续的物理空间，所以我们并不能拿到前一个或后一个的迭代器反而让迭代器成了野指针！
那怎么办呢！我们可以对list的迭代器进行封装，而迭代器的底层原理还是使用节点的指针！只不过，我们要在迭代器里面对*、++、--、==、!= 等操作进行运算符重载！
>整体框架
那我们先实现迭代器的整体框架！
因为该迭代器只是给list使用，外面根本不知道，所以我们干脆用struct定义，将所有成员公开！
//链表的迭代器
template<class T>
struct list_iterator
{
typedef list_node<T> node;//给节点取别名
typedef list_iterator<T> self;//给自己取别名
node* it;//链表中的迭代器其实就是一个节点的指针
//只不过其访问和迭代操作要用一个类封装起来
list_iterator(node* node)
:it(node)
{}
//成员函数
//………………
};
>成员函数
//返回T&
T& operator*()
{
return it->data;
}
//（前置++）++it
self& operator++()
{
it = it->next;
return *this;
}
//（前置--）--it
self& operator--()
{
it = it->pre;
return *this;
}
//(后置++) it++
self operator++(int)
{
self tmp(*this);
it = it->next;
return tmp;//一定不能用引用接收，不然会有野指针！
}
//(后置--) it--
self operator--(int)
{
self tmp(*this);
it = it->pre;
return tmp;
}
//比较迭代器里面的it指针相不相等
bool operator==(const self& comp)
{
return it==comp.it;
}
bool operator!=(const self& comp)
{
return it!=comp.it;
}
>运算符->重载
如果节点中存储的是自定义类型Pos(坐标类）
struct Pos
{
int _row;
int _col;
Pos(int row, int col)
:_row(row)
, _col(col)
{}
};
如果我们想要方便访问坐标，那我们可以重载->操作符
T* operator->()
{
return &(it->data);
}
list<Pos> lt;
lt.push_back(Pos(1, 1));
lt.push_back(Pos(2, 2));
lt.push_back(Pos(3, 3));
lt.push_back(Pos(4, 4));
auto it = lt.begin();
while (it != lt.end())
{
cout << it->_col << " " << it->_row << endl;
++it;
}
上面的->实际上的完整调用是下面的模式
auto it = lt.begin();
while (it != lt.end())
{
cout << it.operator->()->_row << " " << it.operator->()->_col << endl;
++it;
}
it先调用重载的->，返回Pos类型的原生指针指针后再调用原始指针的->。而为了方便与可读性，编译器允许我们省略一个->调用！
>const迭代器
我们在上面只实现了一个普通的迭代器，如果我们要再实现一个const的常量迭代器，我们是不是就要再自己实现一个迭代器类呢？雀氏行的通！
//链表的迭代器
template<class T>
struct list_const_iterator
{
typedef list_node<T> node;//给节点取别名
typedef list_const_iterator<T> self;//给自己取别名
node* it;//链表中的迭代器其实就是一个节点的指针
//只不过其访问和迭代操作要用一个类封装起来
list_const_iterator(node* node)
:it(node)
{}
//成员函数
//………………
};
不过，在内部的成员函数实现中，只有一些函数的返回值是不同的，而函数体的是一样的！想这样俩个相似度高度集中的类，我们就可以使用类模版的方法将俩个类进行合并！
而我们具体的做法则是增加模版参数！
合并后的完整代码：
<code>//链表的迭代器
template<class T, class ref,class ptr>
struct list_iterator
{
typedef list_node<T> node;//给节点取别名
typedef list_iterator<T, ref, ptr> self;//给自己取别名
node* it;//链表中的迭代器其实就是一个节点的指针
//只不过其访问和迭代操作要用一个类封装起来
list_iterator(node* node)
:it(node)
{}
//返回T*
ptr operator->()
{
return &(it->data);
}
//返回T&
ref operator*()
{
return it->data;
}
//（前置++）++it
self& operator++()
{
it = it->next;
return *this;
}
/*self operator++()
{
it = it->next;
return it;
}*/
//（前置--）--it
self& operator--()
{
it = it->pre;
return *this;
}
/*self operator--()
{
it = it->pre;
return it;
}*/
//(后置++) it++
self operator++(int)
{
self tmp(*this);
it = it->next;
return tmp;//一定不能用引用接收，不然会有野指针！
}
//(后置--) it--
self operator--(int)
{
self tmp(*this);
it = it->pre;
return tmp;
}
//比较迭代器里面的it指针相不相等
bool operator==(const self& comp)
{
return it==comp.it;
}
bool operator!=(const self& comp)
{
return it!=comp.it;
}
};
>迭代器类的一些问题的思考
(1) 类中是否需要写析构函数？
这个迭代器类不要写析构函数，因为这里的节点不是迭代器的，是链表的，不用把它释放。我们使用begin，end返回节点给迭代器，是借助迭代器修改，访问数据，所以我们不需要释放。
(2) 类中是否需要写拷贝构造进行深拷贝和写赋值拷贝？
这里也不需要写拷贝构造进行深拷贝，因为这里要的就是浅拷贝。begin返回了第一个节点的迭代器给it，这里就是用默认生成的拷贝构造，浅拷贝给it，那这两个迭代器就指向同一个节点，所以这里用默认的拷贝构造和赋值拷贝就可以了。
3、成员函数
对于list的常见成员函数的实现我们已近轻车熟路了！这里就直接给源码了！
//链表的节点
template<class T>
struct list_node
{
list_node(const T& val = T())
:data(val)
,pre(nullptr)
,next(nullptr)
{}
T data;//数据
list_node<T>* pre;//前驱指针
list_node<T>* next;//后继指针
};
//链表的迭代器
template<class T, class ref,class ptr>
struct list_iterator
{
typedef list_node<T> node;//给节点取别名
typedef list_iterator<T, ref, ptr> self;//给自己取别名
node* it;//链表中的迭代器其实就是一个节点的指针
//只不过其访问和迭代操作要用一个类封装起来
list_iterator(node* node)
:it(node)
{}
//返回T*
ptr operator->()
{
return &(it->data);
}
//返回T&
ref operator*()
{
return it->data;
}
//（前置++）++it
self& operator++()
{
it = it->next;
return *this;
}
/*self operator++()
{
it = it->next;
return it;
}*/
//（前置--）--it
self& operator--()
{
it = it->pre;
return *this;
}
/*self operator--()
{
it = it->pre;
return it;
}*/
//(后置++) it++
self operator++(int)
{
self tmp(*this);
it = it->next;
return tmp;//一定不能用引用接收，不然会有野指针！
}
//(后置--) it--
self operator--(int)
{
self tmp(*this);
it = it->pre;
return tmp;
}
//比较迭代器里面的it指针相不相等
bool operator==(const self& comp)
{
return it==comp.it;
}
bool operator!=(const self& comp)
{
return it!=comp.it;
}
};
//双向循环带头链表
template<class T>
class list
{
public:
typedef list_node<T> node;//给节点取别名
typedef list_iterator<T, T&, T*> iterator;//普通迭代器
typedef list_iterator<T, const T&, const T*> const_iterator;//常量迭代器
//size
size_t size() const
{
return _size;
}
//begin
iterator begin()
{
return _head->next;
}
//end
iterator end()
{
return _head;
}
//cbegin
const_iterator begin() const
{
return _head->next;
}
//cend
const_iterator end() const
{
return _head;
}
//clear
void clear()
{
auto it = begin();
while (it!= end())
{
it=erase(it);
}
}
//swap
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
//empty
bool empty()
{
return _size == 0;
}
//空初始化
void emptyInit()
{
_head = new node;
_head->next = _head->pre = _head;
_size = 0;
}
//无参的默认构造
list()
{
emptyInit();
}
//拷贝构造
list(const list<T>& lt)
{
emptyInit();//先空参构造_head
for (auto& e : lt)
{
push_back(e);
}
/*auto it = lt.begin();
while (it != lt.end())
{
push_back(*it);
++it;
}*/
}
//赋值运算符重载
list<T>& operator=(list<T> tmp)
{
swap(tmp);
return *this;
}
//析构
~list()
{
clear();
delete _head;
_head = nullptr;
}
//insert
iterator insert(iterator pos, const T& val)
{
node* newNode = new node(val);
node* cur = pos.it;
node* pre = cur->pre;
newNode->next = cur;
newNode->pre = pre;
pre->next = newNode;
cur->pre = newNode;
_size++;
return newNode;
}
//push_front（头插）
void push_front(const T& val)
{
insert(begin(), val);
}
//push_back（尾插）
void push_back(const T& val)//传引用减少拷贝构造
{
/*node* newNode = new node(val);
node* tail = _head->pre;
tail->next = newNode;
newNode->next = _head;
newNode->pre = tail;
_head->pre = newNode;
++_size;*/
insert(end(), val);
}
//erase
iterator erase(iterator pos)
{
assert(pos != end());
node* next = pos.it->next;
node* pre = pos.it->pre;
pre->next = next;
next->pre = pre;
delete pos.it;
pos.it = nullptr;
_size--;
return next;
}
//pop_front(头删)
void pop_front()
{
erase(begin());
}
//pop_back(尾删)
void pop_back()
{
erase(--end());
}
private:
node* _head=nullptr;//带哨兵卫的头结点
size_t _size = 0;//记录节点个数
};
4、完结散花
好了，这期的分享到这里就结束了~
如果这篇博客对你有帮助的话，可以用你们的小手指点一个免费的赞并收藏起来哟~
如果期待博主下期内容的话，可以点点关注，避免找不到我了呢~
我们下期不见不散~~
声明
本文内容仅代表作者观点，或转载于其他网站，本站不以此文作为商业用途
如有涉及侵权，请联系本站进行删除
转载本站原创文章，请注明来源及作者。