做网站前端程序员,建筑信息平台查询,开发前端后端,免费申请com网站送给大家一句话#xff1a;
若结局非你所愿#xff0c;就在尘埃落定前奋力一搏。—— 《夏目友人帐》 手搓 list 容器 1 前言1.1 底层结构1.2 使用场景1.3 功能简介 2 框架搭建2.1 节点类2.2 list 类2.3 迭代器类 3 功能实现3.1 begin() 与 end()3.2 插入操作3.3 删除操作3… 送给大家一句话
若结局非你所愿就在尘埃落定前奋力一搏。—— 《夏目友人帐》 手搓 list 容器 1 前言1.1 底层结构1.2 使用场景1.3 功能简介 2 框架搭建2.1 节点类2.2 list 类2.3 迭代器类 3 功能实现3.1 begin() 与 end()3.2 插入操作3.3 删除操作3.4 拷贝构造3.5 析构函数3.6 其他函数 4 总结Thanks♪(ω)谢谢阅读下一篇文章见 1 前言
List是C标准模板库(STL)中的一个成员其本质为带头双向循环链表。不同于连续的、紧密排列的数组容器VectorList容器的内部是由双向链表构成的使得它在插入和删除操作上就如同行云流水一般顺畅不需移动其它元素。
1.1 底层结构
List容器的底层结构是一个经典的带头双向循环链表。每个节点包含
数据指向前一个节点的指针指向后一个节点的指针。
这种结构赋予了List灵动的特性它能够轻松地在任意位置增加或移除元素而这种操作几乎是与容器大小无关的体现了时间复杂度上的优势。但这种优势的代价是与数组相比List在访问元素时的速度会较慢因为它需要从头开始遍历。这也决定了list的更适合频繁插入的动态数据。 来看STL源码中的节点结构
template class T
struct __list_node {typedef void* void_pointer;void_pointer next;void_pointer prev;T data;
};1.2 使用场景
List最适合的场景是那些需要频繁进行插入和删除操作的场合。 例如如果你正在管理一个动态变化的列表如任务调度、人员排队等场景List的特性将大放异彩。但是如果你的应用场景更多地需要随机访问元素那么向量Vector或者数组可能是更佳的选择。因为List的顺序访问性能相比之下会显得有些力不从心。
所以如果需要频繁随机的访问数据那么选择vector容器如果需要频繁插入删除数据那么选择list容器排序不要选择list 其删除节点的过程就决定了其速度不会太快。
1.3 功能简介
功能简介我们可以参考STL官方库 :list文档介绍
插入与删除List的插入和删除操作非常高效它可以在任意位置快速地添加或移除元素而不需要像连续内存容器那样进行大量元素的移动。多种构造类都应该包含多种构造函数支持迭代器迭代器是C重要的特性我们写的list 也一定要支持迭代器。
2 框架搭建
现在我们开始实现list 容器首先先要思考一下框架结构
首先我们需要一个节点结构体类似源码中的节点其次我们的list 类要带一个头结点让我们更方便进行插入删除操作
基本就是这样现在我们开始手搓
2.1 节点类
// 节点 结构体
templateclass T
struct ListNode
{ListNode* _next;ListNode* _prev;T _data;ListNode(T x T()) :_next(nullptr),_prev(nullptr),_data(x){}//ListNode(T x T()) //{// _next nullptr;// _prev nullptr;// _data x;//} ~ListNode(){_next nullptr;_prev nullptr;}
};这里使用模版来适配更多的情景然后基本的数据前后指针都很简单。在编写一个构造函数构造函数使用初始化列表并不是必须使用。析构函数避免野指针出现将指针赋值为nullptr就可以了。
2.2 list 类
我们先进行简单的框架书写构造函数需要创建一个头结点因为我们要创建双向循环链表所以头尾都要指向头结点本身。 _size赋初值。
templateclass T
class list
{
public://设置适配的节点typedef ListNodeT Node;//空初始化void empty_init(){_head new Node;_head-_next _head;_head-_prev _head;_size 0;}//构造函数list() :_head(nullptr){empty_init();}
private:Node* _head;size_t _size;
};接下来我们来逐步完成功能书写由于我们还没有进行迭代器的书写
2.3 迭代器类
我们思考一下这里能不能使用原生指针来完成迭代器的操作 ! --当然是不能的因为链表的物理地址并不是连续的对原生指针的或–操作是没有意义的所以我们需要自行编写迭代器类对原生指针进行封装来满足我们特殊的和–操作。 //这里的模板可以再次升级 先简单写一下templateclass Tclass ListIterator {public://重命名方便书写typedef ListNodeT Node;typedef ListIteratorT Self;Node* _node;ListIterator(Node* x ):_node(x){}//操作符重载 前置 与 后置的区别是参数是否带int//tSelf operator(){_node _node-_next;return *this;}//tSelf operator(int){Self tmp(*this);//浅拷贝即可_node _node-_next;return tmp;}//--tSelf operator--(){_node _node-_prev;return *this;}//t--Self operator--(int){Self tmp(*this);//浅拷贝即可_node _node-_prev;return tmp;}//判断是否相等 比较指针地址是否相同即可bool operator!(const Self it){return _node ! it._node;}//判断是否相等 比较指针地址是否相同即可bool operator(const Self it){return _node it._node;}// 解引用操作 *it 返回节点数据的引用 可以进行修改T operator*(){return _node-_data;}//因为指针才能使用- 所以-要返回地址指针 T* operator-()//编译器会进行省略-{return _node-_data;}};这样迭代器类就大致写好了那么一般我们的迭代器应该还要支持const不然我们传入一个不可修改的链表const list l,就会反生报错那么我们还要书写一份const版的迭代器。如果进行编写那么是不是会有大部分与刚才我们书写的迭代器重复 -- ! 都是一样的只有operator*()和operator-()返回值不一致
因为是常迭代器使用场景是对const listT l进行操作那么节点数据不可改变所以不影响 -- ! 这些操作受影响的是operator*()和operator-()返回值该情况下链表本身是只读的又因为不能将权限进行扩大所以返回值应该也是只读的const。那这样就发现了不同常迭代器应该为 const T operator*() 和 const T* operator-() ,所以有没有一种办法可以简单解决呢当然有了我们设置一个新模版带有三个参数创建的时候就传入对应参数
我们将模版修改为这样 //reference 引用 pointer 指针
templateclass T , class Ref ,class Ptr对应返回值也改变 Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}那么类实例化的时候传入对应参数就好了
typedef ListIteratorT, T, T* iterator;
typedef ListIteratorT, const T, const T* const_iterator;这样就实现了迭代器的创建是不是就非常简洁了呢
3 功能实现
3.1 begin() 与 end()
使用迭代器即可注意end()是头结点因为遍历过程中全部遍历后会回到头结点所以直接判断是否为头结点就能控制结束位置。
//普通迭代器
typedef ListIteratorT, T, T* iterator;
//常迭代器
typedef ListIteratorT, const T, const T* const_iterator;iterator begin() { return _head-_next; }
iterator end() { return _head; }const_iterator begin() const { return _head-_next; }
const_iterator end() const { return _head; }3.2 插入操作
插入操作我们很熟悉步骤是创建一个新节点然后通过改变指针指向来完成插入操作 来看尾插操作
void push_back(const T x T())
{//创建新节点Node* node new Node(x);//找尾Node* tail _head-_prev;//进行插入node-_next _head;node-_prev tail;tail-_next node;_head-_prev node;//别忘记大小_size;
}任意位置插入操作思路依然是对前后节点与新节点的指针指向进行操作来完成插入。
void insert(iterator pos begin(), T x T())
{//创建新节点Node* node new Node(x);//前节点 后节点Node* prev pos._node-_prev;Node* next pos._node;//处理新节点node-_prev prev;node-_next next;//出现前后节点prev-_next node;next-_prev node;//别忘记大小_size;
} 头插直接干脆调用insert就可以了
void push_front(const T x T())
{insert(begin(), x);
}3.3 删除操作
删除操作同样是使用指针操作来达到删除的效果。注意要对删除的节点进行释放空间操作delete不然会发生内存泄漏
尾删
void pop_back()
{Node* tail _head-_prev;Node* prev tail-_prev;prev-_next _head;_head-_prev prev;delete tail;_size--;
}
//头删
void pop_front()
{Node* head _head-_next;Node* next head-_next;_head-_next next;next-_prev _head;delete head;_size--;
}
//任意位置删除
iterator erase(iterator pos)
{Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;prev-_next next;next-_prev prev;delete cur;_size--;return iterator(next);
}需要注意的是任意位置删除因为使用了迭代器删除后会造成迭代器失效所以需要更新迭代器返回被删除节点的下一个节点的迭代器即可。
3.4 拷贝构造
拷贝构造直接将数据一个一个插入到该链表中即可
list(const listT l)
{empty_init();iterator it l.begin();while (it ! l.end()){push_back(*it);it;}
}这样十分方便快捷
3.5 析构函数
void clear()
{//依次释放iterator it begin();while (it ! end()){it erase(it);}
}
~list()
{clear();//需要单独释放头结点空间delete _head;_head nullptr;
}3.6 其他函数
返回大小
size_t size() const { return _size; }判断是否为空
bool empty()
{return _size 0;
}清空数据
void clear()
{iterator it begin();while (it ! end()){it erase(it);}
}4 总结
本文我们实现了STL库中重要的list 的模拟实现其中最重要莫过于迭代器的封装类的书写这是前所未有的操作对于我来说我是第一次使用这种结构。通过list 的模拟实现也帮我们巩固了类与对象的知识也强化了指针操作的思路。欢迎大家讨论分析。
Thanks♪(ω)谢谢阅读
下一篇文章见
