STL详解——list的模拟实现

目录

1.list的定义

2.迭代器

2.1基本功能实现

2.2const迭代器

2.2.1基本迭代器的完善

2.2.2const迭代器的基本实现

2.2.3模板优化语法

2.3自定义类型数据迭代器

2.3.1使用情景

2.3.2嵌套类模板

3.其他接口的实现

3.1insert与erase

3.2头插与头删

3.3析构与拷贝构造

3.4赋值运算符重载与构造扩展

1.list的定义

STL中的list容器不同于数据结构中常见的单链表，而是一种带头双向链表，因此在实现过程中也以此结构为基础实现。对于链表，最基本的便的其结点，因此我们先实现结点的定义：

template<class T>
struct _list_node
{
	T val;
	_list_node* next;
	_list_node* prev;
};

 完成结点的定义后，我们便成将list容器抽象为以头结点(哨兵位)为头的多结点链，结点间能通过彼此互相访问。因此list的成员变量便是头结点(_head)。

对list进行初始化，因是带头双向链表，因此初始化就是将头结点初始化为一个next与prev都指向头的结点，但在这之前需要给_head申请(new)一个结点(Node)的空间，new自定义类型的时候会调用结点类的构造函数，因此这时还需要完善结点类的构造函数

//结点
template<class T>
struct _list_node
{
	T val;
	_list_node* next;
	_list_node* prev;

	//完善构造
	_list_node()
		:val(0)
		,next(nullptr)
		,prev(nullptr)
	{

	}
};

//list链表
template<class T>
class list
{
public:
	typedef _list_node<T> Node;

	//构造
	list()
	{
		_head = new Node;
		_head->next = _head;
		_head->prev = _head;
	}

private:
	Node* _head;
};

2.迭代器

2.1基本功能实现

迭代器的基本功能就是通过类指针的形式来遍历容器元素，对于vector这种底层为数据的容器，可以用最简单的指针来完成迭代器的封装，而list这种底层非连续空间的容器，则需要将遍历的方式封装为一种迭代器类。初步接触迭代器封装，可以通过使用来逐步实现：

namespace my_list
{
	void test01()
	{
		list<int> lt1;
		list<int>::iterator it = lt1.begin();
		while (it != lt1.end())
		{
			cout << *it << ' ';
            ++it;
		}
		cout << endl;
	}
}

迭代器最基本的使用无非就是要完成上面的功能，list最基本元素是结点，因此迭代器成员变量代表的也应是结点， 接下来要实现的便是++迭代器能完成指向下一个结点，迭代器解引用能返回结点中的值。代码如下：

	//迭代器(一、初代)
	template<class T>
	struct _list_iterator
	{
		typedef _list_node<T> Node;
        Node* _node;
		
		_list_iterator(Node* node)
			:_node(node)
		{

		}

		T& operator*()
		{
			return _node->val;
		}

		_list_iterator<T> operator++()
		{
			_node = _node->next;
			return *this;
		}

		bool operator!=(const _list_iterator<T>& it)//注意不能使用非const引用
		{
			return _node != it._node;
		}
	};

	//list链表
	template<class T>
	class list
	{
	public:
		typedef _list_node<T> Node;
		typedef _list_iterator<T> iterator;

		//构造
		list()
		{
			_head = new Node;
			_head->next = _head;
			_head->prev = _head;
		}

		//迭代器
		iterator begin()
		{
			return iterator(_head->next);
		}

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

	private:
		Node* _head;
	};

这里需要注意的是begin与end的返回值为临时对象(具有常性)不能用非const引用来接受，因此在!=重载函数中的参数选择为const引用。

下面通过push_back插入数据来检验一下：

void push_back(const T& x)
{
	Node* newnode = new Node;
	newnode->val = x;
	newnode->next = _head;
	newnode->prev = _head->prev;
	_head->prev->next = newnode;
	_head->prev = newnode;
}

namespace my_list
{
	void test01()
	{
		list<int> lt1;
		lt1.push_back(1);
		lt1.push_back(2);
		lt1.push_back(3);
		lt1.push_back(4);
		lt1.push_back(5);
		list<int>::iterator it = lt1.begin();
		while (it != lt1.end())
		{
			cout << *it << ' ';
			++it;
		}
		cout << endl;
	}
}

