【C++】list的模拟实现

前言

在之前string和vector的模拟实现中，我们了解到了它们的底层是怎么实现的，在本篇博客我会为大家介绍list的模拟实现，list的模拟实现和string,vector不同，因为list是由一个一个节点连接而成的，所以物理空间是不连续的，迭代器的底层实现也有差异。

一. list的底层结构

list的底层是一个带头双向循环链表。

因为list的物理存储空间不是连续的，如果迭代器是节点指针就不能通过++或- -使迭代器向左或向右移动，那么怎么解决这个问题呢？

可以通过将节点指针封装成迭代器类，在类里实现迭代器的各种操作来完成。这种容器的迭代器设计思路体现了封装的特性，它屏蔽了底层实现细节和各容器结构的差异，本质封装底层细节和差异，提供统一的访问方式。

list由节点结构体，迭代器类，list类三部分组成的。

节点结构体

template<class T>
struct list_node
{
	T _data; //存储数据
	list_node<T>* _next; //存储下一个节点的指针
	list_node<T>* _prev; //存储上一个节点的指针
	list_node(const T& data = T())
		:_data(data),
		_next(nullptr),
		_prev(nullptr)
	{
	}
};

节点结构体不需要实现析构函数，因为它的职责就是创造节点，节点的释放和销毁由list类的析构函数统一管理。

结构体与类的最主要区别是：结构体的成员访问类型默认是公有的（public），类的成员访问类型默认是私有的（private）。

迭代器类

1. 迭代器类是对节点指针的封装，同样不会创造或销毁节点，不用手动去实现拷贝构造函数和析构函数，浅拷贝就可以了。
2. 在使用迭代器时，解引用操作符的重载函数返回的是引用类型，操作符->重载函数返回的是指针类型。因为不知道迭代器是普通迭代器还是const迭代器，所以返回的数据类型不知道是否要带const，这时我们可以传引用类型和指针类型给两个模板参数Ref和Ptr，上述函数的返回类型就是对应的模板参数。（比如，普通迭代器就传T&和T*, const迭代器就传const T&和const T*）
3. 为了方便返回迭代器对象，可以将其typedef为Self。

template<class T, class Ref, class Ptr>
struct list_iterator
{
	typedef list_node<T> Node; //节点
	typedef list_iterator<T, Ref, Ptr> Self; //迭代器对象
	typedef typename Ref Ref;
    typedef typename Ptr Ptr;
	list_iterator(Node* n)
		:node(n)
	{ }
	Node* node; //存储节点指针
}

list类

list类中包含了哨兵位节点（头节点）phead和记录链表长度的值_size。

template<class T>
class list
{
public:
	typedef list_node<T> Node; //节点
	typedef list_iterator<T, T&, T*> iterator; //普通迭代器
	typedef list_iterator<T, const T&, const T*> const_iterator; //const迭代器
private:
	Node* phead; //哨兵位节点（头节点）
	size_t _size; //记录链表长度
};

二. list迭代器

list是双向循环链表，可以往前走也可以往后走（比如begin()++,begin()–），但是list不支持随机访问（不允许begin()+n,n为整数），因为物理存储空间不是连续的。也就是说，list迭代器是双向迭代器。

在 C++ 标准库中，迭代器（Iterators）是容器和算法之间的桥梁，它们提供了统一的访问容器元素的方式。迭代器根据其支持的操作分为不同类别，其中最常见的是 单向迭代器、双向迭代器 和 随机迭代器。以下是它们的核心区别和特性：

1.单向迭代器（Forward Iterators）

定义：单向迭代器是最基础的迭代器类型，只能向前移动（即只能进行单向遍历）。

支持的操作：

*iter：解引用，获取当前元素。
iter->：访问当前元素的成员。
++iter：向前移动到下一个元素。
iter1 == iter2 和 iter1 != iter2：比较两个迭代器是否相等。

适用容器：

std::forward_list（单链表）
哈希表（如 std::unordered_set、std::unordered_map）

限制：无法回退，只能单向遍历。

2.双向迭代器（Bidirectional Iterators）

定义：双向迭代器可以在容器中向前和向后移动。

支持的操作：

单向迭代器支持的所有操作。
–iter：向后移动到前一个元素。

适用容器：

