C++——list

目录

前言

一、接口

二、迭代器

 三、模拟实现

1.基本框架

2.迭代器处理

3.迭代器失效问题

4.模拟实现整体代码

list.h

test.cpp

---

前言

        list，其实就是我们C语言数据结构学过的带头双向循环链表，每一个节点都有指向前一个和后一个节点的指针，除头节点外都存储数据。

        list的接口与string和vector的接口很类似，因此博客不再过多演示。

        由于物理结构的差异（内存存储位置不连续），与string和vector不同，list的模拟实现中不能再使用原生指针作为迭代器进行封装，因此本博客的重心会放在list迭代器的实现。

一、接口

        大体上的接口我们在前面的vector和list就已经很熟悉了，由于list的本身特性，库里面增添了remove和sort的接口， remove是删除所有等于value的元素，remove_if是删除所有符合条件的元素，这个判断是否符合条件是需要传仿函数或者函数指针过去的。

仿函数实际是一个类实例化出的对象，通过运算符重载达到的类似函数调用的效果，这个以后会具体写代码来讲解实现，这里给出文档的示例，了解一下即可

另外值得一提的是，由于物理空间上的限制，list的sort效率并不高，我们对list进行排序的时候，也可以考虑先用迭代器构造将其数据转到相应的vector里，再用迭代器构造出一个list存储排序后的数据。 

二、迭代器

由于容器物理空间分布的不同，容器的迭代器可以大致分为三种类型：单向，双向和随机迭代器。

它们之间是继承的关系，继承简单来说就是子类在继承父类原有内容基础上增添了新的功能。

单向迭代器 ：只能++，不能--

双向迭代器：只能++和--，不能+和-

随机迭代器：支持+和-，以及+=，++，-=，--等各种操作

由于list物理结构的原因，它的迭代器只支持++和--，也就是双向迭代器，可以利用对list进行遍历等等操作。

实际上，如果非要支持+和-，也不是不行，但是时间复杂度会是O（N），所以就放弃了这种方式，如果我们需要跳跃多个节点，可以利用while循环让迭代器++或者--。

 三、模拟实现

1.基本框架

list，带头双向链表，实现它自然需要结点（存储当前结点数据以及前后结点位置）和迭代器（具体实现后面会细说），把两者封装起来成list，list的私有成员即为头节点指针和_size，我们每次插入和删除数据都对size进行++或--操作，方便记录结点个数。

namespace muss
{template<class T>struct list_node{T _data;list_node<T>* _next;list_node<T>* _prev;};template<class T>struct list_iterator{};template<class T>class list{public:private:Node* _head;size_t _size;};
}

这是最基本的框架，我们后面会对其进行完善 

2.迭代器处理

        对于迭代器的实现，我们为了让其能实现++，--的遍历操作，我们让封装起来的迭代器储存对应结点的地址，这样方便我们通过它的两个指针来找到前后两个结点。通过运算符重载，实现它的遍历操作，也就是可以实现++和--。

        一个容器的迭代器一般都需要实现两个版本，const和非const，然而我们对其分别进行实现，会发现一个问题，除了一些成员函数的返回值外，其它的部分，这两个迭代器的实现几乎一模一样，这样就出现了很多代码相同但没有很好复用的情况，处理这种情况，库里面是这样做的：

库里面模板传了两个额外的参数作为了返回值，传什么样的模板参数就决定了会实例化除出一个怎样的迭代器版本。其实两种方式生成的迭代器效果是一样的，这是通过模板实现代码复用的一种手段。 

3.迭代器失效问题

list的迭代器失效主要是因为结点的删除导致其对应位置迭代器的失效，由于结点的增加并不会改变其它结点的地址等，所以结点的增加并不会带来迭代器失效的问题。

可以看到，为了支持连续删除，erase会把删除元素的下一个结点的迭代器返回，我们可以利用这个返回值进行连续删除。 

namespace muss
{template<class T>class list{public:iterator 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;return next;}private:Node* _head;size_t _size;};
}

4.模拟实现整体代码

list.h

