C++ list容器模拟实现：迭代器、构造与STL风格编程

// 第一个类模板：list_node
template<class T>  // 作用范围：下面的 struct list_node
struct list_node { ... };

// 第二个类模板：list
template<class T>  // 作用范围：下面的 class list
class list { ... };

template<class T>
class outer {
    // 嵌套类，直接使用外部的 T
    class inner {
        T data;  // 这里的 T 继承自 outer 的 template<class T>
    };
};

template<class T>
class outer {
    // 嵌套类有自己的模板参数 U
    template<class U>  // 单独声明，作用范围：下面的 inner
    class inner {
        T a;  // 来自 outer 的 T
        U b;  // 来自 inner 自己的 U
    };
};

template<class T>
class list
{
public:
    list()
    {
        // 调用list_node的带参构造，传入T的默认值
        _head = new Node(T()); 
        _head->_prev = _head;
        _head->_next = _head;
    }
    // 其余成员保持不变...
};

template<class T>
struct list_node
{
    list_node<T>* _prev;
    list_node<T>* _next;
    T _data;

    // 无参构造（用于创建头结点）
    list_node() : _prev(nullptr), _next(nullptr), _data() {}
    // 带参构造（用于创建数据节点）
    list_node(const T& x) : _prev(nullptr), _next(nullptr), _data(x) {}
};

template<class T>
struct list_node
{
    list_node<T>* _prev;
    list_node<T>* _next;
    T _data;

    // 带参数的构造函数，并提供一个默认参数 T()
    list_node(const T& x = T())
        : _prev(nullptr)
        , _next(nullptr)
        , _data(x)
    {}
};

yunze::list<int> mylist;
// 如果 iterator 是 private，下面这行代码会编译失败，因为外部无法访问 private 成员
yunze::list<int>::iterator it = mylist.begin(); 

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

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

std::vector<int> vec = {3, 1, 4, 1, 5, 9};
std::sort(vec.begin(), vec.end()); // 使用迭代器作为参数

Node* it1;
yunze::list<int>::iterator it2；

// 1. 用容器的begin()获取起始迭代器
auto __it = lt.begin();
// 2. 用容器的end()获取结束迭代器
auto __end = lt.end();
// 3. 用迭代器的!=判断是否遍历结束
for (; __it != __end; ++__it) {
    // 4. 用迭代器的*获取元素
    auto e = *__it;
    // 你写的循环体逻辑（比如cout << e << " "）
}

cout << lt.size() << endl;

class list {
public:
    // size是const成员函数
    size_t size() const {
        // 这里的*this，类型是 const list<T>&（const版本的list对象）
        // 而不是普通的 list<T>&
    }
};

// 1. 调用容器的begin()，拿到起始迭代器
auto it = *this.begin();
// 2. 调用容器的end()，拿到结束迭代器
auto end_it = *this.end();
// 3. 遍历迭代器
while (it != end_it) {
    auto& e = *it;
    ++it;
}

类似的命名还有：
OutputIterator：输出迭代器（能写元素）
ForwardIterator：前向迭代器（能单向遍历 + 读写）
BidirectionalIterator：双向迭代器（能双向遍历 + 读写）

// 你写的代码
for (auto& e : container) { ... }

// 编译器实际展开的代码（简化版）
auto __begin = container.begin(); // 必须能调用begin()
auto __end = container.end();     // 必须能调用end()
for (; __begin != __end; ++__begin) {
    auto& e = *__begin;
    ...
}

template<class T>
void swap(T& a, T& b) {
    T tmp(a);  // 1. 拷贝构造tmp（深拷贝，链表要复制所有节点）
    a = b;     // 2. 赋值a = b（再次深拷贝）
    b = tmp;   // 3. 赋值b = tmp（第三次深拷贝）
}