std::list（双向链表）
std::set, std::map（红黑树实现）

限制：不支持随机跳跃访问（如 +n 或 -n）。

3.随机迭代器（Random Access Iterators）

定义：随机迭代器支持在容器中随机访问任意位置的元素，可以进行算术运算（如加减整数）。

支持的操作：

双向迭代器支持的所有操作。
iter + n 和 iter - n：向前或向后移动 n 个位置。
iter1 - iter2：计算两个迭代器之间的距离。
iter[n]：直接访问第 n 个元素。
比较操作符：<, >, <=, >=。

适用容器：

std::vector（动态数组）
std::deque（双端队列）
原生数组（指针也是随机迭代器）

优势：时间复杂度为O(1)的随机访问。

关键区别总结

为什么迭代器分类重要？

1. 算法兼容性：不同算法需要不同迭代器类别。例如：
   std::sort 需要随机迭代器（只能在 vector 或 deque 上使用）。
   std::list::sort 是成员函数，因为 list 只提供双向迭代器。
2. 性能优化：随机迭代器支持高效随机访问，适合复杂算法；单向迭代器适用于简单遍历。

2.1 迭代器设计思想

我们规定list迭代器begin指向头节点的下一个节点（链表中的第一个有效节点），end指向头节点，返回的都是迭代器对象。之前提到过：list迭代器实际上就是对节点指针的封装，通过各种运算符重载函数，使得迭代器的行为看起来和普通指针一样，例如：要想实现迭代器++，只需要将迭代器存储的节点指针改为该节点的下一个节点指针即可(Node=Node->next)。

迭代器分为iterator和const_iterator，适用于普通对象和const对象，如果不实现多参数模板则需要写两份迭代器对象，造成代码冗余，如果实现了多参数模板，只需要根据list对象的类型去传类型参数从而构建对应的迭代器类。

多参数模板：

• T：节点数据的类型
• Ref：节点数据类型的引用类型
• Ptr：节点数据类型的指针类型

2.2 迭代器操作设计

begin和end返回的都是迭代器对象，只需返回匿名对象即可。

list类

template<class T>
class list
{
public:
	typedef list_node<T> Node; //节点
	typedef list_iterator<T, T&, T*> iterator; //普通迭代器
	typedef list_iterator<T, const T&, const T*> const_iterator; //const迭代器
	iterator begin()
	{
		return iterator(phead->_next);
	}
	iterator end()
	{
		return iterator(phead);
	}
	const_iterator begin() const
	{
		return const_iterator(phead->_next);
	}
	const_iterator end() const
	{
		return const_iterator(phead);
	}
private:
	Node* phead; //哨兵位节点（头节点）
	size_t _size; //记录链表长度
};

list_iterator类

template<class T, class Ref, class Ptr>
struct list_iterator
{
	typedef list_node<T> Node; //节点
	typedef list_iterator<T, Ref, Ptr> Self; //迭代器对象
	list_iterator(Node* n)
		:node(n)
	{ }
	Self& operator++() //前置++
	{
		node = node->_next;
		return *this;
	}
	Self& operator--() //前置--
	{
		node = node->_prev;
		return *this;
	}
	Self operator++(int) //后置++
	{
		Self tmp(*this);
		node = node->_next;
		return tmp;
	}
	Self operator--(int) //后置--
	{
		Self tmp(*this);
		node = node->_prev;
		return tmp;
	}
	bool operator!=(const Self& it)
	{
		return node != it.node;
	}
	bool operator==(const Self& it)
	{
		return node == it.node;
	}
	Node* node; //存储节点指针
};

对于前置的++或–，只需将存储的节点指针改为下一个节点指针或上一个节点指针即可（node=node->_next或node=node->_prev）。

对于后置的++或–，需要创建一个临时的迭代器对象tmp去拷贝当前的迭代器对象，再将当前迭代器对象存储的节点指针改为下一个节点指针或上一个节点指针，最后返回临时对象tmp即可。

Ref operator*() const
{
	return node->_data;
}
Ptr operator->() const
{
	return &(node->_data);
}

解引用操作符*的重载函数返回的是节点存储数据_data的引用，->操作符重载函数返回的是节点存储数据_data的地址。

为什么要重载操作符->？$⟶$因为list存储的数据可能是一个类，想要通过迭代器对象去访问指向的类的成员，可以重载->直接去访问类里的成员。

