list接口总览

namespace qq
{//模拟list中的节点类template<class T>struct ListNode{//成员变量ListNode<T>* _next;ListNode<T>* _prev;T _data;//成员函数ListNode(const T& x = T()):_next(nullptr), _prev(nullptr), _data(x){}};//模拟实现list迭代器template<class T, class Ref, class Ptr>struct ListIterator{typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> self;//成员变量Node* _node;//构造函数ListIterator(Node* node):_node(node){}//各种运算符重载函数Ref operator*();Ptr operator->();self& operator++();		//++itself& operator++(int);	//it++self& operator--();		//--itself& operator--(int);	//it--bool operator!=(const self& it);bool operator==(const self& it);};//模拟实现listtemplate<class T>class list{public:typedef ListNode<T> Node;typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;//list iterator(迭代器)const_iterator begin()const;const_iterator end()const;iterator begin();iterator end();void clear();					//默认成员函数list();list(const list<T>& lt);		list<T>& operator=(list<T> lt);	~list();void empty_init();//list element access(访问容器相关函数)		注意：List不支持operator[]											T& front();const T& front()const;T& back();const T& back()const;// list modifiers(修改)void swap(list<T>& lt);		void push_back(const T& x);void push_front(const T& x);void pop_back();void pop_front();void insert(iterator pos, const T& val);iterator erase(iterator pos);size_t size()const;bool empty()const;private:Node* _head;size_t _size;};
}

在上面的代码中，模拟实现STL std::list 通过三个主要的类进行封装：ListNode，ListIterator，和 list。这样的封装提供了清晰的职责分离，并模仿了 STL 的设计哲学，每个类都具有特定的功能和目的。下面详细解释每个类的作用及其重要性：

1. ListNode
   这个类代表链表的节点。链表是由一系列节点组成，每个节点包含数据和指向链表中前一个节点和后一个节点的指针。在 ListNode 中，成员变量 _next 和 _prev 分别是指向下一个和上一个节点的指针，而 _data 存储节点的值。这种设计允许链表在插入和删除操作中提供高效的性能，因为不需要重新排列整个数据结构，只需要修改指针。

2. ListIterator
   这个类是链表的迭代器，它提供了遍历链表的机制。迭代器是一个重要的抽象，使得链表可以使用类似于数组的方式进行访问和修改。迭代器通过重载操作符（如 ++ 和 --）来前进和后退，通过解引用操作符 (* 和 ->) 来访问节点的数据。通过提供标准迭代器接口，list 类可以与标准算法（如 std::sort, std::find 等）一起工作，增加了其通用性和灵活性。

3. list
   这是一个容器类，提供对链表的高级管理。这个类封装了对链表的所有操作，如添加和删除元素、访问元素、清空列表、获取列表大小等。它使用 ListNode 来存储数据，使用 ListIterator 来提供对元素的迭代访问。此外，list 还负责管理资源，包括节点的创建和销毁，确保程序的正确性和效率。

通过将不同的功能封装在不同的类中，代码更加模块化，易于理解和维护。例如，ListNode 关心节点的表示和链接，ListIterator 关心如何遍历这些节点，而 list 管理整个链表的结构。

---

并且，这里的 list 与之前模拟实现的 vector 和 string 有一些显著的不同。后两者都是在连续的物理空间上进行操作，类似于数组，这使得它们可以通过简单的指针运算快速访问任意位置的元素。相比之下，list 并不是在连续的物理空间中存储数据，而是由一系列分散的节点组成，每个节点通过指针与前一个和后一个节点相连接。

因此，对于 vector 和 string，它们的迭代器基本上是对原生指针的轻量级封装，直接指向元素的存储位置。这使得迭代器可以直接通过指针运算来访问或修改元素，从而提供类似数组的效率。

然而，list 的存储结构要求其迭代器必须能够处理非连续的节点。因此，list 的迭代器不是简单的原生指针，而是一个更复杂的对象，它包含指向当前节点的指针。这种迭代器通过重载 ++ 和 --等操作符来移动到相邻的节点，而不是通过简单的地址运算。此外，迭代器需要通过解引用操作访问节点内部的数据（例如，通过 _data 成员），这进一步区别于基于连续内存存储的容器。

这种设计使得list的插入和删除操作可以在任何位置高效进行，因为这些操作只涉及到指针的重新指向，而不需要移动多个元素。这使得list在需要频繁插入和删除的场景下表现得更优越。然而，这也意味着list在随机访问方面的性能不如基于数组的容器，如 vector 或 string。

结点类的模拟实现

list 在底层来看，他是一个带头双向循环链表，如下图：

