【C++STL ：list类 (二) 】序列容器性能的本质：深度剖析 list 与 vector 的迭代器核心奥秘

// 测试链表基础功能和迭代器的函数
// 目的：验证链表的基本插入操作和两种遍历方式
void Test_list1()
{
	// 创建一个整型双向链表对象
	jqj::list<int> lt;
	// 向链表尾部依次添加元素 1, 2, 3, 4
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);

	// 方式1：使用显式迭代器遍历链表
	// 获取指向链表第一个元素的迭代器
	jqj::list<int>::iterator it = lt.begin();

	// 传统while循环遍历，从begin()到end()
	// end()返回的是哨兵节点，表示链表末尾
	while (it != lt.end())
	{
		cout << *it << " ";// 解引用迭代器，获取当前元素值
		++it;                // 迭代器递增，移动到下一个节点
	}
	cout << endl;
	// 预期输出：1 2 3 4

	// 方式2：使用C++11范围for循环遍历链表
	// 这是更现代的遍历方式，编译器会自动转换为迭代器操作
	// auto& e：自动类型推导，使用引用避免拷贝
	for (auto& e : lt)
	{
		cout << e << " "; // 直接访问元素值
	}
	cout << endl;
	// 预期输出：1 2 3 4
}

// 测试链表基本操作的函数
// 目的：验证push_back、push_front、pop_back、pop_front等操作的正确性
void Test_list2()
{
	jqj::list<int> lt; // 创建一个整型双向链表对象
	// 向链表尾部依次添加元素 1, 2, 3, 4
	// 链表变化过程：1 → 1→2 → 1→2→3 → 1→2→3→4
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);

	// 向链表头部依次添加元素 -1, -2, -3
	// 链表变化过程：1→2→3→4 → -1→1→2→3→4 → -2→-1→1→2→3→4 → -3→-2→-1→1→2→3→4
	lt.push_front(-1);
	lt.push_front(-2);
	lt.push_front(-3);

	// 第一次遍历输出：显示所有插入后的链表元素
	// 使用范围for循环遍历链表，auto&避免拷贝，提高效率
	// 预期输出：-3 -2 -1 1 2 3 4
	for (auto& e : lt)
	{
		cout << e << " "; // 输出当前元素值加空格
	}
	cout << endl;

	// 删除操作：从尾部删除2个元素，从头部删除2个元素
	// 链表变化过程：-3→-2→-1→1→2→3→4 → -3→-2→-1→1→2→3 → -3→-2→-1→1→2 → -2→-1→1→2 → -1→1→2
	lt.pop_back();
	lt.pop_back();
	lt.pop_front();
	lt.pop_front();

	// 第二次遍历输出：显示删除操作后的剩余元素
	// 预期输出：-1 1 2
	for (auto& e : lt)
	{
		cout << e << " "; // 输出当前元素值加空格
	}
	cout << endl;

	// 输出链表当前包含的元素个数
	// 预期输出：3（因为初始7个元素，删除了4个，剩余3个）
	cout << lt.size() << endl;
}

// 打印链表函数 - 常量版本
// 功能：遍历并输出链表中所有元素，不修改原链表
// 参数：lt —— 常量链表引用，确保函数内不会修改链表内容
void Print(const jqj::list<int>& lt)
{
	// 使用常量迭代器开始遍历，从链表头部开始
	// const_iterator确保在遍历过程中不会修改链表元素
	jqj::list<int>::const_iterator it = lt.begin();
	// 循环遍历直到到达链表末尾
	// end()返回的是哨兵节点，表示链表的结束位置

	while (it != lt.end())
	{
		// 这行代码被注释掉了，因为它试图修改常量迭代器指向的值
		// 在const_iterator中，operator*()返回const T&，所以不能赋值
		//*it = 1; // 错误：尝试修改常量数据

		// 输出当前元素的值，后跟空格分隔符
		cout << *it << " ";

		// 移动到下一个节点
		// ++it调用的是迭代器的前置递增运算符
		++it;
	}
	// 输出换行，使输出结果更清晰
	cout << endl;
}

