• 进阶C++__STL__容器list使用方法【简单易懂】

    目录

    list构造函数 

    list 赋值和交换

    list 大小操作

    list 插入和删除

    list 数据存取

    list 反转和排序

    list去重与缝合

    unique 去重

    splice 接合

    list删除导致迭代器失效问题

    list代码实现

    模拟实现list类函数接口

    list.h

    test.cpp

    reverse_iterator.h

    list构造函数 

    • list lst; //list采用采用模板类实现,对象的默认构造形式：
    • list(beg,end); //构造函数将[beg, end)区间中的元素拷贝给本身。
    • list(n,elem); //构造函数将n个elem拷贝给本身。
    • list(const list &lst); //拷贝构造函数。
    1. #include
    2. #include 
    3. using namespace std;
    4. #include 
    5.  
    6. void printList(const list<int>& L){
    7. 	for(list<int>::const_iterator it =L.begin();it!=L.end();it++){
    8. 		cout<<*it<<" ";
    9. 	}
    10. 	cout<
    11. }
    12.  
    13. void test01()
    14. {
    15. 	list<int>L1;//默认构造 
    16. 	L1.push_back(10);
    17. 	L1.push_back(20);
    18. 	L1.push_back(30);
    19. 	L1.push_back(40);
    20.  
    21. 	printList(L1);
    22.  
    23. 	list<int>L2(L1.begin(),L1.end());//区间拷贝 
    24. 	printList(L2);
    25.  
    26. 	list<int>L3(L2);//拷贝构造 
    27. 	printList(L3);
    28.  
    29. 	list<int>L4(10, 1000);//构造函数将n个elem拷贝给本身
    30. 	printList(L4);
    31. }
    32.  
    33. int main() {
    34.  
    35. 	test01();
    36.  
    37. 	system("pause");
    38.  
    39. 	return 0;
    40. }
    41.  
    42.

    10 20 30 40
    10 20 30 40
    10 20 30 40
    1000 1000 1000 1000 1000 1000 1000 1000 1000 1000

     list 赋值和交换

    • assign(beg, end); //将[beg, end)区间中的数据拷贝赋值给本身。
    • assign(n, elem); //将n个elem拷贝赋值给本身。
    • list& operator=(const list &lst); //重载等号操作符
    • swap(lst); //将lst与本身的元素互换。

    1. #include
    2. #include 
    3. using namespace std;
    4. #include 
    5.  
    6. void printList(const list<int>& L) {
    7.  
    8. 	for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {
    9. 		cout << *it << " ";
    10. 	}
    11. 	cout << endl;
    12. }
    13.  
    14. //赋值和交换
    15. void test01()
    16. {
    17. 	list<int>L1;
    18. 	L1.push_back(10);
    19. 	L1.push_back(20);
    20. 	L1.push_back(30);
    21. 	L1.push_back(40);
    22. 	printList(L1);
    23.  
    24. 	//赋值
    25. 	list<int>L2;
    26. 	L2 = L1;
    27. 	printList(L2);
    28.  
    29. 	list<int>L3;
    30. 	L3.assign(L2.begin(), L2.end());
    31. 	printList(L3);
    32.  
    33. 	list<int>L4;
    34. 	L4.assign(10, 100);
    35. 	printList(L4);
    36.  
    37. }
    38.  
    39. //交换
    40. void test02()
    41. {
    42.  
    43. 	list<int>L1;
    44. 	L1.push_back(10);
    45. 	L1.push_back(20);
    46. 	L1.push_back(30);
    47. 	L1.push_back(40);
    48.  
    49. 	list<int>L2;
    50. 	L2.assign(10, 100);
    51.  
    52. 	cout << "交换前： " << endl;
    53. 	printList(L1);
    54. 	printList(L2);
    55.  
    56. 	cout << endl;
    57.  
    58. 	L1.swap(L2);
    59.  
    60. 	cout << "交换后： " << endl;
    61. 	printList(L1);
    62. 	printList(L2);
    63.  
    64. }
    65.  
    66. int main() {
    67.  
    68. 	test01();
    69.  
    70. 	test02();
    71.  
    72. 	system("pause");
    73.  
    74. 	return 0;
    75. }

    10 20 30 40
    10 20 30 40
    10 20 30 40
    100 100 100 100 100 100 100 100 100 100
    交换前：
    10 20 30 40
    100 100 100 100 100 100 100 100 100 100

    交换后：
    100 100 100 100 100 100 100 100 100 100
    10 20 30 40

     list 大小操作

    • size(); //返回容器中元素的个数

    • empty(); //判断容器是否为空

    • resize(num); //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。

      ​ //如果容器变短，则末尾超出容器长度的元素被删除。

    1. #include
    2. #include 
    3. using namespace std;
    4. #include 
    5.  
    6. void printList(const list<int>& L) {
    7.  
    8. 	for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {
    9. 		cout << *it << " ";
    10. 	}
    11. 	cout << endl;
    12. }
    13.  
    14. //大小操作
    15. void test01()
    16. {
    17. 	list<int>L1;
    18. 	L1.push_back(10);
    19. 	L1.push_back(20);
    20. 	L1.push_back(30);
    21. 	L1.push_back(40);
    22.  
    23. 	if (L1.empty())
    24. 	{
    25. 		cout << "L1为空" << endl;
    26. 	}
    27. 	else
    28. 	{
    29. 		cout << "L1不为空" << endl;
    30. 		cout << "L1的大小为： " << L1.size() << endl;
    31. 	}
    32.  
    33. 	//重新指定大小
    34. 	L1.resize(10);
    35. 	printList(L1);
    36.  
    37. 	L1.resize(2);
    38. 	printList(L1);
    39. }
    40.  
    41. int main() {
    42.  
    43. 	test01();
    44.  
    45. 	system("pause");
    46.  
    47. 	return 0;
    48. }

    L1不为空
    L1的大小为： 4
    10 20 30 40 0 0 0 0 0 0
    10 20

    list 插入和删除

    • push_back(elem);//在容器尾部加入一个元素
    • pop_back();//删除容器中最后一个元素
    • push_front(elem);//在容器开头插入一个元素
    • pop_front();//从容器开头移除第一个元素
    • insert(pos,elem);//在pos位置插elem元素的拷贝，返回新数据的位置。
    • insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值。
    • insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值。
    • clear();//移除容器的所有数据
    • erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。
    • erase(pos);//删除pos位置的数据，返回下一个数据的位置。
    • remove(elem);//删除容器中所有与elem值匹配的元素。

    1. #include
    2. #include 
    3. using namespace std;
    4. #include 
    5.  
    6. void printList(const list<int>& L) {
    7.  
    8. 	for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {
    9. 		cout << *it << " ";
    10. 	}
    11. 	cout << endl;
    12. }
    13.  
    14. //插入和删除
    15. void test01()
    16. {
    17. 	list<int> L;
    18. 	//尾插
    19. 	L.push_back(10);
    20. 	L.push_back(20);
    21. 	L.push_back(30);
    22. 	//头插
    23. 	L.push_front(100);
    24. 	L.push_front(200);
    25. 	L.push_front(300);
    26.  
    27. 	printList(L);
    28.  
    29. 	//尾删
    30. 	L.pop_back();
    31. 	printList(L);
    32.  
    33. 	//头删
    34. 	L.pop_front();
    35. 	printList(L);
    36.  
    37. 	//插入
    38. 	list<int>::iterator it = L.begin();
    39. 	L.insert(++it, 1000);//链表不可跳跃访问 
    40. 	printList(L);
    41.  
    42. 	//删除
    43. 	it = L.begin();
    44. 	L.erase(++it);
    45. 	printList(L);
    46.  
    47. 	//移除
    48. 	L.push_back(10000);
    49. 	L.push_back(10000);
    50. 	L.push_back(10000);
    51. 	printList(L);
    52. 	L.remove(10000);
    53. 	printList(L);
    54.     
    55.     //清空
    56. 	L.clear();
    57. 	printList(L);
    58. }
    59.  
    60. int main() {
    61.  
    62. 	test01();
    63.  
    64. 	system("pause");
    65.  
    66. 	return 0;
    67. }
    68.

    300 200 100 10 20 30
    300 200 100 10 20
    200 100 10 20
    200 1000 100 10 20
    200 100 10 20
    200 100 10 20 10000 10000 10000
    200 100 10 20
    （清空时打印空字符串）

    list 数据存取

    • front(); //返回第一个元素。
    • back(); //返回最后一个元素。

        cout << L1.at(0) << endl;//错误 不支持at访问数据
        cout << L1[0] << endl; //错误  不支持[]方式访问数据

        list容器的迭代器是双向迭代器，不支持随机访问

        it = it + 1;//错误，不可以跳跃访问，即使是+1

    1. #include
    2. #include 
    3. using namespace std;
    4. #include 
    5.  
    6. //数据存取
    7. void test01()
    8. {
    9. 	list<int>L1;
    10. 	L1.push_back(10);
    11. 	L1.push_back(20);
    12. 	L1.push_back(30);
    13. 	L1.push_back(40);
    14.  
    15. 	
    16. 	//cout << L1.at(0) << endl;//错误 不支持at访问数据
    17. 	//cout << L1[0] << endl; //错误  不支持[]方式访问数据
    18. 	cout << "第一个元素为： " << L1.front() << endl;
    19. 	cout << "最后一个元素为： " << L1.back() << endl;
    20.  
    21. 	//list容器的迭代器是双向迭代器，不支持随机访问
    22. 	list<int>::iterator it = L1.begin();
    23. 	//it = it + 1;//错误，不可以跳跃访问，即使是+1
    24. }
    25.  
    26. int main() {
    27.  
    28. 	test01();
    29.  
    30. 	system("pause");
    31.  
    32. 	return 0;
    33. }
    34.

    第一个元素为： 10
    最后一个元素为： 40

    list 反转和排序

    • reverse(); //反转链表
    • sort(); //链表排序
    1. #include
    2. #include 
    3. using namespace std;
    4. #include 
    5. void printList(const list<int>& L) {
    6.  
    7. 	for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {
    8. 		cout << *it << " ";
    9. 	}
    10. 	cout << endl;
    11. }
    12.  
    13. bool myCompare(int val1 , int val2)
    14. {
    15. 	return val1 > val2;
    16. }
    17.  
    18. //反转和排序
    19. void test01()
    20. {
    21. 	list<int> L;
    22. 	L.push_back(90);
    23. 	L.push_back(30);
    24. 	L.push_back(20);
    25. 	L.push_back(70);
    26. 	printList(L);
    27.  
    28. 	//反转容器的元素
    29. 	L.reverse();
    30. 	printList(L); 
    31. 	//排序
    32. 	L.sort(); //默认的排序规则 从小到大
    33. 	printList(L);
    34.  
    35. 	L.sort(myCompare); //指定规则，从大到小
    36. 	//L.sort(greater());也可以 
    37. 	printList(L);
    38. }
    39.  
    40. int main() {
    41.  
    42. 	test01();
    43.  
    44. 	system("pause");
    45.  
    46. 	return 0;
    47. }

    90 30 20 70
    70 20 30 90
    20 30 70 90
    90 70 30 20

    list去重与缝合

    unique 去重

    去重之前是有要求的，去重之前一定要先排序！如果不排序可能会去不干净。

    1. #include
    2. #include 
    3. using namespace std;
    4. #include 
    5. #include
    6.  
    7. void test11() {
    8. 	list<int> L;
    9. 	L.push_back(2);
    10. 	L.push_back(1);
    11. 	L.push_back(2);
    12. 	L.push_back(1);
    13. 	for (auto e : L) cout << e << " "; cout << endl;
    14.  
    15. 	L.sort(); // 去重前排个序
    16.  
    17. 	cout << "去重后：";
    18. 	L.unique();
    19. 	for (auto e : L) cout << e << " "; cout << endl;
    20. }
    21.  
    22. int main() {
    23.  
    24. 	test11();
    25.  
    26. 	system("pause");
    27.  
    28. 	return 0;
    29. }
    30.  
    31.

    输出：

    2 1 2 1
    去重后：1 2

    splice 接合

    1. #include
    2. #include 
    3. using namespace std;
    4. #include 
    5. #include
    6.  
    7. void test11() {
    8. 	list<int> L1;
    9. 	L1.push_back(1);
    10. 	L1.push_back(2);
    11. 	L1.push_back(3);
    12. 	cout << "L1: ";
    13. 	for (auto e : L1) cout << e << " "; cout << endl;
    14.  
    15. 	list<int> L2;
    16. 	L2.push_back(10);
    17. 	L2.push_back(20);
    18. 	L2.push_back(30);
    19. 	cout << "L2: ";
    20. 	for (auto e : L2) cout << e << " "; cout << endl;
    21.  
    22. 	list<int>::iterator pos = L1.begin();
    23. 	L1.splice(pos, L2);  // 把L2的内容，接到L1的begin()前面
    24. 	cout << "接合后：";
    25. 	for (auto e : L1) cout << e << " "; cout << endl;
    26. }
    27.  
    28. int main() {
    29.  
    30. 	test11();
    31.  
    32. 	system("pause");
    33.  
    34. 	return 0;
    35. }
    36.  
    37.

     输出：

    L1: 1 2 3
    L2: 10 20 30
    接合后：10 20 30 1 2 3

    list删除导致迭代器失效问题

    1. template<typename T>
    2.  
    3. void removeDuplicates(list& aList)
    4.  
    5. {
    6.  
    7. 	T curValue;
    8.  
    9. 	list::iterator cur, p;
    10.  
    11. 	cur = aList.begin();
    12.  
    13. 	while (cur != aList.end())
    14.  
    15. 	{
    16.  
    17. 		curValue = *cur;
    18.  
    19. 		//空白行 1
    20.  
    21. 		while (p != aList.end())
    22.  
    23. 		{
    24.  
    25. 			if (*p == curValue)
    26.  
    27. 			{
    28.  
    29. 				//空白行 2
    30.  
    31. 			}
    32.  
    33. 			else
    34.  
    35. 			{
    36.  
    37. 				p++;
    38.  
    39. 			}
    40.  
    41. 		}
    42.  
    43. 	}
    44.  
    45. }

    A. p=cur+1;aList.erase(p++);

    B.p=++cur; p == cur ? cur = p = aList.erase(p) : p = aList.erase(p);

    C.p=cur+1;aList.erase(p);

    D.p=++cur;aList.erase(p);

    分析：迭代p需要迭代不重复节点的下一节点，重要的是cur迭代器需要往下迭代，因此cur需要往前移动，二答案A C的cur都不会改变，空白行2是当需要找到重复值时进行节点删除，当删除时当前迭代器会失效，因此需要将迭代器p往后迭代，所以答案为 B

    list代码实现

    模拟实现list类函数接口

    1. namespace bite
    2.  
    3. {
    4.  
    5.   // List的节点类
    6.  
    7.   template<class T>
    8.  
    9.   struct ListNode
    10.  
    11.   {
    12.  
    13.     ListNode(const T& val = T());
    14.  
    15.     ListNode* _pPre;
    16.  
    17.     ListNode* _pNext;
    18.  
    19.     T _val;
    20.  
    21.   };
    22.  
    23.  
    24.  
    25.   //List的迭代器类
    26.  
    27.   template<class T, class Ref, class Ptr>
    28.  
    29.   class ListIterator
    30.  
    31.   {
    32.  
    33.     typedef ListNode* PNode;
    34.  
    35.     typedef ListIterator Self;
    36.  
    37.   public:
    38.  
    39.     ListIterator(PNode pNode = nullptr)；
    40.  
    41.     ListIterator(const Self& l)；
    42.  
    43.     T& operator*()；
    44.  
    45.     T* operator->()；
    46.  
    47.     Self& operator++()；
    48.  
    49.     Self operator++(int)；
    50.  
    51.     Self& operator--();
    52.  
    53.     Self& operator--(int);
    54.  
    55.     bool operator!=(const Self& l)；
    56.  
    57.     bool operator==(const Self& l)；
    58.  
    59.   private:
    60.  
    61.     PNode _pNode;
    62.  
    63.   };
    64.  
    65.  
    66.  
    67.   //list类
    68.  
    69.   template<class T>
    70.  
    71.   class list
    72.  
    73.   {
    74.  
    75.     typedef ListNode Node;
    76.  
    77.     typedef Node* PNode;
    78.  
    79.   public:
    80.  
    81.     typedef ListIterator iterator;
    82.  
    83.     typedef ListIteratorconst T&, const T&> const_iterator;
    84.  
    85.   public:
    86.  
    87.     ///
    88.  
    89.     // List的构造
    90.  
    91.     list();
    92.  
    93.     list(int n, const T& value = T());
    94.  
    95.     template <class Iterator>
    96.  
    97.     list(Iterator first, Iterator last);
    98.  
    99.     list(const list& l);
    100.  
    101.     list& operator=(const list l);
    102.  
    103.     ~list();
    104.  
    105.  
    106.  
    107.     ///
    108.  
    109.     // List Iterator
    110.  
    111.     iterator begin();
    112.  
    113.     iterator end();
    114.  
    115.     const_iterator begin();
    116.  
    117.     const_iterator end();
    118.  
    119.  
    120.  
    121.     ///
    122.  
    123.     // List Capacity
    124.  
    125.     size_t size()const;
    126.  
    127.     bool empty()const;
    128.  
    129.  
    130.  
    131.     
    132.  
    133.     // List Access
    134.  
    135.     T& front();
    136.  
    137.     const T& front()const;
    138.  
    139.     T& back();
    140.  
    141.     const T& back()const;
    142.  
    143.  
    144.  
    145.     
    146.  
    147.     // List Modify
    148.  
    149.     void push_back(const T& val){insert(begin(), val);}
    150.  
    151.     void pop_back(){erase(--end());}
    152.  
    153.     void push_front(const T& val){insert(begin(), val);}
    154.  
    155.     void pop_front(){erase(begin());}
    156.  
    157.     // 在pos位置前插入值为val的节点
    158.  
    159.     iterator insert(iterator pos, const T& val);
    160.  
    161.     // 删除pos位置的节点，返回该节点的下一个位置
    162.  
    163.     iterator erase(iterator pos);
    164.  
    165.     void clear();
    166.  
    167.     void swap(List& l);
    168.  
    169.   private:
    170.  
    171.     void CreateHead();
    172.  
    173.     PNode _pHead;
    174.  
    175.   };
    176.  
    177. };

    list.h

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include 
    3. #include 
    4. using namespace std;
    5.  
    6. namespace chaos
    7. {
    8. 	/* 定义结点 */
    9. 	template<class T>
    10. 	struct ListNode {
    11. 		T _data;				  // 用来存放结点的数据
    12. 		ListNode* _next;       // 指向后继结点的指针
    13. 		ListNode* _prev;	      // 指向前驱结点的指针
    14.  
    15. 		ListNode(const T& data = T())   // 全缺省构造（初始化）
    16. 			: _data(data)
    17. 			, _next(nullptr)
    18. 			, _prev(nullptr)
    19. 		{}
    20. 	};
    21.  
    22. 	/* 定义迭代器 */
    23. 	template<class T, class Ref, class Ptr>
    24. 	struct __list_iterator {
    25. 		typedef ListNode Node;
    26. 		typedef __list_iterator self;    // 为了方便我们重命名为self
    27. 		
    28. 		typedef Ref reference;
    29. 		typedef Ptr pointer;
    30.  
    31. 		Node* _node;
    32.  
    33. 		__list_iterator(Node* x)
    34. 			: _node(x) 
    35. 		{}
    36.  
    37. 		/* 解引用 */
    38. 		Ref operator*() {
    39. 			return _node->_data;       // 返回结点的数据
    40. 		}
    41. 		Ptr operator->() {
    42. 			return &_node->_data;     
    43. 		}
    44.  
    45. 		/* ++it */
    46. 		self& operator++() {
    47. 			_node = _node->_next;  // 让 _node 指向下一个结点
    48. 			return *this;  // 返回加加后的值
    49. 		}
    50. 		/* it++ */
    51. 		self operator++(int) {
    52. 			self tmp(*this);   // 拷贝构造一个tmp存储原来的值
    53. 			_node = _node->_next;
    54. 			return tmp;
    55. 		}
    56. 		/* != */
    57. 		bool operator!=(const self& it) {
    58. 			return _node != it._node;  // 它们结点的指针不一样吗？T or F
    59. 		}
    60.  
    61. 		/* --it */
    62. 		self& operator--() {
    63. 			_node = _node->_prev;  
    64. 			return *this;
    65. 		}
    66. 		/* it-- */
    67. 		self operator--(int) {
    68. 			self tmp(*this); 
    69. 			_node = _node->_prev;
    70. 			return tmp;
    71. 		}
    72. 	};
    73.  
    74. 	///* 定义const迭代器 */
    75. 	//template
    76. 	//struct __const_list_iterator {
    77. 	//	typedef ListNode Node;
    78. 	//	Node* _node;
    79.  
    80. 	//	__const_list_iterator(Node* x)
    81. 	//		: _node(x)
    82. 	//	{}
    83. 	//	/* 解引用 */
    84. 	//	const T& operator*() {
    85. 	//		return _node->_data;       // 返回结点的数据
    86. 	//	}
    87. 	//	/* ++it */
    88. 	//	__const_list_iterator& operator++() {
    89. 	//		_node = _node->_next;  // 让 _node 指向下一个结点
    90. 	//		return *this;  // 返回加加后的值
    91. 	//	}
    92. 	//	/* it++ */
    93. 	//	__const_list_iterator operator++(int) {
    94. 	//		__const_list_iterator tmp(*this);   // 拷贝构造一个tmp存储原来的值
    95. 	//		_node = _node->_next;
    96. 	//		return tmp;
    97. 	//	}
    98. 	//	/* != */
    99. 	//	bool operator!=(const __const_list_iterator& it) {
    100. 	//		return _node != it._node;  // 它们结点的指针不一样吗？T or F
    101. 	//	}
    102. 	//	/* --it */
    103. 	//	__const_list_iterator& operator--() {
    104. 	//		_node = _node->_prev;
    105. 	//		return *this;
    106. 	//	}
    107. 	//	/* it-- */
    108. 	//	__const_list_iterator operator--(int) {
    109. 	//		__list_iterator tmp(*this);
    110. 	//		_node = _node->_prev;
    111. 	//		return tmp;
    112. 	//	}
    113. 	//};
    114.  
    115. 	/* 定义链表 */
    116. 	template<class T>
    117. 	class list {
    118. 		typedef ListNode Node;      // 重命名为Node
    119. 	public:
    120. 		/* 迭代器 */
    121. 		typedef __list_iterator iterator;
    122. 		typedef __list_iteratorconst T&, const T*> const_iterator;
    123. 		iterator begin() { 
    124. 			return iterator(_pHead->_next); 
    125. 		}
    126. 		iterator end() { 
    127. 			return iterator(_pHead); 
    128. 		}
    129. 		const_iterator begin() const {
    130. 			return const_iterator(_pHead->_next);  
    131. 		}
    132. 		const_iterator end() const {
    133. 			return const_iterator(_pHead);
    134. 		}
    135.  
    136. 		/* 构造函数：初始化头结点 */
    137. 		list() {
    138. 			_pHead = new Node();
    139. 			_pHead->_next = _pHead;
    140. 			_pHead->_prev = _pHead;
    141. 		}
    142. 		list(size_t n, const T& val = T()) {   // 初始化n个结点
    143. 			_pHead = new Node();
    144. 			_pHead->_next = _pHead;
    145. 			_pHead->_prev = _pHead;
    146. 			for (size_t i = 0; i < n; i++) {
    147. 				push_back(val);
    148. 			}
    149. 		}
    150. 		list(int n, const T& val = T()) {   // 初始化n个结点
    151. 			_pHead = new Node();
    152. 			_pHead->_next = _pHead;
    153. 			_pHead->_prev = _pHead;
    154. 			for (int i = 0; i < n; i++) {
    155. 				push_back(val);
    156. 			}
    157. 		}
    158.  
    159. 		template<class InputIterator> 
    160. 		list(InputIterator first, InputIterator last) {
    161. 			_pHead = new Node();
    162. 			_pHead->_next = _pHead;
    163. 			_pHead->_prev = _pHead;
    164.  
    165. 			while (first != last) {
    166. 				push_back(*first);
    167. 				first++;
    168. 			}
    169. 		}
    170. 		/* 拷贝构造（现代写法）：L2(L1) */
    171. 		list(const list& L) {
    172. 			_pHead = new Node();
    173. 			_pHead->_next = _pHead;
    174. 			_pHead->_prev = _pHead;
    175.  
    176. 			list tmp(L.begin(), L.end());
    177. 			swap(_pHead, tmp._pHead);
    178. 		}
    179.  
    180. 		/* 拷贝构造：L2(L1) */
    181. 		/*list(const list& L) {
    182. 			_pHead = new Node();
    183. 			_pHead->_next = _pHead;
    184. 			_pHead->_prev = _pHead;
    185. 			for (auto e : L) {
    186. 				push_back(e);
    187. 			}
    188. 		}*/
    189.  
    190. 		///* 赋值：L2 = L1 */
    191. 		//list& operator=(list L) {
    192. 		//	if (this != &L) {
    193. 		//		clear();
    194. 		//		for (auto e : L) {
    195. 		//			push_back(e);
    196. 		//		}
    197. 		//	}
    198. 		//	return *this;
    199. 		//}
    200.  
    201.  
    202. 		/* 赋值（现代写法）：L2 = L1 */
    203. 		list& operator=(list L) {
    204. 			swap(_pHead, L._pHead);
    205. 			return *this;
    206. 		}
    207.  
    208.  
    209. 		/* 在pos位置前插入 */
    210. 		void insert(iterator pos, const T& x) {
    211. 			Node* cur = pos._node;     // 找到pos位置的结点
    212. 			Node* cur_prev = cur->_prev;     // 因为要在pos位置前插入，所以要找到当前pos位置的前一个结点
    213. 			Node* new_node = new Node(x);  // 创建新节点
    214.  
    215. 			// 缝合： cur_prev <-> new_node <-> cur
    216. 			cur_prev->_next = new_node;
    217. 			new_node->_prev = cur_prev;
    218. 			new_node->_next = cur;
    219. 			cur->_prev = new_node;
    220. 		}
    221.  
    222. 		/* 尾插：push_back */
    223. 		void push_back(const T& x) {
    224. 			//Node* pTail = _pHead->_prev;     // pHead的前驱就是pTail
    225. 			//Node* new_node = new Node(x);    // 创建新结点（会调用构造，自动创建）
    226. 			//
    227. 			//pTail->_next = new_node;
    228. 			//new_node->_prev = pTail;
    229. 			//new_node->_next = _pHead;
    230. 			//_pHead->_prev = new_node;
    231.  
    232. 			insert(end(), x);   // 在end(头结点)前插入，即尾插
    233. 		}
    234.  
    235. 		/* 头插：push_front */
    236. 		void push_front(const T& x) {
    237. 			insert(begin(), x);  // 在begin（头结点的下一个结点）前插入，即头插
    238. 		}
    239.  
    240.  
    241. 		/* 任意位置删除 */
    242. 		iterator erase(iterator pos) {
    243. 			assert(pos != end());   // 防止头结点被删除
    244.  
    245. 			Node* cur = pos._node;   // 找到pos位置的结点
    246. 			Node* cur_prev = cur->_prev;   // 找到pos的前驱
    247. 			Node* cur_next = cur->_next;   // 找到pos的后继
    248.  
    249. 			// 删除cur
    250. 			delete cur;
    251.  
    252. 			// 缝合：  cur_prev <-> cur(删) <-> cur_next
    253. 			cur_prev->_next = cur_next;
    254. 			cur_next->_prev = cur_prev;
    255.  
    256. 			return iterator(cur_next);
    257. 		}
    258.  
    259. 		/* 尾删 */
    260. 		void pop_back() {
    261. 			erase(--end());  // 删除最后一个元素，即尾结点
    262. 		}
    263.  
    264. 		/* 头删 */
    265. 		void pop_front() {
    266. 			erase(begin());  // 删除头结点的下一个结点（即begin位置的结点）
    267. 		}
    268.  
    269. 		/* 清空链表所有数据 */
    270. 		void clear() {
    271. 			 利用迭代器去遍历整个链表
    272. 			//iterator it = begin();
    273. 			//while (it != end()) {
    274. 			//	iterator del = it++;  // 巧妙利用后置++的特性
    275. 			//	delete del._node;  // 删除当前结点，后置++生效
    276. 			//}
    277.  
    278. 			 删完之后我们还需要将其恢复到初始状态
    279. 			//_pHead->_next = _pHead;
    280. 			//_pHead->_prev = _pHead;
    281.  
    282. 			iterator it = begin();
    283. 			while (it != end()) {
    284. 				// iterator del = it++;
    285. 				erase(it++);   // 直接反复调用erase删除结点
    286. 			}
    287. 		}
    288.  
    289. 		~list() {
    290. 			// 清空链表有效数据
    291. 			clear();
    292. 			// 干掉头结点
    293. 			delete _pHead;
    294. 			_pHead = nullptr;
    295. 		}
    296.  
    297. 	private:
    298. 		Node* _pHead;
    299. 	};
    300.  
    301. 		void print_list(const list<int>& L) {
    302. 			list<int>::const_iterator it = L.begin();
    303. 			while (it != L.end()) {
    304. 				// *it = 100;
    305. 				cout << *it << " ";
    306. 				it++;
    307. 			}
    308. 			cout << endl;
    309. 		}
    310.  
    311.  
    312. 		void test_list1() {
    313. 			list<int> L;
    314. 			L.push_back(1);
    315. 			L.push_back(2);
    316. 			L.push_back(3);
    317. 			L.push_back(4);	
    318.  
    319. 			list<int>::iterator it = L.begin();
    320. 			while (it != L.end()) {
    321. 				*it *= 2;
    322. 				cout << *it << " ";
    323. 				it++;
    324. 			}
    325. 			cout << endl;
    326. 		}
    327.  
    328. 		void test_list2() {
    329. 			list<int> L;
    330. 			L.push_back(2);
    331. 			L.push_back(4);
    332. 			L.push_back(6);
    333. 			L.push_back(8);
    334.  
    335. 			print_list(L);
    336. 		}
    337.  
    338.  
    339. 		struct Date {
    340. 			int _year;
    341. 			int _month;
    342. 			int _day;
    343.  
    344. 			Date(int year = 1, int month = 1, int day = 1) 
    345. 				: _year(year)
    346. 				, _month(month)
    347. 				, _day(day) 
    348. 			{}
    349. 		};
    350.  
    351. 		void test_list3() {
    352. 			list L;
    353. 			L.push_back(Date(2022, 5, 1));
    354. 			L.push_back(Date(2022, 5, 2));
    355. 			L.push_back(Date(2022, 5, 3));
    356.  
    357. 			list::iterator it = L.begin();
    358. 			while (it != L.end()) {
    359. 				cout << it->_year << "/" << it->_month << "/" << it->_day << endl;
    360. 				it++;
    361. 			}
    362. 			cout << endl;
    363. 		}
    364.  
    365. 		void test_list4() {
    366. 			list<int> L1;
    367. 			L1.push_back(1);
    368. 			L1.push_back(2);
    369. 			L1.push_back(3);
    370.  
    371. 			list<int> L2(L1);
    372. 			for (auto e : L2) cout << e << " ";
    373. 		}
    374.  
    375. 		void test_list5() {
    376. 			list<int> L;
    377. 			L.push_back(1);
    378. 			L.push_back(2);
    379. 			L.push_back(3);
    380. 			cout << "删除前：";
    381. 			print_list(L);
    382.  
    383. 			cout << "删除后：";
    384. 			L.clear();
    385. 			print_list(L);
    386. 		}
    387. }
    388.  
    389.  
    390. -------------------------------------------------------------------
    391. namespace bite
    392.  
    393. {
    394.  
    395.   // List的节点类
    396.  
    397.   template<class T>
    398.  
    399.   struct ListNode
    400.  
    401.   {
    402.  
    403.     ListNode(const T& val = T()): _pPre(nullptr), _pNext(nullptr), _val(val)
    404.  
    405.     {}
    406.  
    407.     ListNode* _pPre;
    408.  
    409.     ListNode* _pNext;
    410.  
    411.     T _val;
    412.  
    413.   };
    414.  
    415.  
    416.  
    417.   //List的迭代器类
    418.  
    419.   template<class T, class Ref, class Ptr>
    420.  
    421.   class ListIterator
    422.  
    423.   {
    424.  
    425.     typedef ListNode* PNode;
    426.  
    427.     typedef ListIterator Self;
    428.  
    429.   public:
    430.  
    431.     ListIterator(PNode pNode = nullptr):_pNode(pNode)
    432.  
    433.     {}
    434.  
    435.     ListIterator(const Self& l): _pNode(l._pNode)
    436.  
    437.     {}
    438.  
    439.     T& operator*()
    440.  
    441.     {
    442.  
    443.       return _pNode->_val;
    444.  
    445.     }
    446.  
    447.     T* operator->()
    448.  
    449.     {
    450.  
    451.       return &*this;
    452.  
    453.     }
    454.  
    455.     Self& operator++()
    456.  
    457.     {
    458.  
    459.       _pNode = _pNode->_pNext;
    460.  
    461.       return *this;
    462.  
    463.     }
    464.  
    465.     Self operator++(int)
    466.  
    467.     {
    468.  
    469.       Self temp(*this);
    470.  
    471.       _pNode = _pNode->_pNext;
    472.  
    473.       return temp;
    474.  
    475.     }
    476.  
    477.     Self& operator--()
    478.  
    479.     {
    480.  
    481.       _pNode = _pNode->_pPre;
    482.  
    483.       return *this;
    484.  
    485.     }
    486.  
    487.     Self& operator--(int)
    488.  
    489.     {
    490.  
    491.       Self temp(*this);
    492.  
    493.       _pNode = _pNode->_pPre;
    494.  
    495.       return temp;
    496.  
    497.     }
    498.  
    499.     bool operator!=(const Self& l)
    500.  
    501.     {
    502.  
    503.       return _pNode != l._pNode;
    504.  
    505.     }
    506.  
    507.     bool operator==(const Self& l)
    508.  
    509.     {
    510.  
    511.       return !(*this!=l);
    512.  
    513.     }
    514.  
    515.   private:
    516.  
    517.     PNode _pNode;
    518.  
    519.   };
    520.  
    521.  
    522.  
    523.   //list类
    524.  
    525.   template<class T>
    526.  
    527.   class list
    528.  
    529.   {
    530.  
    531.     typedef ListNode Node;
    532.  
    533.     typedef Node* PNode;
    534.  
    535.   public:
    536.  
    537.     typedef ListIterator iterator;
    538.  
    539.     typedef ListIteratorconst T&, const T&> const_iterator;
    540.  
    541.   public:
    542.  
    543.     ///
    544.  
    545.     // List的构造
    546.  
    547.     list()
    548.  
    549.     {
    550.  
    551.       CreateHead();
    552.  
    553.     }
    554.  
    555.     list(int n, const T& value = T())
    556.  
    557.     {
    558.  
    559.       CreateHead();
    560.  
    561.       for (int i = 0; i < n; ++i)
    562.  
    563.        push_back(value);
    564.  
    565.     }
    566.  
    567.     template <class Iterator>
    568.  
    569.     list(Iterator first, Iterator last)
    570.  
    571.     {
    572.  
    573.       CreateHead();
    574.  
    575.       while (first != last)
    576.  
    577.       {
    578.  
    579.         push_back(*first);
    580.  
    581.         ++first;
    582.  
    583.       }
    584.  
    585.     }
    586.  
    587.     list(const list& l)
    588.  
    589.     {
    590.  
    591.       CreateHead();
    592.  
    593.       // 用l中的元素构造临时的temp,然后与当前对象交换
    594.  
    595.       list temp(l.cbegin(), l.cend());
    596.  
    597.       this->swap(temp);
    598.  
    599.     }
    600.  
    601.     list& operator=(const list l)
    602.  
    603.     {
    604.  
    605.       this->swap(l);
    606.  
    607.       return *this;
    608.  
    609.     }
    610.  
    611.     ~list()
    612.  
    613.     {
    614.  
    615.       clear();
    616.  
    617.       delete _pHead;
    618.  
    619.       _pHead = nullptr;
    620.  
    621.     }
    622.  
    623.  
    624.  
    625.     ///
    626.  
    627.     // List Iterator
    628.  
    629.     iterator begin()
    630.  
    631.     {
    632.  
    633.       return iterator(_pHead->_pNext);
    634.  
    635.     }
    636.  
    637.     iterator end()
    638.  
    639.     {
    640.  
    641.       return iterator(_pHead);
    642.  
    643.     }
    644.  
    645.     const_iterator begin()const
    646.  
    647.     {
    648.  
    649.       return const_iterator(_pHead->_pNext);
    650.  
    651.     }
    652.  
    653.     const_iterator end()const
    654.  
    655.     {
    656.  
    657.       return const_iterator(_pHead);
    658.  
    659.     }
    660.  
    661.  
    662.  
    663.     ///
    664.  
    665.     // List Capacity
    666.  
    667.     size_t size()const
    668.  
    669.     {
    670.  
    671.       size_t size = 0;
    672.  
    673.       ListNode *p = _pHead->_pNext;
    674.  
    675.       while(p != _pHead)
    676.  
    677.       {
    678.  
    679.         size++;
    680.  
    681.         p = p->_pNext;
    682.  
    683.       }
    684.  
    685.       return size;       
    686.  
    687.     }
    688.  
    689.     bool empty()const
    690.  
    691.     {
    692.  
    693.       return size() == 0;
    694.  
    695.     }
    696.  
    697.  
    698.  
    699.     
    700.  
    701.     // List Access
    702.  
    703.     T& front()
    704.  
    705.     {
    706.  
    707.       assert(!empty());
    708.  
    709.       return _pHead->_pNext->_val;
    710.  
    711.     }
    712.  
    713.     const T& front()const
    714.  
    715.     {
    716.  
    717.       assert(!empty());
    718.  
    719.       return _pHead->_pNext->_val;
    720.  
    721.     }
    722.  
    723.     T& back()
    724.  
    725.     {
    726.  
    727.       assert(!empty());
    728.  
    729.       return _pHead->_pPre->_val;
    730.  
    731.     }
    732.  
    733.     const T& back()const
    734.  
    735.     {
    736.  
    737.       assert(!empty());
    738.  
    739.       return _pHead->_pPre->_val;
    740.  
    741.     }
    742.  
    743.  
    744.  
    745.     
    746.  
    747.     // List Modify
    748.  
    749.     void push_back(const T& val)
    750.  
    751.     {
    752.  
    753.       insert(begin(), val);
    754.  
    755.     }
    756.  
    757.     void pop_back()
    758.  
    759.     {
    760.  
    761.       erase(--end());
    762.  
    763.     }
    764.  
    765.     void push_front(const T& val)
    766.  
    767.     {
    768.  
    769.       insert(begin(), val);
    770.  
    771.     }
    772.  
    773.     void pop_front()
    774.  
    775.     {
    776.  
    777.       erase(begin());
    778.  
    779.     }
    780.  
    781.     // 在pos位置前插入值为val的节点
    782.  
    783.     iterator insert(iterator pos, const T& val)
    784.  
    785.     {
    786.  
    787.       PNode pNewNode = new Node(val);
    788.  
    789.       PNode pCur = pos._pNode;
    790.  
    791.       // 先将新节点插入
    792.  
    793.       pNewNode->_pPre = pCur->_pPre;
    794.  
    795.       pNewNode->_pNext = pCur;
    796.  
    797.       pNewNode->_pPre->_pNext = pNewNode;
    798.  
    799.       pCur->_pPre = pNewNode;
    800.  
    801.       return iterator(pNewNode);
    802.  
    803.     }
    804.  
    805.     // 删除pos位置的节点，返回该节点的下一个位置
    806.  
    807.     iterator erase(iterator pos)
    808.  
    809.     {
    810.  
    811.       // 找到待删除的节点
    812.  
    813.       PNode pDel = pos._pNode;
    814.  
    815.       PNode pRet = pDel->_pNext;
    816.  
    817.       // 将该节点从链表中拆下来并删除
    818.  
    819.       pDel->_pPre->_pNext = pDel->_pNext;
    820.  
    821.       pDel->_pNext->_pPre = pDel->_pPre;
    822.  
    823.       delete pDel;
    824.  
    825.       return iterator(pRet);
    826.  
    827.     }
    828.  
    829.     void clear()
    830.  
    831.     {
    832.  
    833.       iterator p = begin();
    834.  
    835.       while(p != end())
    836.  
    837.       {
    838.  
    839.         p = erase(p);
    840.  
    841.       }
    842.  
    843.     }
    844.  
    845.     void swap(List& l)
    846.  
    847.     {
    848.  
    849.       pNode tmp = _pHead;
    850.  
    851.       _pHead = l._pHead;
    852.  
    853.       l._pHead = tmp;
    854.  
    855.     }
    856.  
    857.   private:
    858.  
    859.     void CreateHead()
    860.  
    861.     {
    862.  
    863.       _pHead = new Node;
    864.  
    865.       _pHead->_pPre = _pHead;
    866.  
    867.       _pHead->_pNext = _pHead;
    868.  
    869.     }
    870.  
    871.     PNode _pHead;
    872.  
    873.   };
    874.  
    875. }

    test.cpp

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include "list.h"
    3.  
    4. int main(void)
    5. {
    6. 	chaos::test_list1();
    7.  
    8. 	return 0;
    9. }

    reverse_iterator.h

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include "list.h"
    3.  
    4. namespace chaos
    5. {
    6. 	// Iterator是哪个容器的迭代器，reverse_iterator就可以
    7. 	// 适配出哪个容器的反向迭代器。复用的体现
    8. 	//template 
    9.  
    10. 	/* 定义反向迭代器 */
    11. 	template <class Iterator>
    12. 	class reverse_iterator {
    13. 		typedef reverse_iterator self;
    14. 		typedef typename Iterator::Ref reference;  
    15. 		typedef typename Iterator::Ptr pointer;
    16. 	public:
    17. 		reverse_iterator(Iterator it)
    18. 			:_it(it)
    19. 		{}
    20.  
    21. 		Ref operator*() {
    22. 			//return *_it;
    23. 			Iterator prev = _it;
    24. 			return *--prev;
    25. 		}
    26.  
    27. 		Ptr operator->() {
    28. 			return &operator*();
    29. 		}
    30.  
    31. 		self& operator++() {
    32. 			--_it;
    33. 			return *this;
    34. 		}
    35.  
    36. 		self& operator--() {
    37. 			++_it;
    38. 			return *this;
    39. 		}
    40.  
    41. 		bool operator!= (const self& rit) const {
    42. 			return _it != rit._it;
    43. 		}
    44.  
    45. 	private:
    46. 		Iterator _it;
    47. 	};
    48. }
    49.

  • 相关阅读:
    C++程序结束
    在vite（vue）项目中使用mockjs
    Spring @Profile注解使用和源码解析
    Mysql简单主从复制和读写分离
    如何在Python中捕获异常
    Java基础之浅聊 CompletableFuture类
    孔乙己第一问之服务通信知多少？
    设备巡检系统为巡检人员带来便利有哪些
    Vue——消息的订阅与发布
    MySQL底层知识总结
  • 原文地址：https://blog.csdn.net/qq_61386381/article/details/125922910