那为什么操作符->的重载函数返回的是存储数据的地址？

这是因为C++编译器的优化，如果是正常通过->去访问类成员，应该是迭代器对象->()->类成员（比如：it->()->data，data是类成员）,经过编译器优化后可以直接写成迭代器对象->类成员（it->data，data是类成员）。

经过C++编译器的优化，不用显示使用两次箭头->进行访问，一个箭头->就可以访问类成员，符合我们日常使用习惯，也避免了冗余的箭头操作。

三. list的实现

3.1 默认成员函数

3.1.1 构造函数

默认构造函数

因为list的底层是带头双向循环链表，所以在构造初始化时应创建一个哨兵位节点（头节点），因为有多个构造函数，为了避免代码冗余，可以将其封装成一个函数。

void empty_list()
{
	phead = new Node();
	phead->_next = phead;
	phead->_prev = phead;
}

因为只有一个哨兵位节点，需要将其_next和_prev指针指向自己。

list()
	:_size(0)
{
	empty_list();
}

用n个val值构造

list(size_t n, const T& val = T())
	:_size(0)
{
	empty_list();
	for (size_t i = 0; i < n; i++)
	{
		push_back(val);
	}
}

push_back函数的作用是在链表的尾部插入一个新节点，后面会实现。

用一段迭代器区间构造

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

声明和定义一个模板函数，模板参数InputIterator可以替换为任意不同迭代器的类型，从迭代器区间的起始位置first开始至结束位置last的前一个位置，依次将该区间内的所有元素插入到链表list中。

这段代码与用n个val值构造list的构造函数可能会发生冲突：当调用MyList::list< int > lt(5, 3);这个函数时，5和3都是int类型，list(size_t n, const T& val = T())的第一个参数类型为size_t，要想调用这个函数只能将n隐式类型转换为int，而使用迭代器区间进行构造的构造函数可以将模板参数InputIterator推导为int，first和last都是int类型，编译器会调用更符合的构造函数，也就是使用迭代器区间进行构造的构造函数，从而发生冲突。

解决办法就是再写一个用val值构造list的构造函数，不同的点是：n为int类型。

list(int n, const T& val = T())
	:_size(0)
{
	empty_list();
	for (int i = 0; i < n; i++)
	{
		push_back(val);
	}
}

用初始化列表构造初始化

传统写法：

list(initializer_list<T> lt)
	:_size(0)
{
	empty_list();
	for (auto& e : lt)
	{
		push_back(e);
	}
}

使用范围for循环遍历初始化列表里的所有元素，并使用push_back函数将每个元素插入到列表的末尾。

现代写法：

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

list(initializer_list<T> lt)
	:_size(0)
{
	empty_list();
	list<T> tmp(lt.begin(), lt.end());
	swap(tmp);
}

创建一个临时对象tmp，并用lt的迭代器区间进行构造初始化，再将当前对象的哨兵位结点和tmp的哨兵位结点进行交换即可。

注意：当前对象必须先使用empty_list函数创建一个非空哨兵位结点后才能进行交换，不然哨兵位结点指针为nullptr，进行交换时编译器会报错。

拷贝构造函数

传统写法：

list(const list<T>& lt)
	:_size(0)
{
	empty_list();
	for (auto& e : lt)
	{
		push_back(e);
	}
}

先使用empty_list函数创建一个哨兵位结点，再将链表lt的每个元素插入到当前链表的末尾。

现代写法：

list(const list<T>& lt)
	:_size(0)
{
	empty_list();
	list<T> tmp(lt.begin(), lt.end());
	swap(tmp);
}

创建一个临时对象tmp并用lt的迭代器区间进行构造初始化，再使用swap函数将当前对象与tmp进行交换。

3.1.2 赋值运算符重载

传统写法：

list<T>& operator=(const list<T>& lt)
{
	if (this != &lt) //防止自己给自己赋值
	{
		clear(); //清空链表的有效结点
		for (auto& e : lt) //将lt的每个元素插入到当前链表的末尾
		{
			push_back(e);
		}
	}
	return *this; //返回当前对象的引用
}

返回当前对象的引用是为了可以支持连续赋值，清空链表的函数clear后面会讲到，现在不做过多的阐述。

