C++:list增删查改模拟实现

前言

本篇博客采用SGI版本，同时考虑到看到此篇博客大部分为初学者，为此博主仅仅给出有用片段。C++:list增删查改模拟实现就是用C++复写双链表，非常简单。难点主要在迭代器实现

一、list底层双链表验证、节点构造

1.1 list底层数据结构

list底层使用什么数据结构来实现的呢？我们先来看看SGI库中list的成员函数和初始化吧。

我们发现list实现中，只有node一个成员变量。构造函数构造出一个头尾相连的哨兵位。同时验证了list底层是一个带哨兵位的双链表。

1. 2 节点构造

节点和双链表一样有三个成员：节点数据、指向前一个节点(prev)、指向后一个节点(next)。

//节点
template<class T>
struct List_node
{
	T _data;
	List_node<T>* _prev;
	List_node<T>* _next;

	List_node(const T& x = T())
		:_data(x)
		,_prev(nullptr)
		,_next(nullptr)
	{}
};

小tips:

1. 我们这里类名和库中一样(List_node)，后续在其他类中使用时在typedef。
2. 这里类名使用struct而不是class原因在于struct默认访问权限为公有，后续其他类只都需要大量使用。如果使用class需要使用大量友元类，过于繁琐。

二、迭代器封装实现（重点、难点）

2.1 前置说明

1. 我们知道迭代器的最大用途便是遍历数据。但何时停在，迭代器指向空间存储数据时是什么…导致我们需要使用!=、++、*等操作。但自定义类型是无法支持使用这些操作符的。为此给出的解决办法是：封装加运算符重载。
2. 迭代器使用上分为普通迭代器和const迭代器（还分为单向迭代器、双向迭代器和随机访问迭代器）。其中一种最简单的实现方式就是实现两个类。但。。。我们知道两个迭代器的不同之处在于const迭代器无法修改数据，只是j相关借口（这里有*、->）不同而已便实现两个类未免过于“小题大做”。
   所以接下来我们来看看库中是如何巧妙的解决这个问题吧！
   

2.2 迭代器实现

前置说明中以及解决了如何实现一个类达到目的。接下来的实现过于简单就不单独说明了。

//迭代器封装
template<class T, class Ref, class Ptr>
struct __list_iterator
{
	typedef List_node<T> Node;//节点类名重命名
	//由于迭代器实现中,如++、--等重载函数返回值类型为__list_iterator，名字过长,这里我们重命名self意味自身
	typedef __list_iterator<T,Ref, Ptr> self;
	Node* _node;//成员变量

	__list_iterator(Node* node)//构造出一个节点
		:_node(node)
	{}

	//前置++
	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;
	}
	
	//解引用操作符重载
	Ref operator*()
	{
		return _node->_data;
	}
	
	//用于访问迭代器指向对象中存储的是自定义类型
	Ptr operator->()
	{
		return &_node->_data;
	}

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

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

三、list实现

3.1 基本框架

list模拟中，我们和库中一样，给出一个头节点_head、_size两个成员变量。同时我们将节点、迭代器进行重命名。迭代器重命名不是单纯图方便，更重要的是提供统一接口(例如sting、vector、set等接口都一样)，屏蔽底层的变量和成员函数属性，实现过程和差异。

//list模拟实现
template<class T>
class List
{
	typedef List_node<T> Node;
public:
	//迭代器重命名，提供统一的接口，屏蔽底层实现细节和差异
	typedef __list_iterator<T, T&, T*> iterator;
	typedef __list_iterator<T, const T&, const T*> const_iterator;
private:
	Node* _head;//头节点
	int _size;
};

3.2 迭代器和const迭代器

下面是begin()、end()指向一个有效双线表的位置。

实现：

const_iterator begin()const
{
	//return const_iterator(_head->_next);或
	return _head->_next;//单参数类型支持隐式类型转换
}

const_iterator end()const
{
	return _head;
}

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

iterator end()
{
	return _head;
}

3.2 构造函数、析构函数、拷贝构造、赋值重载

3.2.1 构造函数

构造函数的实现和开头中看到的一样：构造函数中调用一个函数（empty_Init）来是实现。empty_Init()用来完成初始化。（empty_Init()函数后续其他接口也要调用）

