【C++】list的使用与模拟实现

                                                

🔥个人主页：北辰水墨

🔥专栏：C++学习仓

Alt

本节内容我们来讲解list的使用和模拟实现。 本节难点：list迭代器的模拟实现。

一、list的介绍：

列表
列表是一种序列容器，允许在序列的任何位置进行时间复杂度为O(1)的插入和删除操作，并可在前后两个方向上进行迭代。

列表容器被实现为双向链表；双向链表可以将它们包含的每个元素存储在不同且不相关的存储位置中。通过将每个元素关联到其前面的元素和后面的元素的链接来在内部保持顺序。

它们与forward_list非常相似：主要区别在于forward_list对象是单向链表，因此forward_list对象只能向前迭代，作为交换，forward_list对象相对较小和更高效。

与其他基本标准序列容器（数组，向量和双端队列）相比，列表在已获得迭代器的情况下通常在容器内的任何位置执行插入、提取和移动元素方面表现更好，因此在那些大量使用这些操作的算法（如排序算法）中也表现更好。

与其他序列容器相比，列表和forward_list的主要缺点是它们缺乏通过位置直接访问元素的能力；例如，要访问列表中的第六个元素，需要从已知位置（如开头或结尾）迭代到该位置，这在这两者之间的距离上需要线性时间。它们还会消耗一些额外的内存来保存与每个元素关联的链接信息（对于大量小尺寸元素的大型列表可能是一个重要因素）。

总结：list是一个带头双向循环列表。

二、接口函数：

2.1 构造函数：

 2.1.1 Default constructor (构造一个空的 std::list):
             std::list<int> myList1;    // 创建一个空的整型链表

2.1.2 Fill constructor (构造一个有特定数量元素且每个元素都有相同初始值的 std::list):
            std::list<int> myList2(5, 10); // 创建一个有5个元素的链表，每个元素都初始化为10

2.1.3 Range constructor (从另一个迭代器定义范围的容器中构建 std::list):
            std::vector<int> myVector{1, 2, 3, 4, 5};
            std::list<int> myList3(myVector.begin(), myVector.end()); // 使用vector的范围来初始化链表

2.1.4 Copy constructor (使用另一个 std::list 来构造一个新的 std::list, 是副本):
            std::list<int> myOriginalList{1, 2, 3, 4, 5};
            std::list<int> myList4(myOriginalList); // 使用另一个list来初始化这个新的list

Fill constructor构造函数前面加explicit,表示不能隐式类型转换

2.2 迭代器

 用法保持不变：

#include<iostream>
#include<list>
using namespace std;
int main()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";it++;}cout << endl;list<int>::reverse_iterator rit = lt.rbegin();while (rit != lt.rend()){cout << *rit << " ";rit++;}return 0;
}

2.3 容量操作： 

  • empty检测list是否为空，是返回true，否则返回false
  • size返回有效元素个数的值

2.4 元素访问：

  • front返回list的第一个节点值的引用
  • back返回list的最后一个节点值的引用

 2.5内容操作：

这里大多数函数我们在前面都讲解过，包括头插头删尾插尾删之类的。 

2.5.1 assign

清除原来的数据，再链接新数据（模拟实现原理，先clear（），再push_back() ）

  size的大小会跟着改变。

// list::assign
#include <iostream>
#include <list>int main()
{std::list<int> first;std::list<int> second;first.assign(7, 100);                      // 7 ints with value 100second.assign(first.begin(), first.end()); // a copy of firstint myints[] = { 1776,7,4 };first.assign(myints, myints + 3);            // assigning from arrayfor (auto u : first){std::cout << u << " ";}std::cout << std::endl;std::cout << "Size of first: " << int(first.size()) << '\n';std::cout << std::endl;for (auto u : second){std::cout << u << " ";}std::cout << std::endl;std::cout << "Size of second: " << int(second.size()) << '\n';return 0;
}

2.5.2 

push_front   头插 

push_back   尾插

pop_front   头删

pop_back   尾删

2.5.3  insert

      1. 不会出现迭代器失效：它不像vector那样会有异地扩容，挪动数据，iterator野指针的问题。

      2. 不用it接收返回值：那么it还是指向那个节点的地址。

      3. 用it接收返回值：就指向新添加的首节点的地址

#include <iostream>
#include <list>
#include <vector>int main()
{std::list<int> mylist;std::list<int>::iterator it;// set some initial values:for (int i = 1; i <= 5; ++i) mylist.push_back(i); // 1 2 3 4 5it = mylist.begin();++it;       // it points now to number 2           ^it=mylist.insert(it,3, 10);                       // 1 10 10 10 2 3 4 5用it接收返回值                                     ^mylist.insert(it, 2, 20);                      // 1 20 20 10 10 10 2 3 4 5没有用it接收返回值，还是指向那一块空间                  ^std::cout << "mylist contains:";for (it = mylist.begin(); it != mylist.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';return 0;
}