#pragma once
#include <assert.h>
namespace muss
{template<typename T>struct list_node{typedef list_node<T> node;T _data;node* _prev;node* _next;list_node(const T& data = T()): _data(data), _prev(nullptr), _next(nullptr){}};// 模板参数:        T、                 T&、                T*template<typename T, typename Ref, typename Ptr>struct list_iterator{typedef list_node<T> node;				 // list节点 typedef list_iterator<T, Ref, Ptr> Self; // 迭代器自身类型node* _node;											 // 迭代器遍历的关键:存储节点地址list_iterator(node* node):_node(node){}Ref operator*(){return _node->_data;}// 详细情况在test5，迭代器的->做了特殊处理Ptr operator->(){return &_node->_data;}// 前置++、--Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}// 后置++、--Self& operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self& operator--(int){Self tmp(*this);_node = _node->_next;return tmp;}bool operator==(const Self& it) const{return _node == it._node;}bool operator!=(const Self& it) const{return _node != it._node;}};template<typename T>class list{public:typedef list_node<T> node;typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;// 置空并初始化listvoid empty_initialize(){_head = new node;_head->_prev = _head->_next = _head;_size = 0;}list(){empty_initialize();}// 支持初始化列表初始化list(initializer_list<T> il){empty_initialize();for (auto& e : il){push_back(e);}}list(const list<T>& lt){empty_initialize();for (auto& e : lt){push_back(e);}}~list(){clear();delete _head;_head = nullptr;}// 不能返回引用，因为是中间变量的引用，使不得iterator begin(){// 返回头节点的下一个节点// 最拉跨//node* node = _head->_next;//iterator ret(node);//return ret;// 匿名对象//return iterator(_head->_next);// 强制类型转化return _head->_next;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}bool empty() const{return _head->_next == _head;}size_t size() const{return _size;}iterator insert(iterator it, const T& value = T()){node* newnode = new node(value);node* prev = it._node->_prev;node* next = it._node;prev->_next = newnode;newnode->_prev = prev;next->_prev = newnode;newnode->_next = next;++_size;return newnode;}void push_back(const T& value = T()){insert(end(), value);}void push_front(const T& value = T()){insert(begin(), value);}iterator 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;return next;}void pop_back(){erase(--end());}void pop_front(){erase(begin());}void clear(){auto it = begin();while (it != end()){it = erase(it);}}void swap(list<T>& lt){std::swap(_size, lt._size);std::swap(_head, lt._head);}// l1 =  l2   // 为什么能得到深拷贝：// 传参的时候传值传参，调用自己写的拷贝构造深拷贝// 这里lt和l2无关，交换后，释放lt也就是原来的l1，l1得到lt也就是l2的深拷贝list<T>& operator=(list<T> lt){swap(lt);return *this;}private:node* _head;size_t _size;};template<class Container>void print_container(const Container& con){typename Container::const_iterator it = con.begin();while (it != con.end()){cout << *it << " ";++it;}cout << endl;}void list_test1(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(5);lt.push_back(6);lt.push_back(7);lt.push_back(8);lt.push_back(9);lt.push_back(10);print_container(lt);lt.erase(lt.begin());lt.erase(--lt.end());list<int>::iterator ilt = lt.begin();print_container(lt);ilt++;ilt++;ilt++;ilt++;lt.erase(ilt);print_container(lt);lt.clear();print_container(lt);lt.push_back(1);lt.push_back(2);lt.push_back(3);print_container(lt);lt.empty_initialize();print_container(lt);lt.push_back(1);lt.push_back(2);lt.push_back(3);print_container(lt);}void list_test2(){list<int> l1;list<int> l2;l1.push_back(1);l1.push_back(2);l1.push_back(3);l2.push_back(8);l2.push_back(8);l2.push_back(8);l2.push_back(8);l2.push_back(8);print_container(l1);print_container(l2);swap(l1, l2);print_container(l1);print_container(l2);l2 = l1;print_container(l1);print_container(l2);l1.push_back(123);print_container(l1);print_container(l2);// }void list_test3(){list<string> ls;ls.push_back("abcdefg1");ls.push_back("abcdefg2");ls.push_back("abcdefg3");ls.push_back("abcdefg4");ls.push_back("abcdefg5");ls.push_back("abcdefg6");print_container(ls);ls.push_front("haha");print_container(ls);ls.insert(++ls.begin(), "wohaoshuai");print_container(ls);ls.pop_back();print_container(ls);ls.pop_front();print_container(ls);ls.erase(++(++ls.begin()));print_container(ls);}// =void list_test4(){list<int> l1 = { 1,2,3,4,5 };list<int> l2 = { 5,6,7 };print_container(l1);print_container(l2);l1 = l2;print_container(l1);print_container(l2);l2.push_back(15);print_container(l1);print_container(l2);}struct AA{int a1 = 1;int a2 = 2;};// ->void list_test5(){list<int> l1 = { 1,2,3,4,5 };auto it = l1.begin();//cout << it->// 不能这样，下面那个存struct的地址，struct里面有元素，所以才能访问// 而这里存int的地址，内没有元素，不能访问list<AA> lsa;lsa.push_back(AA());lsa.push_back(AA());lsa.push_back(AA());lsa.push_back(AA());auto ita = lsa.begin();//Ptr operator->()//{//	return &node->_data;//}// 其实是两个箭头，为了可读性而特殊处理了cout << ita->a1 << " " << ita->a2 << endl;cout << ita.operator->()->a1 << " " << ita.operator->()->a2 << endl;}void list_test6(){list<int> l1 = { 1,2,3,4,5 };auto it = l1.begin();++it;auto ret = l1.insert(it, 7);cout << *ret << endl;}
}

test.cpp

#include<iostream>
#include<list>
using namespace std;#include"List.h"int main()
{muss::list_test2();return 0;
}

---

此博客完结~~~~~