//初始化
void empty_Init()
{
	_head = new Node;
	_head->_next = _head;
	_head->_prev = _head;

	_size = 0;
}

//无参构造
List()
{
	empty_Init();
}

3.2.2 析构函数

析构函数我们调用一个clear函数来将数据全部清空，在将_head变量释放。

//析构函数
~List()
{
	clear();
	delete _head;
	_head = nullptr;
}

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

3.2.3 拷贝构造

拷贝构造时首先要初始化出一个节点，然后将需要拷贝的数据依次尾插即可（尾插接口后续给出实现）

//拷贝构造
List(const List<T>& It)
{
	empty_Init();
	for (auto e : It)
	{
		push_back(e);
	}
}

3.2.4 赋值重载

赋值重载有很多方式。比较简单的参数我们直接传值，然后将待赋值的变量和传值传参省生成的临时变量的数据进行交换即可。

void swap(const List<T>& It)
{
	std::swap(_head, It._head);
}

//赋值重载
List<T>& operator=(const List<T> It)
{
	swap(It);
	return *this;
}

3.3 任意位置插入、任意位置删除、尾插、尾删、头插、头删

3.3.1任意位置插入

首先new出待插入节点newnode，然后将pos前一个节点prev、newnode、pos相连。最后++_size即可。

iterator insert(iterator pos, const T& 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 newnode;
}

3.3.2任意位置插入删除

将待删除数据的前后节点先保存起来，然后将删除pos处节点，再将前后节点连接起来。最后–_size即可。

iterator erase(iterator pos)
{
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* next = cur->_next;
	delete cur;
	prev->_next = next;
	next->_prev = prev;

	_size--;
	return next;
}

3.3.3 尾插、尾删、头插、头删

尾插、尾删、头插、头删都是复用任意位置插入、任意位置删除接口。

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

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

void pop_back()
{
	erase(--end());
}

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

四、list功能完善

4.1 迭代器operator->()

我们先来看看下面这段代码对吗？

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

	int _a1;
	int _a2;
};

void test_list3()
{
	list<AA> lt;
	lt.push_back(AA(1, 1));
	lt.push_back(AA(2, 2));
	lt.push_back(AA(3, 3));

	list<AA>::iterator it = lt.begin();
	while (it != lt.end())
	{
		cout<<*it<<" ";
		++it;
	}
	cout << endl;
}

由于list没有重载<<，所以对存储的是自定义类型之间访问会编译报错。
那我们重载下<<运算符不就行了吗？很不幸的是C++库在list中不支持<<，很大原因也在于编译器不知到我们如何取数据

所以对于自定义类型我们可以先解引用在去访问成员，也可以在迭代器中重载operator->()函数。但需要注意的是编译器隐藏了一个->，具体原生行为如下：

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

	int _a1;
	int _a2;
};

void test_list3()
{
	list<AA> lt;
	lt.push_back(AA(1, 1));
	lt.push_back(AA(2, 2));
	lt.push_back(AA(3, 3));

	list<AA>::iterator it = lt.begin();
	while (it != lt.end())
	{
		//cout << (*it)._a1<<" "<<(*it)._a2 << endl;
		cout << it->_a1 << " " << it->_a2 << endl;
		//上面编译器访问成员变量的真正行为如下：
		//cout << it.operator->()->_a1 << " " << it.operator->()->_a1 << endl;
		++it;
	}
	cout << endl;
}

4.2 打印数据

//大多数情况模板是class还是typename是一样的，但当有未实例化模板时，必须使用typename
//template<typename T>
void print_list(const list<T>& lt)
{
	// list<T>未实例化的类模板，编译器不能去他里面去找
	// 编译器就无法list<T>::const_iterator是内嵌类型，还是静态成员变量
	// 前面加一个typename就是告诉编译器，这里是一个类型，等list<T>实例化
	// 再去类里面去取
	typename list<T>::const_iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;  
}

优化：上面打印数据是针对list，下面是针对容器的。

// 模板(泛型编程)本质，本来应该由我们干的活交给编译器
template<typename Container>
void print_container(const Container& con)
{
	typename Container::const_iterator it = con.begin();
	while (it != con.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

五·、所有代码以及测试用例

giteeC++:list增删查改模拟实现代码以及测试用例
推荐：giteeC++:list增删查改模拟实现代码（最终版本、感觉版本！！！）