void Test_list3()
{
	// 使用初始化列表构造链表
	jqj::list<int> lt1 = { 1,2,3,4,5,6 };
	for (auto& e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;
	// 预期输出: 1 2 3 4 5 6

	// 测试拷贝构造函数
	jqj::list<int> lt2(lt1);
	for (auto& e : lt2)
	{
		cout << e << " ";
	}
	cout << endl;
	// 预期输出: 1 2 3 4 5 6

	// 测试赋值运算符
	jqj::list<int> lt3 = { 10,20,30,40 };
	lt1 = lt3; // 赋值操作：lt1现在变成lt3的内容
	for (auto& e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;
	// 预期输出: 10 20 30 40

	// 使用Print函数再次输出
	Print(lt1);
	// 预期输出: 10 20 30 40
}

#pragma once

namespace jqj
{
	// --------------链表节点结构--------------
	template<class T>
	struct list_node
	{
		list_node<T>* _next;    // 指向下一个节点的指针
		list_node<T>* _prev;	// 指向前一个节点的指针
		T _data;						// 节点存储的数据

		// --------------节点构造函数--------------
		list_node(const T& x = T())
			:_next(nullptr)
			, _prev(nullptr)
			, _data(x) // x 节点数据，默认为T类型的默认值
		{}
	};

	// --------------链表迭代器--------------
	// 实现双向迭代器功能，支持前向和后向遍历
	template<class T, class Ref,class Ptr> // T 数据类型
	// Ref 引用类型（T& 或 const T&）
	struct list_iterator
	{
		// using还具有tepedef没有的功能
		// 使用类型别名（C++11新特性）
		using Self = list_iterator<T, Ref, Ptr>; // 自身类型
		using Node = list_node<T>; // 节点类型
		Node* _node; // 当前指向的节点指针

		// 迭代器构造函数
		list_iterator(Node* node)
			:_node(node)
		{}

		// 迭代器解引用操作
		// *it = 1
		// Ref 返回节点数据的引用（可读或可写）
		Ref operator*() // 解引用，Ref就是reference，引用的意思
		{
			return _node->_data;
		}
		// operator*()返回对应数据类型的引用

		Ptr operator->() // 返回对应数据类型的指针
		{
			return &_node->_data;
		}

		// ++it  
		// 前向迭代操作
		Self& operator++() // Self& 返回递增后的迭代器引用
		{
			_node = _node->_next;
			return *this;
		}

		Self operator++(int) // Self 返回递增前的迭代器副本
		{
			Self tmp(*this);
			_node = _node->_next;
			return tmp;
		}

		// --it
		// 后向迭代操作
		Self& operator--() // Self& 返回递减后的迭代器引用
		{
			_node = _node->_prev;
			return *this;
		}

		Self operator--(int) // Self 返回递减前的迭代器副本
		{
			Self tmp(*this);
			_node = _node->_prev;
			return tmp;
		}

		// 迭代器比较操作
		bool operator!=(const Self& s) const // bool 两个迭代器是否不指向同一节点
		{
			return _node != s._node;
		}

		bool operator==(const Self& s) const // bool 两个迭代器是否不指向同一节点
		{
			return _node == s._node;
		}
	};

	//template<class T>
	//struct list_const_literator
	//{
	//	using Self = list_const_literator<T>;
	//	using Node = list_node<T>; Node* _node;
	//	Node* _node;

	//	list_const_iterator(Node* node)
	//		:_node(node)
	//	{ }

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

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

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

	//	// --it
	//	Self& operator--()
	//	{
	//		_node = _node->_prev;
	//		return *this;
	//	}

	//	Self operator--(int)
	//	{
	//		Self tmp(*this);
	//		_node = _node->_prev;
	//		return tmp;
	//	}

	//	bool operator!=(const Self& s) const
	//	{
	//		return _node != s._node;
	//	}

	//	bool operator==(const Self& s) const
	//	{
	//		return _node == s._node;
	//	}
	//};

	// --------------链表主体类--------------
	template<class T>
	class list
	{
		using Node = list_node<T>; // 节点类型别名
	public:
		// 迭代器类型定义 
		using iterator = list_iterator<T, T&, T*>; // 普通迭代器
		using const_iterator = list_iterator<T, const T&, const T*>; // 常量迭代器
		// const T* 只能读数据，不能修改数据

		//using iterator = list_iterator<T>;
		//using const_iterator = list_const_iterator<T>;

		// --------------迭代器访问接口--------------
		// 获取指向第一个元素的迭代器
		// iterator 指向首元素的迭代器
		iterator begin()
		{
			return iterator(_head->_next);
		}

		// iterator 指向哨兵节点的迭代器
		iterator end()
		{
			return iterator(_head);
		}

		// 获取指向第一个元素的常量迭代器
		// const_iterator 指向首元素的常量迭代器
		const_iterator begin() const
		{
			return const_iterator(_head->_next);
		}

		// const_iterator 指向哨兵节点的常量迭代器
		const_iterator end() const
		{
			return const_iterator(_head);
		}

		// ----------------链表初始化相关----------------- 
		void empty_init() // 初始化空链表（创建哨兵节点）
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}

		// 默认构造函数
		list()
		{
			empty_init();
		}

		// 初始化列表构造函数
		// il 初始化列表
		list(initializer_list<T> il)
		{
			empty_init();
			for (auto& e : il)
			{
				push_back(e);
			}
		}

		// 范围构造函数
		// InputIterator 输入迭代器类型
		template <class InputIterator> 
		list(InputIterator first, InputIterator last) // first 范围起始迭代器 // last 范围结束迭代器
		{
			empty_init();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		// 数量构造函数（size_t版本）
		list(size_t n, T val = T()) // val 元素值，默认为T的默认值
		{
			empty_init();
			for (size_t i = 0; i < n; ++i)
			{
				push_back(val);
			}
		}

		// 数量构造函数（int版本）
		list(int n, T val = T()) // val 元素值，默认为T的默认值
		{
			empty_init();
			for (size_t i = 0; i < n; ++i)
			{
				push_back(val);
			}
		}

		// -------------析构函数-------------
		// 清理所有节点并释放哨兵节点
		~list()
		{
			clear();

			delete _head;
			_head = nullptr;
			_size = 0;
		}

		// -----------拷贝控制函数----------
		// lt 要拷贝的源链表
		// lt2（lt1）
		list(const list<T>& lt)
		{
			empty_init();
			for (auto& e : lt)
			{
				push_back(e);
			}
		}

		// 拷贝赋值运算符
		// lt 要拷贝的源链表
		// list<T>& 返回当前链表的引用
		// lt1 = lt3
		list<T>& operator=(const list<T>& lt)
		{
			if (this != &lt)
			{
				clear();
				for (auto& e : lt)
				{
					push_back(e);
				}
			}

			return *this;
		}

		////
		//list(list<T>& lt)
		//	list(const list& lt)
		//{
		//	empty_init();

		//	list tmp(lt.begin(), lt.end());
		//	swap(tmp);
		//}

		//// lt1 = lt3
		////list<T>& operator=(list<T> tmp)
		//list& operator=(list tmp)
		//{
		//	swap(tmp);
		//}

		// ----------------容量操作---------------
		// 交换两个链表的内容
		void swap(list<T>& lt) // lt 要交换的另一个链表
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}

		// 清空链表中的所有元素
		// 保留哨兵节点，删除所有数据节点
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

		//void push_back(const T& x)
		//{
		//	Node* newnode = new Node(x);
		//	Node* tail = _head->_prev;
		//	tail->_next = newnode;
		//	newnode->_prev = tail;
		//	newnode->_next = _head;
		//	_head->_prev = newnode;
		//}

		// -----------------元素访问操作--------------------
		// 复用
		void push_back(const T& x) // 在链表尾部插入元素，x：要插入的元素值
		{
			insert(end(), x);
		}

		// 在链表头部插入元素，x：要插入的元素值
		void push_front(const T& x)
		{
			insert(begin(), x);
		}

		// 删除链表尾部元素
		void pop_back()
		{
			erase(--end());
		}

		// 删除链表头部元素
		void pop_front()
		{
			erase(begin());
		}

		// ---------------- 指定位置操作 ----------------
		// 在指定位置前插入元素
		void insert(iterator pos, const T& x) // pos：插入位置的迭代器，x：要插入的元素值
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* newnode = new Node(x);

			// // 连接新节点：prev -> newnode -> cur
			// prev newnode cur
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;

			++_size;
		}

		// 删除指定位置的元素
		iterator erase(iterator pos) // iterator 返回指向被删除元素后一个元素的迭代器
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;

			// 跳过被删除节点：prev -> next
			prev->_next = next;
			next->_prev = prev;
			delete cur;
			--_size;

			/*return iterator(next);*/
			return next; /// 返回下一个节点的迭代器
			//两种写法都可以
		}

		// -------------- 容量信息 ------------------
		size_t size() const
		{
			//size_t n = 0;
			//for (auch e : *this)
			//{
			//	++n;
			//}
			//return n;
			return _size;
		}

	private:
		Node* _head;		// 哨兵头节点指针
		size_t _size = 0;	// 链表元素个数计数器
	};
}