所以，一个节点包含三个成员变量前驱指针(_next) 后驱指针 ( _prev) 数据(_data)

成员函数只用提供一个构造函数即可。
而析构函数是因为 ListNode 类中的数据成员决定了是否需要一个显式的析构函数。

1. 简单数据成员：如果 ListNode 的 _data 成员是内置类型（如 int, double, char 等），或者是一些简单的、不需要特殊资源管理的自定义类型（例如不涉及动态内存管理的类），那么编译器生成的默认析构函数足以正确清理 ListNode 对象。在这种情况下，节点的内存管理（创建和销毁节点）由 list 类通过其构造函数和析构函数来处理。

2. 复杂数据成员：如果 _data 成员是一个复杂的类，如那些拥有动态内存分配或其他资源（如文件句柄、网络连接等）的类，则这个类需要自己的析构函数来正确释放这些资源。然而，在 ListNode 类中，即便 _data 是复杂类型，其析构也应由 _data 类型自身负责。ListNode 类本身只需关心其指针成员 _next 和 _prev 的链接关系，而这些成员也不需要特殊的资源释放逻辑。

3. 资源管理：关于 ListNode 的 next 和 prev 指针，它们通常只是指向其他 ListNode 对象，不需要在 ListNode 的析构函数中进行特殊处理。资源的分配和释放（比如 new 和 delete 操作）通常在 list 类的其他成员函数中处理，如插入、删除元素的函数。

总结来说，ListNode 类不需要显式定义析构函数，是因为其成员自动调用它们各自的析构函数，无需额外逻辑来释放资源。list 的析构函数负责遍历所有节点并删除它们，从而管理整个链表的生命周期。

构造函数

结点类的构造函数直接根据所给数据构造一个结点即可，构造出来的结点的数据域存储的就是所给数据，而前驱指针和后继指针均初始化为空指针即可。

//构造函数
ListNode(const T& x = T()):_next(nullptr),_prev(nullptr),_data(x){}

注意：
使用 T() 表示如果在构造 ListNode 对象时没有提供参数，构造函数会自动创建一个 T 类型的临时对象（使用 T 的默认构造函数）。这使得在创建 ListNode 时可以省略参数，构造函数会使用 T 类型的默认值。

迭代器类的模拟实现