现代写法：

list<T>& operator=(list<T> lt)
{
	swap(lt);
	return *this;
}

这里使用传值传参，lt是使用拷贝构造函数构造出来的临时对象，再调用swap函数将当前对象与临时对象lt交换即可。代码非常简洁，可读性强。

3.1.3 析构函数

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

先调用清空链表的函数clear将链表中所有的有效结点释放掉，然后将哨兵位结点释放掉，最后将哨兵位结点指针指向空，_size置为0即可。

3.2 增删查改

3.2.1 数据访问

T& front()
{
	return *begin();
}
const T& front() const
{
	return *begin();
}
T& back()
{
	return *(--end());
}
const T& back() const
{
	return *(--end());
}

这里复用了迭代器相关的函数begin和end。

3.2.2 insert

iterator insert(iterator position, const T& val)
{
	Node* cur = position.node;
	Node* prev = cur->_prev;
	Node* newnode = new Node(val);

	prev->_next = newnode;
	newnode->_prev = prev;
	newnode->_next = cur;
	cur->_prev = newnode;
	++_size;
	return iterator(newnode);
}

void insert(iterator position, size_t n, const T& val)
{
	Node* cur = position.node;
	Node* prev = cur->_prev;
	for (size_t i = 0; i < n; i++)
	{
		Node* newnode = new Node(val);
		prev->_next = newnode;
		newnode->_prev = prev;
		prev = newnode;
	}
	prev->_next = cur;
	cur->_prev = prev;
	_size += n;
}

template <class InputIterator>
void insert(iterator position, InputIterator first, InputIterator last)
{
	Node* cur = position.node;
	Node* prev = cur->_prev;
	while (first != last)
	{
		Node* newnode = new Node(*first);
		prev->_next = newnode;
		newnode->_prev = prev;
		prev = newnode;
		++_size;
		++first;
	}
	prev->_next = cur;
	cur->_prev = prev;
}

注意：当数据类型为int时，要执行插入函数lt.insert(lt.begin(), 1, 1);时，模板实例化出来的函数（iterator,int,int）比原本的函数（iterator,size_t,int）更加匹配，编译器会优先调用更加匹配的函数，从而引发错误。

解决办法：再写一个参数类型为（iterator,int,int）的插入函数，让编译器优先调用这个函数，而不是模板实例化出的函数。

void insert(iterator position, int n, const T& val)
{
	Node* cur = position.node;
	Node* prev = cur->_prev;
	for (int i = 0; i < n; i++)
	{
		Node* newnode = new Node(val);
		prev->_next = newnode;
		newnode->_prev = prev;
		prev = newnode;
	}
	prev->_next = cur;
	cur->_prev = prev;
	_size += n;
}

3.2.3 erase

iterator erase(iterator position)
{
	assert(!empty());
	assert(position != end());
	Node* del = position.node;
	Node* prev = del->_prev;
	Node* cur = del->_next;

	prev->_next = cur;
	cur->_prev = prev;
	delete del;
	del = nullptr;
	--_size;
	return iterator(cur);
}

该函数的作用是删除指定迭代器位置的结点，因为迭代器指向的结点被删除，导致迭代器失效，所以要返回被删除结点的下一个结点的迭代器。

iterator erase(iterator first, iterator last)
{
	assert(!empty());
	assert(first != end());
	Node* prev = (first.node)->_prev;
	Node* next = last.node;
	while (first != last)
	{
		iterator tmp(first++);
		delete tmp.node;
		--_size;
	}
	prev->_next = next;
	next->_prev = prev;
	return last;
}

该函数的作用是删除指定迭代器区间的所有结点（左闭右开[first,last)），指定迭代器区间内的所有迭代器都失效了，所以返回指定迭代器区间的下一个迭代器，即last。

list的迭代器失效

迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

3.2.4 剩下的直接复用

void push_back(const T& val)
{
	insert(end(), val);
}

void push_front(const T& val)
{
	insert(begin(), val);
}

void pop_front()
{
	assert(!empty());
	erase(begin());
}

void pop_back()
{
	assert(!empty());
	erase(--end());
}

3.2.5 resize

该函数的作用是调整链表的长度，如果n小于_size，则从尾部开始删除结点至链表的长度为n，如果n大于_size，则从链表的尾部开始依次增加值为val的结点，直到链表的长度为n。