2.5.4 erase

        在earse时会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不受影响

只需要用it接收earse函数返回值。

返回值为删除元素的下一个节点。

// erasing from list
#include <iostream>
#include <list>int main ()
{std::list<int> mylist;std::list<int>::iterator it1,it2;// set some values:for (int i=1; i<10; ++i) mylist.push_back(i*10);// 10 20 30 40 50 60 70 80 90it1 = it2 = mylist.begin(); // ^^advance (it2,6);            // ^                 ^++it1;                      //    ^              ^it1 = mylist.erase (it1);   // 10 30 40 50 60 70 80 90//    ^           ^it2 = mylist.erase (it2);   // 10 30 40 50 60 80 90//    ^           ^++it1;                      //       ^        ^--it2;                      //       ^     ^mylist.erase (it1,it2);     // 10 30 60 80 90//        ^std::cout << "mylist contains:";for (it1=mylist.begin(); it1!=mylist.end(); ++it1)std::cout << ' ' << *it1;std::cout << '\n';return 0;
}

2.5.5 clear

清除数据，保留 带头节点，size变成0 

2.6  opeations

std::list 提供了一些有用的成员函数，允许执行各种操作，如元素的合并、移除、排序和倒序。下面是这些函数的简要说明和使用示例：

splice: 将元素从一个列表转移到另一个列表，可以转移整个列表、一个单独的元素或一个元素范围。不会执行任何元素的复制或者移动操作，只是在内部节点之间调整指针。

std::list<int> list1 = {1, 2, 3};

std::list<int> list2 = {4, 5, 6};

list1.splice(list1.end(), list2); // 把list2的所有元素移动到list1的末尾 

remove: 从列表中移除所有具有特定值的元素。

 list lt={1,2,3,4,5,3,3,4};

lt.remove(3);// 移除所有值为3的元素     最后为 lt={1,2,4,5,4};

remove_if: 根据一个判断条件移除元素。

 bool ref(const int n)  {return n % 2 == 0; }    //判断条件，偶数为true

 myList.remove_if(ref);       //删除返回值为true的元素

#include <iostream>
#include <list>
bool ref(const int n)
{return n % 2 == 0; 
}int main()
{std::list<int> myList = { 1, 2, 3, 4, 5 };myList.remove_if(ref);for (auto u : myList){std::cout << u << " ";}return 0;
}

unique: 移除连续并且重复的元素，只保留唯一的元素。

必须要是有序的，才可以使用unique函数（底层原理：判断前后元素是否相同） 

#include <iostream>
#include<list>
using namespace std;
int main()
{list<int> lt = {1,5,3,4,5,6,2,3,4,1,5,4,5,6};lt.unique();for (auto u : lt){cout << u << " ";}cout << endl;lt.sort();lt.unique();for (auto u : lt){cout << u << " ";}return 0;
}

一开始无序：不做任何处理 

merge: 合并两个已排序的列表，并确保结果列表也是排序的。

 std::list<int> list1 = {1, 3, 5};

std::list<int> list2 = {2, 4, 6};

list1.merge(list2); // 合并两个列表为1, 2, 3, 4, 5, 6

sort: 对列表中的元素进行排序。它接受一个比较函数作为参数（可选）。

 std::list<int> myList = {4, 3, 5, 2, 1};

myList.sort(); // 排序列表为1, 2, 3, 4, 5

reverse: 反转列表中元素的顺序。

 std::list<int> myList = {1, 2, 3, 4, 5};

myList.reverse(); // 反转后列表为5, 4, 3, 2, 1

三、模拟实现： 

 3.1基本框架：

namespace moon
{template<class T>struct __list_node{T _val;__list_node<T>* prev;__list_node<T>* next;__list_node(const T& x=T()):_val(x),prev(nullptr),next(nullptr){}};template<class T>class list{typedef __list_node<T> Node;public:private:Node* _head;size_t size;};
}

这段代码实现了一个简单双向链表的基础结构。让我们分两部分来解释这个代码： 

1.  namespace moon 命名空间 moon 用于封装代码，避免与其他库中的同名类型或函数冲突。在这个命名空间中，定义了模板类__list_node和模板类list。

2.  模板类__list_node :

        数据的存储是用了T模版类型，还定义了两个指针，分别指向前驱和后继。

        还有一个构造函数，用于在创建模板类__list_node的对象时进行初始化。

        值得注意的是：构造函数的缺省值是T()，调用他自身的构造，如A类，就去调用A本身的构造函数。而内置类型：在C++中也有对应的构造函数。

        是用struct来写的，目的是:允许别人访问我的成员