void swap(list<T>& lt) {
    std::swap(_head, lt._head);  // 交换哨兵节点的指针（仅交换地址，无内存操作）
    std::swap(_size, lt._size);  // 交换元素个数（仅交换数值）
}

list<int>//类外面必须类名+模板参数使用

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

void push_back(const T& x); // T=A，参数只有1个：const A&

lt.push_back(A(1, 1)); // 显式调用A的构造函数，生成A对象，作为push_back的单个参数

lt.push_back({1, 1}); // 隐式构造A对象，本质还是传递单个初始化器列表参数

template<class T, class Ref>
struct list_iterator
{
    using Node = list_node<T>;
    Node* _node; // 迭代器指向的链表节点指针

    // 1. 重载operator*：返回T对象的引用，适配.的使用规则
    Ref operator*()
    {
        return _node->_data; // T=A时，返回A对象的引用（A&）
    }

    // 2. 重载operator->：返回T对象的指针，适配->的使用规则
    T* operator->()
    {
        return &_node->_data; // T=A时，返回A对象的地址（A*）
    }
};

#include "list.h"
using namespace yunze;

int main() {
    // 场景1：创建普通list<int>对象
    list<int> lt;
    lt.push_back(10);
    lt.push_back(20);

    // 场景2：普通迭代器遍历+修改
    list<int>::iterator it = lt.begin();
    *it = 100;
    ++it;

    // 场景3：const list<int>对象 + const迭代器
    const list<int> clt = lt;
    list<int>::const_iterator cit = clt.begin();
    cout << *cit << endl;

    return 0;
}

// 编译器生成的list<int>核心代码（简化版）
class list<int> {
    // 内部别名：Node = list_node<int>
    using Node = list_node<int>;
public:
    // 迭代器别名：实例化list_iterator的两个版本
    using iterator = list_iterator<int, int&, int*>;
    using const_iterator = list_iterator<int, const int&, const int*>;

    // 成员函数声明（此时还未实例化，调用时才实例化）
    iterator begin();
    iterator end();
    const_iterator begin() const;
    const_iterator end() const;
    void empty_init();
    list<int>(); // 构造函数
    void push_back(const int& x);
    // ... 其他成员
private:
    Node* _head;
    size_t _size = 0;
};

// 编译器生成的list_node<int>代码
struct list_node<int> {
    list_node<int>* _prev;
    list_node<int>* _next;
    int _data;

    list_node(const int& x = int())
        : _prev(nullptr), _next(nullptr), _data(x) {}
};

// 编译器生成的普通迭代器代码
struct list_iterator<int, int&, int*> {
    using Self = list_iterator<int, int&, int*>;
    using Node = list_node<int>;
    Node* _node;

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

    // 解引用：返回int&（可修改）
    int& operator*() { return _node->_data; }

    // 箭头：返回int*
    int* operator->() { return &_node->_data; }

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

    // 后置++、--、==、!=等逻辑（编译器生成对应代码）
    Self operator++(int) { /* 具体逻辑 */ }
    bool operator!=(const Self& s) const { return _node != s._node; }
    // ...
};

// 编译器生成的const迭代器代码
struct list_iterator<int, const int&, const int*> {
    using Self = list_iterator<int, const int&, const int*>;
    using Node = list_node<int>;
    Node* _node;

    list_iterator(Node* node) : _node(node) {}

    // 解引用：返回const int&（只读）
    const int& operator*() { return _node->_data; }

    // 箭头：返回const int*
    const int* operator->() { return &_node->_data; }

    // ++/--/==/!=等逻辑和普通迭代器完全一致（编译器复用逻辑，仅修改返回类型）
    Self& operator++() {
        _node = _node->_next;
        return *this;
    }
    // ...
};

// 编译器生成的list<int>::push_back代码
void list<int>::push_back(const int& x) {
    insert(end(), x); // 调用insert
}

