• list的简单模拟实现

    文章目录

    目录

    文章目录

    前言

    一、使用list时的注意事项

            1.list不支持std库中的sort排序

    2.去重操作

    3.splice拼接

    二、list的接口实现

            1.源码中的节点

            2.源码中的构造函数

            3.哨兵位头节点

            4.尾插和头插

    5.迭代器*

           5.1 迭代器中的operator++和--

              5.2其他迭代器中的接口

           5.3迭代器类的使用

            5.4 前置后置--

            5.5 list不支持重载+和-

            5.6 operator->

    6.const迭代器

            6.1写俩个类实现const迭代器

            6.2更简洁的const 迭代器

    7.insert插入

    8.erase删除节点

    9.insert和erase的复用

            9.1尾插        

            9.2尾删

            9.3头插

            9.4头删

            10.析构函数

            11.拷贝构造

            12.operator=赋值操作

    13.initializer_list构造

    14.反向迭代器

    前言

            list是带头双向循环链表。是序列容器，允许在序列中的任何位置进行常数时间的插入和删除操作，并且可以在两个方向上进行迭代。list被实现为双向链表；双向链表可以将其包含的每个元素存储在不同且不相关的存储位置中。通过将每个元素与其前面的元素和后面的元素的链接关联起来，可以在内部保持排序。

    一、使用list时的注意事项

            1.list不支持std库中的sort排序

            由于std库中sort内部是快排操作，涉及三数取中操作，需要迭代器可以相减。而由于list不支持迭代器相减操作 ，所以，不能使用std库中的sort排序。因为效率和空间问题，链表的空间不是连续的，实现迭代器相减操作非常影响效率。

            list想要进行排序就要使用它专门提供的操作：

    默认升序：

    1. #include 
    2. using namespace std;
    3. #include 
    4. int main()
    5. {
    6. 	list<int> lt1 = { 9,8,4,2,1,3 };
    7. 	for (auto e : lt1)
    8. 	{
    9. 		cout << e << ' ';
    10. 	}
    11. 	cout << endl;
    12. 	lt1.sort();
    13. 	for (auto e : lt1)
    14. 	{
    15. 		cout << e << ' ';
    16. 	}
    17. 	return 0;
    18. }

    降序：
    使用greater进行排序。也可以直接使用匿名对象（lt1.sort(greater());）。

    1. #include 
    2. using namespace std;
    3. #include 
    4. int main()
    5. {
    6. 	list<int> lt1 = { 9,8,4,2,1,3 };
    7.     //lt1.sort(greater());
    8. 	greater<int> gt;
    9. 	lt1.sort(gt);
    10. 	for (auto e : lt1)
    11. 	{cout << e << ' ';}
    12. 	return 0;
    13. }

    list中的排序是归并排序。在使用如果使用list排序，它的效率较vector的排序效率较低。所以大量数据时不建议使用list 的排序。

    2.去重操作

    操作中的去重是去掉重复的元素，但是前提是要进行排序：

    1. void test_list02()
    2. {
    3. 	list<int> lt1 = { 9,8,4,2,1,3 ,2,1,3};
    4. 	for (auto e : lt1)
    5. 	{cout << e << ' ';}
    6. 	cout << endl;
    7. 	//直接调用去重
    8. 	lt1.unique();
    9. 	for (auto e : lt1)
    10. 	{cout << e << ' ';}
    11. }

    没有进行去重操作无法使得相同元素在一起。调用排序sort：

    3.splice拼接

            实际上就是转移另一个链表中的元素到目标链表的某个位置之前，可以转移一个或者整个链表。

    注意是将另一个链表中的节点直接拿过来，所以另一个链表中的元素在转移之后要去掉。

    也可以将自己的元素转移到自己的某个位置 。

    1. void test_list01()
    2. {
    3. 	list<int> mylist1;
    4. 	for (int i = 1; i <= 4; i++)
    5. 	{
    6. 		mylist1.push_back(i);  // 1 2 3 4
    7. 	}
    8. 	for (auto e : mylist1)
    9. 		cout << e << ' ';
    10. 	cout << endl;
    11. 	auto it = std::find(mylist1.begin(), mylist1.end(), 3);
    12. 	//将3转移到头
    13. 	mylist1.splice(mylist1.begin(), mylist1, it);
    14. 	for (auto e : mylist1)
    15. 		cout << e << ' ';
    16. }

    二、list的接口实现

            1.源码中的节点

            list一般是带头双向循环链表，所以节点的结构是俩个指针：

    源码中用void*指针，在后面使用时都要进行强转成节点类型的指针。

    我们在实现过程中不必这样，直接使用模板定下指针的类型：

    1.  // List的节点类
    2.  template<class T>
    3.  struct ListNode
    4.  {
    5.      ListNode* _prev;
    6.      ListNode* _next;
    7.      T _val;
    8.  };

    再看整个list框架，迭代器刚开始看不懂，往下翻发现有个节点的指针：

    link_type是什么？可以通过vs中ctrl+F功能进行查找，往上翻：

    link_type实际上就是节点的指针。

    1. #pragma once
    2. #include 
    3. using namespace std;
    4.  
    5. namespace mylist
    6. {
    7. 	template<class T>
    8. 	struct ListNode
    9. 	{
    10. 		ListNode* _prev;
    11. 		ListNode* _next;
    12. 		T val;
    13. 	};
    14.  
    15. 	template<class T>
    16. 	class list
    17. 	{
    18. 		typedef ListNode Node;
    19. 	private:
    20. 		Node* _head;
    21. 	};
    22. }

    为什么节点不使用class？原因是因为节点的成员变量和成员函数需要频繁访问，使用public和友元也可以，但是这样实际上和struct一样，并且使用public和友元实际上破坏了封装。

            2.源码中的构造函数

                    empty_initialize()从字面意思上理解就是空节点初始化。

    观察：

    这个函数就是给出哨兵位。

            get_node()函数就是获取节点，观察：

            C++获取节点时，都是从内存池上获取的，内存池就是我们使用空间配置中自己管理的空间。

    使用内存池的好处就是可以更灵活的利用空间，使得代码空间获取效率提高。由于我们初步接触list，所以我们使用new开辟的就好。

             由于内存池的空间是我们自己管理，所以对于自定义类型不能自动的调用构造函数，所以在源码中还有一个creat_node()函数：

            consruct函数调用的是构造函数。对开辟好的内存池进行初始化，也就是定位new的功能。

    这里不是本章重点，仅仅了解一下。

            代码实现很简单：

    1. 		void empty_init()
    2. 		{
    3. 			_head = new Node;
    4. 			_head->_next = _head;
    5. 			_head->_prev = _head;
    6. 		}
    7. 		list()
    8. 		{
    9. 			empty_init();
    10. 		}

            3.哨兵位头节点

           创建节点时，哨兵为的prev和next都应该指向自己：

    1. 	template<class T>
    2. 	class list
    3. 	{
    4. 	public:
    5. 		typedef ListNode Node;
    6. 	public:
    7. 		void empty_init()
    8. 		{
    9. 			_head = new Node;
    10. 			_head->_next = _head;
    11. 			_head->_prev = _head;
    12. 		}
    13. 		list()
    14. 		{
    15. 			empty_init();
    16. 		}
    17. 	private:
    18. 		Node* _head;
    19. 	};

            写到这时我们实例化一个对象观察是否有错误：

    1. void test_mylist01()
    2. {
    3. 	mylist::list<int> lt1;
    4. }

    结果：

            由于节点是一个自定义类型，new在对自定义类型开空间时，需要调用相应的默认构造函数.

    而Node中没有构造函数，所以我们加上默认构造：

    1. 	template<class T>
    2. 	struct ListNode
    3. 	{
    4. 		ListNode* _prev;
    5. 		ListNode* _next;
    6. 		T val;
    7. 		ListNode(const T& data = T())
    8. 			:_prev(nullptr)
    9. 			, _next(nullptr)
    10. 			, val(data) 
    11. 		{}
    12. 	};

            

            4.尾插和头插

            尾插和头插操作源码中调用的是insert()：

            观察insert：

    在迭代器position位置插入x。 

                    先写一个简单的尾插：

    找尾：

    修改指向：

    代码：

    1. void push_back(const T& x)
    2. {
    3. 	//创建新节点然后初始化
    4. 	Node* newnode = new Node(x);
    5. 	//找尾
    6. 	Node* ptail = head->prev;
    7. 	//改变新节点指向
    8. 	newnode->_next = head;
    9. 	newnode->_prev = ptail;
    10. 	//改变head和ptail指向
    11. 	ptail->_next = newnode;
    12. 	head->prev = newnode;
    13. }

    测试代码：

    1. void test_mylist01()
    2. {
    3. 	mylist::list<int> lt1;
    4. 	lt1.push_back(1);
    5. 	lt1.push_back(2);
    6. 	lt1.push_back(3);
    7. }

            结果：

            已经插入了3个节点然后遍历节点？

    遍历节点有很多种方式，最常用的是使用迭代器遍历。接下来我们进入重点。

    5.迭代器*

            链表的迭代器实现与vector和string不同，考虑到没有operator[]，并且不像vector那样空间连续，使用+=比较麻烦，空间不连续。有没有更好的方法？

            迭代器模拟的是指针的行为。

            实际上链表要遍历很简单，因为链表中已经有后继节点和前驱节点了。

            这里不能像vector那样直接typedef一个指针成为迭代器。空间不连续。如何实现一个迭代器，可以实现++到下一个节点、--到前一个节点、解引用*访问节点？

    typedef Node* iterator；无法满足我们的行为。

            我们一般会想到函数重载和重载运算符，那么如何将这些函数封装成一个迭代器？答案是--类。而++和--等运算符对内置类型可以直接使用，但是对于自定义类型我们需要重载，而重载的条件之一就是必须有一个参数是自定义类型，所以迭代器用类封装再好不过了。

    有了类就可以定义迭代器的行为。

    1. template<class T>
    2. class ListIterator
    3. {
    4. 	typedef ListNode Node;
    5.  
    6. 	Node* _node;
    7. };

    由于迭代器实际上是对节点的指针进行操作，所以我们需要指针的成员变量：

    迭代器用节点的指针构造。所以在迭代器中还需要构造函数：

    1. 	template<class T>
    2. 	class ListIterator
    3. 	{
    4. 		typedef ListNode Node;
    5.     	typedef ListIterator Self;//指向迭代器本身的类型重命名
    6.     public:
    7. 		Node* _node;
    8.     public:
    9. 		ListIterator(Node* node)
    10. 			:_node(node)
    11. 		{}
    12. 	};
    13.  
    14. //用迭代器时，要获取指针：
    15.     iterator(节点的指针);

           5.1 迭代器中的operator++和--

            由于++和--的返回值是迭代器，所以在迭代器中还需要一个指向自己的typedef。

    1. 		typedef ListNode Node;
    2. 		typedef ListIterator Self;
    3.     public:
    4. 		Node* _node;
    5.     public:
    6. 		ListIterator(Node* node)
    7. 			:_node(node)
    8. 		{}
    9. 		Self& operator++()
    10. 		{
    11. 			_node = _node->_next;
    12. 			return *this;
    13. 		}
    14. 		Self operator++(int)
    15. 		{
    16. 			Self tmp(*this);
    17. 			_node = _node->_next;
    18. 			return tmp;
    19. 		}

              5.2其他迭代器中的接口

            接下来我们先写出接口，然后进行分析；注意迭代器中构造函数和其他函数应该是公有的。

    1. template<class T>
    2. class ListIterator
    3. {
    4. 	typedef ListNode Node;
    5. 	typedef ListIterator Self;
    6. public:
    7. 	Node* _node;
    8. public:
    9. 	ListIterator(Node* node)
    10. 		:_node(node)
    11. 	{}
    12.  
    13. 	Self& operator++()//前置++
    14. 	{
    15. 		_node = _node->_next;
    16. 		return *this;
    17. 	}
    18. 	Self operator++(int)//后置++
    19. 	{
    20. 		Self tmp(*this);
    21. 		_node = _node->_next;
    22. 		return tmp;
    23. 	}
    24. 	T& operator*()//访问数据
    25. 	{
    26. 		return _node->val;
    27. 	}
    28. 	bool operator!=(const Self& it)//比较节点地址
    29. 	{
    30. 		return _node != it._node;
    31. 	}
    32. };

           5.3迭代器类的使用

            我们可以通过迭代器进行修改数据(operator*),也可以进行比较。

            实现迭代器begin()和end()（迭代器的实例化）：

    1. 	template<class T>
    2. 	class list
    3. 	{
    4. 	public:
    5. 		typedef ListNode Node;
    6. 		typedef ListIterator iterator;
    7. 	public:
    8. 		iterator begin()
    9. 		{
    10. 			return iterator(_head->_next);//匿名对象
    11. 		}
    12. 		iterator end()
    13. 		{
    14. 			return iterator(_head);//末尾就是哨兵位
    15. 		}
    16. //代码....

            使用迭代器遍历链表测试接口：

    1. void test_mylist02()
    2. {
    3. 	mylist::list<int> lt1;
    4. 	lt1.push_back(1);
    5. 	lt1.push_back(2);
    6. 	lt1.push_back(3);
    7. 	lt1.push_back(4);
    8. 	mylist::list<int>::iterator it = lt1.begin();
    9. 	while (it != lt1.end())
    10. 	{
    11. 		cout << *it << ' ';
    12. 		++it;
    13. 	}
    14. }

            代码结果：

    测试前置后置++：

    1. void test_mylist02()
    2. {
    3. 	mylist::list<int> lt1;
    4. 	lt1.push_back(1);
    5. 	lt1.push_back(2);
    6. 	lt1.push_back(3);
    7. 	lt1.push_back(4);
    8. 	//测试前置++
    9. 	mylist::list<int>::iterator it1 = lt1.begin();
    10. 	cout << *(++it1) << endl;
    11. 	cout << *it1 << endl;
    12. 	cout << endl;
    13. 	//测试后置++
    14. 	mylist::list<int>::iterator it2 = lt1.begin();
    15. 	cout << *(it2++) << endl;
    16. 	cout << *it2 << endl;
    17. }

    结果：

            5.4 前置后置--

            和++类似找到前一个节点：

    1. Self& operator--()
    2. {
    3. 	_node = _node->_prev;
    4. 	return *this;
    5. }
    6. Self operator--(int)
    7. {
    8. 	Self tmp(*this);
    9. 	_node = _node->_prev;
    10. 	return tmp;
    11. }

            5.5 list不支持重载+和-

            由于链表的空间地址不连续，重载+和-就需要遍历到n次节点，所以效率不高，标准库中未支持+、-。

            迭代器不需要写析构函数，不需要对节点进行释放。节点的释放应该由list来做。

            5.6 operator->

            标准库中的list不仅仅重载了operator*并且重载了operator->：

            图中operator*的返回值是引用(被typedef了),而operator->的返回值是T*的指针即数据的指针。

    1. T& operator*()
    2. {
    3. 	return _node->val;
    4. }
    5. T* operator->()
    6. {
    7. 	return &_node->val;
    8. }

    为什么要重载->?观察下面代码：
    假设我们需要存储坐标：

    1. void test_mylist03()
    2. {
    3. 	struct Pos
    4. 	{
    5. 		int _row;
    6. 		int _col;
    7. 		Pos(int row = 0, int col = 0)//需要默认构造，节点需要对象的默认构造
    8. 			:_row(row)
    9. 			,_col(col)
    10. 		{}
    11. 	};
    12. 	mylist::list lt1;
    13. 	lt1.push_back(Pos(1, 2));
    14. 	lt1.push_back(Pos(3, 4));
    15. 	lt1.push_back(Pos(5, 6));
    16. 	//迭代器遍历数据
    17. 	mylist::list::iterator it = lt1.begin();
    18. 	while (it != lt1.end())
    19. 	{
    20. 		cout << *it << ' ';//这样是编译不过的
    21. 		++it;
    22. 	}
    23. }

    我们需要访问成员：

    1. 	//迭代器遍历数据
    2. 	mylist::list::iterator it = lt1.begin();
    3. 	while (it != lt1.end())
    4. 	{
    5. 		cout << (*it)._row << ':' << (*it)._col << endl;
    6. 		++it;
    7. 	}

    结果：

    那有不有更便捷的方式？如果是Pos*的数据该怎么访问？

    所以我们重载了operator->：

    1. T* operator->()
    2. {
    3. 	return &_node->val;
    4. }
    5.  
    6.  
    7. 	//迭代器遍历数据
    8. 	mylist::list::iterator it = lt1.begin();
    9. 	while (it != lt1.end())
    10. 	{
    11. 		//cout << (*it)._row << ':' << (*it)._col << endl;
    12. 		cout << it->_row << ':' << it->_col << endl;
    13. 		++it;
    14. 	}

    结果：

    这里就会有疑惑，这个->为什么可以调用成功？在平常使用时不应该需要一个结构体指针才用到 ->吗？

    实际上这就是一个结构体指针调用，由于重载的特性，使用->会直接执行迭代器中我们所写的重载函数operator->().

    在代码中调用了operator->函数，实际上是俩个对头，为了可读性将第二个->省略了：

    6.const迭代器

            6.1写俩个类实现const迭代器

            在访问const链表的时，需要const迭代器，如果使用非const迭代器则会报错：

            const迭代器的作用时可以访问，不可修改。

    不能在我们实现的迭代器前加const修饰：

    所以我们需要自己写一个const迭代器类，如何做到可以遍历，但是不能修改？

    只需要将访问的函数和可以修改的值的函数用const修饰，将迭代器指向的内容修饰即可。

    即将operator*和operator->进行修饰：
            list类中：

    1. 	typedef ListIterator iterator;
    2. 	typedef ConstListIterator const_iterator;

            定义新的const迭代器类模板：

    1. 	template<class T>
    2. 	class ConstListIterator
    3. 	{
    4. 		typedef ListNode Node;
    5. 		typedef ConstListIterator Self;
    6. 	public:
    7. 		Node* _node;
    8.  
    9. 		ConstListIterator(Node* node)
    10. 			:_node(node)
    11. 		{}
    12. 		Self& operator++()
    13. 		{
    14. 			_node = _node->_next;
    15. 			return *this;
    16. 		}
    17. 		Self operator++(int)
    18. 		{
    19. 			Self tmp(*this);
    20. 			_node = _node->_next;
    21. 			return tmp;
    22. 		}
    23. 		Self& operator--()
    24. 		{
    25. 			_node = _node->_prev;
    26. 			return *this;
    27. 		}
    28. 		Self operator--(int)
    29. 		{
    30. 			Self tmp(*this);
    31. 			_node = _node->_prev;
    32. 			return tmp;
    33. 		}
    34. 		const T& operator*()
    35. 		{
    36. 			return _node->val;
    37. 		}
    38. 		const T* operator->()
    39. 		{
    40. 			return &_node->val;
    41. 		}
    42. 		bool operator!=(const Self& it)
    43. 		{
    44. 			return _node != it._node;
    45. 		}
    46. 	};

            list类模板中定义新的迭代器：

    1. typedef ListNode Node;
    2. typedef ListIterator iterator;
    3. typedef ConstListIterator const_iterator;
    4. iterator begin()
    5. {
    6. 	return iterator(_head->_next);//匿名对象
    7. }
    8. const_iterator begin()const
    9. {
    10. 	return const_iterator(_head->_next);//匿名对象
    11. }
    12. iterator end()
    13. {
    14. 	return iterator(_head);//末尾就是哨兵位
    15. }
    16. const_iterator end() const
    17. {
    18. 	return const_iterator(_head);//末尾就是哨兵位
    19. }

    const迭代器：

    观察测试：

    *it不能修改，it可以修改。


    写到这里肯定会觉得写俩个类是不是很重复。能不能像下面这样：

    这样是不行的，因为，迭代器中的所有T类型变为了const T类型，除了operator*和operator->符合我们的预期其他的函数，参数全部改变，那么const对象的迭代器就不能匹配上const迭代器中的其他函数，进而报错。

    如list时，const迭代器中的节点都是const int。

    迭代器中：

    链表中：

    节点的类型都不匹配了。

            6.2更简洁的const 迭代器

            增加俩个模板参数，改变opeartor*和operator->：
    同一个类模板给不同参数，就是不同类型：
            class Ref表示引用，Ptr表示指针。

    1. template<class T,class Ref, class Ptr>
    2. class ListIterator
    3. {
    4. 	typedef ListNode Node;
    5. 	typedef ListIterator Self;
    6. public:
    7. 	Node* _node;
    8.  
    9. 	ListIterator(Node* node)
    10. 		:_node(node)
    11. 	{}
    12. 	Self& operator++()
    13. 	{
    14. 		_node = _node->_next;
    15. 		return *this;
    16. 	}
    17. 	Self operator++(int)
    18. 	{
    19. 		Self tmp(*this);
    20. 		_node = _node->_next;
    21. 		return tmp;
    22. 	}
    23. 	Self& operator--()
    24. 	{
    25. 		_node = _node->_prev;
    26. 		return *this;
    27. 	}
    28. 	Self operator--(int)
    29. 	{
    30. 		Self tmp(*this);
    31. 		_node = _node->_prev;
    32. 		return tmp;
    33. 	}
    34. 	Ref operator*()
    35. 	{
    36. 		return _node->val;
    37. 	}
    38. 	Ptr operator->()
    39. 	{
    40. 		return &_node->val;
    41. 	}
    42. 	bool operator!=(const Self& it)
    43. 	{
    44. 		return _node != it._node;
    45. 	}
    46. };

            list中定义：

    1. 	template<class T>
    2. 	class list
    3. 	{
    4. 	public:
    5. 		typedef ListNode Node;
    6. 		typedef ListIterator iterator;
    7. 		//typedef ConstListIterator const_iterator;
    8. 		typedef ListIteratorconst T&, const T*> const_iterator;

            其实就是写了俩个类，交给编译器完成，让编译器打工。

    俩种写法实际上没有区别，但是，减少了我们的代码量。

    测试：

    1. void Func(const mylist::list<int>& lt)
    2. {
    3. 	mylist::list<int>::const_iterator it = lt.begin();
    4. 	while (it != lt.end())
    5. 	{
    6. 		cout << *it << ' ';
    7. 		++it;
    8. 	}
    9. }
    10. void test_mylist04()
    11. {
    12. 	mylist::list<int> lt1;
    13. 	lt1.push_back(1);
    14. 	lt1.push_back(2);
    15. 	lt1.push_back(3);
    16. 	lt1.push_back(4);
    17. 	Func(lt1);
    18. }

    结果：

            也可以传递俩个模板参数：

    7.insert插入

                    源码插入：

            我们实现一个简单的插入；

    1. 	void insert(iterator pos, const T& x)
    2. 	{
    3. 		//创建新的节点
    4. 		Node* newnode = new Node(x);//新节点
    5. 		Node* cur = pos._node;  //pos节点
    6. 		Node* prev = cur->_prev;//前驱节点
    7. 		newnode->_next = cur;
    8. 		newnode->_prev = cur->_prev;
    9. 		//改变前驱节点的指向
    10. 		//prev newnode cur
    11. 		prev->_next = newnode;
    12. 		cur->_prev = newnode;
    13. 	}

    思考：list中的迭代器有无迭代器失效？

            链表中的迭代器不会失效，因为它的空间不连续。没有扩容这一说法。但是为了和库保持一致，我们和vector一样，给insert一个返回值：

    1. 	iterator insert(iterator pos, const T& x)
    2. 	{
    3.         //代码....
    4. 		return iterator(newnode);
    5. 	}

    测试代码：

    1. void test_mylist05()
    2. {
    3. 	mylist::list<int> lt1;
    4. 	lt1.push_back(1);
    5. 	lt1.push_back(2);
    6. 	lt1.push_back(3);
    7. 	lt1.push_back(4);
    8. 	for (auto e : lt1)
    9. 	{
    10. 		cout << e << ' ';
    11. 	}
    12. 	lt1.insert(lt1.begin(), 5);
    13.     lt1.insert(lt1.end(),6);
    14. 	cout << endl;
    15. 	for (auto e : lt1)
    16. 	{
    17. 		cout << e << ' ';
    18. 	}
    19. }

    结果：

    8.erase删除节点

            改变前继节点和后继节点的指向。

    1. 	#include 
    2.     iterator erase(iterator pos)
    3. 	{
    4.         //不能删除哨兵位
    5.         assert( pos != end());
    6. 		Node* cur = pos._node;
    7. 		Node* prev = cur->_prev;
    8. 		Node* next = cur->_next;
    9. 		//prev cur next
    10. 		prev->_next = next;
    11. 		next->_prev = prev;
    12. 		delete cur;
    13. 		//删除后迭代器失效，因为pos指向的节点已经被释放
    14. 		//需要返回值来获取下一个节点的元素。
    15. 		return iterator(next);
    16. 	}

    由于delete释放了pos位置的节点，所以删除有迭代器失效。我们需要迭代器返回。

    测试：

    1. void test_mylist06()
    2. {
    3. 	mylist::list<int> lt1;
    4. 	lt1.push_back(1);
    5. 	lt1.push_back(2);
    6. 	lt1.push_back(3);
    7. 	lt1.push_back(4);
    8. 	for (auto e : lt1)
    9. 	{
    10. 		cout << e << ' ';
    11. 	}
    12. 	lt1.erase(lt1.begin());
    13. 	cout << endl;
    14. 	for (auto e : lt1)
    15. 	{
    16. 		cout << e << ' ';
    17. 	}
    18. }

    结果：

    9.insert和erase的复用

            9.1尾插        
    1. 	void push_back(const T& x)
    2. 	{
    3. 		创建新节点然后初始化
    4. 		//Node* newnode = new Node(x);
    5. 		找尾
    6. 		//Node* ptail = _head->_prev;
    7. 		改变新节点指向
    8. 		//newnode->_next = _head;
    9. 		//newnode->_prev = ptail;
    10. 		改变head和ptail指向
    11. 		//ptail->_next = newnode;
    12. 		//_head->_prev = newnode;
    13. 		insert(end(), x);
    14. 	}
            9.2尾删
    1. void pop_back()
    2. {
    3. 	insert(--end());
    4. }
            9.3头插
    1. 	void push_front(const T& x)
    2. 	{
    3. 		insert(begin(), x);
    4. 	}
            9.4头删
    1. 	void pop_front()
    2. 	{
    3. 		erase(begin());
    4. 	}

    测试：

    实际上迭代器我们经常要访问它的成员变量和成员函数，所以迭代器也可以写出strcut 的类。

    虽然它公有但是，我们接触的是list而不是迭代器的类模板。

            10.析构函数

            链表的析构需要一个一个节点释放，在观察list等容器的代码会发现，一般的容器都会有一个clear的函数。

            clear函数专门用于清除有效数据的空间，而不清理哨兵位。

    1. void clear()
    2. {
    3. 	auto it = begin();
    4. 	while (it != end())
    5. 	{
    6. 		it = erase(it);
    7. 	}
    8. }

            析构函数在这个函数基础上进行空间释放：

    1. ~list()
    2. {
    3. 	clear();
    4. 	delete _head;
    5. 	_head = nullptr;
    6. }

            11.拷贝构造

            不写拷贝构造编译器会生成一个，该默认生成的拷贝构造是值拷贝即浅拷贝。使用浅拷贝构造的链表，和原链表指向的是一块空间。

    1. void test_mylist08()
    2. {
    3. 	mylist::list<int> lt1;
    4. 	lt1.push_back(1);
    5. 	lt1.push_back(2);
    6. 	lt1.push_back(3);
    7. 	lt1.push_back(4);
    8. 	Func(lt1);
    9. 	mylist::list<int> lt2(lt1);
    10. 	lt1.push_back(5);
    11. 	Func(lt2);
    12. }

    俩个链表指向同一块空间。浅拷贝会有俩个问题：
    1.修改lt1，lt2也会跟着改变。

    2.析构时会对同一块空间进行释放俩次。

            所以我们需要自己写一份深拷贝：

    使用empty_init创建一个新的哨兵位，不指向旧空间。

    1. //lt1(lt2)
    2. list(const list& lt)
    3. {
    4. 	empty_init();
    5. 	for (const auto& e : lt)
    6. 	{
    7. 		push_back(e);
    8. 	}
    9. }

            测试代码：

    1. void Func(const mylist::list<int>& lt)
    2. {
    3. 	mylist::list<int>::const_iterator it = lt.begin();
    4. 	while (it != lt.end())
    5. 	{
    6. 		cout << *it << ' ';
    7. 		++it;
    8. 	}
    9. 	cout << endl;
    10. }
    11. void test_mylist08()
    12. {
    13. 	mylist::list<int> lt1;
    14. 	lt1.push_back(1);
    15. 	lt1.push_back(2);
    16. 	lt1.push_back(3);
    17. 	lt1.push_back(4);
    18. 	Func(lt1);
    19. 	mylist::list<int> lt2(lt1);
    20. 	lt1.push_back(5);
    21. 	Func(lt1);
    22. 	Func(lt2);
    23. }

            结果：

            12.operator=赋值操作

            赋值操作也需要深拷贝，有了拷贝构造，赋值操作就可以使用现代写法：

            函数的参数lt是lt1的一份拷贝，然后将拷贝的空间和lt2进行交换，lt2指向的空间就是lt的空间，最后出函数作用域对lt空间进行释放。

    1. 	list& operator=(list lt)
    2. 	{
    3. 		std::swap(_head, lt._head);
    4. 		return *this;
    5. 	}

    测试代码：

    1. void test_mylist09()
    2. {
    3. 	mylist::list<int> lt1;
    4. 	lt1.push_back(1);
    5. 	lt1.push_back(2);
    6. 	lt1.push_back(3);
    7. 	Func(lt1);
    8. 	mylist::list<int> lt2;
    9. 	lt2.push_back(1);
    10. 	lt2.push_back(2);
    11. 	Func(lt2);
    12. 	lt2 = lt1;
    13. 	Func(lt2);
    14. }

    测试结果：

    13.initializer_list构造

            该构造就是支持{}括号构造：

    1. list(initializer_list il)
    2. {
    3. 	empty_init();
    4. 	for (const auto& e : il)
    5. 	{
    6. 		push_back(e);
    7. 	}
    8. }

            测试代码：

    1. void test_mylist10()
    2. {
    3. 	mylist::list<int> lt1 = { 1,2,3,4,5 };
    4. 	Func(lt1);
    5. }

    14.反向迭代器

            反向迭代器我们需要学会复用iterator：

    1. template 
    2. class list
    3. {
    4. public:
    5.     //反向迭代器
    6.     typedef Reverse_iterator reverse_iterator;
    7.     typedef Reverse_iteratorconst T&, const T*> const_reverse_iterator;
    8.     reverse_iterator rbegin()
    9.     {
    10.     	return reverse_iterator(end());
    11.     }
    12.     const_reverse_iterator rbegin() const
    13.     {
    14.     	return const_reverse_iterator(end());
    15.     }
    16.     reverse_iterator rend()
    17.     {
    18.     	return reverse_iterator(begin());
    19.     }
    20.     const_reverse_iterator rend() const
    21.     {
    22.     	return const_reverse_iterator(begin());
    23.     }
    24.  
    25. };

            反向迭代器就是从后开始往前遍历，那么使用普通迭代器。从最后一个元素到哨兵位。

    1. 	// 适配器 -- 复用
    2. 	template<class Iterator, class Ref, class Ptr>
    3. 	struct Reverse_iterator
    4. 	{
    5. 		typedef Reverse_iterator< Iterator, Ref, Ptr> Self;
    6. 		Iterator _it;
    7. 		
    8. 		Reverse_iterator(const Iterator& it)
    9. 			:_it(it)
    10. 		{}
    11. 		//
    12. 		Self& operator++()
    13. 		{
    14. 			--_it;
    15. 			return *this;
    16. 		}
    17.  
    18. 		Self operator++(int)
    19. 		{
    20. 			Self tmp(*this);
    21. 			_it--;
    22. 			return tmp;
    23. 		}
    24. 		Self& operator--()
    25. 		{
    26. 			++_it;
    27. 			return *this;
    28. 		}
    29.  
    30. 		Self operator--(int)
    31. 		{
    32. 			Self tmp(*this);
    33. 			_it++;
    34. 			return tmp;
    35. 		}
    36. 		Ref operator*()
    37. 		{
    38. 			Iterator tmp(_it);
    39. 			//反向迭代器的rbegin()是正向迭代器end()的--；//有效元素
    40. 			//反向迭代器的rend()是正向迭代器begin()的--;//表示哨兵位位置
    41. 			return *(--tmp);
    42. 		}
    43. 		Ptr operator->()
    44. 		{
    45. 			return  &(operator*());//是访问的地址
    46. 		}
    47. 		bool operator!=(const Self& it)
    48. 		{
    49. 			return _it != it._it;//自定义类型比较所以参数需要成员函数
    50.  
    51. 		}
    52. 	};

    测试代码：

    1. void func(const mylist::list<int>& lt)
    2. {
    3. 	mylist::list<int>::const_reverse_iterator it = lt.rbegin();
    4. 	while (it != lt.rend())
    5. 	{
    6. 		cout << *it << ' ';
    7. 		++it;
    8. 	}
    9. 	cout << endl;
    10. }
    11. void test_mylist11()
    12. {
    13. 	mylist::list<int> lt1 = { 1,2,3,4,5 };
    14. 	func(lt1);
    15. }

    结果：

    三、所有代码：

    1. #pragma once
    2. #include 
    3. using namespace std;
    4. #include 
    5. #include 
    6. #include 
    7. namespace mylist
    8. {
    9. 	template<class T>
    10. 	struct ListNode
    11. 	{
    12. 		ListNode* _prev;
    13. 		ListNode* _next;
    14. 		T val;
    15. 		ListNode(const T& data = T())
    16. 			:_prev(nullptr)
    17. 			, _next(nullptr)
    18. 			, val(data) 
    19. 		{}
    20. 	};
    21. 	template<class T,class Ref, class Ptr>
    22. 	struct ListIterator
    23. 	{
    24. 		typedef ListNode Node;
    25. 		typedef ListIterator Self;
    26. 		Node* _node;
    27. 		ListIterator(Node* node)
    28. 			:_node(node)
    29. 		{}
    30. 		Self& operator++()
    31. 		{
    32. 			_node = _node->_next;
    33. 			return *this;
    34. 		}
    35. 		Self operator++(int)
    36. 		{
    37. 			Self tmp(*this);
    38. 			_node = _node->_next;
    39. 			return tmp;
    40. 		}
    41. 		Self& operator--()
    42. 		{
    43. 			_node = _node->_prev;
    44. 			return *this;
    45. 		}
    46. 		Self operator--(int)
    47. 		{
    48. 			Self tmp(*this);
    49. 			_node = _node->_prev;
    50. 			return tmp;
    51. 		}
    52. 		Ref operator*()
    53. 		{
    54. 			return _node->val;
    55. 		}
    56. 		Ptr operator->()
    57. 		{
    58. 			return &_node->val;
    59. 		}
    60. 		bool operator!=(const Self& it)
    61. 		{
    62. 			return _node != it._node;//内置类型比较
    63. 		}
    64. 	};
    65.  
    66. 	//template
    67. 	//class ConstListIterator
    68. 	//{
    69. 	//	typedef ListNode Node;
    70. 	//	typedef ConstListIterator Self;
    71. 	//	Node* _node;
    72. 	//public:
    73. 	//	ConstListIterator(Node* node)
    74. 	//		:_node(node)
    75. 	//	{}
    76. 	//	Self& operator++()
    77. 	//	{
    78. 	//		_node = _node->_next;
    79. 	//		return *this;
    80. 	//	}
    81. 	//	Self operator++(int)
    82. 	//	{
    83. 	//		Self tmp(*this);
    84. 	//		_node = _node->_next;
    85. 	//		return tmp;
    86. 	//	}
    87. 	//	Self& operator--()
    88. 	//	{
    89. 	//		_node = _node->_prev;
    90. 	//		return *this;
    91. 	//	}
    92. 	//	Self operator--(int)
    93. 	//	{
    94. 	//		Self tmp(*this);
    95. 	//		_node = _node->_prev;
    96. 	//		return tmp;
    97. 	//	}
    98. 	//	const T& operator*()
    99. 	//	{
    100. 	//		return _node->val;
    101. 	//	}
    102. 	//	const T* operator->()
    103. 	//	{
    104. 	//		return &_node->val;
    105. 	//	}
    106. 	//	bool operator!=(const Self& it)
    107. 	//	{
    108. 	//		return _node != it._node;
    109. 	//	}
    110. 	//};
    111. 	
    112. 	// 适配器 -- 复用
    113. 	template<class Iterator, class Ref, class Ptr>
    114. 	struct Reverse_iterator
    115. 	{
    116. 		typedef Reverse_iterator< Iterator, Ref, Ptr> Self;
    117. 		Iterator _it;
    118. 		
    119. 		Reverse_iterator(const Iterator& it)
    120. 			:_it(it)
    121. 		{}
    122. 		//
    123. 		Self& operator++()
    124. 		{
    125. 			--_it;
    126. 			return *this;
    127. 		}
    128.  
    129. 		Self operator++(int)
    130. 		{
    131. 			Self tmp(*this);
    132. 			_it--;
    133. 			return tmp;
    134. 		}
    135. 		Self& operator--()
    136. 		{
    137. 			++_it;
    138. 			return *this;
    139. 		}
    140.  
    141. 		Self operator--(int)
    142. 		{
    143. 			Self tmp(*this);
    144. 			_it++;
    145. 			return tmp;
    146. 		}
    147. 		Ref operator*()
    148. 		{
    149. 			Iterator tmp(_it);
    150. 			//反向迭代器的rbegin()是正向迭代器end()的--；//有效元素
    151. 			//反向迭代器的rend()是正向迭代器begin()的--;//表示哨兵位位置
    152. 			return *(--tmp);
    153. 		}
    154. 		Ptr operator->()
    155. 		{
    156. 			return  &(operator*());//是访问的地址
    157. 		}
    158. 		bool operator!=(const Self& it)
    159. 		{
    160. 			return _it != it._it;//自定义类型比较所以参数需要成员函数
    161.  
    162. 		}
    163. 	};
    164. 	// vector和list反向迭代器实现
    165.  
    166. 	template<class T>
    167. 	class list
    168. 	{
    169. 	public:
    170. 		typedef ListNode Node;
    171. 		//普通迭代器
    172. 		typedef ListIterator iterator;
    173. 		//typedef ConstListIterator const_iterator;
    174. 		typedef ListIteratorconst T&, const T*> const_iterator;
    175. 		iterator begin()
    176. 		{return iterator(_head->_next);//匿名对象
    177. 		}
    178. 		const_iterator begin()const
    179. 		{return const_iterator(_head->_next);//匿名对象
    180. 		}
    181. 		iterator end()
    182. 		{return iterator(_head);//末尾就是哨兵位
    183. 		}
    184. 		const_iterator end() const
    185. 		{return const_iterator(_head);//末尾就是哨兵位
    186. 		}
    187. 		//反向迭代器
    188. 		typedef Reverse_iterator reverse_iterator;
    189. 		typedef Reverse_iteratorconst T&, const T*> const_reverse_iterator;
    190. 		reverse_iterator rbegin()
    191. 		{
    192. 			return reverse_iterator(end());
    193. 		}
    194. 		const_reverse_iterator rbegin() const
    195. 		{
    196. 			return const_reverse_iterator(end());
    197. 		}
    198. 		reverse_iterator rend()
    199. 		{
    200. 			return reverse_iterator(begin());
    201. 		}
    202. 		const_reverse_iterator rend() const
    203. 		{
    204. 			return const_reverse_iterator(begin());
    205. 		}
    206.  
    207. 	public:
    208. 		void empty_init()
    209. 		{
    210. 			_head = new Node;
    211. 			_head->_next = _head;
    212. 			_head->_prev = _head;
    213. 		}
    214. 		list()
    215. 		{ 
    216. 			empty_init();
    217. 		}
    218. 		list(const list& lt)
    219. 		{
    220. 			empty_init();
    221. 			for (const auto& e : lt)
    222. 			{
    223. 				push_back(e);
    224. 			}
    225. 		}
    226. 		list& operator=(list lt)
    227. 		{
    228. 			std::swap(_head, lt._head);
    229. 			return *this;
    230. 		}
    231. 		list(initializer_list il)
    232. 		{
    233. 			empty_init();
    234. 			for (const auto& e : il)
    235. 			{
    236. 				push_back(e);
    237. 			}
    238. 		}
    239. 		~list()
    240. 		{
    241. 			clear();
    242. 			delete _head;
    243. 			_head = nullptr;
    244. 		}
    245. 		void clear()
    246. 		{
    247. 			auto it = begin();
    248. 			while (it != end())
    249. 			{
    250. 				it = erase(it);
    251. 			}
    252. 		}
    253. 		void push_back(const T& x)
    254. 		{
    255. 			创建新节点然后初始化
    256. 			//Node* newnode = new Node(x);
    257. 			找尾
    258. 			//Node* ptail = _head->_prev;
    259. 			改变新节点指向
    260. 			//newnode->_next = _head;
    261. 			//newnode->_prev = ptail;
    262. 			改变head和ptail指向
    263. 			//ptail->_next = newnode;
    264. 			//_head->_prev = newnode;
    265. 			insert(end(), x);
    266. 		}
    267. 		void pop_back()
    268. 		{
    269. 			insert(--end());
    270. 		}
    271. 		void push_front(const T& x)
    272. 		{
    273. 			insert(begin(), x);
    274. 		}
    275. 		void pop_front()
    276. 		{
    277. 			erase(begin());
    278. 		}
    279. 		iterator insert(iterator pos, const T& x)
    280. 		{
    281. 			//创建新的节点
    282. 			Node* newnode = new Node(x);
    283. 			Node* cur = pos._node;
    284. 			Node* prev = cur->_prev;
    285. 			newnode->_next = cur;
    286. 			newnode->_prev = cur->_prev;
    287. 			//改变前驱节点的指向
    288. 			//prev newnode cur
    289. 			prev->_next = newnode;
    290. 			cur->_prev = newnode;
    291. 			return iterator(newnode);
    292. 		}
    293. 		iterator erase(iterator pos)
    294. 		{
    295. 			assert(pos != end());
    296. 			Node* cur = pos._node;
    297. 			Node* prev = cur->_prev;
    298. 			Node* next = cur->_next;
    299. 			//prev cur next
    300. 			prev->_next = next;
    301. 			next->_prev = prev;
    302. 			delete cur;
    303. 			//删除后迭代器失效，因为pos指向的节点已经被释放
    304. 			//需要返回值来获取下一个节点的元素。
    305. 			return iterator(next);
    306. 		}
    307. 	private:
    308. 		Node* _head;
    309. 		};
    310. }

    如果你有所收获，可以留下你的点赞和关注。谢谢你的观看！！！

  • 相关阅读:
    Docker学习笔记(一)安装Docker、镜像操作、容器操作、数据卷操作
    传道授业20年，这是一个老网工的初心
    Java多线程：线程的生命周期的六种状态
    代码随想录1刷—单调栈篇
    和运维工程师聊完，发现小丑竟是我自己
    补知识点：Feign、Nacos配置中心（命名空间、配置分组）
    MaxKey单点登录认证系统v3.5.10GA发布
    docker命令
    基于Java+SpringBoot+vue+element疫情药品采购出入库系统设计实现
    按位异或的应用
  • 原文地址：https://blog.csdn.net/Jk_Mr/article/details/139203078