【C++】—— list 模拟实现
9毫米的幻想 2024-09-20 10:05:02 阅读 69
【C++】—— list 模拟实现
1 list 基础结构2 默认构造3 迭代器3.1 整体框架3.2 成员函数3.3 begin() 与 end() 的实现3.4 operator-> 的实现3.5 const 迭代器3.5.1 const 迭代器为什么命名 const_iterator3.5.2 const 迭代器的实现3.5.3 合并两个迭代器
4 源码
1 list 基础结构
l
i
s
t
list
list 的底层就是我们之前学过的<code>双向链表,它由一个哨兵位头结点 _pHead
和记录链表长度的 _size
组成。
而链表中的每个节点都是由两个自身类型指针
和一个存储数据的变量组成
的。因此,我们不仅要定义链表的类,还要定义节点的类
下面是
l
i
s
t
list
list 的成员变量和整体框架
namespace my_list
{ -- -->
template<class T>
struct ListNode
{
ListNode* _prev;
ListNode* _next;
T _val;
//默认构造
ListNode(const T& val = T())
:_prev(nullptr)
,_next(nullptr)
,_val(val)
{ }
};
template<class T>
class list
{
typedef ListNode<T> Node;//给节点重命名
//成员函数···
private:
Node* _pHead;//哨兵位头结点指针
size_t _size;
}
}
因为我们要频繁访问节点,因此我们直接用
s
t
r
u
c
t
struct
struct 定义节点,其成员变量默认全公有
。
2 默认构造
我们先写一个简单的无参默认构造出来。
默认构造可以直接这样写吗?
list()
:_pHead(nullptr)
,_size(0)
{ }
不可以的,因为双向链表有个哨兵位
。即使链表中没有任何数据,头节点指针也是指向哨兵位,而不是空,所以我们应创建哨兵位,并将其初始化
而哨兵位的前驱指针 _
p
r
e
v
prev
prev 和后继指针 _
n
e
x
t
next
next,因为整个链表只有它自己,它的前一个和后一个节点都是自己,因此 _
p
r
e
v
prev
prev 和 _
n
e
x
t
next
next 都是指向哨兵位自己
list()
{
_pHead = new Node;
_pHead->_next = _pHead;
_pHead->_prev = _pHead;
_size = 0;
}
其是不仅仅是无参的构造,所有的构造函数第一步都是初始化哨兵位
,因此我们不妨单独写一个函数出来
list()
{
CreateHead();
}
void CreateHead()
{
_pHead = new Node;
_pHead->_next = _pHead;
_pHead->_prev = _pHead;
_size = 0;
}
这里有个问题就是CreateHead()
是非
c
o
n
s
t
const
const 成员函数,那定义
c
o
n
s
t
const
const 成员是否还能来调用呢?答案自然是可以的,因为
c
o
n
s
t
const
const 变量在定义的时候是不具有
c
o
n
s
t
const
const 属性的,定义完成之后才有。比如说:
//如果在定义之前就具有const属性,那么n就无法赋值
//const变量只有在定义时可以被赋值
const int n = 10;
const list<int> l1;
3 迭代器
要模拟实现
l
i
s
t
list
list ,迭代器的实现
是其中的重中之重。
前面我们模拟实现
s
t
r
i
n
g
string
string 和
v
e
c
t
o
r
vector
vector,他们的迭代器都是原生指针,他们的原生指针完美符合迭代器的所有要求。其本质是因为他们底层物理空间是连续的。
但
l
i
s
t
list
list 不像
s
t
r
i
n
g
string
string 和
v
e
c
t
o
r
vector
vector 那样天生丽质,它的底层结构是一个一个节点,并不连续,无法满足迭代器的要求(比如 ++,我们希望的是迭代器跳到下一个节点,如果使用原生指针,因为不是连续的物理空间,当前节点 ++ 大概率是个野指针)。
但没关系,
l
i
s
t
list
list 可以通过封装,通过运算符重载,来满足迭代器的要求。
3.1 整体框架
迭代器其本身就是模拟指针的行为
,既然节点的原生指针无法满足迭代器的要求,我们对节点指针进行封装,通过运算符重载让其满足迭代器的需求
template<class T>
struct ListIterator
{
typedef ListIterator<T> Self;//给自身类(迭代器)重命名,短一点方便
typedef ListNode<T> Node;//节点重命名
//成员变量:节点的指针
Node* pNode;
//成员函数
//···
};
因为待会链表中要大量访问成员变量,我们直接用默认全公有的
s
t
r
u
c
t
struct
struct
到现在,我们一共实现了三个类,为什么要实现三个类呢?我们先把每个类的作用过一遍:
class list
:链表这个类是链表的基本结构,指向哨兵位的头结点
,管理这整个链表struct ListNode
:节点这个类是因为链表中每个节点都是自定义类型,每个数据都是存在一个独立的结构体里面struct ListIterator
:迭代器这个类,遍历整个链表本来是用节点的指针,但是节点的指针是不符合我们的预期,我们希望有一个迭代器统一的方式进行遍历,因此我们用一个结构去封装节点的指针,封装以后通过重载运算符使节点的指针能达到迭代器那样的行为
3.2 成员函数
有了迭代器这个类,我们就可以运用运算符重载满足迭代器的行为啦
template<class T>
struct ListIterator
{
typedef ListIterator<T> Self;
typedef ListNode<T> Node;
//成员变量
Node* pNode;
//解引用
T& operator*()
{
return pNode->_val;
}
//前置++
Self& operator++()
{
pNode = pNode->_next;
return *this;
}
//后置++
Self& operator++(int)
{
Self tmp = *this;
pNode = pNode->_next;
return tmp;
}
//前置--
Self& operator--()
{
pNode = pNode->_prev;
return *this;
}
//后置--
Self& operator--(int)
{
Self tmp = *this;
pNode = pNode->_prev;
return tmp;
}
//不等于
bool operator!=(const Self& x)
{
return pNode != x.pNode;
}
//等于
bool operator==(const Self& x)
{
return pNode == x.pNode;
}
}
3.3 begin() 与 end() 的实现
迭代器的基本行为实现了,我们也可以在list类
中实现begin()
、end()
等函数了
begin()
函数是返回第一个迭代器,我们要构造第一个位置的迭代器,那怎么构造呢?我们用第一个节点的指针,即_pHead->_next
,就能构造第一个迭代器,但现在ListIterator类
中还缺少一个构造函数:
//默认构造
ListIterator(Node* p = nullptr)
:pNode(p)
{ }
//拷贝构造
ListIterator(const ListIterator& x)
{
pNode = x.pNode;
}
其实上述拷贝构造可以不用实现,编译器会自己生成一个拷贝构造,完成浅拷贝,指向链表的节点。
这里不要认为有指针指向资源就要自己实现深拷贝,而是看指针所指向的资源是不是属于自己的。像
s
t
r
i
n
g
string
string、
v
e
c
t
o
r
vector
vector 那些就需要自己实现深拷贝,但迭代器指向的是链表的资源,并不是迭代器自己的,并且迭代器本身的目标就是指向链表的节点,以此来访问遍历链表,因此浅拷贝
即可。
所以赋值重载和析构与不需要写
现在,万事具备只欠东风,我们还要在list类
中将ListIterator类
t
y
p
e
d
e
f
typedef
typedef 成
i
t
e
r
a
t
o
r
iterator
iterator
template<class T>
class list
{
typedef ListNode<T> Node;
typedef ListIterator<T> iterator;//重命名为iterator
//成员函数···
private:
Node* _pHead;
size_t _size;
}
下面是begin()
的实现
iterator begin()
{
iterator it(_pHead->_next);
return it;
}
上述是有名对象的写法,我们可以用匿名对象的写法
iterator begin()
{
return iterator(_pHead->_next);
}
甚至我们可以用隐式类型转换
,直接传指针就好啦
迭代器本身就是节点的指针,指针节点指针本身不满足迭代器的那些需求,所以我们才用一个类把他封装一层,用重载运算符使其达到迭代器的要求。
iterator begin()
{
return _pHead->_next;
}
end()
是最后一个数据的下一个位置,就是哨兵位的头结点
iterator end()
{
return _pHead;
}
3.4 operator-> 的实现
既然迭代器模拟的是指针的行为,那它还要实现 operator->
什么情况下用到 ->
运算符呢?
现在我们定义一个类型 AA,链表中存储的数据是 AA 类型,我们想依次遍历链表,打印每个节点 AA 中的两个成员变量
struct AA
{
int _a1 = 1;
int _a2 = 2;
}
void test1()
{
list<AA> lta;
lta.push_back(AA());
lta.push_back(AA());
lta.push_back(AA());
list<AA>::iterator it = lta.begin();
while (it != lta.end())
{
cout << (*it)._a1 << " " << (*it)._a2 << endl;
cout << it->_a1 << " " << it->_a2 << endl;
}
}
上述(*it)._a1
与it->_a1
的写法是等价的,但现在还没重载->
运算符
下面是operator->
的实现方式
T* operator->()
{
return &(pNode->_val);
}
operator->
的实现方式非常奇怪,返回的是T*
其实这里省略了一个 ->,因为太难看了,为了可读性省略了一个 ->
cout << it->_a1 << " " << it->_a2 << endl;
//本质是这样的
cout << it->->_a1 << " " << it->->_a2 << endl;
第一个->是运算符重载出来的,第二个则是普通的->
本质是这样的:
cout << it.operator->()->_a1 << " " << it.operator->()->_a2 << endl;
cout << &(pNode->_val)->_a1 << " " << &(pNode->_val)->_a2 << endl;
3.5 const 迭代器
3.5.1 const 迭代器为什么命名 const_iterator
首先问大家一个问题:
c
o
n
s
t
const
const 迭代器为什么是const_iterator
,而不是const iterator
呢
c
o
n
s
t
const
const 迭代器是自身不能修改
还是指向的内容不能修改
呢?
就和指针一样,指针的
c
o
n
s
t
const
const 有两个,一个在 * 之前,一个在 * 之后
T* const ptr1//指针本身不能修改
const T* ptr2//指向的内容不能修改
如果是 const iterator
,const 直接修饰一个变量,就是这个变量本身不能修改,即迭代器本身不能修改,而我们
c
o
n
s
t
const
const 迭代器是要指向的内容不能修改,所以const_iterator
更合适
3.5.2 const 迭代器的实现
那我们如何让迭代器指向的内容不能修改呢?
迭代器修改我们指向的内容是怎么修改的?通过operator*
和operator->
,那我们在其返回值上加上
c
o
n
s
t
const
const 就不能修改了
const T& operator*()
{
return pNode->_val;
}
const T* operator->()
{
return &(pNode->_val);
}
那我们就再自己实现一个
c
o
n
s
t
const
const 迭代器的封装吧
template<class T>
struct const_ListIterator
{
typedef const_ListIterator<T> Self;
typedef ListNode<T> Node;
Node* pNode;
const_ListIterator(Node* p = nullptr)
:pNode(p)
{ }
const T& operator*()
{
return pNode->_val;
}
const T* operator->()
{
return &(pNode->_val);
}
Self& operator++()
{
pNode = pNode->_next;
return *this;
}
Self& operator++(int)
{
Self tmp = *this;
pNode = pNode->_next;
return tmp;
}
Self& operator--()
{
pNode = pNode->_prev;
return *this;
}
Self& operator--(int)
{
Self tmp = *this;
pNode = pNode->_prev;
return tmp;
}
bool operator!=(const Self& x)
{
return pNode != x.pNode;
}
bool operator==(const Self& x)
{
return pNode == x.pNode;
}
};
3.5.3 合并两个迭代器
上面我们再重新封装了一个const_iterator
,基本满足了需求,但是代码太冗余了,除了operator*
和operator->
的返回值类型不一样,其他代码全是一样的,有什么办法将他们合二为一呢?
我们来看一下库中是怎么实现的
库中的<code>__list_iterator类,用了三个模板参数,新增了 Ref
与 Ptr
两个参数。
在
l
i
s
t
list
list 类中,将__list_iterator<T, T&, T*>
t
y
p
e
d
e
f
typedef
typedef 成
i
t
e
r
a
t
o
r
iterator
iterator,将__list_iterator<T, const T&, const T*>
t
y
p
e
d
e
f
typedef
typedef 成
c
o
n
s
t
const
const_
i
t
e
r
a
t
o
r
iterator
iterator。
也就是说
i
t
e
r
a
t
o
r
iterator
iterator 的
R
e
f
Ref
Ref 参数即 T&,
P
t
r
Ptr
Ptr 即参数 T*,
c
o
n
s
t
const
const_
i
t
e
r
a
t
o
r
iterator
iterator 的
R
e
f
Ref
Ref参数即
c
o
n
s
t
const
const T&,
P
t
r
Ptr
Ptr 参数即
c
o
n
s
t
const
const T*
以operator*
举例:
T& 传给Ref,Ref 即reference,operator*
的返回值是reference,替换过来operator*
的返回值就是 T&
对
c
o
n
s
t
const
const_
i
t
e
r
a
t
o
r
iterator
iterator
c
o
n
s
t
const
const T& 传给
R
e
f
Ref
Ref,替换过来operator*
的返回值就是
c
o
n
s
t
const
const T&
其实,这种写法与上面我们自己实现两个类模板并没有本质区别,他们实例化出来都是两个不同的类。不同的是第一种写法是我们自己写了两个不同的类,而第二种是我们通过控制模板参数让编译器实例化出两个不同的类,把我们干的活交给了编译器
代码如下:
template<class T, class Ref, class Ptr>
struct ListIterator
{ -- -->
typedef ListIterator<T, Ref, Ptr> Self;
typedef ListNode<T> Node;
Node* pNode;
ListIterator(Node* p = nullptr)
:pNode(p)
{ }
Ref operator*()
{
return pNode->_val;
}
Ptr operator->()
{
return &(pNode->_val);
}
Self& operator++()
{
pNode = pNode->_next;
return *this;
}
Self& operator++(int)
{
Self tmp = *this;
pNode = pNode->_next;
return tmp;
}
Self& operator--()
{
pNode = pNode->_prev;
return *this;
}
Self& operator--(int)
{
Self tmp = *this;
pNode = pNode->_prev;
return tmp;
}
bool operator!=(const Self& x)
{
return pNode != x.pNode;
}
bool operator==(const Self& x)
{
return pNode == x.pNode;
}
};
4 源码
对于
l
i
s
t
list
list 的其他成员函数,与前面的
s
t
r
i
n
g
string
string、
v
e
c
t
o
r
vector
vector 实现起来都大同小异,这里就不再赘述了,我们直接看源码
#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
namespace my_list
{
template<class T>
struct ListNode
{
ListNode* _prev;
ListNode* _next;
T _val;
ListNode(const T& val = T())
:_prev(nullptr)
,_next(nullptr)
,_val(val)
{ }
};
template<class T, class Ref, class Ptr>
struct ListIterator
{
typedef ListIterator<T, Ref, Ptr> Self;
typedef ListNode<T> Node;
Node* pNode;
ListIterator(Node* p = nullptr)
:pNode(p)
{ }
Ref operator*()
{
return pNode->_val;
}
Ptr operator->()
{
return &(pNode->_val);
}
Self& operator++()
{
pNode = pNode->_next;
return *this;
}
Self& operator++(int)
{
Self tmp = *this;
pNode = pNode->_next;
return tmp;
}
Self& operator--()
{
pNode = pNode->_prev;
return *this;
}
Self& operator--(int)
{
Self tmp = *this;
pNode = pNode->_prev;
return tmp;
}
bool operator!=(const Self& x)
{
return pNode != x.pNode;
}
bool operator==(const Self& x)
{
return pNode == x.pNode;
}
};
template<class T>
class list
{
typedef ListNode<T> Node;
public:
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;
list()
:_pHead(nullptr)
, _size(0)
{
CreateHead();
}
list(int n, const T& value = T())
{
CreateHead();
while (n--)
{
push_back(value);
}
}
template <class Iterator>
list(Iterator first, Iterator last)
{
CreateHead();
Iterator it = first;
while (it != last)
{
push_back(*it);
++it;
}
}
list(const list<T>& l)
{
CreateHead();
const_iterator it = l.begin();
while (it != l.end())
{
push_back(*it);
++it;
}
}
list<T>& operator=(list<T> l)
{
swap(l);
return *this;
}
~list()
{
clear();
delete _pHead;
_pHead = nullptr;
}
iterator begin()
{
return _pHead->_next;
}
iterator end()
{
return _pHead;
}
const_iterator begin() const
{
return _pHead->_next;
}
const_iterator end() const
{
return _pHead;
}
size_t size()const
{
return _size;
}
bool empty()const
{
return _size == 0;
}
T& front()
{
return _pHead->_next->_val;
}
T& back()
{
return _pHead->_prev->_val;
}
const T& front() const
{
return _pHead->_next->_val;
}
const T& back() const
{
return _pHead->_prev->_val;
}
void push_back(const T& val)
{
Node* p = new Node(val);
p->_next = _pHead;
_pHead->_prev->_next = p;
p->_prev = _pHead->_prev;
_pHead->_prev = p;
++_size;
}
void pop_back()
{
Node* p = _pHead->_prev;
p->_prev->_next = _pHead;
_pHead->_prev = p->_prev;
delete p;
--_size;
}
void push_front(const T& val)
{
Node* p = new Node(val);
p->_next = _pHead->_next;
p->_prev = _pHead;
_pHead->_next = p;
p->_next->_prev = p;
++_size;
}
void pop_front()
{
Node* p = _pHead->_next;
_pHead->_next = p->_next;
p->_next->_prev = _pHead;
delete p;
--_size;
}
iterator insert(iterator pos, const T& val)
{
Node* p = new Node(val);
p->_next = pos.pNode;
p->_prev = pos.pNode->_prev;
pos.pNode->_prev->_next = p;
pos.pNode->_prev = p;
++_size;
return pos;
}
iterator erase(iterator pos)
{
assert(pos != end());
iterator ret = pos.pNode->_next;
pos.pNode->_prev->_next = pos.pNode->_next;
pos.pNode->_next->_prev = pos.pNode->_prev;
delete pos.pNode;
--_size;
return ret;
}
void clear()
{
iterator it = begin();
while (it != end())
{
iterator cur = it++;
delete cur.pNode;
}
_pHead->_next = _pHead;
_pHead->_prev = _pHead;
_size = 0;
}
void swap(list<T>& l)
{
std::swap(_pHead, l._pHead);
std::swap(_size, l._size);
}
private:
Node* _pHead;
size_t _size;
void CreateHead()
{
_pHead = new Node;
_pHead->_next = _pHead;
_pHead->_prev = _pHead;
_size = 0;
}
};
}
template<class Container>
void print_container(const Container& v)
{
auto it = v.begin();
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
好啦,本期关于
l
i
s
t
list
list 的知识就介绍到这里啦,希望本期博客能对你有所帮助。同时,如果有错误的地方请多多指正,让我们在 C++ 的学习路上一起进步!
声明
本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。