#define  _CRT_SECURE_NO_WARNINGS  1
#include<iostream>
#include<algorithm>
#include<vector>
#include<list>
using namespace std;

void Test_op1()
{
	srand(time(0));
	const int N = 1000000000;

	list<int> lt1;
	vector<int> v;

	for (int i = 0; i < N; ++i)
	{
		auto e = rand() + i;
		lt1.push_back(e);
		v.push_back(e);
	}

	int begin1 = clock();
	//
	sort(v.begin(), v.end());
	int end1 = clock();

	int begin2 = clock();
	lt1.sort();
	int end2 = clock();

	printf("vector sort:%d\n", end1 - begin1);
	printf("list sort:%d\n", end2 - begin2);
}

void Test_op2()
{
	srand(time(0));
	const int N = 1000000;

	list<int> lt1;
	list<int> lt2;

	for (int i = 0; i < N; ++i)
	{
		auto e = rand() + i;
		lt1.push_back(e);
		lt2.push_back(e);
	}

	int begin1 = clock();
	// vector
	vector<int> v(lt2.begin(), lt2.end());
	// 
	sort(v.begin(), v.end());

	// lt2
	lt2.assign(v.begin(), v.end());

	int end1 = clock();

	int begin2 = clock();
	lt1.sort();
	int end2 = clock();

	printf("list copy vector sort copy list sort:%d\n", end1 - begin1);
	printf("list sort:%d\n", end2 - begin2);
}