void resize(size_t n, const T& val = T())
{
	if (n < _size)
	{
		size_t len = _size - n;
		for (size_t i = 0; i < len; i++)
		{
			pop_back();
		}
	}
	else {
		size_t len = n - _size;
		for (size_t i = 0; i < len; i++)
		{
			push_back(val);
		}
	}
}

3.2.6 clear

该函数的功能是清空链表的有效结点，但是保留哨兵位结点（头节点）。

void clear()
{
	iterator it = begin();
	while (it != end())
	{
		it = erase(it); //迭代器it失效后，it指向下一个结点
		it++;
	}
	phead->_next = phead;
	phead->_prev = phead;
	_size = 0;
}

注意：不要忘了将头节点的_next和_prev指针指向自己。

3.2.7 swap

该函数的作用是将两个链表交换。

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

上述该函数是成员函数。

template<class T>
void swap(list<T>& left, list<T>& right)
{
	left.swap(right);
}

上述该函数是在类外声明和定义的，也用于交换两个链表。

为什么还要手动再实现一个swap函数，不能用库函数std::swap吗？

因为库函数std::swap还需要用第三个变量来进行交换，这样会导致有很多不必要的拷贝，导致效率下降。直接复用成员函数swap，交换两个对象的成员即可。

3.3 其它函数

3.3.1 empty

该函数的功能是判断链表是否为空。

bool empty() const
{
	return phead->_next == phead;
}

3.3.2 size

该函数的功能是获取链表的长度。

size_t size() const
{
	return _size;
}

3.3.3 printContainer

该函数的功能是打印容器里的元素。

template <class Container>
void printContainer(const Container& container)
{
	cout << "[";
	bool vis = true;
	for (const auto& e : container)
	{
		if (!vis) {
			cout << ", ";
		}
		cout << e;
		vis = false;
	}
	cout << "]" << endl;
}

3.4 反向迭代器

反向迭代器的++就是正向迭代器的–，反向迭代器的–就是正向迭代器的++，因此反向迭代器的实现可以借助正向迭代器，即：反向迭代器内部可以包含一个正向迭代器，对正向迭代器的接口进行包装即可。

reverse_iterator.h头文件

#pragma once
template<class iterator,class Ref,class Ptr>
struct ReverseIterator
{
	typedef ReverseIterator<iterator, Ref, Ptr> Self;
	ReverseIterator(iterator it)
		:lt(it)
	{}
	Ref operator*()
	{
		iterator tmp(lt);
		--tmp;
		return *tmp;
	}
	Ptr operator->()
	{
		return &(operator*());
	}
	Self& operator++()
	{
		lt--;
		return *this;
	}
	Self& operator--()
	{
		lt++;
		return *this;
	}
	Self operator++(int)
	{
		Self tmp(*this);
		lt--;
		return tmp;
	}
	Self operator--(int)
	{
		Self tmp(*this);
		lt++;
		return tmp;
	}
	bool operator!=(const Self& l)
	{
		return lt != l.lt;
	}
	bool operator==(const Self& l)
	{
		return lt == l.lt;
	}
	iterator lt;
};

list类内部要包含反向迭代器

typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;
reverse_iterator rbegin()
{
	return reverse_iterator(end());
}
reverse_iterator rend()
{
	return reverse_iterator(begin());
}
const_reverse_iterator rbegin() const
{
	return const_reverse_iterator(end());
}
const_reverse_iterator rend() const
{
	return const_reverse_iterator(begin());
}

迭代器萃取版本的反向迭代器：

#pragma once
template<class iterator>
struct ReverseIterator
{
    // 注意：此处typename的作用是明确告诉编译器，Ref是Iterator类中的类型，而不是静态成员变量
    // 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量 
    // 因为静态成员变量也是按照类名::静态成员变量名的方式访问的
	typedef typename iterator::Ref Ref;
	typedef typename iterator::Ptr Ptr;
	typedef ReverseIterator<iterator> Self;
	ReverseIterator(iterator it)
		:_it(it)
	{
	}
	Ref operator*()
	{
		iterator tmp(_it);
		--tmp;
		return *tmp;
	}
	Ptr operator->()
	{
		return &(operator*());
	}
	Self& operator++()
	{
		_it--;
		return *this;
	}
	Self& operator--()
	{
		_it++;
		return *this;
	}
	Self operator++(int)
	{
		Self tmp(*this);
		_it--;
		return tmp;
	}
	Self operator--(int)
	{
		Self tmp(*this);
		_it++;
		return tmp;
	}
	bool operator!=(const Self& l)
	{
		return _it != l._it;
	}
	bool operator==(const Self& l)
	{
		return _it == l._it;
	}
	iterator _it;
};

