当前位置：首页 > news >正文

【C++/STL】list模拟实现和迭代器失效问题

news 2025/8/11 6:03:03

list是带头双向循环链表
在这里插入图片描述
constructor
list的迭代器失效
即迭代器所指向的节点的无效，即该节点被删除了。因为list底层为带头结点的双向循环链表，所以在list中插入元素时不会导致迭代器失效，只有删除时才会失效，且失效的只是指向被删除节点的迭代器，其他迭代器不会被影响。

#include <iostream>
#include <list>
using namespace std;
void test1()
{int arr[] = { 1,2,3,4,5,6,7,8,9,0 };list<int> lt(arr, arr + sizeof(arr) / sizeof(arr[0]));auto it = lt.begin();while (it != lt.end()){lt.erase(it);//erase函数执行后，it所指向的节点//已被删除，因此it无效，在下一次使用it时，必须先给其赋值。++it;}
}
//改正：
void test2()
{int arr[] = { 1,2,3,4,5,6,7,8,9,0 };list<int> lt(arr, arr + sizeof(arr) / sizeof(arr[0]));auto it = lt.begin();while (it != lt.end()){it = lt.erase(it);//lt.erase(it++);}for (auto e : lt){cout << e << " ";}cout << endl;
}
int main()
{//test1();test2();return 0;
}

在这里插入图片描述

list的模拟实现

#pragma once
#include <iostream>
#include <assert.h>
using namespace std;
namespace Q
{template<class T>struct list_node{list_node<T>* _next;list_node<T>* _prev;T _val;list_node(const T& val = T()):_next(nullptr), _prev(nullptr), _val(val){ }};template<class T,class Ref,class Ptr>struct _list_iterator{typedef list_node<T> Node;typedef _list_iterator<T, 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++(int){self tmp(*this);_node = _node->_next;return tmp;}self& operator--(){_node = _node->_prev;return *this;}self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const self& it) const{return _node != it._node;}bool operator==(const self& it) const{return _node == it._node;}};template<class T>class list{typedef list_node<T> Node;public:typedef _list_iterator<T, T&, T*> iterator;typedef _list_iterator<T, const T&, const T*> const_iterator;iterator begin(){return iterator(_head->_next);}iterator end(){return (iterator)_head;}const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return (const_iterator)_head;//???}void empty_init(){_head = new Node;_head->_prev = _head;_head->_next = _head;_size = 0;}list(){empty_init();}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 clear(){iterator it = begin();while (it != end()){it = erase(it);}_size = 0;}~list(){clear();delete _head;_head = nullptr;}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());}iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;return (iterator)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;--_size;return (iterator)next;}size_t size(){return _size;}private:Node* _head;size_t _size;};void print(const list<int>& lt){list<int>::const_iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;}void test_list1(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);lt.push_back(6);list<int>::iterator it = lt.begin();while (it != lt.end()){(*it) += 1;cout << *it << " ";++it;}cout << endl;for (auto e : lt){cout << e << " ";}cout << endl;}
}