建设p2p网站,wordpress插件是什么,太原网站关键词优化,做网站的注意事项#x1f44d;作者主页#xff1a;进击的1 #x1f929; 专栏链接#xff1a;【1的C初阶】 文章目录 一#xff0c;什么是list二#xff0c;构造与析构2.1 结点结构2.2 链表结构2.3 迭代器结构 三#xff0c;部分重要接口的作用及其实现3.1 迭代器相关的接口3.2 list相关… 作者主页进击的1 专栏链接【1的C初阶】 文章目录 一什么是list二构造与析构2.1 结点结构2.2 链表结构2.3 迭代器结构 三部分重要接口的作用及其实现3.1 迭代器相关的接口3.2 list相关接口 一什么是list
list是可以在常数范围内进行任意插入和删除的序列式容器。 list底层是前后循环链表因此可以双向前后迭代。与其他序列式容器相比list的最大缺陷是不支持任意位置的随机访问。并且list还需要一些额外的空间来保存结点与结点间的相关联信息。
二构造与析构
2.1 结点结构
templateclass Tstruct list_node{list_node* prev;//指向上一个结点list_node* next;//指向下一个结点T data;//构造list_node(const T val T()):data(val), prev(nullptr), next(nullptr){}};在此结构中定义出来了指向结点的前后指针结点数据类型并对上述成员变量进行了初始化。
2.2 链表结构
templateclass Tclass list{public:typedef list_nodeT Node;//构造list(){_head new Node;_head-prev _head;_head-next _head;}void clear(){iterator it begin();while (it ! end()){it erase(it);}}//拷贝构造template class InputIteratorlist(InputIterator first, InputIterator last){_head new Node;_head-prev _head;_head-next _head;while (first ! last){push_back(*first);first;}}//拷贝构造//现代写法list(const listT lt){_head new Node;_head-prev _head;_head-next _head;listT tmp(lt.begin(), lt.end());std::swap(_head, tmp._head);}~list(){clear();delete _head;_head nullptr;}private:Node* _head; };此结构中定义了头结点并对头结点进行了初始化使其指向上一个的指针指向自己指向下一个的指针指向自己。 拷贝构造我们用的是现代写法通过迭代器构造构造出一个临时对象再将其头结点指针进行交换。需要注意的是在拷贝前都要进行初始化防止其成为野指针。 在析构之前先将哨兵位头结点前的结点进行释放因此就有了clear()函数最后在析构时就只需将头结点释放。
2.3 迭代器结构
templateclass T, class Ref, class Ptrstruct list_iterator{typedef list_iteratorT,Ref,Ptr iterator;typedef list_nodeT Node;//申请一个结点指针Node* _node;//构造list_iterator(Node* node):_node(node){}};list迭代器的本质就是一个指向结点的指针。先是申请结点指针进行初始化使其指向传过来的结点指针。
三部分重要接口的作用及其实现
3.1 迭代器相关的接口
bool operator !(const iterator it)const{return _node ! it._node;}bool operator (const iterator it)const{return _node it._node;}Ref operator *(){return _node-data;}Ptr operator-(){return (operator*());}iterator operator(){_node _node-next;return *this;}iterator operator(int){iterator tmp *this;_node _node-next;return tmp;}iterator operator--(){_node _node-prev;return *this;}iterator operator--(int){iterator tmp *this;_node _node-prev;return tmp;}因为list迭代器是自定义类型因此迭代器之间的一些操作我们就必须要进行函数重载。我们解释几个比较重要的函数重载 。 Ptr operator-(){return (operator*());}
此重载所适合的环境当list中存储的也是一个结构体是此运算符就能够使用。 例
struct pos{int a;int b;};listpos lt;listpos::iterator itlt.begin();it-a;在此函数内部返回了(operator*())而operator*()我们也进行了重载返回的是结点数据–data要是按此形式那么此函数最终返回的就是data的地址。这与我们上述it-a不符合。原因在于此处还有个隐藏的-其最终形式为it-data-a;这是编译器为了语法的可读性而进行的的特殊处理。
说完-重载我们在来说说的重载。
iterator operator()//前置{_node _node-next;return *this;}由于list的空间是不连续的因此迭代器就是到下一结点。
3.2 list相关接口
inert的实现
iterator insert(iterator pos,const T val){Node* cur pos._node;Node* newnode new Node(val);Node* prev cur-prev;prev-next newnode;newnode-prev prev;newnode-next cur;cur-prev newnode;return iterator(newnode);}erase的实现
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 iterator(next);}
