前言在学习了list容器的基本使用的前提下本文将重点分析容器类的常用接口及其应用实现。一、list的成员变量如图所示list的底层数据结构为双向链表通过下面三个结构体和类实现list①结构体 struct list_node 用来存储链表结点的信息。②结构体struct list_iterator用来封装结点指针使其能够通过重载运算符访问结点。③类 class list 用来实现双向链表的各种增删查改操作1.1 结构体list_nodetemplateclass T struct list_node { //对struct list_node重命名为 Node typedef list_nodeT Node; //链表存储的节点值 T _data; //前驱指针 Node* _prev; //后继指针 Node* _next; };对于双向链表的结点 struct list_node①前驱指针Node* _prev②后继指针Node* _next③链表存储的节点值T _data;温馨提示因为struct list_node过长通过typedef将其重命名为Node。如下图所示1.2 结构体list_iterator//迭代器对结点指针进行封装 templateclass T, class Ref, class Ptr struct list_iterator { //将list_node 结构体类型重命名为Node typedef list_nodeT Node; //将list_iterator 结构体类型重命名为Self typedef list_iterator T, Ref, Ptr Self; //定义结点指针 Node* _pnode; };对于双向链表的迭代器 struct list_iterator①重命名结构体名typedef list_nodeT Node将list_node 结构体类型重命名为Nodetypedef list_iterator T, Ref, Ptr Self将list_iterator 结构体类型重命名为Self②核心成员变量Node* _pnode③模板参数分析templateclass T, class Ref, class Ptr核心目的仅用一个类模板就能同时生成普通迭代器 (iterator) 和常量迭代器 (const_iterator)从而避免代码重复。A.class T含义: 用于接收容器中实际存储的元素类型。作用 用于定义迭代器内部节点的数据类型或者作为某些通用操作的类型推导基础示例 如果你的容器存储的是整数那么T就是int。B.class Ref含义迭代器解引用操作符operator*()的返回类型作用 决定了通过迭代器访问元素时该元素是否可以被修改。示例 对于普通迭代器传入 T允许修改对于常量迭代器传入 const T只读。C. class Ptr含义迭代器箭头操作符 operator-() 的返回类型。作用 决定了通过迭代器访问元素成员时底层指针的属性。示例 对于普通迭代器传入 T*对于常量迭代器传入 const T*。1.3 类class list//链表 templateclass T class list { public: //将list_node 结构体类型重命名为Node typedef list_nodeT Node; //将list_iterator 结构体类型重命名为iterator typedef list_iteratorT, T, T* iterator; //将list_iterator 结构体类型重命名为const_iterator typedef list_iteratorT, const T, const T* const_iterator; private: //哨兵位结点指针 Node* _head; };双向链表class list①重命名结构体名A.typedef list_nodeT Node 将list_node 结构体类型重命名为NodeB. typedef list_iteratorT, T, T* iterator 将list_iterator 结构体类型重命名为iteratorC. typedef list_iteratorT, const T, const T* const_iterator将list_iterator 结构体类型重命名为const_iterator②核心变量 Node* _head哨兵位结点指针二、默认成员函数2.1 list_node的构造函数list_node的默认构造函数//默认构造函数 list_node(const T data T(), Node* prev nullptr, Node* next nullptr) : _data(data) , _prev(prev) , _next(next) {}①const T data T() (数据部分)A. T 是模板类型例如 int 、string...等B. const T表示我们通过常引用来接收数据如果是大型对象比如复杂的结构体传引用可以避免产生昂贵的拷贝开销。const 保证我们在构造时不会意外修改传入的原数据。C. data T()这是默认值。如果你创建节点时不给数据它就会调用类型 T 的默认构造函数。例如 若T 是 int默认就是 0 若T 是指针默认就是空指针。② Node* prev nullptr (前驱指针)③ Node* next nullptr (后继指针)2.2 list_iterator的构造函数list_iterator的默认构造//迭代器的默认构造函数 list_iterator(Node* pnode nullptr) :_pnode(pnode) {}list_iterator的普通构造允许从普通迭代器构造 const 迭代器// 允许从普通迭代器构造 const 迭代器 list_iterator(const list_iteratorT, T, T* it) : _pnode(it._pnode) {}2.3 class list的构造函数list的无参构造templateclass T void listT::CreateHead() { //1.这里会自动调用带有默认参数的构造函数data为T(), prev为nullptr, next为nullptr _head new Node; //2.然后再手动将其构造成一个自循环的结构 _head-_next _head; _head-_prev _head; } //无参构造 list() { CreateHead(); }list的拷贝构造//拷贝构造函数 list(const list lt) { CreateHead(); for (const auto elem : lt) { push_back(elem); } }list的赋值重载templateclass T void listT::swap(listT lt) { std::swap(_head, lt._head); } //赋值重载函数 listT operator(listT lt) { swap(lt); return *this; }list的析构函数//析构函数 ~list() { //释放除哨兵结点以外的结点 clear(); //释放哨兵节点 delete _head; //将哨兵_head指针置空 _head nullptr; }三、list的迭代器3.1 重载运算符*函数原型Ref operator*()函数功能返回迭代器所指向的值函数参数A.如果是普通迭代器Ref 被推导为 T。B.如果是常量迭代器Ref 被推导为 const T。模拟实现指针解引用的功能当我们拿到一个普通指针 int* p 时我们会用 *p 来获取它指向的数据。现在你的迭代器是一个自定义的类class/struct直接对一个类写 *it 编译器是会报错的。这段代码就是告诉编译器“当用户对我的迭代器使用 * 号时你应该去底层节点里把真实的数据拿出来给他。代码实现重载运算符*//运算符重载 Ref operator*() { return _pnode-_data; }功能演示// 假设这是你写代码时的场景 listint::iterator it mylist.begin(); // 场景 1读取数据 cout *it endl; // 发生的事情调用 operator*() - 找到 _pnode - 返回 _data 的引用 - 打印出来 // 场景 2修改数据 (如果 it 是普通迭代器) *it 999; // 发生的事情调用 operator*() - 返回了 _data 的引用 (int) - 将 999 赋值给这个引用 - 节点里的数据真正变成了 9993.2 重载运算符-函数原型Ptr operator-()函数功能返回迭代器所指向的元素的地址函数参数分析A. 如果是普通迭代器Ptr 被推导为 T*你可以通过箭头修改对象的成员。B. 如果是常量迭代器Ptr 被推导为 const T*你只能通过箭头读取成员或者调用 const 成员函数保护了数据的安全。代码实现重载运算符-Ptr operator-() { return (_pnode-_data); }C 中 operator- 的“魔法” (隐藏的二次调用)这是 C 语法中一个非常特殊的设计。假设你链表里存的是一个结构体struct Student { string name; int age; };当你在代码中写下 it-age 时编译器在底层到底做了什么按照字面意思it.operator-() 返回的是一个 Student* 指针那岂不是变成了 (Student*)age这语法不对啊实际上C 编译器对 - 运算符做了特殊处理如果 operator- 返回的是一个指针编译器会自动在后面再加一个隐式的 -。真实的底层转换过程是这样的①编译器看到 it-age。②编译器调用 it.operator-()得到了真实数据的指针Student* p (_pnode-_data)。③编译器自动帮你对这个指针再调用一次箭头变成了 p-age。我们只需要简单地返回数据的地址 (_pnode-_data)用户端用起来就极其自然仿佛迭代器本身就是一个原生指针一样。3.3 重载运算符前置函数原型Self operator()函数功能目的是让迭代器指向下一个节点。函数参数Selftypedef list_iteratorT, Ref, Ptr Self 的别名定义使用 Self 可以避免在返回值中反复写冗长的模板参数。Self既支持了C 的连续调用语法链式操作通过引用返回减少了拷贝的消耗。代码实现重载运算符前置Self operator() { _pnode _pnode-_next; return *this; }3.4 重载运算符后置函数原型Self operator(int)函数功能目的是让迭代器指向下一个节点。函数参数Selftypedef list_iteratorT, Ref, Ptr Self 的别名定义使用 Self 可以避免在返回值中反复写冗长的模板参数。代码实现重载运算符后置Self operator(int) { Self tmp *this; (*this); return tmp; }3.5 重载运算符前置--函数原型Self operator--()函数功能目的是让迭代器指向上一个节点。函数参数Selftypedef list_iteratorT, Ref, Ptr Self 的别名定义使用 Self 可以避免在返回值中反复写冗长的模板参数。Self既支持了C 的连续调用语法链式操作通过引用返回减少了拷贝的消耗。代码实现重载运算符前置--Self operator--() { _pnode _pnode-_prev; return *this; }3.6 重载运算符后置--函数原型Self operator--(int)函数功能目的是让迭代器指向上一个节点。函数参数Selftypedef list_iteratorT, Ref, Ptr Self 的别名定义使用 Self 可以避免在返回值中反复写冗长的模板参数。代码实现重载运算符后置--Self operator--(int) { Self tmp *this; --(*this); return tmp; }3.7 重载运算符!函数原型bool operator!(const Self s)函数功能判断两个迭代器指向的位置是否不同代码实现重载运算符!bool operator!(const Self s) { return _pnode ! s._pnode; }3.8 重载运算符函数原型bool operator(const Self s)函数功能判断两个迭代器指向的位置是否相同代码实现重载运算符bool operator(const Self s) { return _pnode s._pnode; }四、list相关函数操作4.1 begin函数原型① iterator begin();② const_iterator begin() const函数功能返回一个指向 list 中第一个元素的迭代器。代码实现iterator begin() { //指向容器中第一个元素的迭代器 return iterator(_head-_next); //返回匿名对象 } const_iterator begin() const { return const_iterator(_head-_next); //返回匿名对象 }4.2 end函数原型① iterator end();② const_iterator end() const函数功能返回一个指向 vector 容器 中最后一个元素之后的元素。代码实现iterator end() { //指向容器中最后一个元素之后位置的迭代器 return iterator(_head); //返回匿名对象 } const_iterator end() const { return const_iterator(_head); //返回匿名对象 }4.3 insert函数原型templateclass Titerator insert (iterator position, const T val);函数功能容器通过在指定位置之前插入新元素来扩展。代码实现insert函数templateclass T typename listT::iterator listT::insert(iterator pos, const T x) { //申请一个新结点 Node* newnode new Node(x); //pos位置结点指针 Node* cur pos._pnode; newnode-_prev cur-_prev; newnode-_next cur; cur-_prev-_next newnode; cur-_prev newnode; return iterator(newnode); }如下图所示插入一个元素4.4 erase函数原型iterator erase (iterator position);函数功能从 list 容器中删除单个元素位置代码实现 erase函数templateclass T typename listT::iterator listT::erase(iterator pos) { //不能删除哨兵结点 assert(pos._pnode ! _head); //pos位置的结点指针 Node* cur pos._pnode; //pos位置前一个位置的结点指针 Node* prev cur-_prev; //pos位置后一个位置的结点指针 Node* next cur-_next; prev-_next next; next-_prev prev; //cur-_prev-_next cur-_next; //cur-_next-_prev cur-_prev; delete cur; return iterator(next); //通过匿名变量返回下一个位置的结点指针 }如下图所示删除一个元素4.5 push_back函数原型templateclass Tvoid push_back (const T val);函数功能在末尾添加元素代码实现通过复用insert实现尾插元素templateclass T void listT::push_back(const T x) { insert(end(), x); }如下图所示尾插一个元素4.6 push_front函数原型templateclass Tvoid push_front (const T val);函数功能在开头插入元素。代码实现通过复用insert实现头插元素templateclass T void listT::push_front(const T x) { insert(begin(), x); }如下图所示头插一个元素4.7 pop_back函数原型void pop_back();函数功能删除最后一个元素。代码实现通过复用erase函数实现尾删元素templateclass T void listT::pop_back() { erase(--end()); }如下图所示尾删一个元素4.8 pop_front函数原型void pop_front();函数功能在开头删除元素。代码实现复用erase实现头删元素templateclass T void listT::pop_front() { erase(begin()); }如下图所示头删一个元素4.9 clear函数原型void clear();函数功能从 list 容器中移除所有元素这些元素将被销毁使容器的大小变为 0代码实现list 容器中移除所有元素templateclass T void listT::clear() { //it 可能是const_iterator 或则 iterator auto it begin(); while (it ! end()) { // erase 返回的是被删结点的下一个位置所以迭代器不会失效 iterase(it); } }既然看到这里了不妨关注点赞收藏感谢大家若有问题请指正。