网站数据报表,揭阳专业网站建设,网页设计大赛新闻稿,WordPress主题 SlhaoSTL容器-- list的模拟实现#xff08;附源码#xff09; List的实现主要考察我们对list这一容器的理解#xff0c;和代码的编写能力#xff0c;通过上节对list容器的使用#xff0c;我们对list容器已经有了一些基本的了解#xff0c;接下来就让我们来实现一些list容器常见…STL容器-- list的模拟实现附源码 List的实现主要考察我们对list这一容器的理解和代码的编写能力通过上节对list容器的使用我们对list容器已经有了一些基本的了解·接下来就让我们来实现一些list容器常见的功能函数来加深我们对c工程的理解 一、基本框架的搭建
首先我们需要将基本的框架搭建好 从之前我们学数据结构时对list的一些认识并结合c stl标准可以得出
定义节点的构造明确指针的指向list的封装 根据c中的标准我们可以得知list时一个双向迭代器 所以对应的 我们需要定义的双向循环链表
1.1节点的构造
template class T
struct ListNode
{T _data;ListNodeT* _next;ListNodeT* _prev;// 节点的构造函数ListNode(const T val):_data(val),_next(nullptr),_prev(nullptr){}
};在定义一个节点的时候我们先让这个节点的_next and _prev指针为空
1.2 list的封装 template class T
struct ListNode
{T _data;ListNodeT* _next;ListNodeT* _prev;// 节点的构造函数ListNode(const T val T()):_data(val),_next(nullptr),_prev(nullptr){}
};templateclass T
class list
{
public:typedef ListNodeT node;void empty_init(){// zdl :: 在初始化一个空链表时 先定义一个哨兵位_head new node();_head-_next _head;_head-_prev _head;}list(){empty_init();}// functon define:}private:node* _head;
};同时为了防止访问冲突我们可以将我们自己实现的类放在我们自己定义的命名域中
namespace zdl
{template class Tstruct ListNode{T _data;ListNodeT* _next;ListNodeT* _prev;// 节点的构造函数ListNode(const T val):_data(val),_next(nullptr),_prev(nullptr){}};template class Tstruct ListNode{T _data;ListNodeT* _next;ListNodeT* _prev;// 节点的构造函数ListNode(const T val T()):_data(val),_next(nullptr),_prev(nullptr){}};templateclass Tclass list{public:typedef ListNodeT node;void empty_init(){// zdl :: 在初始化一个空链表时 先定义一个哨兵位_head new node();_head-_next _head;_head-_prev _head;}list(){empty_init();}// functon define:}private:node* _head;};
}这样list的基本框架就搭建好了
二、节点的尾插和头插
2.1 节点的头插 (push_back) 通过前面数据结构的学习。我们已经清楚了链表的结构在进行数据尾插时, 就只是在改变指针的指向罢了
void push_back(const T val){node* creat new node(val);node* tail _head-_prev;tail-_next creat;creat-_prev tail;creat-_next _head;_head-_prev creat; }2.2 节点的头插(push_front)
节点的头插和尾插十分的相似 这里我们就直接展示一下代码
void push_front(const T val){node* fnode new node(val);fnode-_next _head-_next;fnode-_prev _head;_head-_next-_prev fnode;_head-_next fnode;}2.3 数据插入验证
为了方便起见 我这里再再这个类里面定义一个打印链表的函数 void Print_list(){node* cur _head-_next;while (cur ! _head){cout cur-_data ;cur cur-_next;}cout endl;}完成了list容器的头插和尾插操作接下来我们可以来验证一下我们的函数实现是否有问题
#includelist.hint main()
{zdl::listint l1;l1.push_back(1);l1.push_back(2);l1.push_front(3);l1.Print_list();return 0;
}通过运行可知 这里的函数没有问题 三、list迭代器的实现
list迭代器的功能和vetor的功能有很多相似的地方但是二者在底层实现时使用的不同的方法 基于list迭代器的特殊性质我们会采用类封装的方式来满足list_iterator的特殊性质
3.1迭代器基本功能的实现和封装处理
templateclass Tstruct list_iterator{typedef ListNodeT node;typedef list_iteratorT self;node* _nd;list_iterator(node* nd):_nd(nd){}// zdl:: 实现迭代器的基本功能// 解引用数值T operator*(){return _nd-_data;}// zdl:: 前置 / --self operator(){_nd _nd-_next;return *this;}self operator--(){_nd _nd-_prev;return *this;}// zdl:: 后置 / --self operator(int){self tmp _nd;_nd _nd-_next;return tmp;}self operator--(int){self tmp _nd;_nd _nd-_prev;return tmp;}// zdl:: ! 运算bool operator!(const self s){return _nd ! s._nd;}};实现了list_iterator的功能后我们就只需要将他封装道list类中就可以正常使用了 基本的逻辑都是十分的简单的接下来我们来简单的验证一代码是否可行
3.2 对结构体(类的解引用 对 -运算符的重载 大家现在可以想象一下这样的场景假设我现在在llist中存储的不是基础类型的元素而是类等较为复杂的对象时,我们应当怎么正常的使用这个类对象的成员呢 这时我们就可以考虑对-运算符重载 通过返回对象的地址来访问成员变量和成员函数等 下面我们就来举个例子 假设我现在我要在list中存储pos类
struct pos
{int row;int col;//构造函数pos(const int x 0, const int y 0):row(x),col(y){}//成员函数void pos_show(){printf((%d, %d) ,row, col);}
};我们就只需要重载-运算符
T* operator-()
{return _nd-_data;
}运行后可以得到 但是大家可能会觉得很奇怪通过-重载返回的只是_data的地址为什么能直接访问到元素呢不应该使用it--解引用两次才行啊 这个其实就只是c便准下为我们提供的特殊语法 通过这样的规定使我们能够直接访问到元素 当然c也是支持这样的写法的 但是不支持这样的写法
3.3const迭代器的实现与模板参数的巧用
前面我们已经实现了可读可写的迭代器现在我们就来实现一下只读迭代器: const iterator, 其实从功能上看这个迭代器与原来的迭代器十分的相似只是不能对指向对象的值进行修改因此我们就只需要对* 和 -运算符重载的时候稍加修改就可以得到我们想要的结果即再创建一个类 其他的共同功能粗需要改动只需要改动下面两个重载函数 const T operator*()
{return _nd-_data;
}
const T* operator-()
{return _nd-_data;
}紧接着我们还需要在llist类中实现const对象专用的begin()、end()
接下来我们来验证一下效果 现在consr iterator也实现好了但是这里依然还存在问题这样我们将相当于为迭代器实现了两个类这两个类的攻击能还高度重合这并没有体现出模板函数的简洁性因此我们还可以通过其他的方式来优化我们现在的代码。 通过对源码的分析参照我们或许可以从中得到一些启发 从源码中可知我们可以得知通过对模板参数的巧用就可以的实现代码的简化 接下来我们就只需要将代码稍加改动就可以实现我们的目的 接下来我们再次运行看看是否可以达到简化代码的效果 可以发现现在的代码依然有效代码简化成功
四、丰富构造函数、list增删查改的实现
现在我们已经完成了list的简单构造函数现在我们就可以参照 c library完成其他的构造函数
4.1 list(size_t n, const T x T())
我们要实现的这个函数和标准库中的一样并且直接复用我峨嵋你已经实现的函数就好了
list(size_t n, const T x T())
{for (int i 0; i n; i){push_back(x);}
}直接来演示一下的效果
4.2 拷贝构造
我们就只需要将被拷贝链表的元素一个一个的拷贝进链表就行了
list(const listT l1)
{empty_init();for (auto e : l1) push_back(e);
}我们来测试一下效果
4.3 插入函数的实现insert)
想要在这个双向链表中插入节点我们就需要 待插入的值 待插入位置
所以insert函数定义为 void insert(iterator pos, const T val T())
iterator insert(iterator pos, const T val T())
{node* cur pos._nd;node* prev pos._nd-_prev;node* insrt new node(val);prev-_next insrt;insrt-_prev prev;insrt-_next cur;cur-_prev insrt;return iterator(cur-_prev);}这个函数也十分的简单如果有的uu还没有接触过链表或者是已经忘了链表的增删查改可以移步去看看我之前的博客链表的介绍
4.4链表的删除(earse)
关于erase和函数的定义我们就只需要拿到需要删除的位置就可以了 所以定义为void erase(iterator pos)
iterator erase(iterator pos)
{assert(pos ! end()); //! 注意不能够将哨兵位删除node* cur pos._nd;node* prev cur-_prev;prev-_next cur-_next;cur-_next-_prev prev;delete cur;return iterator(prev-_next);}现在我们就直接来测试一下这个函数是否可以满足我们的要求 由此可知我们实现的都没有问题。
4.5链表元素的查找(find)
定义find函数时我们就只需要给函数一个特定的需要查找到的值然后使这个函数返回这个元素的位置迭代器
iterator find(const T val)
{auto it begin();while (it ! end() *it ! val){it;}if (*it val) return it;return nullptr;}4.6 头删和尾删操作
前面我们已经实现了earse 现在我们就只需要对这个和拿书尽心你给复用就好了
void pop_front()
{erase(end());
}
void pop_back()
{erase(--end());
}接下来我们就直接来演示这个函数是否有用 五、析构函数与clear函数
最后我们就来实现一下list的析构函数我们还是继续函数的复用
// zdl:: 析构类函数的实现~list(){// ! 不仅要将所有的数值删除还需要将哨兵位也清除clear();delete _head;_head nullptr; }void clear(){// !! 不能删除哨兵位就只是将所有的数值清空。auto it begin();while (it ! end()) it erase(it);}现在我们就将已有的链表清空试试
六、代码展示
list.h
#pragma once #includeiostream
#includecassert
using namespace std;
namespace zdl
{template class Tstruct ListNode{T _data;ListNodeT* _next;ListNodeT* _prev;// 节点的构造函数ListNode(const T val T()):_data(val),_next(nullptr),_prev(nullptr){}};templateclass T, class Ref, class Ptrstruct list_iterator{typedef ListNodeT node;typedef list_iteratorT, Ref, Ptr self;node* _nd;list_iterator(node* nd):_nd(nd){}// zdl:: 实现迭代器的基本功能// 解引用数值Ref operator*(){return _nd-_data;}Ptr operator-(){return _nd-_data;}// zdl:: 前置 / --self operator(){_nd _nd-_next;return *this;}self operator--(){_nd _nd-_prev;return *this;}self operator(size_t n){while (n--){_nd _nd-_next;}return *this;}self operator-(size_t n){while (n--){_nd _nd-_prev;}return *this;}// zdl:: 后置 / --self operator(int){self tmp _nd;_nd _nd-_next;return tmp;}self operator--(int){self tmp _nd;_nd _nd-_prev;return tmp;}// zdl:: ! 运算bool operator!(const self s){return _nd ! s._nd;}};templateclass Tclass list{public:typedef ListNodeT node;typedef list_iteratorT, T, T* iterator;typedef list_iteratorT, const T, const T* const_iterator;void empty_init(){// zdl :: 在初始化一个空链表时 先定义一个哨兵位_head new node();_head-_next _head;_head-_prev _head;}list(){empty_init();}list(const listT l1){empty_init();for (auto e : l1) push_back(e);}list(size_t n, const T x T()){empty_init();for (size_t i 0; i n; i){push_back(x);}}void push_back(const T val){node* creat new node(val);node* tail _head-_prev;tail-_next creat;creat-_prev tail;creat-_next _head;_head-_prev creat; }void push_front(const T val){node* fnode new node(val);fnode-_next _head-_next;fnode-_prev _head;_head-_next-_prev fnode;_head-_next fnode;}void Print_list(){node* cur _head-_next;while (cur ! _head){cout cur-_data ;cur cur-_next;}cout endl;}// zdl:: 增删查改的实现iterator insert(iterator pos, const T val T()){node* cur pos._nd;node* prev pos._nd-_prev;node* insrt new node(val);prev-_next insrt;insrt-_prev prev;insrt-_next cur;cur-_prev insrt;return iterator(cur-_prev);}iterator erase(iterator pos){assert(pos ! end()); //! 注意不能够将哨兵位删除node* cur pos._nd;node* prev cur-_prev;prev-_next cur-_next;cur-_next-_prev prev;delete cur;return iterator(prev-_next);}iterator find(const T val){auto it begin();while (it ! end() *it ! val){it;}if (*it val) return it;return nullptr;}void pop_front(){erase(begin());}void pop_back(){erase(--end());}// zdl:: 析构类函数的实现~list(){// ! 不仅要将所有的数值删除还需要将哨兵位也清除clear();delete _head;_head nullptr; }void clear(){// !! 不能删除哨兵位就只是将所有的数值清空。auto it begin();while (it ! end()) it erase(it);}
// zdl:: 使用类来模拟迭代器的行为iterator begin(){return iterator(_head-_next);}iterator end(){return iterator(_head);}const_iterator begin() const{return const_iterator(_head-_next);}const_iterator end() const{return const_iterator(_head);}private:node* _head;};
}
test.cpp #includelist.h
#includelist
struct pos
{int row;int col;//构造函数pos(const int x 0, const int y 0):row(x),col(y){}//成员函数void pos_show(){printf((%d, %d) ,row, col);}
};
int main()
{// zdl::listpos l1;// pos p[] {{1, 2}, {3, 4}, {5, 6}};// for (int i 0; i 3; i) l1.push_back(p[i]);// auto it l1.begin();// while (it ! l1.end())// {// it-pos_show();// it;// cout endl;// }// cout endl;// zdl::listint l2(5, 4);// for (autoi : l2) cout i ;// cout endl;// zdl::listint l4(3, 3);// l4.Print_list();// l4.insert(l4.begin() 2, 2);// l4.Print_list();// l4.erase(l4.begin() 2);// l4.Print_list();// zdl::listintl5;// for (int i 1; i 10; i) l5.push_back(i);// cout 原数组 endl;// l5.Print_list();// // zdl:: 现在我们要借助 find erase函数来删除元素5// l5.erase(l5.find(5));// cout 删除后 endl;// l5.Print_list();// zdl:: 进行头删和尾删// cout 进行尾删和头删后: endl;// l5.pop_back();// l5.pop_front();// l5.Print_list();// cout 现在将所有的元素都删除 endl;// l5.clear();// l5.Print_list();zdl::listint l1(10, 10);cout l1: endl;l1.Print_list();zdl::listint l2(l1);cout l2: endl;l2.Print_list();return 0;
}好常用的接口我们就实现了list学习到此告一段落再见