// 同时实例化insert函数（因为push_back调用了insert）
list<int>::iterator list<int>::insert(iterator pos, const int& x) {
    Node* cur = pos._node;
    Node* prev = cur->_prev;
    Node* newnode = new Node(x);
    prev->_next = newnode;
    newnode->_prev = prev;
    newnode->_next = cur;
    cur->_prev = newnode;
    ++_size;
    return iterator(newnode);
}

#pragma once
#include<iostream>
using namespace std;

namespace yunze
{
	// 泛型
	// 定义链表节点结构
	template<class T>
	struct list_node
	{
		list_node<T>* _prev;
		list_node<T>* _next;
		T _data;
		//节点的构造函数
		list_node(const T& x = T())
			:_prev(nullptr)
			, _next(nullptr)
			, _data(x)
		{
		}
	};

	//Ref(引用)
	template<class T, class Ref, class Ptr>
	//用类封装迭代器
	//list_iterator 本身是一个类模板，list_iterator<T> 是这个类模板的一个实例化
	struct list_iterator
	{
		//自身类型别名 
		using Self = list_iterator<T, Ref, Ptr>;
		//链表节点类型别名
		using Node = list_node<T>;
		//指向链表节点的指针（迭代器的抓手）
		Node* _node;

		//构造函数接收一个Node*类型的指针，通过初始化列表将_node指向该节点
		//作用是确定迭代器在链表中的初始位置（比如指向第一个有效节点、哨兵节点等）
		list_iterator(Node* node)
			:_node(node)
		{
		}

		//*it = 1
		Ref operator*()
		{
			return _node->_data;
		}

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

		//前置++
		Self& operator++()
		{
			_node = _node->_next;
			//返回迭代器对象自身
			return *this;
		}

		//后置++
		Self operator++(int)
		{
			Self tmp(*this);
			_node = _node->_next;
			//返回迭代器对象自身
			return tmp;
		}

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

		//it--
		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>
	////用类封装迭代器
	//struct list_const_iterator
	//{
	//	//自身类型别名
	//	using Self = list_const_iterator<T>;
	//	//链表节点类型别名
	//	using Node = list_node<T>;
	//	//指向链表节点的指针（迭代器的抓手）
	//	Node* _node;

	//	//构造函数接收一个Node*类型的指针，通过初始化列表将_node指向该节点
	//	//作用是确定迭代器在链表中的初始位置（比如指向第一个有效节点、哨兵节点等）
	//	list_const_iterator(Node* node)
	//		:_node(node)
	//	{
	//	}

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

	//	//前置++
	//	Self& operator++()
	//	{
	//		_node = _node->_next;
	//		//返回迭代器对象自身
	//		return *this;
	//	}

	//	//后置++
	//	Self operator++(int)
	//	{
	//		Self tmp(*this);
	//		_node = _node->_next;
	//		//返回迭代器对象自身
	//		return tmp;
	//	}

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

	//	//it--
	//	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*>;
		//using const_iterator = list_const_iterator<T>;

		iterator begin()
		{
			return iterator(_head->_next);
		}

		iterator end()
		{
			return iterator(_head);
		}

		const_iterator begin() const
		{
			return const_iterator(_head->_next);
		}

		const_iterator end() const
		{
			return const_iterator(_head);
		}

		void empty_init()
		{
			//创建一个哨兵节点（头节点），不存储任何有效数据
			_head = new Node;
			_head->_prev = _head;
			_head->_next = _head;
		}

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

		//{ }初始化
		list(initializer_list<T> il)
		{
			empty_init();
			for (auto& e : il)
			{
				push_back(e);
			}
		}

