谈谈对电子商务网站建设与管理,c 网站登录验证码怎么做,网站备案帐户有什么用,网站开发需要多少钱点评今天我们了解list#xff0c;list在python中是列表的意思 #xff0c;但是在C中它是一个带头双向循环链表#xff1a;
list的介绍
list是可以在常数范围内在任意位置进行插入和删除的序列式容器#xff0c;并且该容器可以前后双向迭代。list的底层是双向链表结构#xf…今天我们了解listlist在python中是列表的意思 但是在C中它是一个带头双向循环链表
list的介绍
list是可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代。list的底层是双向链表结构双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指向其前一个元素和后一个元素。list与forward_list非常相似最主要的不同在于forward_list是单链表只能朝前迭代已让其更简单高效。与其他的序列式容器相比(arrayvectordeque)list通常在任意位置进行插入、移除元素的执行效率更好。与其他序列式容器相比list和forward_list最大的缺陷是不支持任意位置的随机访问比如要访问list的第6个元素必须从已知的位置(比如头部或者尾部)迭代到该位置在这段位置上迭代需要线性的时间开销list还需要一些额外的空间以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)
list的模拟实现
有了前面的string和vector的模拟实现我们的list的模拟实现算是轻车熟路了我们要想模拟实现list就需要了解list在库里面的源码我们用everything查找一下 可以看到在list的类里面成员参数只有一个但是这个参数是此前定义的一个结构体它包含了nextprev和当前节点存储的data所以我们同样需要去自定义一个结构体
我们首先把定义一个结构体就是list的节点的结构同时在里面定义一个构造新节点的函数
template class T
struct list_node
{T _data;list_nodeT* _prev;list_nodeT* _next;list_node(const T x T()):_data(x), _prev(nullptr), _next(nullptr){}
};然后我们就可以在命名空间内定义list类了 为了可读性和代码的简洁我就用Node来作为list_node的重命名了
namespace jh
{template class Tstruct list_node{T _data;list_node* _prev;list_node* _next;list_node(const T x T()):_data(x), _prev(nullptr), _next(nullptr){}};template class Tclass list{typedef list_nodeT Node;private:Node* _head;size_t _size;};
}我们首先就拿下最难啃的一块骨头
迭代器
我们再次查看list的源码就会发现 迭代器同样地使用了一个结构体来构造所以这里我们也采用结构体 我们先整体地构造一个框架 至于模块的地方为什么有多个参数我稍后做讲解这是一个很重要的点 迭代器就是一个节点我们同时定义一个拷贝构造的函数 template class T,class Ref,class Ptrstruct __list_iterator{typedef list_nodeT Node;typedef __list_iteratorT,Ref,Ptr self;Node* _node;__list_iterator(Node* node):_node(node){}};和–的重载 迭代器最常用的点就是和–因为我们需要用迭代器来初始化等等我们就首先在结构体内重载和– 括号后面又int的我们之前的博客也进行学习过它是后置编译器会自动识别的temp就是一个匿名参数他的生命周期只有一行这里的-运算符我们之后也要做重载不然不能用 这里还有一个需要注意的点 前置是返回对象本身所以用引用返回减少拷贝但是后置返回的是对象temp临时变量是一个常量不能用引用
self operator()
{_node _node-_next;return *this;
}
self opetrator--()
{_node _node-prev;return *this;
}
self operator(int)
{self temp(*this);_node _node-next;return temp;
}
self operator--(int)
{self temp(*this);_node _node-prev;return temp;
}*和-的重载 *是解引用就是返回迭代器所存储的数据返回data就是 —操作符前的是一个地址所以就取地址就可以了这里的Ref和Ptr就派上用场了
Ref operator*()
{return _node-_data;
}Ptr operator-()
{return _node-data;
}!和操作符重载 这里用bool类型就可以了直接返回它们之间的关系即可
bool operator!(const self s)
{return _node ! s._node;
}bool operator(const self s)
{return _node s._node;
}迭代器就完成了 增加Ref和Ptr的作用就是为了随时适应例如需要const T或者const T*这种这样就省去了const迭代器的代码更加简洁了这是迭代器的妙处之一 template class T,class Ref,class Ptrstruct __list_iterator{typedef list_nodeT Node;typedef __list_iteratorT,Ref,Ptr self;Node* _node;__list_iterator(Node* node):_node(node){}self operator(){_node _node-_next;return *this;}self operator--(){_node _node-prev;return *this;}self operator(int){self temp(*this);_node _node-next;return temp;}self operator--(int){self temp(*this);_node _node-prev;return temp;}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-data;}bool operator!(const self s){return _node ! s._node;}bool operator(const self s){return _node s._node;}};迭代器解决后我们就可以将其应用到list类里了 这里大家记住 begin就是头节点head的下一个节点 end就是head节点
const_iterator begin() const
{return const_iterator(_head-_next);
}
const_iterator end() const
{return const_iterator(_head);
}
iterator begin()
{return iterator(_head-_next);
}
iterator end()
{return iterator(_head);
}构造函数
构造函数我们必须有一个头节点head同时我们要知道当list为空时head的next和prev都是head本身
void empty_init()
{_head new Node;_head-_next _head;_head-_prev _head;
}list()
{empty_init();
}insert函数
insert函数要做的就是首先构造一个新的节点然后插入插入很简单我们在数据结构中学过这里不做过多的讲解 记住最后要返回插入的那个新节点
iterator insert(iterator pos, const T x T())
{Node* cur pos._node;Node* newnode new Node(x);Node* prev cur-_prev;prev-_next newnode;newnode-_next cur;cur-_prev newnode;newnode-_prev prev;return iterator(newnode);
}erase函数
erase函数同样地也是用数据结构的知识来操作但是erase函数返回的是删除pos位置的下一个位置的迭代器
iterator erase(iterator pos)
{Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;delete cur;prev-_next next;next-_prev prev;return iterator(next);
}尾删和头删尾插和头插
这些我们在有了解决了erase和insert之后可以直接复用了
void push_back(const T x)
{insert(end(), x);
}
void push_front(const T x)
{insert(begin(), x);
}
void pop_back()
{erase(end());
}
void pop_front()
{erase(begin());
}拷贝构造函数
拷贝构造函数我们依旧用pushback和语法糖来实现 逐一将lt中的元素尾插进入即可
list(const listtT lt)
{empty_init();for (auto e : lt){push_back(e);}
}赋值操作符重载
赋值操作符重载我们用swap解决直接调用std库里的swap函数即可
void swap(listT lt)
{std::swap(_head, lt._head);
}
listT operator(listT lt)
{swap(lt);return *this;
}析构函数
我们先定义一个clear函数用于清理空间然后复用记住将head节点释放
void clear()
{iterator it begin();while (it ! end()){it erase(it);//erase每次返回的都是it的next故可以这样写}
}
~list()
{clear();delete _head;_head nullptr;
}到这里list的模拟实现差不多就结束了感谢大家的支持
完整代码如下
using namespace std;
namespace jh
{template class Tstruct list_node{T _data;list_nodeT* _prev;list_nodeT* _next;list_node(const T x T()):_data(x), _prev(nullptr), _next(nullptr){}};templateclass T, class Ref, class Ptrstruct __list_iterator{typedef list_nodeT Node;typedef __list_iteratorT, Ref, Ptr self;Node* _node;__list_iterator(Node* node):_node(node){}self operator(){_node _node-_next;return *this;}self operator--(){_node _node-_prev;return *this;}self operator(int){self temp(*this);_node _node-_next;return temp;}self operator--(int){self temp(*this);_node _node-_prev;return temp;}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}bool operator!(const self s){return _node ! s._node;}bool operator(const self s){return _node s._node;}};template class Tclass list{typedef list_nodeT Node;public:typedef __list_iteratorT, const T, const T* iterator;typedef __list_iteratorT, const T, const T* const_iterator;const_iterator begin() const{return const_iterator(_head-_next);}const_iterator end() const{return const_iterator(_head);}iterator begin(){return iterator(_head-_next);}iterator end(){return iterator(_head);}void empty_init(){_head new Node;_head-_next _head;_head-_prev _head;}list(){empty_init();}iterator insert(iterator pos, const T x T()){Node* cur pos._node;Node* newnode new Node(x);Node* prev cur-_prev;prev-_next newnode;newnode-_next cur;cur-_prev newnode;newnode-_prev prev;return iterator(newnode);}iterator erase(iterator pos){Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;delete cur;prev-_next next;next-_prev prev;return iterator(next);}void push_back(const T x){insert(end(), x);}void push_front(const T x){insert(begin(), x);}void pop_back(){erase(end());}void pop_front(){erase(begin());}list(const listT lt){empty_init();for (auto e : lt){push_back(e);}}void swap(listT lt){std::swap(_head, lt._head);}listint operator(listint lt){swap(lt);return *this;}void clear(){iterator it begin();while (it ! end()){it erase(it);}}~list(){clear();delete _head;_head nullptr;}private:Node* _head;size_t _size;};
}