int main()
{
	my_list::test01();

	return 0;
}

运行结果如下：

这里也算基本完成迭代器功能。

2.2const迭代器

2.2.1基本迭代器的完善

在完成const迭代器前，先对之前的基本迭代器进行完善，即完善相对应的运算符重载。

_list_iterator<T> operator++(int)
{
	_list_iterator<T> tmp(*this);
	_node = _node->next;
	return *this;
}

_list_iterator<T>& operator--()
{
	_node = _node->prev;
	return *this;
}

_list_iterator<T> operator--(int)
{
	_list_iterator<T> tmp(*this);
	_node = _node->prev;
	return tmp;
}

bool operator== (const _list_iterator<T>& it)
{
	return _node == it._node;
}

2.2.2const迭代器的基本实现

const迭代器的功能是迭代器可以修改，但让迭代器指向的内容不能修改。因此这里的迭代器不能像vector中的直接在iterator前加const修饰，因为vector中迭代器底层是指针，const修饰的实际是指针类型；而list中迭代器是一种自定义类型，使用const修饰的效果为迭代器不能修改，但迭代器指向的内容可以修改。

因此这里要实现const迭代器功能主要是让解引用返回的对象不能修改，也就是让返回值变为const T&即可。

但这里的iterator需变为const_iterator，类的类型发生了改变，因此这里需要再重新创建一个const迭代器类：

//二、const迭代器
template<class T>
struct _list_iterator
{
	typedef _list_node<T> Node;
	Node* _node;

	_list_iterator(Node* node)
		:_node(node)
	{

	}

	T& operator*()
	{
		return _node->val;
	}

	_list_iterator<T> operator++()
	{
		_node = _node->next;
		return *this;
	}

	bool operator!=(const _list_iterator<T>& it)
	{
		return _node != it._node;
	}

	_list_iterator<T> operator++(int)
	{
		_list_iterator<T> tmp(*this);
		_node = _node->next;
		return *this;
	}

	_list_iterator<T>& operator--()
	{
		_node = _node->prev;
		return *this;
	}

	_list_iterator<T> operator--(int)
	{
		_list_iterator<T> tmp(*this);
		_node = _node->prev;
		return tmp;
	}

	bool operator== (const _list_iterator<T>& it)
	{
		return _node == it._node;
	}
};

template<class T>
struct _list_const_iterator
{
	typedef _list_node<T> Node;
	Node* _node;

	_list_const_iterator(Node* node)
		:_node(node)
	{

	}

	_list_const_iterator(const _list_iterator<T>& it)
		:_node(it._node)
	{ }

	const T& operator*()
	{
		return _node->val;
	}

	_list_const_iterator<T> operator++()
	{
		_node = _node->next;
		return *this;
	}

	bool operator!=(const _list_const_iterator<T>& it)
	{
		return _node != it._node;
	}

	_list_const_iterator<T> operator++(int)
	{
		_list_const_iterator<T> tmp(*this);
		_node = _node->next;
		return *this;
	}

	_list_const_iterator<T>& operator--()
	{
		_node = _node->prev;
		return *this;
	}

	_list_const_iterator<T> operator--(int)
	{
		_list_const_iterator<T> tmp(*this);
		_node = _node->prev;
		return tmp;
	}

	bool operator== (const _list_const_iterator<T>& it)
	{
		return _node == it._node;
	}
};

list中迭代器相关函数const重载如下:

//迭代器
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);
}

在const迭代器类中为支持非const迭代器转换为const迭代器，重载了使用迭代器初始化的拷贝构造。

这里能不能将代码进行简化呢？

2.2.3模板优化语法

const迭代器仅仅是在解引用时返回值不同，按前面写法便要写两个类。若这时将解引用返回的类型用模板表示，这时通过不同的模板实例化也能区分两种类。具体实现方法如下：

//二、const迭代器
template<class T, class Ref>
struct _list_iterator
{
	typedef _list_node<T> Node;
	typedef _list_iterator<T, Ref> Self;

	Node* _node;

	_list_iterator(Node* node)
		:_node(node)
	{

	}