template<class T,class Ref,class Ptr>struct ListIterator{typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> self;Node* _node;ListIterator(Node* node):_node(node){}//*itRef operator*(){return _node->_data;}//it->Ptr 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;} };

迭代器类的模板参数说明

为什么我们实现的迭代器类的模板参数有三个参数？

template<class T,class Ref,class Ptr>

在list的模拟实现当中，我们typedef了两个迭代器类型，普通迭代器和const迭代器。

typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T,const T&,const T*> const_iterator;

在 ListIterator 类的模板参数列表中，Ref 和 Ptr 分别指代引用和指针类型。

使用普通迭代器时，编译器会实例化一个普通迭代器对象；而使用常量迭代器时，则会实例化一个常量迭代器对象。

若该迭代器类不设计三个模板参数，将难以有效区分普通迭代器和常量迭代器。

构造函数

//构造函数
ListIterator(Node* node): _node(node)
{}

参数：构造函数接受一个指向 ListNode<T> 类型的指针 node。这个指针指向列表中的一个节点。
功能：构造函数的主要功能是将 _node 成员变量初始化为传入的 node 指针所指向的节点。这样就建立了迭代器与列表节点之间的关联，使得迭代器可以通过指针访问节点的数据。

++运算符的重载

++it 前置递增操作符重载

	//++itself& operator++(){_node = _node->_next;return *this;}

• 功能：这个函数实现了前置递增操作符，即 ++it。它使迭代器向前移动到列表中的下一个节点。
• 操作：将迭代器当前指向的节点 _node指向下一个节点 _next。这样迭代器就指向了列表中的下一个元素。
• 返回值：返回类型为self&，表示返回一个对自身的引用，以支持链式调用。这样可以使得多次操作可以连续执行。

it++ 后置递增操作符重载

	//it++self& operator++(int){self tmp(*this);_node = _node->_next;return tmp;}

• 功能：这个函数实现了后置递增操作符，即 it++。它使迭代器向前移动到列表中的下一个节点，并返回移动前的迭代器。
• 操作：首先，创建一个临时的迭代器 tmp，它是当前迭代器的副本。然后，将当前迭代器指向下一个节点。最后，返回之前创建的临时迭代器 tmp，表示返回移动前的迭代器。
• 返回值：返回类型为 self&，表示返回一个对自身的引用，以支持链式调用。因为后置递增操作符应该返回移动前的迭代器的值，而不是移动后的。

–运算符的重载

–的重载思路与++相类似

//--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;} 

• 功能：这个函数用于比较两个迭代器是否指向相同的节点。
• 参数：参数 const self& it 是另一个迭代器对象，表示要与当前迭代器进行比较的对象。
• 操作：将当前迭代器 _node 指向的节点地址与参数迭代器 it 的 _node 指向的节点地址进行比较。如果它们指向的是同一个节点，则返回 true；否则返回 false。
• 返回值：返回一个布尔值，表示两个迭代器是否相等。如果它们指向相同的节点，则返回 true；否则返回 false。

!=运算符的重载

bool operator!=(const self& it){return _node != it._node;}

• 功能：该函数用于比较两个迭代器是否指向不同的节点。
• 参数：参数 const self& it 是另一个迭代器对象，表示要与当前迭代器进行比较的对象。
• 操作：将当前迭代器 _node 指向的节点地址与参数迭代器 it 的 _node 指向的节点地址进行比较。如果它们指向的不是同一个节点，则返回 true；否则返回 false。
• 返回值：返回一个布尔值，表示两个迭代器是否不相等。如果它们指向不同的节点，则返回 true；否则返回 false。

* 运算符的重载

//*itRef operator*(){return _node->_data;}	

• 功能：这个函数用于返回迭代器当前指向节点的数据。
• 操作：它通过返回 _node->_data，即当前节点的数据，来提供对数据的访问。
• 返回值：返回类型为 Ref，即引用类型，表示返回的是当前节点数据的引用。这样做可以直接操作节点数据，而不需要进行拷贝。

-> 运算符的重载

//it->Ptr operator->(){return &_node->_data;}

• 功能：这个函数用于返回一个指向迭代器当前指向节点数据的指针。
• 操作：它通过返回 &_node->_data，即指向当前节点数据的指针，来提供对数据的访问。
• 返回值：返回类型为 Ptr，即指针类型，表示返回的是当前节点数据的指针。这样做使得我们可以通过指针访问节点的数据成员，例如使用箭头运算符（->）。

---

想想如下场景：
 当list容器当中的每个结点存储的不是内置类型，而是自定义类型，例如日期类，那么当我们拿到一个位置的迭代器时，我们可能会使用->运算符访问Date的成员：

	list<Date> lt;Date d1(2021, 8, 10);Date d2(1980, 4, 3);Date d3(1931, 6, 29);lt.push_back(d1);lt.push_back(d2);lt.push_back(d3);list<Date>::iterator pos = lt.begin();cout << pos->_year << endl; //输出第一个日期的年份

注意： 使用pos->_year这种访问方式时，需要将日期类的成员变量设置为公有。

对于->运算符的重载，我们直接返回结点当中所存储数据的地址即可。

Ptr operator->()
{return &_pnode->_val; //返回结点指针所指结点的数据的地址
}

这里本来是应该有两个->的，第一个箭头是pos ->去调用重载的operator->返回Date* 的指针，第二个箭头是Date* 的指针去访问对象当中的成员变量_year。

但是一个地方出现两个箭头，程序的可读性太差了，所以编译器做了特殊识别处理，为了增加程序的可读性，省略了一个箭头。

list的模拟实现

默认成员函数

构造函数

list是一个带头双向循环链表，在构造一个list对象时，直接申请一个头结点，并让其前驱指针和后继指针都指向自己即可。

//构造函数
list()
{_head = new Node;			 //申请一个头结点_head->_next = _head;		//头结点的后继指针指向自己_head->_prev = _head;		//头结点的前驱指针指向自己_size = 0;					//用于计数，先置为0
}

拷贝构造函数

拷贝构造函数就是根据所给list容器，拷贝构造出一个对象。对于拷贝构造函数，我们先申请一个头结点，并让其前驱指针和后继指针都指向自己，然后将所给容器当中的数据，通过遍历的方式一个个尾插到新构造的容器后面即可。

list(const list<T> &lt){//先申请一个头节点_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;//复用push_back 来对这个节点进行尾插。//这里和vector的拷贝构造类似，不建议使用memcoy，如果是自定义类型数据，则memcpy将会出错。for (auto& e : lt){push_back(e);}}

赋值运算符重载函数

我们这里直接使用现代写法：
这里编译器接收右值的时候自动调用其拷贝构造函数，使用swap()来交换这两个对象，因为值传值传参，故交换的是临时拷贝对象。

list<T>& operator=(list<T> lt)	//编译器接收右值的时候自动调用其拷贝构造函数{swap(lt);	//交换这两个对象return *this;	//支持连续赋值}

析构函数

对对象进行析构时，首先调用clear()函数清理容器当中的数据，然后将头结点释放，最后将头指针置空即可。

//析构函数
~list()
{clear(); //清理容器delete _head; //释放头结点_head = nullptr; //头指针置空
}

list iterator(迭代器)

begin和end

iterator begin()
{//返回使用头结点后一个结点的地址构造出来的普通迭代器return iterator(_head->_next);
}
iterator end()
{//返回使用头结点的地址构造出来的普通迭代器return iterator(_head);
}

重载一对用于const对象的begin函数和end函数。

const_iterator begin() const
{//返回使用头结点后一个结点的地址构造出来的const迭代器return const_iterator(_head->_next);
}
const_iterator end() const
{//返回使用头结点的地址构造出来的普通const迭代器return const_iterator(_head);
}

list element access(访问容器相关函数)

front和back

front和back函数分别用于获取第一个有效数据和最后一个有效数据，因此，实现front和back函数时，直接返回第一个有效数据和最后一个有效数据的引用即可。

T& front()
{return *begin(); //返回第一个有效数据的引用
}
T& back()
{return *(--end()); //返回最后一个有效数据的引用
}

当然，这也需要重载一对用于const对象的front函数和back函数，因为const对象调用front和back函数后所得到的数据不能被修改。

const T& front() const
{return *begin(); //返回第一个有效数据的const引用
}
T& back()
{return *(--end()); //返回最后一个有效数据的引用
}
const T& back() const
{return *(--end()); //返回最后一个有效数据的const引用
}

list modifiers(修改)

insert

insert函数可以在所给迭代器之前插入一个新结点。

这里的逻辑与之前我们用C实现链表数据结构时候的思想差不多，具体看见数据结构 | C语言链表讲解（新手入门）.

void insert(iterator pos, const T& val){ _size++;Node* cur = pos._node;Node* newnode = new Node(val);Node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;}

erase

erase函数可以删除所给迭代器位置的结点。

iterator erase(iterator pos){_size--;Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;return iterator(next);}

push_back和pop_back

push_back和pop_back函数分别用于list的尾插和尾删，在已经实现了insert和erase函数的情况下，我们可以通过复用函数来实现push_back和pop_back函数。

push_back函数就是在头结点前插入结点，而pop_back就是删除头结点的前一个结点。

void push_back(const T& x){insert(end(), x);}

void pop_back(){erase(--end());}

push_front和pop_front

当然，用于头插和头删的push_front和pop_front函数也可以复用insert和erase函数来实现。

push_front函数就是在第一个有效结点前插入结点，而pop_front就是删除第一个有效结点。

void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}

size

_size作为类的成员变量,当每次改变 list 的容量时，_size相应的++ 或者 -- 。

size_t size()const{return _size;}

empty

bool empty()const{return _size == 0;}

swap

swap函数用于交换两个容器，list容器当中存储的实际上就只有链表的头指针，我们将这两个容器当中的头指针交换即可。

void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}

