兰州市规划建设局网站,房地产网站开发公司电话,小程序需要写网站建设方案书,WordPress更新时间一、list介绍
1、list是可以在常数范围内在任意位置进行插入和删除的序列式容器#xff0c;并且该容器可以前后双向迭代。
2、list就是一个带头双向循环链表#xff0c;list通常在任意位置进行插入、移除元素的执行效率更好。
3、list最大的缺陷是不支持任意位置的随机访问…一、list介绍
1、list是可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代。
2、list就是一个带头双向循环链表list通常在任意位置进行插入、移除元素的执行效率更好。
3、list最大的缺陷是不支持任意位置的随机访问。
二、list的使用
有了前面使用string和vector的经验后list的使用也跟它们如出一辙看一下文档介绍就可以使用了。这里就不演示使用了。文档链接list - C Reference (cplusplus.com)
要注意的点就是迭代器失效问题迭代器失效即迭代器所指向的节点的无效即该节点被删除了。因为list的底层结构为带头结点的双向循环链表因此在list中进行插入时是不会导致list的迭代器失效的只有在删除时才会失效并且失效的只是指向被删除节点的迭代器其他迭代器不会受到影响。
三、list模拟实现
templateclass T//节点类型struct _list_node{_list_node* _next;_list_node* _prev;T _val;_list_node(const T val T()):_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;}Ptr operator-(){return (_node-_val);}self operator(){_node _node-_next;return *this;}self operator--(){_node _node-_prev;return *this;}bool operator!(const self it) const{return _node ! it._node;}bool operator(const self it) const{return _node it._node;}};templateclass Tclass list{typedef _list_nodeT Node;public:typedef __list_iteratorT, T, T* iterator;typedef __list_iteratorT, const T, const T* const_iterator;typedef ReverseIteratoriterator, T, T* reverse_iterator;typedef ReverseIteratorconst_iterator, const T, const T* const_reverse_iterator;reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}const_reverse_iterator rbegin() const{return reverse_iterator(end());}const_reverse_iterator rend() const{return reverse_iterator(begin());}iterator begin(){return _head-_next;//隐式类型转换}iterator end(){return _head;//隐式类型转换}const_iterator begin() const {return _head-_next;//隐式类型转换}const_iterator end() const{return _head;//隐式类型转换}list(){_head new Node;_head-_next _head;_head-_prev _head;_size 0;}list(const listT lt){_head new Node;_head-_next _head;_head-_prev _head;_size 0;for (auto e : lt){push_back(e);}}/*list(const listT lt){_head new Node;_head-_next _head;_head-_prev _head;_size 0;const_iterator it lt.begin();while (it ! lt.end()){push_back(*it);it;}}*/void swap(listT tl){std::swap(_head, tl._head);std::swap(_size, tl._size);}listT operator(listT tmp){swap(tmp);return *this;}void push_back(const T x){insert(end(), x);/*Node* newnode new Node(x);Node* tail _head-_prev;tail-_next newnode;newnode-_prev tail;newnode-_next _head;_head-_prev newnode;*/}void push_front(const T x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}iterator insert(iterator pos, const T x){Node* newnode new Node(x);Node* cur pos._node;Node* prev cur-_prev;prev-_next newnode;newnode-_next cur;cur-_prev newnode;newnode-_prev prev;_size;return newnode;}iterator erase(iterator pos){assert(pos._node ! _head);Node* prev pos._node-_prev;Node* next pos._node-_next;prev-_next next;next-_prev prev;delete pos._node;--_size;return next;}size_t size(){return _size;}void clear(){iterator it begin();while (it ! end()){it erase(it);}_size 0;}~list(){clear();delete _head;_head nullptr;}private:Node* _head;size_t _size;};
后面再总结反向迭代器的实现。
四、vector和list的区别
vectorlist底层结构动态顺序表一段连续的空间带头双向循环链表随机访问支持随机访问访问某个元素效率为O(1)不支持随机访问访问某个元素效率为O(N)插入和删除在尾部删除和插入效率高其余地方插入和删除效率低。任意位置插入和删除的效率都高空间利用率空间利用率高底层为连续空间不容易造成内存碎片底层节点动态开辟空间利用率低迭代器原生态指针对原生指针节点指针进行封装迭代器失效在插入数据时可能会扩容导致迭代器失效删除时当前迭代器需要重新赋值否则会失效插入元素不会导致迭代器失效删除元素时只会导致当前迭代器失效其它不受影响使用场景需要高效存储支持随机访问不关心插入删除效率大量的插入和删除操作不关心随机访问