3.模板类list ：       

  • 类型定义 typedef ListNode<T> Node 是为了简化代码，使得在类 list 中可以直接使用 Node 来指代 ListNode<T>。
  • _head 是一个指向链表头部节点的指针。
  • _size 是一个 size_t 类型的值，用来存储链表的长度（即节点个数）。

  • 用class来写，目的是：封装，保护

  • 成员变量包括：指向头节点的指针 和 存储链表的长度的size

3.2 list的基本函数：

🔥list()

list()
{_head = new Node;_head->prev = _head;_head->next = _head;_size = 0;
}

🔥尾插 push_back（）

void push_back(const T& x)
{Node* NewNode = new Node(x);Node* end = _head->prev;end->next = NewNode;NewNode->prev = end;_head->prev = NewNode;NewNode->next = _head;_size++;
}

我们完成了添加元素的基本操作，那么我们如何遍历它呢？

我们需要用迭代器来遍历，这就是我们本篇文章的重点，迭代器的模拟实现。

3.3迭代器的封装和实现： 

我们来思考一下，原生的指针能不能帮助我们完成迭代器？

1. 链表是随机存储的，让原生指针++，是不会跳到下一个节点。应该对++进行运算符重载。

2. 对原生指针进行解引用，得不到我们需要的节点中的_val。