		template <class InputIterator>
		list(InputIterator first, InputIterator last)
		{
			empty_init();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		list(size_t n, T val = T())
		{
			empty_init();
			for (size_t i = 0; i < n; i++)
			{
				push_back(val);
			}
		}

		list(int n, T val = T())
		{
			empty_init();
			for (int i = 0; i < n; i++)
			{
				push_back(val);
			}
		}

		// 传统写法
		// lt2(lt1)
		list(const list<T>& lt)
		{
			empty_init();
			for (auto& e : lt)
			{
				push_back(e);
			}
		}

		//支持连续赋值
		list<T>& operator=(const list<T>& lt)
		{
			//判断是不是自己给自己赋值
			if (this != &lt)
			{
				//释放lt1
				clear();
				for (auto& e : lt)
				{
					push_back(e);
				}
			}
			return *this;
		}

		//// 现代写法
		//// lt2(lt1)
		////list(list<T>& lt)
		//list(const list& lt)
		//{
		//	empty_init();
		//	//list<T> tmp(lt.begin(), lt.end());
		//	list tmp(lt.begin(), lt.end());
		//	swap(tmp);
		//}

		//// 现代写法
		//// lt1 = lt3
		////list<T>& operator=(list<T> tmp)
		//list& operator=(list tmp)
		//{
		//	swap(tmp);
		//	return *this;
		//}

		//void swap(list<T>& lt)
		void swap(list& lt)
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}

		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
			_size = 0;
		}

		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)
		{
			//在end前面插入一个值
			insert(end(), x);
		}

		void push_front(const T& x)
		{
			//在begin前面插入一个值
			insert(begin(), x);
		}

		void pop_back()
		{
			//找到end的前一个节点
			erase(--end());
		}

		void pop_front()
		{
			erase(begin());
		}

		void insert(iterator pos, const T& x)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* newnode = new Node(x);
			//prev newnode cur
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;
			++_size;
		}

		iterator erase(iterator pos)
		{
			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 (auto& e : *this)
			//{
			//	++n;
			//}
			//return n;
			return _size;
		}
	private:
		//链表的唯一私有成员，指向哨兵节点（头节点）的指针
		//通过该指针可访问整个链表
		Node* _head;
		size_t _size = 0;
	};
}

#define _CRT_SECURE_NO_WARNINGS 666
#include"List.h"

//void test_list1()
//{
//	bit::list<int> lt;
//	lt.push_back(1);
//	lt.push_back(2);
//	lt.push_back(3);
//	lt.push_back(4);
//
//	bit::list<int>::iterator it = lt.begin();
//	while (it != lt.end())
//	{
//		cout << *it << " ";
//		++it;
//	}
//	cout << endl;
//
//	for (auto e : lt)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//}

void test_list2()
{
	yunze::list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_front(-1);
	lt.push_front(-2);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
	lt.pop_back();
	lt.pop_back();
	lt.pop_front();
	lt.pop_front();
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
	cout << lt.size() << endl;
}

void Print(const yunze::list<int>& lt)
{
	yunze::list<int>::const_iterator it = lt.begin();
	while (it != lt.end())
	{
		//*it = 1; const迭代器不能修改
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

void test_list3()
{
	yunze::list<int> lt1 = { 1,2,3,4,5,6 };
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;

	yunze::list<int> lt2(lt1);
	for (auto e : lt2)
	{
		cout << e << " ";
	}
	cout << endl;

	yunze::list<int> lt3 = { 10, 20, 30 };
	lt1 = lt3;
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;

	Print(lt1);
}

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

void test_list4()
{
	yunze::list<A> lt;
	lt.push_back({ 1, 1 });
	lt.push_back({ 2, 2 });
	lt.push_back({ 3, 3 });
	yunze::list<A>::iterator it = lt.begin();
	while (it != lt.end())
	{
		//cout << *it << " ";
		cout << (*it)._a1 << ":" << (*it)._a2 << endl;
		cout << it->_a1 << ":" << it->_a2 << endl;
		//显式调用的完整写法
		cout << it.operator->()->_a1 << ":" << it.operator->()->_a2 << endl;
		++it;
	}
	cout << endl;
}

int main()
{
	//test_list1();
	//test_list2();
	//test_list3();
	test_list4();
	return 0;
}