//--------------------------------------------------------------------
#include"list.h"

// 测试链表基础功能和迭代器的函数
// 目的：验证链表的基本插入操作和两种遍历方式
void Test_list1()
{
	// 创建一个整型双向链表对象
	jqj::list<int> lt;
	// 向链表尾部依次添加元素 1, 2, 3, 4
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);

	// 方式1：使用显式迭代器遍历链表
	// 获取指向链表第一个元素的迭代器
	jqj::list<int>::iterator it = lt.begin();

	// 传统while循环遍历，从begin()到end()
	// end()返回的是哨兵节点，表示链表末尾
	while (it != lt.end())
	{
		cout << *it << " ";// 解引用迭代器，获取当前元素值
		++it;                // 迭代器递增，移动到下一个节点
	}
	cout << endl;
	// 预期输出：1 2 3 4

	// 方式2：使用C++11范围for循环遍历链表
	// 这是更现代的遍历方式，编译器会自动转换为迭代器操作
	// auto& e：自动类型推导，使用引用避免拷贝
	for (auto& e : lt)
	{
		cout << e << " "; // 直接访问元素值
	}
	cout << endl;
	// 预期输出：1 2 3 4
}

// 测试链表基本操作的函数
// 目的：验证push_back、push_front、pop_back、pop_front等操作的正确性
void Test_list2()
{
	jqj::list<int> lt; // 创建一个整型双向链表对象
	// 向链表尾部依次添加元素 1, 2, 3, 4
	// 链表变化过程：1 → 1→2 → 1→2→3 → 1→2→3→4
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);

	// 向链表头部依次添加元素 -1, -2, -3
	// 链表变化过程：1→2→3→4 → -1→1→2→3→4 → -2→-1→1→2→3→4 → -3→-2→-1→1→2→3→4
	lt.push_front(-1);
	lt.push_front(-2);
	lt.push_front(-3);

	// 第一次遍历输出：显示所有插入后的链表元素
	// 使用范围for循环遍历链表，auto&避免拷贝，提高效率
	// 预期输出：-3 -2 -1 1 2 3 4
	for (auto& e : lt)
	{
		cout << e << " "; // 输出当前元素值加空格
	}
	cout << endl;

	// 删除操作：从尾部删除2个元素，从头部删除2个元素
	// 链表变化过程：-3→-2→-1→1→2→3→4 → -3→-2→-1→1→2→3 → -3→-2→-1→1→2 → -2→-1→1→2 → -1→1→2
	lt.pop_back();
	lt.pop_back();
	lt.pop_front();
	lt.pop_front();

	// 第二次遍历输出：显示删除操作后的剩余元素
	// 预期输出：-1 1 2
	for (auto& e : lt)
	{
		cout << e << " "; // 输出当前元素值加空格
	}
	cout << endl;

	// 输出链表当前包含的元素个数
	// 预期输出：3（因为初始7个元素，删除了4个，剩余3个）
	cout << lt.size() << endl;
}