所以我们需要对迭代器进行封装。 

	template<class T>struct __list_iterator{trpedef __list_node<T> Node;//成员变量Node* _PtrNode;__list_iterator(Node* node):_PtrNode(node){}};

注意：我们的迭代器是在list类中访问的： 

list<int>::iterator it=lt.begin(); 

我们应该在list类中实现嵌套，对__list_node<T>  typedef

template<class T> class list

{

public:

        // 这是一个嵌套类型的别名定义。

        typedef __list_iterator<T> iterator;

        // ...

}; 

list<int>::iterator it = lt.begin(); 这一行涉及到了所谓的嵌套类型或者内嵌类型。

        在C++中，当一个类型（比如 __list_iterator<T>）是在另一个类型的作用域内部定义的（比如 list<T>）时，这个类型被称为嵌套类型。嵌套类型通常用于与外部类型紧密相关联的概念，例如迭代器、节点或其他辅助类。

        这里的 iterator 是 list 类的嵌套类型的别名:

template<class T>
class list {
public:  typedef __list_iterator<T> iterator;
};

        所以当我们在类外部引用它时，我们需要使用类的名称（在这个例子中是 list<int>），后跟两个冒号来限定作用域，然后是别名 iterator。因此 list<int>::iterator 指的是 __list_iterator<int>，它是链接到特定的 list 实例化类型的迭代器类型

        要点是，内嵌类型通常在类定义内部，并且与该类紧密关联。当我们在类外部谈到这些类型时，需要使用类的名称来限定这些类型，就像我们引用 list<int>::iterator  一样。这种设计方式提供了良好的封装和组织结构，在集合和容器类（如 list ）中是一种常见做法

list<int>::iterator it1=lt.begin();vector<int>::iterator it2=v.begin();string::iterator it3=str.begin();

目前所学的：这三者的底层完全不同，但是上层都用法相同，就可以对他们进行遍历。 

 在对应的list vector string类中都对iterator typedef了。其实调用的都是不同的迭代器。

 迭代器就是一个节点的指针，我们这个类的成员就是_PtrNode（节点指针）

	template<class T>struct __list_iterator{trpedef __list_node<T> Node;//成员变量Node* _PtrNode;__list_iterator(Node* node):_PtrNode(node){}};

迭代器与list的联系： 

我们还需要在list类中给__list_iterator类提供两个接口，lt.begin() 和lt.end()

	template<class T>class list{typedef __list_node<T> Node;typedef __list_iterator<T> iterator;public:list(){_head = new Node;_head->prev = _head;_head->next = _head;_size = 0;}iterator begin(){return _head->next;}iterator end(){return _head;}private:Node* _head;size_t _size;};
}

分析代码：
        1. 涉及到隐式类型转换：把_head->next和_head节点指针，隐式转换成迭代器。因为迭代器的构造函数是 __list_iterator(Node* node) 单参数的构造函数。

        2. begin返回第一个数据的迭代器，end返回最后一个数据的下一个位置 

 回到最初的问题，实现迭代器的++和*等操作：

🔥operator++()和operator--()

     这里的++/--，改变指针的位置，挪到下一个/上一个节点。

前置++：

		self& operator++(){_PtrNode = _PtrNode->next;//节点的指针return  *this; // 迭代器}

后置++：

		self& operator++(int){self tmp(*this);_PtrNode=_PtrNode->next;return tmp;}

这里的浅拷贝是不会出现问题的，因为是内置类型，指针类型。就是为了创建一个新的指向那个位置的指针。 

 前置--：

		self& operator--(){_PtrNode = _PtrNode->prev;//节点的指针return  *this; // 迭代器}

后置--：

		self& operator--(int){self tmp(*this);_PtrNode=_PtrNode->prev;return tmp;}

 🔥operator*（）

直接解引用不能得到我们想要的数据，所以我们需要对解引用操作符重载

T& operator*()
{return _PtrNode->_val;
}

  🔥operator!=（）

bool operator!=(self& lt)  //it!=lt.end()
{return _PtrNode != lt._PtrNode;
}

3.4 list函数的完善： 

 又了迭代器，我们就可以完善list函数了。

 🔥insert()

iterator insert(iterator pos,const T& val)
{Node* newnode = new Node(val);//pos是__list_iterator类的一个实例化对象，pos._PtrNode是去取对象中的成员Node* cur = pos._PtrNode;Node* prev = cur->prev;// prev newnode curprev->next = newnode;newnode->prev = prev;cur->prev = newnode;newnode->next = cur;_size++;return newnode;
}

🔥erase()

iterator erase(iterator pos)
{Node* cur = pos._PtrNode;Node* prev = cur->prev;Node* next = cur->next;prev->next = next;next->prev = prev;delete(cur);_size--;return next;  //erase函数返回的是下一个节点的迭代器//同样，这里包括隐式类型转换
}

 🔥拷贝构造

list(const list<T>& lt)//这个函数需要先完成const迭代器才行，const迭代器后面会有模拟实现
{_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;for (auto e : lt)  //通过const迭代器实现{push_back(e);}
}

 🔥赋值重载

void swap(list<T>& lt)
{std::swap(_head, lt._head);std::swap(_size, lt._size);
}// lt3 = lt1
list<int>& operator=(list<int> lt)  //自定义类型传参，调用拷贝构造
{swap(lt);  //交换头节点和_sizereturn *this;  //出了函数，lt会去调用析构函数，顺便把一开始*this中的数据清除
}

1. 传参时：拷贝构造，得到lt

2. 调用自己写的swap函数，把头节点和_size交换

3. 出了函数，lt 调用析构函数

🔥头尾删插

有了insert和erase函数，我们就可以对push_back/push_front/ pop_back/pop_front进行复用

void push_back(const T& val)
{insert(end(), val);
}
void  push_front(const T& val)
{insert(begin(), val);
}
void pop_back()
{erase(--end());  //end()返回的是带头节点
}
void pop_front()
{erase(begin());
}

 🔥与_size相关的函数

//返回_size的大小
size_t size()
{return _size;
}//判断是否为空
bool empty()
{return _size == 0;
}

🔥链表销毁

void clear()
{iterator it = begin();while (it != end()){it = erase(it); //_size在erase函数中会减小}
}
~list()
{clear();delete _head;_head = nullptr;
}

 3.5 进一步完善迭代器：

对于下面的这种类

 struct A{int _a1;int _a2;A(int a1 = 0, int a2 = 0):_a1(a1), _a2(a2){}};

如果list存的是上面的自定义类型呢？

插入有以下几种方法：

void test_list2()
{list<A> lt;A aa1(1, 1);A aa2 = { 1, 1 };lt.push_back(aa1);lt.push_back(aa2);lt.push_back(A(2, 2));lt.push_back({ 3, 3 });lt.push_back({ 4, 4 });  
}

上面代码使用不同方式来创建和插入 A 类型的对象到自定义的 list 容器中。下面是每种方式的详细说明以及它们所涉及的概念：

有名对象的直接插入:

A aa1(1, 1);
lt.push_back(aa1);

这里，首先创建了一个命名对象 aa1，使用了 A 的构造函数 A(int a1, int a2) 并为其提供了两个参数。然后，你将 aa1 作为参数传递给 lt.push_back() 函数。在这种情况下，aa1 是有名对象（也就是说，它有一个名称），并且 push_back 函数接受到的是 aa1 的一个副本

多参数隐式类型转换:

A aa2 = { 1, 1 };
lt.push_back(aa2);

aa2 通过列表初始化的方式被创建。这里的列表初始化允许直接用花括号 {} 来初始化对象。C++11 引入的列表初始化特性可以用来初始化任何对象，包括具有构造函数的对象。创建了 aa2 有名对象并将其插入到列表中

通过构造函数创建匿名对象并插入:

lt.push_back(A(2, 2));

在这里，没有给新创建的 A 对象一个名字，因此它是一个匿名对象（也称作临时对象）。这个匿名的 A 对象是通过调用它的构造函数来直接初始化的，并立即被传递到 push_back 函数中。

通过隐式类型转换创建匿名对象并插入:

lt.push_back({ 3, 3 });

与第三种方式类似，创隐式类型转换建了一个匿名的 A 对象，但这次是通过。初始化时没有使用相应类型的构造函数，而是依赖编译器生成的代码来创建一个具有给定初始化列表的对象，并将其传递给 push_back 函数。

在所有这些情况中，实际插入到 list 容器中的都是 A

现在我们来进行遍历：

list<A>::iterator it = lt.begin();
while (it != lt.end())
{cout<<*it<<" ";++it;
}

 A是自定义类型，不支持留插入，我们解引用得到的_data是A的对象

这里数据是公有的，解引用得到的可以通过.访问符进行访问

cout << (*it)._a1 << ":" << (*it)._a2 << endl;

这种访问方式相当于这种形式：

A* ptr = &aa1;
(*ptr)._a1;

这种指针访问行为十分复杂，我们可以重载一个函数使实现这种访问方式：

ptr->_a1;

在迭代器中重载->运算符

T* operator->()
{
    return &_node->_data;
}

这里返回的是_data的地址

我们就可以这样访问：

cout << it->_a1 << ":" << it->_a2 << endl;

实际上它的访问方式如下：

cout << it.operator->()->_a1 << ":" << it.operator->()->_a2 << endl;

注意：

这里隐藏了一个箭头，一个是重载，一个是原生指针的访问操作

实际上，并不需要在代码中写两次箭头。这是因为在 C++ 中，operator-> 有一个特殊的规则

当重载 operator->，不会直接返回成员的值，而是应该返回一个指针，这个指针指向的对象包含我们想要访问的成员。当使用 ->运算符时，C++ 会自动和透明地调用重载的 operator-> 并继续 “链式” 访问成员，而不需要程序员显示地添加多余的箭头。

这是如何工作的：

1.  如果有一个用户自定义类型的对象（比如迭代器）it，并且我们调用 it->member，编译器会查找这个类型是否有 operator->
2.  如果这个类型有一个 operator-> 的重载，编译器就调用 it.operator->()
3.  it.operator->() 应该返回一个指向对象的指针，这个对象有一个我们尝试访问的 member 成员
4.  编译器取得这个指针，并继续访问 member

这个流程只需要一个 -> 即可。编译器在背后处理了所有操作，直到访问到一个实际对象，然后这个对象的成员可以直接通过 -> 运算符访问

因此，我们不需要手动写成 it->->member；只需写 it->member 即可。编译器会自动将其 “转换” 为 it.operator->()->member

在 ListIterator 示例里，it->_a1 意味着：

1.  调用 it.operator->() 拿到 ListNode 中 _data 成员的地址（这是一个 A 类型的对象）。
2.  使用返回的指针来访问 A 对象的 _a1 成员。

整个过程对于编程者来说是透明的，不需要编写多个 ->。这种处理方式使得重载 -> 可以更自然地使用，就像处理普通的指针一样。

const迭代器

我们上面写的迭代器对于const对象是无法编译成功的，const不能调用非const成员函数

对于const类迭代器，我们需要在list类里面重新增加重载：

typedef _const__list_iterator<T> const_iterator;const_iterator begin() const
{return _head->_next;
}const_iterator end() const
{return _head;
}

这样子我们就有两个版本：iterator 和 const_iterator

    普通对象调用iterator版本     const对象调用iterator版本 

1.  这里的const版本不是对普通迭代器进行const修饰。（想象当我们使用const修饰指针，指针不能移动，指针指向的内容可以修改，不符合我们的预期）

2.  const迭代器是一个重新定义的类型，本身可以修改，指向的内容不可以修改

总结：const_interator 是一个单独的类，我们要实现的是 不能修改数据的（不能改变迭代器指向内容的值），而不是不能移动的迭代器（让迭代器++/--等等操作，这样子就需要能改变迭代器的值）。

方法一：单独再实现一个const_iterator类

	template<class T>struct _const__list_iterator{typedef __list_node<T> Node;typedef _const__list_iterator<T> self;//成员变量Node* _PtrNode;_const__list_iterator(Node* x):_PtrNode(x){}self& operator++(){_PtrNode = _PtrNode->next;//节点的指针return  *this; // 迭代器}self& operator++(int){self tmp(*this);_PtrNode = _PtrNode->next;return tmp;}self& operator--(){_PtrNode = _PtrNode->prev;//节点的指针return  *this; // 迭代器}self& operator--(int){self tmp(*this);_PtrNode = _PtrNode->prev;return tmp;}const T& operator*(){return _PtrNode->_val;}bool operator!=(const self& it)  //it!=lt.end(){return _PtrNode != it._PtrNode;}const T* operator->(){return &_PtrNode->_val;}};

 

 合并两中迭代器：

这里仅仅只是两种返回类型不同，这里我们利用模版来对这里内容进行合并 

	template<class T,class Ref,class Ptr>struct __list_iterator{typedef __list_node<T> Node;typedef __list_iterator<T,Ref,Ptr> self;//成员变量Node* _PtrNode;__list_iterator(Node* x):_PtrNode(x){}Ref operator*(){return _PtrNode->_val;}Ptr operator->(){return &_PtrNode->_val;}self& operator++(){_PtrNode = _PtrNode->next;//节点的指针return  *this; // 迭代器}self& operator++(int){self tmp(*this);_PtrNode=_PtrNode->next;return tmp;}self& operator--(){_PtrNode = _PtrNode->prev;//节点的指针return  *this; // 迭代器}self& operator--(int){self tmp(*this);_PtrNode = _PtrNode->prev;return tmp;}bool operator!=(const self& it)  //it!=lt.end(){return _PtrNode != it._PtrNode;}};

 我们只提取不同的部分，其他部分与原来相同

Ref代表引用，Ptr代表指针

让我们来看一下这个合并后的迭代器的模板参数：

  • T：列表节点存储的数据类型

  • Ref：通过迭代器访问数据时的返回类型，可以是T&或者const T&。

  • Ptr：通过迭代器访问数据的指针类型，可以是T*或者const 

这样，我们可以创建一个常量迭代器，为Ref和Ptr参数指定常量类型，例如：

__list_iterator<T, const T&, const T*> const_iterator;

对于非常量迭代器，就简单地传递非常量类型的引用和指针： 

__list_iterator<T, T&, T*> iterator;

在list类中，我们需要相应地声明两种类型的迭代器：

	template<class 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;list(){_head = new Node;_head->prev = _head;_head->next = _head;_size = 0;}iterator begin(){return _head->next;}iterator end(){return _head;}const_iterator begin() const{return _head->next;}const_iterator end() const{return _head;}iterator insert(iterator pos,const T& val){Node* newnode = new Node(val);Node* cur = pos._PtrNode;//pos是__list_iterator类的一个实例化对象，pos._PtrNode是去取对象中的成员Node* prev = cur->prev;// prev newnode curprev->next = newnode;newnode->prev = prev;cur->prev = newnode;newnode->next = cur;_size++;return newnode;}iterator erase(iterator pos){Node* cur = pos._PtrNode;Node* prev = cur->prev;Node* next = cur->next;prev->next = next;next->prev = prev;delete(cur);_size--;return next;}void push_back(const T& val){insert(end(), val);}void  push_front(const T& val){insert(begin(), val);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}size_t size(){return _size;}bool empty(){return _size == 0;}void clear(){iterator it = begin();while (it != end()){it = erase(it); //_size在erase函数中会减小}}~list(){clear();delete _head;_head = nullptr;}private:Node* _head;size_t _size;};
}

list类中的其他成员函数像begin、end需要按照是否接收常量类型来适配这两种迭代器。 

 list<int>::const_iterator it=lt.begin();

list<int>:: iterator it=lt.begin();

需要在list<int>类里面访问

通过左边的类型，推出右边是用哪一种迭代器。

 模拟实现list的源码，仅供参考，纯手打的代码，可能会有bug，还请各位大佬批评指正。

namespace moon
{template<class T>struct __list_node{T _val;__list_node<T>* prev;__list_node<T>* next;__list_node(const T& x=T()):_val(x),prev(nullptr),next(nullptr){}};template<class T,class Ref,class Ptr>struct __list_iterator{typedef __list_node<T> Node;typedef __list_iterator<T,Ref,Ptr> self;//成员变量Node* _PtrNode;__list_iterator(Node* x):_PtrNode(x){}Ref operator*(){return _PtrNode->_val;}Ptr operator->(){return &_PtrNode->_val;}self& operator++(){_PtrNode = _PtrNode->next;//节点的指针return  *this; // 迭代器}self& operator++(int){self tmp(*this);_PtrNode=_PtrNode->next;return tmp;}self& operator--(){_PtrNode = _PtrNode->prev;//节点的指针return  *this; // 迭代器}self& operator--(int){self tmp(*this);_PtrNode = _PtrNode->prev;return tmp;}bool operator!=(const self& it)  //it!=lt.end(){return _PtrNode != it._PtrNode;}};template<class 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;list(){_head = new Node;_head->prev = _head;_head->next = _head;_size = 0;}iterator begin(){return _head->next;}iterator end(){return _head;}const_iterator begin() const{return _head->next;}const_iterator end() const{return _head;}iterator insert(iterator pos,const T& val){Node* newnode = new Node(val);Node* cur = pos._PtrNode;//pos是__list_iterator类的一个实例化对象，pos._PtrNode是去取对象中的成员Node* prev = cur->prev;// prev newnode curprev->next = newnode;newnode->prev = prev;cur->prev = newnode;newnode->next = cur;_size++;return newnode;}iterator erase(iterator pos){Node* cur = pos._PtrNode;Node* prev = cur->prev;Node* next = cur->next;prev->next = next;next->prev = prev;delete(cur);_size--;return next;}void push_back(const T& val){insert(end(), val);}void  push_front(const T& val){insert(begin(), val);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}size_t size(){return _size;}bool empty(){return _size == 0;}void clear(){iterator it = begin();while (it != end()){it = erase(it); //_size在erase函数中会减小}}~list(){clear();delete _head;_head = nullptr;}private:Node* _head;size_t _size;};
}

 本篇list的使用与模拟实现，纯干货！！！

 

 

 

 

 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://xiahunao.cn/news/3029361.html

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

如何制作微信表情包动图？三步在线制作gif表情包

如何制作微信表情包动图？三步在线制作gif表情包

喜欢使用聊天软件的小伙伴们经常会使用一些有趣动态表情包。当我们想要自己制作gif动画&#xff0c;还不想下载软件的时候要怎么实现呢&#xff1f;很简单&#xff0c;通过使用gif在线制作&#xff08;https://www.gif.cn/&#xff09;网站-GIF中文网&#xff0c;无需下载软件手…
阅读更多...
基于ESP32和ESP8266的物联网开发过程（二）

基于ESP32和ESP8266的物联网开发过程（二）

在做这个项目前&#xff0c;也做了一些调研。项目的初衷是想要用于智能家居。我比较了小米IoT、阿里云、ESPHOME、巴沙云、点灯科技和ONENET等几个平台。最终选择了Onenet&#xff0c;部分原因是之前用过它的多协议版本&#xff0c;但现在这个版本已经下线了。 小米IoT的公测名…
阅读更多...
机器学习的一些知识点

机器学习的一些知识点

、
阅读更多...
Java数据结构(链表实战二)

Java数据结构(链表实战二)

前言 基于链表的操作比较多&#xff0c;希望通过一系列的实战操作&#xff0c;加深对链表的理解和应用。每日更新两题&#xff0c;希望学习的小伙伴关注一波&#xff0c;评论区欢迎讨论交流。 今日份练习 leetcode合并两个有序链表 实现原理 1.先建一个dummy的链表&#x…
阅读更多...
React19学习-初体验

React19学习-初体验

升级react19版本 安装 npm install reactbeta react-dombeta如果使用ts则需要在package.json中添加。等正式版发布直接可以使用types/react了 "overrides": {"types/react": "npm:types-reactbeta","types/react-dom": "npm:ty…
阅读更多...
【LLM 论文】Chain-of-Verification：通过验证链来减少 LLM 幻觉

【LLM 论文】Chain-of-Verification：通过验证链来减少 LLM 幻觉

论文&#xff1a;Chain-of-Verification Reduces Hallucination in Large Language Models ⭐⭐⭐ arXiv:2309.11495 论文速读 LLM 由于不可避免地会产生幻觉&#xff0c;现有的研究主要鼓励 LLM 在产生 response 之前生成内部思想的推理链&#xff0c;或者通过 self-critique…
阅读更多...
PG 全页写

PG 全页写

1.什么是全页写 修改一个块的时候&#xff0c;把块读到内存中&#xff0c;commit后,WAL写进程会触发写&#xff0c;把修改的块写到WAL日志文件&#xff0c;如果再往这个块中插入一条数据&#xff0c;数据缓冲区里面的块有两条数据了&#xff0c;再次commit后&#xff0c;PG会把…
阅读更多...
车载测试系列：自动驾驶中间件SOME/IP

车载测试系列：自动驾驶中间件SOME/IP

一、以太网引入汽车 2004年&#xff0c;宝马汽车的OBD诊断口采用的是高速CAN总线&#xff0c;速率为500kbit/s&#xff0c;除去CAN协议本身的开销&#xff0c;通过OBD口升级控制器的净升级速度降到200kbit/s。预计到2008年&#xff0c;软件更新的数据量会达到1GB&#xff0c;按…
阅读更多...
2024年化学材料、清洁能源与生物技术国际学术会议(ICCMCEB2024)

2024年化学材料、清洁能源与生物技术国际学术会议(ICCMCEB2024)

2024年化学材料、清洁能源与生物技术国际学术会议(ICCMCEB2024) 会议简介 2024国际化学材料、清洁能源和生物技术大会&#xff08;ICCMCEB2024&#xff09;将在长沙隆重举行。本次会议旨在汇聚来自世界各地的化学材料、清洁能源和生物技术领域的专家学者&#xff0c;共同探…
阅读更多...
【计算机毕业设计】springboot合庆镇停车场车位预约系统

【计算机毕业设计】springboot合庆镇停车场车位预约系统

本系统为用户而设计制作合庆镇停车场车位预约系统&#xff0c;旨在实现合庆镇停车场车位预约智能化、现代化管理。本合庆镇停车场车位预约管理自动化系统的开发和研制的最终目的是将合庆镇停车场车位预约的运作模式从手工记录数据转变为网络信息查询管理&#xff0c;从而为现代…
阅读更多...
vue----- watch监听$attrs 的注意事项

vue----- watch监听$attrs 的注意事项

目录 前言 原因分析 解决方案 总结 前言 在 Vue 开发过程中&#xff0c;如遇到祖先组件需要传值到孙子组件时&#xff0c;需要在儿子组件接收 props &#xff0c;然后再传递给孙子组件&#xff0c;通过使用 v-bind"$attrs" 则会带来极大的便利&#xff0c;但同时…
阅读更多...
【进程替换】多进程程序替换原理 | 进程程序替换函数 | execlexecv | execlpexecvp

【进程替换】多进程程序替换原理 | 进程程序替换函数 | execlexecv | execlpexecvp

目录 多进程程序替换 多进程程序替换原理 进程程序替换函数详解 execl&execv execlp&execvp execle&execvpe execve 多进程程序替换 我们想要进程替换的同时不影响旧的进程&#xff08;使用多进程版&#xff09;fork创建子进程&#xff0c;让子进程去替换执…
阅读更多...
大模型在智能客服领域的应用思考

大模型在智能客服领域的应用思考

前言 随着大模型技术的飞速发展，其在商业化应用的落地实践上仍面临着挑战，不论是面向C端用户的付费服务模式，还是面向B端企业的业务赋能策略，目前都尚未形成成熟且清晰的商业模式。 在我所专注的智能客服领域，作为人工智能落地应用的前沿阵地，我深刻感受到大模型的生成…
阅读更多...
面试集中营—Redis面试题

面试集中营—Redis面试题

一、Redis的线程模型 Redis是基于非阻塞的IO复用模型&#xff0c;内部使用文件事件处理器&#xff08;file event handler&#xff09;&#xff0c;这个文件事件处理器是单线程的&#xff0c;所以Redis才叫做单线程的模型&#xff0c;它采用IO多路复用机制同时监听多个socket&a…
阅读更多...
gorm-sharding分表插件升级版

gorm-sharding分表插件升级版

代码地址&#xff1a; GitHub - 137/gorm-sharding: Sharding 是一个高性能的 Gorm 分表中间件。它基于 Conn 层做 SQL 拦截、AST 解析、分表路由、自增主键填充&#xff0c;带来的额外开销极小。对开发者友好、透明&#xff0c;使用上与普通 SQL、Gorm 查询无差别.解决了原生s…
阅读更多...
爬虫学习--5.xpath数据解析

爬虫学习--5.xpath数据解析

xpath是XML路径语言&#xff0c;它可以用来确定xml文档中的元素位置&#xff0c;通过元素路径来完成对元素的查找。HTML就是XML的一种实现方式&#xff0c;所以xpath是一种非常强大的定位方式。 基本概念 XPath&#xff08;XML Path Language&#xff09;是一种XML的查询语言…
阅读更多...
03.进程

03.进程

并发 进程是运行起来的程序&#xff0c;是OS&#xff08;操作系统&#xff09;进行资源分配和调度的基本单位。 当只有一个cpu&#xff0c;进程遇到阻塞事件的时候&#xff08;可能是要去磁盘中读取数据&#xff09;&#xff0c;我们知道cpu的执行速度和磁盘的IO速度相差特别大…
阅读更多...
传感器—超声波雷达

传感器—超声波雷达

声波技术 在讲述超声波雷达之前&#xff0c;先了解一下声波的概念以及超声波和声波之间的关系 什么是声波&#xff1f; 声波是物体机械振动状态&#xff08;或能量&#xff09;的传播形式。所谓振动是指物质的质点在其平衡位置附近进行的往返运动形式&#xff0c;这种振动状…
阅读更多...
2023盘古石晋级赛 移动终端取证 WP

2023盘古石晋级赛 移动终端取证 WP

9. 根据容恨寒的安卓手机分析&#xff0c;MAC的开机密码是[答案&#xff1a;asdcz] 到这里火眼就寄了&#xff0c;盘古石 启动&#xff01; 10. 根据容恨寒的安卓手机分析&#xff0c;苹果手机的备份密码前4位是[答案&#xff1a;1234] 11. 根据魏文茵苹果手机分析&#xff0c…
阅读更多...
找不到vcruntime140_1.dll怎么办，介绍5种简单有效的解决方法

找不到vcruntime140_1.dll怎么办，介绍5种简单有效的解决方法

当您的电脑系统提示找不到vcruntime140_1.dll文件时&#xff0c;这通常意味着系统在尝试运行某个应用程序或游戏时&#xff0c;无法定位到这个至关重要的动态链接库&#xff08;DLL&#xff09;文件。此情况可能源于几个不同的原因&#xff0c;包括但不限于&#xff1a;文件被误…
阅读更多...
最新文章

Copyright @ 2022~2023