迭代器萃取版本的反向迭代器有个弊端，如果容器迭代器就是原生指针T*（比如vector,string）呢？ T*可不是一个类，不能通过域作用符::去访问类成员。

在侯捷老师的STL源码剖析这本书中有相关的内容：

从上面可以看到：针对原生指针又设计出了“偏特化版”的反向迭代器类模板。

注意：“偏特化版”的类模板需要在第一个类模板（主模板）实现后才能声明和定义，它不能单独存在。因为主模板的声明中不允许使用模板参数列表。

完整代码：

#pragma once
template<class iterator>
struct ReverseIterator
{
	// 注意：此处typename的作用是明确告诉编译器，Ref是Iterator类中的类型，而不是静态成员变量
	// 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量 
	// 因为静态成员变量也是按照类名::静态成员变量名的方式访问的
	typedef typename iterator::Ref Ref;
	typedef typename iterator::Ptr Ptr;
	typedef ReverseIterator<iterator> Self;
	ReverseIterator(iterator it)
		:_it(it)
	{
	}
	Ref operator*()
	{
		iterator tmp(_it);
		--tmp;
		return *tmp;
	}
	Ptr operator->()
	{
		return &(operator*());
	}
	Self& operator++()
	{
		_it--;
		return *this;
	}
	Self& operator--()
	{
		_it++;
		return *this;
	}
	Self operator++(int)
	{
		Self tmp(*this);
		_it--;
		return tmp;
	}
	Self operator--(int)
	{
		Self tmp(*this);
		_it++;
		return tmp;
	}
	bool operator!=(const Self& l)
	{
		return _it != l._it;
	}
	bool operator==(const Self& l)
	{
		return _it == l._it;
	}
	iterator _it;
};

template<class T>
struct ReverseIterator<T*>
{
	typedef T& Ref;
	typedef T* Ptr;
	typedef ReverseIterator<T*> Self;
	ReverseIterator(T* it)
		:lt(it)
	{
	}
	Ref operator*()
	{
		T* tmp(lt);
		--tmp;
		return *tmp;
	}
	Ptr operator->()
	{
		return &(operator*());
	}
	Self& operator++()
	{
		lt--;
		return *this;
	}
	Self& operator--()
	{
		lt++;
		return *this;
	}
	Self operator++(int)
	{
		Self tmp(*this);
		lt--;
		return tmp;
	}
	Self operator--(int)
	{
		Self tmp(*this);
		lt++;
		return tmp;
	}
	bool operator!=(const Self& l)
	{
		return lt != l.lt;
	}
	bool operator==(const Self& l)
	{
		return lt == l.lt;
	}
	T* lt;
};

template<class T>
struct ReverseIterator<const T*>
{
	typedef const T& Ref;
	typedef const T* Ptr;
	typedef ReverseIterator<const T*> Self;
	ReverseIterator(const T* it)
		:lt(it)
	{
	}
	Ref operator*()
	{
		const T* tmp(lt);
		--tmp;
		return *tmp;
	}
	Ptr operator->()
	{
		return &(operator*());
	}
	Self& operator++()
	{
		lt--;
		return *this;
	}
	Self& operator--()
	{
		lt++;
		return *this;
	}
	Self operator++(int)
	{
		Self tmp(*this);
		lt--;
		return tmp;
	}
	Self operator--(int)
	{
		Self tmp(*this);
		lt++;
		return tmp;
	}
	bool operator!=(const Self& l)
	{
		return lt != l.lt;
	}
	bool operator==(const Self& l)
	{
		return lt == l.lt;
	}
	const T* lt;
};

四. list和vector的对比

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：

最后

list的模拟实现介绍到这里就结束了，对以上内容有异议或者需要补充的，欢迎大家来讨论！

本文整体代码：list的模拟实现