总览

#include<assert.h>
#include<iostream>
namespace qq
{template<class T>struct ListNode{ListNode<T>* _next;ListNode<T>* _prev;T _data;ListNode(const T& x = T()):_next(nullptr),_prev(nullptr),_data(x){}};/*typedef ListIterator<T, T&, T*> iterator;typedef ListConstIterator<T, const T&, const T*> const_iterator;*/template<class T,class Ref,class Ptr>struct ListIterator{typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> self;Node* _node;ListIterator(Node* node):_node(node){}//*itRef operator*(){return _node->_data;}//it->Ptr 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;} };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;const_iterator begin()const{return ListIterator<T, const T&, const T*>(_head->_next);}/*iterator end(){return ListIterator<T>(_head); }*/const_iterator end()const{return _head;}iterator begin(){return ListIterator<T, T&, T*>(_head->_next);}iterator end(){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 clear(){iterator it = begin();while (it != end()){it = erase(it);}}void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}//lt3 = lt1;list<T>& operator=(list<T> lt){swap(lt);return *this;}//需要析构，就需要深拷贝//没有析构，就不用深拷贝~list(){clear();delete _head;_head = nullptr;}/*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;}*/T& front(){return *begin(); //返回第一个有效数据的引用}T& back(){return *(--end()); //返回最后一个有效数据的引用}const T& front() const{return *begin(); //返回第一个有效数据的const引用}T& back(){return *(--end()); //返回最后一个有效数据的引用}const T& back() const{return *(--end()); //返回最后一个有效数据的const引用}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& val){ _size++;Node* cur = pos._node;Node* newnode = new Node(val);Node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;}iterator erase(iterator pos){_size--;Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;return iterator(next);}size_t size()const{return _size;}bool empty()const{return _size == 0;}private:Node* _head;size_t _size;};}