// 打印链表函数 - 常量版本
// 功能：遍历并输出链表中所有元素，不修改原链表
// 参数：lt —— 常量链表引用，确保函数内不会修改链表内容
void Print(const jqj::list<int>& lt)
{
	// 使用常量迭代器开始遍历，从链表头部开始
	// const_iterator确保在遍历过程中不会修改链表元素
	jqj::list<int>::const_iterator it = lt.begin();
	// 循环遍历直到到达链表末尾
	// end()返回的是哨兵节点，表示链表的结束位置

	while (it != lt.end())
	{
		// 这行代码被注释掉了，因为它试图修改常量迭代器指向的值
		// 在const_iterator中，operator*()返回const T&，所以不能赋值
		//*it = 1; // 错误：尝试修改常量数据

		// 输出当前元素的值，后跟空格分隔符
		cout << *it << " ";

		// 移动到下一个节点
		// ++it调用的是迭代器的前置递增运算符
		++it;
	}
	// 输出换行，使输出结果更清晰
	cout << endl;
}

void Test_list3()
{
	// 使用初始化列表构造链表
	jqj::list<int> lt1 = { 1,2,3,4,5,6 };
	for (auto& e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;
	// 预期输出: 1 2 3 4 5 6

	// 测试拷贝构造函数
	jqj::list<int> lt2(lt1);
	for (auto& e : lt2)
	{
		cout << e << " ";
	}
	cout << endl;
	// 预期输出: 1 2 3 4 5 6

	// 测试赋值运算符
	jqj::list<int> lt3 = { 10,20,30,40 };
	lt1 = lt3; // 赋值操作：lt1现在变成lt3的内容
	for (auto& e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;
	// 预期输出: 10 20 30 40

	// 使用Print函数再次输出
	Print(lt1);
	// 预期输出: 10 20 30 40
}

struct A
{
	int _a1;
	int _a2;

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

void Test_list4()
{
	jqj::list<A> lt;
	lt.push_back({ 1,1 }); // 多参数走隐式类型转换
	lt.push_back({ 2,2 });
	lt.push_back({ 3,3 });

	jqj::list<A>::iterator it = lt.begin();
	while (it != lt.end())
	{
		//cout << *it << " "; // 解引用，数据是A类型，这里A类型没有重载流插入
		//cout << (*it) << " "; // 不行
		//cout << (*it)._a1 << ":" << (*it)._a2 << endl; // 迭代器模拟指针行为，这样就可以访问了

		// 为了可读性，省略了一个->
		cout << it->_a1 << ":" << it->_a2 << endl; // 要重载一个operator->() 
		// 迭代器还有一种重载，因为迭代器要模拟指针的行为，指针有两种解引用的方式，一种是“*”，一种是“->”
		cout << it.operator->()->_a1 << ":" << it.operator->()->_a2 << endl; // 两个箭头
		// 第一个箭头是运算符重载，第二个箭头是运算符重载后返回一个A*的数据，A*的数据再去访问A类型指针指向的数组成员
		++it;
	}
	cout << endl;
}

int main()
{
	//Test_op1();
	//Test_op2();

	//Test_list1();
	//Test_list2();

	//Test_list3();
	Test_list4();

	return 0;
}