	_list_iterator(const _list_iterator<T, T&>& it)
		:_node(it._node)
	{

	}

	Ref operator*()
	{
		return _node->val;
	}

	Self operator++()
	{
		_node = _node->next;
		return *this;
	}

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

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

	Self& operator--()
	{
		_node = _node->prev;
		return *this;
	}

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

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

这样通过模板实例化的不同也能实现const迭代器与普通迭代器的分离。

2.3自定义类型数据迭代器

2.3.1使用情景

list作为一种顺序容器，除储存内置类型外，也可储存自定义类型，如储存位置数据(Pos)：

struct Pos
{
	int _row;
	int _col;

	Pos(int row = 0, int col = 0)
		:_row(row)
		,_col(col)
	{

	}
};

void test02()
{
	list<Pos> lt1;
	list<Pos>::iterator it = lt1.begin();
	while (it != lt1.end())
	{

	}
}

对于这种自定义类型，重载的解引用出来是Pos结构体，要访问其中数据还要自己处理：

void test02()
{
	list<Pos> lt1;
	lt1.push_back({ 1,1 });
	lt1.push_back({ 2,2 });
	lt1.push_back({ 3,3 });
	list<Pos>::iterator it = lt1.begin();
	while (it != lt1.end())
	{
		cout << (*it)._row << ':' << (*it)._col << endl;
		++it;
	}
}

但在STL库中，迭代器对于这种自定义类型还提供了类似结构体指针的访问方法：

但对于我们自己的list容器，迭代器并不是指向该自定义类型指针，因此这里实际是对->运算符的重载。->的重载实际是要返回Pos的指针，这里为了区分const与非const，依旧使用模板优化语法。 

template<class T, class Ref, class Ptr>
struct _list_iterator
{
	typedef _list_node<T> Node;
	typedef _list_iterator<T, Ref, Ptr> Self;

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

但这里需要注意：->重载后返回的是结构体的指针，即整个it->代表的是结构体指针，原则上需要在it->后再使用->调用数据，但编译器简化成了一个->。

2.3.2嵌套类模板

先来看看下面场景：

template <class T>
void Print(const list<T>& lt)
{
	list<T>::const_iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << *it << ' ';
        ++it;
	}
	cout << endl;
}

运行结果如下：

可以看到这种写法是错误的，原因是在类模板未实例化时，不能去找类模板后面东西，编译器分不清const_iterator是嵌套内类，还是静态成员变量。这时可以用typename告诉编译器这里是类型：

template <class T>
void Print(const list<T>& lt)
{
	typename list<T>::const_iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << *it << ' ';
	}
	cout << endl;
}

当然也可以用auto接收迭代器：

auto it = lt.begin();

3.其他接口的实现

在实现完迭代器后，便能接着实现许多依托于迭代器功能的接口。

3.1insert与erase

insert与erase接口实现逻辑类似：

iterator insert(const iterator& pos, const T& x)
{
	Node* newnode = new Node(x);
	Node* cur = pos._node;
	
	newnode->prev = cur->prev;
	newnode->next = cur;
	cur->prev->next = newnode;
	cur->prev = newnode;
	
	return iterator(newnode);
}

iterator erase(const iterator& pos)
{
	Node* next = pos._node->next;
	Node* prev = pos._node->prev;

	next->prev = prev;
	prev->next = next;

	delete pos._node;
	return iterator(next);
}

3.2头插与头删

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

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

3.3析构与拷贝构造

void empty_init()
{
	_head = new Node;
	_head->next = _head;
	_head->prev = _head;
}

//构造
list()
{
	empty_init();
}

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

	const_iterator it = lt.begin();
	while (it != lt.end())
	{
		push_back(*it);
		++it;
	}
}

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

void clear()
{
	iterator it = begin();
	while (it != end())
	{
		it = erase(it);
	}
}

3.4赋值运算符重载与构造扩展

list(std::initializer_list<T> il)
{
	empty_init();
	for (const auto& e : il)
	{
		push_back(e);
	}
}

//赋值重载
void swap(list<T>& lt)
{
	if (this != &lt)
	{
		std::swap(_head, lt._head);
	}
}

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