C++STL----list的模拟实现

list模拟实现的大致框架

#include

using namespace std;

namespace lhj
{
    template<class T>
	//单个节点
	//内部框架
	struct list_node
	{};
    
    //迭代器: 像指针一样的对象
	template<class T,class Ref,class Ptr>
	//使迭代器类型泛型化，Ref，Ptr是普通类型，那么迭代器就是普通类型
	//Ref，Ptr是const类型，迭代器就是const类型
	struct __list_iterator
    {};
    
	template<class T>
	class list
	{
	public:
        typedef __list_iterator<T,T&,T*> iterator;
		typedef __list_iterator<T,const T&,const T*>const_iterator;
        //......
    private:
		typedef list_node<T> Node;//将单个节点的类型 重命名为Node 便于书写
		Node* _head;
	};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

节点类的模拟实现

template<class T>
//单个节点
//内部框架
struct list_node
{
	T _data;
	//指向节点的指针，类型为节点的类型
	list_node* _next;
	list_node* _prev;
	list_node(const T& x=T())//构造函数初始化
		:_data(x)
		,_next(nullptr)
		,_prev(nullptr)
	{}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

注意： 若构造结点时未传入数据，则默认以list容器所存储类型的默认构造函数所构造出来的值为传入数据。

迭代器类的模拟实现

迭代器类存在的意义

总结： list迭代器类，实际上就是对结点指针进行了封装，对其各种运算符进行了重载，使得结点指针的各种行为看起来和普通指针一样。（例如，对结点指针自增就能指向下一个结点）

迭代器类的模板参数说明

在list的模拟实现当中，typedef了两个迭代器类型，普通迭代器和const迭代器。

typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;
1
2

迭代器类中

template<class T,class Ref,class Ptr>
//使迭代器类型泛型化，Ref，Ptr是普通类型，那么迭代器就是普通类型
//Ref，Ptr是const类型，迭代器就是const类型
1
2
3

若该迭代器类不设计三个模板参数，那么就不能很好的区分普通迭代器和const迭代器。

迭代器类的模拟实现

template<class T,class Ref,class Ptr>
//使迭代器类型泛型化，Ref，Ptr是普通类型，那么迭代器就是普通类型
//Ref，Ptr是const类型，迭代器就是const类型
struct __list_iterator
{
	typedef list_node<T> Node;
	typedef __list_iterator<T,Ref,Ptr> iterator;
	Node* _node;//迭代器的本质就是指针，故需要定义一个节点的指针
	//构造函数，用一个节点的指针来初始化迭代器
	__list_iterator(Node* node)
		:_node(node)
	{}
	//迭代器不需要提供析构函数
	//_node为指针，属于内置类型
	//同时不需要写拷贝构造函数
	//默认的浅拷贝就是迭代器所需要的	
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

++运算符的重载

前置++原本的作用是将数据自增，然后返回自增后的数据。

先记录当前结点指针的指向，然后让结点指针指向后一个结点，最后返回“自增”前的结点指针

//前置++
iterator operator++(int)
{
	iterator tmp(*this);//记录当前结点指针的指向
	_node = _node->_next; //让结点指针指向后一个结点
	return tmp;//返回自增前的结点指针
}
1
2
3
4
5
6
7

后置++，则应该让结点指针指向后一个结点，然后再返回“自增”后的结点指针

iterator operator++()
{
	_node = _node->_next;//让结点指针指向后一个结点
	return *this;//返回自增后的结点指针
}
1
2
3
4
5

注意：iterator是当前迭代器类实例化出来的一个对象类型

–运算符的重载

iterator operator--()
{
	_node = _node->_prev;
	return *this;
}
//--it
iterator operator--(int)
{
	iterator tmp(*this);
	_node = _node->_prev;
	return tmp;
}
1
2
3
4
5
6
7
8
9
10
11
12

！=与==运算符的重载

bool operator!=(const iterator& it)const
{
	//迭代器之间的比较
	return _node != it._node;
}
bool operator==(const iterator& it)const
{
	//迭代器之间的比较
	return _node == it._node;
}
1
2
3
4
5
6
7
8
9
10

*运算符的重载

对指针变量进行解引用是为了得到该变量的数据内容。故直接返回当前结点指针所指结点的数据，但是这里需要使用引用返回，因为解引用后可能需要对数据进行修改。

Ref operator*()
{
	return _node->_data;//返回结点指针所指结点的数据
}
1
2
3
4

->运算符的重载

对于->运算符的重载，直接返回结点当中所存储数据的地址即可。

Ptr operator->()
{
	return &(operator*());//返回结点指针所指结点的数据的地址
    // &(operator*()) -> &(_pnode->_val)
}
1
2
3
4
5

list的模拟实现

默认成员函数

构造函数

构造一个某类型的空容器。

list<int> lt1; //构造int类型的空容器
1

使用迭代器拷贝构造某一段内容。

string s("hello world");
list<char> lt4(s.begin(),s.end()); //构造string对象某段区间的复制品
1
2

构造函数的模拟实现

void empty_init()
{
    //初始化
	//头结点的_next,_prev都是指向自己
	_head = new Node;
	_head->_next = _head;
	_haed->_prev = _head;

list()
{
    //构造函数，先新建一个节点作为头结点
	empty_init();//复用
}
//迭代器区间初始化
template <class InputIterator>
list(InputIterator first, InputIterator last)
{
	empty_init();//先要将头结点初始化
	while (first!=last)
	{
		push_back(*first);
		++first;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

拷贝构造函数

拷贝构造某类型容器的复制品。

list<int> lt3(lt2); //拷贝构造int类型的lt2容器的复制品
1

拷贝构造函数的模拟实现

拷贝构造一个对象，即需要先构造出一个头结点，然后再用被拷贝对象的迭代器区间初始化一个中间对象，然后再与拷贝对象交换

也可以在初始化出一个头结点后，将所给容器当中的数据，通过遍历的方式一个个尾插到新构造的容器后面

//方法一：
list(const list& lt)
{
	empty_init();//初始化函数
	list<T> tmp(lt.begin(), lt.end());
	swap(tmp);
}

//方法二：
list(const list<T>& lt)
{
	_head = new node; //申请一个头结点
	_head->_next = _head; //头结点的后继指针指向自己
	_head->_prev = _head; //头结点的前驱指针指向自己
	for (const auto& e : lt)
	{
		push_back(e); //将容器lt当中的数据一个个尾插到新构造的容器后面
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

赋值运算符重载函数

//传统写法
list<T>& operator=(const list<T>& lt)
{
	if (this != &lt) //避免自己给自己赋值
	{
		clear(); //清空容器
		for (const auto& e : lt)
		{
			push_back(e); //将容器lt当中的数据一个个尾插到链表后面
		}
	}
	return *this; //支持连续赋值
}

//现代写法
list<T>& operator=(list<T> lt) //编译器接收右值的时候自动调用其拷贝构造函数
{
	swap(lt); //交换这两个对象
	return *this; //支持连续赋值
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

析构函数

~list()
{
	clear();
	delete _head;
	_head = nullptr;
}
1
2
3
4
5
6

迭代器相关函数

begin和end

list的底层为带头双向循环链表，begin()为头结点的下一个结点的地址构造出来的迭代器，end()为最后一个节点的下一个位置的迭代器（最后一个结点的下一个结点就是头结点）

iterator begin()
{
	//返回头结点的下一个结点的地址构造出来的迭代器
	return iterator(_head->_next);
}
iterator end()
{
	//返回使用头结点的地址构造出来的普通迭代器
	return iterator(_head);
}
const_iterator begin() const
{
	//返回头结点的下一个结点的地址构造出来的const迭代器
	return const_iterator(_head->_next);
}
const_iterator end() const
{
	//返回使用头结点的地址构造出来的const迭代器
	return const_iterator(_head);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

元素修改相关函数

front和back

front和back函数分别用于获取第一个有效数据和最后一个有效数据.

T& front()
{
	return *begin(); //返回第一个有效数据的引用
}
T& back()
{
	return *(--end()); //返回最后一个有效数据的引用
}
const T& front() const
{
	return *begin(); //返回第一个有效数据的const引用
}
T& back()
{
	return *(--end()); //返回最后一个有效数据的引用
}
const T& back() const
{
	return *(--end()); //返回最后一个有效数据的const引用
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

insert

list中的插入节点与数据结构中的插入节点一样。

iterator insert(iterator pos, const T& x)
{
    assert(pos._pnode); //检测pos的合法性
	Node* cur = pos._node;//迭代器pos处的结点指针
	Node* prev = cur->_prev;//迭代器pos前一个位置的结点指针
	Node* newnode = new Node(x)//根据所给数据x构造一个待插入结点
    //建立newnode与prev之间的双向关系    
	prev->_next = newnode;
	newnode->_prev = prev;
    //建立newnode与cur之间的双向关系    
	newnode->_next = cur;
	cur->_prev = newnode;

	return iterator(newnode);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

erase

iterator erase(iterator pos)
{
	assert(pos != end());//检测pos的合法性
	assert(pos != end()); //删除的结点不能是头结点	
    
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* next = cur->_next;
    
	//建立prev与next之间的双向关系
	prev->_next = next;
	next->_prev = prev;
	delete cur;//释放cur结点

	return iterator(next);//返回所给迭代器pos的下一个迭代器
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

push_back和pop_back

push_back和pop_back函数分别用于list的尾插和尾删，在已经实现了insert和erase函数的情况下，我们可以通过复用函数来实现push_back和pop_back函数。

//尾插
void push_back(const T& x)
{
	insert(end(), x); //在头结点前插入结点
}
//尾删
void pop_back()
{
	erase(--end()); //删除头结点的前一个结点
}
1
2
3
4
5
6
7
8
9
10

push_front和pop_front

头插和头删的push_front和pop_front函数也可以复用insert和erase函数来实现。

//头插
void push_front(const T& x)
{
	insert(begin(), x); //在第一个有效结点前插入结点
}
//头删
void pop_front()
{
	erase(begin()); //删除第一个有效结点
}
1
2
3
4
5
6
7
8
9
10

其他函数

size

size函数用于获取当前容器当中的有效数据个数，因为list是链表，所以只能通过遍历的方式逐个统计有效数据的个数。

size_t size() const
{
	size_t sz = 0; //统计有效数据个数
	const_iterator it = begin(); //获取第一个有效数据的迭代器
	while (it != end()) //通过遍历统计有效数据个数
	{
		sz++;
		it++;
	}
	return sz; //返回有效数据个数
}
1
2
3
4
5
6
7
8
9
10
11

扩展： 其实也可以给list多设置一个成员变量size，用于记录当前容器内的有效数据个数。

resize

实现resize的方法：设置一个变量len，用于记录当前所遍历的数据个数，然后开始遍历容器

在遍历过程中：

当len大于或是等于n时遍历结束，此时说明该结点后的结点都应该被释放，将之后的结点释放即可。
当容器遍历完毕，说明容器当中的有效数据个数小于n，则需要尾插结点，直到容器当中的有效数据个数为n时停止尾插即可。

void resize(size_t n, const T& val = T())
{
	iterator i = begin(); //获取第一个有效数据的迭代器
	size_t len = 0; //记录当前所遍历的数据个数
	while (len < n&&i != end())
	{
		len++;
		i++;
	}
	if (len == n) //说明容器当中的有效数据个数大于或是等于n
	{
		while (i != end()) //只保留前n个有效数据
		{
			i = erase(i); //每次删除后接收下一个数据的迭代器
		}
	}
	else //说明容器当中的有效数据个数小于n
	{
		while (len < n) //尾插数据为val的结点，直到容器当中的有效数据个数为n
		{
			push_back(val);
			len++;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

clear

void clear()
{
	//clear是清除头结点以外的所有节点
	//析构函数才是清除包括头结点的所有节点
	iterator it = begin();
	while (it!=end())
	{
		it = erase(it);//erase会返回下一个位置的迭代器
		//故不需要it++
	}
}
1
2
3
4
5
6
7
8
9
10
11

swap

void swap(list<T>& lt)
{
	::swap(_head, lt._head); //交换两个容器当中的头指针即可
}
1
2
3
4

注意： 在此处调用库当中的swap函数需要在swap之前加上“::”（作用域限定符），告诉编译器这里优先在全局范围寻找swap函数，否则编译器会认为你调用的就是你正在实现的swap函数（就近原则）。