跨境派

跨境派

跨境派,专注跨境行业新闻资讯、跨境电商知识分享!

当前位置:首页 > 工具系统 > 广告工具 > 【C++】STL--list

【C++】STL--list

时间:2024-04-13 14:35:23 来源:网络cs 作者:胡椒 栏目:广告工具 阅读:

标签:

目录

list的介绍

list的使用

list的构造

list iterator的使用

list capacity

list modifiers

list的迭代器失效

list模拟实现


list的介绍

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。

2. list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。

3.与其他的序列式容器相比(array,vector,deque),list通常在任意位置进行插入、移除元素的执行效率更好。

list的使用

list的构造

1.list(size_t n,const T& lt = T())

说明:构造的list中包含n个值为val的元素

2.list()

说明:构造空的list

3.list(const list& x)

说明:拷贝构造函数

4.list(InputIterator first,InputIterator  last)

说明:用[first,last)区间中的元素构造list

list iterator的使用

此时,我们暂且将迭代器理解成一个指针,该指针指向list中的某个节点。

begin+end:返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器

rbegin+rend:返回第一个元素的reverse_iterator,即end位置,返回最后一个元素下一个位置的reverse_iterator,即begin位置

注意:

1. begin与end为正向迭代器,对迭代器执行++操作,迭代器向后移动

2. rbegin(end)与rend(begin)为反向迭代器,对迭代器执行++操作,迭代器向前移动

list capacity

empty:检测list是否为空,是返回true,否则返回false

size:返回list中有效节点个数

list modifiers

push_front:在list首元素前插入值为val的元素

pop_front:删除list中的第一个元素

push_back:在list尾部插入值为val的元素

pop_back:删除list中的最后一个元素

insert:在pos位置插入值为val的元素

erase:删除pos位置的元素

swap:交换两个list中的元素

clear:清空list中的有效元素

list的迭代器失效

我们将迭代器暂时理解成类似于指针,迭代器失效即迭代器所指向的节点的无效,即该节点被删除了。因为list的底层结构为带头结点的双向循环链表,因此在list中进行插入时是不会导致list的迭代器失效的,只有在删除时才会失效,并且失效的只是指向被删除节点的迭代器,其他迭代器不会受到影响。

void TestListIterator(){int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array + sizeof(array) / sizeof(array[0]));auto it = l.begin();while (it != l.end()){//错误示范        //erase()函数执行后,it所指向的节点已被删除,因此it无效,在下一次使用it时,必须先给其赋值//l.erase(it);//++it;//正确it = l.erase(it);}}

list模拟实现

namespace ghs{template<class T>struct ListNode{ListNode(const T& x = T()):_next(nullptr),_prev(nullptr),_data(x){}ListNode<T>* _next;ListNode<T>* _prev;T _data;};template<class T, class Ref, class Ptr>struct ListIterator{typedef ListNode<T> Node;typedef ListIterator Self;Node* _node;ListIterator(Node* node):_node(node){}//*it//不能传值返回,*it只能传引用返回,因为除了读还有写的功能//T& operator*()Ref operator*(){return _node->_data;}//++itSelf& operator++(){_node = _node->_next;return *this;}//it++Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}//--itSelf& operator--(){_node = _node->_prev;return *this;}//it--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;}//T* operator->()Ptr operator->(){return &_node->_data;}};//template<class T>//struct ListConstIterator//{//typedef ListNode<T> Node;//typedef ListConstIterator Self;//Node* _node;//ListConstIterator(Node* node)//:_node(node)//{}////*it////不能传值返回,*it只能传引用返回,因为除了读还有写的功能//const T& operator*()//{//return _node->_data;//}////++it//Self& operator++()//{//_node = _node->_next;//return *this;//}////it++//Self operator++(int)//{//Self tmp(*this);//_node = _node->_next;//return tmp;//}////--it//Self& operator--()//{//_node = _node->_prev;//return *this;//}////it--//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;//}//const T* operator->()//{//return &_node->_data;//}//};template<class T>class list{typedef ListNode<T> Node;public:/*typedef ListIterator<T> iterator;typedef ListConstIterator<T> const_iterator;*/typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;//iterator begin()//{////匿名对象  //return iterator(_head->_next);//}iterator begin(){return _head->_next;}iterator end(){return _head;}//如果返回值类型是const iterator,那表示迭代器本身不能被修改,而不是迭代器指向的内容不能被修改//我们需要的是迭代器指向的内容不能被修改,const iterator不是我们需要的迭代器const_iterator begin()const{return _head->_next;}const_iterator end()const{return _head;}void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_init();}//lt2(lt1)list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}//需要析构,一般就需要自己写深拷贝//不需要析构,一般就不需要自己写深拷贝,默认浅拷贝就可以void swap(list<T> lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list<T>& operator=(list<T> lt)//()里调用了拷贝构造{swap(lt);return *this;}//void push_back(const T& x)//{//Node* newnode = new Node(x);//Node* tail = _head->_prev;//tail->_next = newnode;//newnode->_prev = tail;//newnode->_next = _head;//_head->_prev = newnode;//}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());}void insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);//prev newnode cur newnode->_next = cur;cur->_prev = newnode;prev->_next = newnode;newnode->_prev = prev;_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);}size_t size()const{return _size;}bool empty(){return _size == 0;}//不清除头结点,只是把数据清掉void clear(){iterator it = begin();while (it != end()){it = erase(it);}}~list(){clear();delete _head;_head = nullptr;}private:Node* _head;size_t _size;};}

本文链接:https://www.kjpai.cn/news/2024-04-13/158098.html,文章来源:网络cs,作者:胡椒,版权归作者所有,如需转载请注明来源和作者,否则将追究法律责任!

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。

文章评论