C++ STL list容器模拟实现
I.引入
STL中的list是带头双向循环链表，毋庸置疑是链表的最终形态，想要模拟实现小白版的list首先我们需要知道我们需要什么，首先是 链表结点结构，链表结构，以及迭代器来访问链表
- 存储元素需要结点--->结点类
- 使用迭代器访问结点--->迭代器类
- 总体--->list类
list容器模拟实现
结点类
作用：存储 list容器 的元素，因为list里面要存储各种类型的元素，所以结点类需要定义成模版。结点类中的成员变量则是有三个，分别是：指向前一个结点的_prev指针，指向后一个结点的_next指针，存储结点元素的_data变量。
#include<iostream>
using namespace std;
namespace zzz
{
class _list_node
{
template<class T>
T _data;
_list_node<T>* _prev;
_list_node<T>* _next;
_list_node(const T& x = T())
:_prev(nullptr)
,_next(nullptr)
,_data(x)
{}
};
}
❓ 思考：为什么这里 ListNode 要加 <T> ？
💡 解读：因为类模板不支持自动推类型。 结构体模板或类模板在定义时可以不加 <T>，但 使用时必须加 <T>。
list类
namespace zzz
{
template<class T>
typedef _list_node<T> Node
class list
{
private:
Node* _head;
public:
list()
{
_head = nullptr;
_head->_prev = _head;
_head->_next = _head;
}
};
}
迭代器类
list的重点是迭代器，因为这里迭代器的实现与前面STL容器的实现方法大相径庭，我们之前的string和vector使用的是原生指针来实现，但是list是个链表，在空间上是不连续的，所以原生指针的实现就被否定了。
所以我们只能自己来实现迭代器类，并且重载运算符*和++
而迭代器的意义就是，让使用者可以不必关心容器的底层实现，可以用简单统一的方式对容器内的数据进行访问。
既然 list 的结点指针的行为不满足迭代器定义，那么我们可以对这个结点指针进行封装，对结点指针的各种运算符操作进行重载，使得我们可以用和string和vector当中的迭代器一样的方式使用list当中的迭代器。
总结：list迭代器类，实际上就是对结点指针进行了封装，对其各种运算符进行了重载，使得结点指针的各种行为看起来和普通指针一样。（例如，对结点指针自增就能指向下一个结点）
0x01迭代器的构造
template<class T,class Ref,class Ptr>
struct __list_iterator{
typedef _list_node<T> Node;
Node* _node;
__list_iterator(Node* node)
：_node(node)
{}
};
在这里我们设置了三个模板参数
template<class T, class Ref, class Ptr>
在 list 的模拟实现当中，我们 typedef 了两个迭代器类型，普通迭代器 和 const迭代器
typedef __list_iterator<T,&T,T*> iterator;
typedef __list_iterator<T,const& T,const T*> const_iterator;
这里我们就可以看出，迭代器类 的模板参数列表当中的 Ref 和 Ptr 分别代表的是 引用类型（T&） 和 指针类型（T *）。
当我们使用 普通迭代器 时，编译器就会实例化出一个 普通迭代器 对象；当我们使用 const迭代器时，编译器就会实例化出一个 const迭代器对象。
若该迭代器类不设计三个模板参数，那么就不能很好的区分-- 普通迭代器 和-- const迭代器。
- 迭代器类 中的成员变量只有一个，那就是 结点类类型的指针 _node，因为 迭代器的本质就是指针。
0x02++运算符重载
加加分为前置和后置，我们这里先实现以下前置++
//重载前置++
//返回迭代器对象自身的引用
//因为对象自身并不是该函数中的局部对象
self& operator++()
{
_node = _node->_next;
return *this;
}
重载前置++ 和 后置++ 时的返回值有所不同，前置++返回值类型是--------迭代器类型的引用，而后置++返回值类型是------ 迭代器类型。
前置++中，返回的是对 this 的解引用，this并不是局部变量，函数结束后依然存在，所以可以返回它的引用，减少值拷贝次数。
后置++中，返回的 temp 是函数中创建的局部对象，在函数结束后会被销毁，所以返回值类型不可以是引用。这里就必须通过值拷贝来返回值。
//重载后置++
//此时需要返回temp对象，而不是引用
//因为temp对象是局部的对象
//函数结束后就被释放
self operator++(int a)
{
self temp(*this);
_node = _node->_next;
return temp;
}
0x03 operator*
解引用就是取结点 _node 里的数据，
并且 operator* 和指针一样，不仅仅能读数据，还能写数据。
为了使 operator* 能支持修改的操作，我们这里用引用返回 &
/* 解引用 */
T& operator*() {
return _node->_data; // 返回结点的数据
}
0x04 operator！=
这里只需要比较_node是否相同即可，因为_node本身就是指向结点的指针，保存着结点的地址，只要地址相同，那自然就是同一个结点了
//重载!=
bool operator!=(const self& s)const
{
return _node != s._node;
}
//重载==
bool operator==(const self& s)const
{
return _node == s._node;
}
0x05 operator->重载
有时候，实例化的模板参数是自定义类型，我们想要像 指针 一样访问访问自定义类型力的成员变量，这样显得更通俗易懂，所以就要重载 -> 运算符，它的返回值是 T*
迭代器是像指针一样的，所以要重载两个解引用。
为什么？指针如果指向的类型是原生的普通类型，要取对象是可以用解引用，
但是如果指向而是一个结构，并且我们又要取它的每一个成员变量，就像这样
比如是一个日期类，假设我们没有实现其流插入，我们自己访问
struct Date {
int _year;
int _month;
int _day;
Date(int year = 1, int month = 1, int day = 1)
: _year(year)
, _month(month)
, _day(day)
{}
};
void test_list3() {
list<Date> L;
L.push_back(Date(2022, 5, 1));
L.push_back(Date(2022, 5, 2));
L.push_back(Date(2022, 5, 3));
list<Date>::iterator it = L.begin();
while (it != L.end()) {
// cout << *it << " "; 假设我们没有实现流插入，我们自己访问
cout << (*it)._year << "/" << (*it)._month << "/" << (*it)._day << endl;
it++;
}
cout << endl;
}
虽然可以访问，但是不是主流访问方法啊，所以我们这里需要重载一下箭头访问符号
/* 解引用 */
Ref operator*() {
return _node->_data; // 返回结点的数据
}
T* operator->() {
return &_node->_data;
}
0x06 list实现
/* 定义迭代器 */
template<class T, class Ref, class Ptr>
struct __list_iterator {
typedef ListNode<T> Node;
typedef __list_iterator<T, Ref, Ptr> self; // 为了方便我们重命名为self
Node* _node;
__list_iterator(Node* x)
: _node(x)
{}
/* 解引用 */
Ref operator*() {
return _node->_data; // 返回结点的数据
}
Ptr operator->() {
return &_node->_data;
}
...
};
/* 定义链表 */
template<class T>
class list {
typedef ListNode<T> Node; // 重命名为Node
public:
/* 迭代器 */
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
...
}
默认成员函数
构造函数
list 的成员变量是 一个节点类，在构造头节点时，需要将这单个头节点构造成一个双向循环链表；
//拷贝构造 --- 现代写法 lt2(lt1)
list(const list<T>& lt)
{
_head = new Node;
_head->_prev = _head;
_head->_next = _head;
list<T> tmp(lt.begin(), lt.end());
std::swap(_head, tmp._head);
}
迭代器区间构造
由于list可以存储各种类型的元素，所以区间构造时自然也会用到各种类型的迭代器，因此区间构造也应该定义为模版，需要给出模版参数列表。具体实现和上一个函数是差不多的。
//迭代器区间构造
template<class iterator>
list(iterator first, iterator last)
{
_head = new Node;
_head->_prev = _head;
_head->_next = _head;
while (first != last)
{
push_back(*first);//尾插数据，会根据不同类型的迭代器进行调用
++first;
}
}
赋值重载
将赋值运算符重载的参数定义为 list 类型的对象而不是对象的引用，传参时会发生值拷贝。
因此我们可以把 list对象 的 this指针 和 拷贝出来的参数 L 指向头结点的指针交换，这样 this指针 就直接指向了拷贝出来的L的头结点。L则指向了list对象的头结点，在函数结束后，作为局部对象的L将被销毁，它指向的空间也会被释放。
list<T>& operator=(list<T> L)
{
swap(_head,L._head);
return *this;
}
析构函数
//析构函数
~list()
{
clear(); //清理容器
delete _head; //释放头结点
_head = nullptr; //头指针置空
}
迭代器相关函数
begin and end
iterator begin()
{
//返回使用头结点后一个结点的地址构造出来的普通迭代器
return iterator(_head->_next);
}
iterator end()
{
//返回使用头结点的地址构造出来的普通迭代器
return iterator(_head);
}
再重载一个用于const对象的begin end
const_iterator begin() const
{
//返回使用头结点后一个结点的地址构造出来的const迭代器
return const_iterator(_head->_next);
}
const_iterator end() const
{
//返回使用头结点的地址构造出来的普通const迭代器
return const_iterator(_head);
}
访问容器相关函数
front和back
front 和 back 函数分别用于获取第一个有效数据和最后一个有效数据，因此，实现front和back函数时，直接返回第一个有效数据和最后一个有效数据的引用即可。
T& front()
{
return *begin(); //返回第一个有效数据的引用
}
T& back()
{
return *(--end()); //返回最后一个有效数据的引用
}
当然，这也需要重载一对用于const对象 的front函数 和 back函数，因为 const对象 调用front和back函数后所得到的数据不能被修改
const T& front() const
{
return *begin(); //返回第一个有效数据的const引用
}
const T& back() const
{
return *(--end()); //返回最后一个有效数据的const引用
}
增删查改
引入case：我们只做insert和erase的展示
Insert
先根据所给迭代器得到该位置处的结点指针cur，然后通过cur指针找到前一个位置的结点指针prev，接着根据所给数据x构造一个待插入结点，之后再建立新结点与cur之间的双向关系，最后建立新结点与prev之间的双向关系即可
void insert(iterator pos,const T& x)
{
assert(pos._node); //检查插入位置是否合法
Node* cur = pos._node;//迭代器pos处的结点指针
Node* prev = cur->_prev;//迭代器pos前一个位置的结点指针
Node* newnode = new Node(x);/根据所给数据x构造一个待插入结点
// 穿针引线
newnode->_new = cur;
cur->_prev = newnode;
newnode->_prev = prev;
prev->_next = newnode;
}
erase
先根据所给迭代器得到该位置处的结点指针cur，然后通过cur指针找到前一个位置的结点指针prev，以及后一个位置的结点指针next，紧接着释放cur结点，最后建立prev和next之间的双向关系即可。
iterator erase(iterator pos)
{
assert(pos._node);//检查删除位置合法性
assert(pos!=end()); //删除位置不能是哨兵位
Node* cur = pos._node;//迭代器pos处的结点指针
Node* prev = cur->_prev;//迭代器pos前一个位置的结点指针
Node* next = cur->_next;//迭代器pos后一个位置的结点指针
delete cur; //释放cur结点
prev->_next = next;
newx->_prev = prev;
return iterator(next);//返回所给迭代器pos的下一个迭代器
更多推荐
16
0- 0
已为社区贡献3条内容
所有评论(0)