C++中list的使用及模拟实现

1list的底层是双向链表结构双向链表中每个元素存储在互不相关的节点中在节点中保存着指向前一个节点和后一个节点的指针。2与forward_list相似forward_list是单链表只能向前迭代。而list是双向链表可以前后迭代。3list与vector相比它的插入和删除元素效率更高不需要遍历一遍原链表。二list的一些基本使用2.1list的构造函数list()//无参构造函数list(size_t n,const value_type val value_type())//n个va的构造list(InputIterator first,InputIterator last)//迭代器区间构造list(const list x)//拷贝构造示例:void Test_List1() { listint lt1; //无参构造值为空 listint lt2(4, 100); //4个100初始化 listint lt3(lt2.begin(), lt2.end()); //迭代器区间构造 listint lt4(lt2); //拷贝构造 }注C11提供了initializer_list的新类型主要用于初始化。用法如下initializer_listint lt { 1,2,3,4,5 }; listint lst(lt); //用lt中的元素初始化lst但一般在写的时候可以使用隐式类型转化listint lt { 1,2,3,4,5 }; //和上面代码一样2.2list的迭代器list提供了双向迭代器可用于遍历和操作容器中的数据。begin()返回指向第一个元素的迭代器。end()返回指向最后一个元素之后位置的迭代器。rbegin()返回指向最后一个元素的逆向迭代器。rend()返回指向第一个元素之前位置的逆向迭代器。代码语言javascriptAI代码解释void Test_List2() { listint myList { 1, 2, 3, 4, 5 }; // 正向迭代器遍历list cout 正向遍历list: ; listint::iterator itr; for (itr myList.begin(); itr ! myList.end(); itr) { cout *itr ; } cout endl; // 逆向迭代器遍历list cout 逆向遍历list: ; listint::reverse_iterator ritr; for (ritr myList.rbegin(); ritr ! myList.rend(); ritr) { cout *ritr ; } cout endl; }运行结果2.3list的插入对于插入操作list实现了如下几个常用的接口push_back(x) //尾插 push_front(x) //头插 insert(iterator it ,x) //在迭代器位置之前插入x示例代码语言javascriptAI代码解释void Test_List3() { listint lt; //尾插 lt.push_back(1); lt.push_back(2); cout push_back:; for (auto e : lt) cout e ; cout endl; //头插 lt.push_front(4); lt.push_front(5); cout push_front:; for (auto e : lt) cout e ; cout endl; //迭代器 lt.insert(lt.begin(), 9); cout insert:; for (auto e : lt) cout e ; cout endl; }运行结果2.4list的删除对于删除list提供的接口如下:pop_back() //尾删 pop_front() //头删 erase(iterator it) //删除it位置 erase(iterator first,iterator last) //删除[first,last)区间示例代码语言javascriptAI代码解释void Test_List4() { listint it { 1,2,3,4,5 }; //尾删 it.pop_back(); cout pop_back:; for (auto e : it) cout e ; cout endl; //头删 it.pop_front(); cout pop_front:; for (auto e : it) cout e ; cout endl; //erase it.erase(it.begin()); it.erase(it.begin(), it.end()); cout erase:; for (auto e : it) cout e ; cout endl; }三list的模拟实现3.1链表节点的定义//定义节点 templateclass T struct list_node { T _data; //存储的数据 list_nodeT* prev;//指向前一个节点 list_nodeT* next;//指向后一个节点 //构造函数 list_node(const T dataT()) :_data(data) ,prev(nullptr) ,next(nullptr) {} };3.2链表主体3.2.1链表的大致轮廓含注释templateclass T class list { public: typedef list_nodeT Node; //构造函数 list() { //当只有一个节点时为了保证满足双向链表的规则 //让新节点的next和prev指针指向自己 _head new Node; _head-_next _head; _head-_prev _head; _size 0; } private: Node* _head; //头节点 size_t _size; //记录数据个数 };3.2.2常见接口的实现插入操作insert(iterator it,T x) ,迭代器前插入void insert(iterator pos, const T x){Node* cur pos._node;Node* prev cur-_prev;Node* newnode new Node(x);//链接前一个指针和后一个指针// prev newnode curnewnode-_next cur;cur-_prev newnode;newnode-_prev prev;prev-_next newnode;_size;}push_back(x尾插。直接开辟一个新节点来存储x的值让新节点链接到链表的最后。注意需要改变头节点和原链表最后一个节点指针的指向。void push_back(const T x) { Node* newnode new Node(x);//开辟新节点存储x Node* tail _head-_prev; //插入之前原链表的尾节点 tail-_next newnode; newnode-_prev tail; newnode-_next _head; _head-_prev newnode; _size; //插入后数据个数 }push_front,头插。这里可以直接复用上面写过的insert逻辑。在迭代器begin() 位置之前插入x也就是头插。当然尾插操作也可以复用void push_front(const T x) { insert(begin(), x); }删除操作erase(iterator it),删除迭代器位置删除之前需要将前一个节点和后一个节点链接起来void erase(iterator pos) { assert(pos ! end()); Node* prev pos._node-_prev; Node* next pos._node-_next; //先将删除位置的前一个节点和后一个节点链接起来 prev-_next next; next-_prev prev; delete pos._node; //释放当前节点 --_size; //数据个数-- }pop_back(),尾删 ,复用erase逻辑。end(),是最后一个节点的下一个位置所以要--void pop_back() { erase(--end()); }pop_front(),头删复用erase逻辑void pop_front() { erase(begin()); }返回链表的数据个数size_t size() const { return _size; }判断链表是否为空bool empty() const { return _size 0; }3.2.3迭代器的实现对于list的迭代器我们用来遍历链表。那么我们需要实现对--*-等操作符的重载同时还需要节点。所以我们需要对链表的节点进行一次封装实现对--*,-等操作符的重载