正规网站制作公司哪里有,网站建设最简单的教程视频教程,国内炫酷的网站首页,怎么识别网站开发语言list是双向带头链表。所以迭代器end()相当于哨兵卫的头。
list不支持和[]重载#xff0c;原因在于list空间不是连续的#xff0c;和[]的代价比较大。
访问第n个节点#xff0c;只能用for循环#xff0c;来实现
listint l;
l.push_back(0);
l.push_back(1);
l.pu…list是双向带头链表。所以迭代器end()相当于哨兵卫的头。
list不支持和[]重载原因在于list空间不是连续的和[]的代价比较大。
访问第n个节点只能用for循环来实现
listint l;
l.push_back(0);
l.push_back(1);
l.push_back(2);
l.push_back(3);
auto lil.begin();
//访问第3个节点
for(size_t i0;i3;i)
{li;
}list的insert不会失效但是erase会迭代器失效。 list是双向迭代器 迭代器可以简单分为单向迭代器(forward)双向迭代器(bidirectional) /-- 随机迭代器(random acess)/-//-- 不同的数据结构的迭代器决定了可以使用不同的算法。其中随机迭代器代器的范围最广可以用的算法最多。 std:sort只能是随机迭代器用list不能使用list也有自己的sort算法但是效率并不高。 list实现
大概思路先不考虑迭代器链表分为两个类一个类表示节点另外一个类表示链表。
节点模板类
templateclass Tstruct list_node{list_nodeT* _next;list_nodeT* _prev;T _val;list_node(const T val T()):_next(nullptr),_prev(nullptr),_val(val){}};
这里有个注意的点模板类的类名不是类型list_node只是类名不是对应的自定义类型所以是
list_nodeT* _next;而不是list_node* _next。 编译器优化
拷贝构造写类名也可以
模拟实现的代码
namespace my_list
{templateclass T struct list_node{list_nodeT* _prev;list_nodeT* _next;T _val;list_node(const T valT()):_next(nullptr),_prev(nullptr),_val(val){}};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){}Ref operator*(){return _node-_val;}self operator(){_node _node-_next;return *this;}self operator--(){_node _node-_prev;return *this;}bool operator!(const self it){return _node ! it._node;}self operator(int){self tmp(*this);_node _node-_next;return tmp;}Ptr operator-(){return _node-_val;}};templateclass Tclass list{typedef list_nodeT Node;public:typedef __list_iteratorT,T,T* iterator;typedef __list_iteratorT, const T,const T* const_iterator;iterator begin(){return _head-_next; }iterator end(){return _head;}const_iterator const_begin(){return _head-_next;}const_iterator const_end(){return _head;}void empty_init(){_head new Node;_head-_next _head;_head-_prev _head;}list(){empty_init();}~list(){clear();delete _head;_head nullptr;}list(const listT lt){empty_init();for (auto e : lt){push_back(e);} }void swap(listT lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}listT operator(listT lt){swap(lt);return *this;}~list(){clear();delete _head;_head nullptr;}void push_back(const T x){/*Node* tail _head-_prev;Node* newnode new Node(x);tail-_next newnode;newnode-_prev tail;newnode-_next _head;_head-_prev newnode;*/insert(end(), x);}void push_front(const T x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_begin(){erase(begin());}iterator insert(iterator pos, const T x){Node* cur pos._node;Node* prev cur-_prev;Node* newnode new Node(x);prev-_next newnode;newnode-_next cur;cur-_prev newnode;newnode-_prev prev;return newnode;}iterator erase(iterator pos){assert(pos ! end());Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;prev-_next next;next-_prev prev;delete cur;return next;}void clear(){iterator it begin();while (it ! end()){iterase(it);}}size_t size(){size_t sz 0;iterator it begin();while (it ! end()){sz;}return sz;}private:Node* _head;Node* _tail;};
}
