list的模拟实现

默认成员函数

构造函数

list是一个带头双向循环链表，在构造一个list对象时，直接申请一个头结点，并让其前驱指针和后继指针都指向自己即可。
在这里插入图片描述

//构造函数
list()
{
	_head = new Node;			 //申请一个头结点
	_head->_next = _head;		//头结点的后继指针指向自己
	_head->_prev = _head;		//头结点的前驱指针指向自己
		
	_size = 0;					//用于计数，先置为0
}

拷贝构造函数

拷贝构造函数就是根据所给list容器，拷贝构造出一个对象。对于拷贝构造函数，我们先申请一个头结点，并让其前驱指针和后继指针都指向自己，然后将所给容器当中的数据，通过遍历的方式一个个尾插到新构造的容器后面即可。

list(const list<T> &lt)
		{
			//先申请一个头节点
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;

			_size = 0;
			
			//复用push_back 来对这个节点进行尾插。
			//这里和vector的拷贝构造类似，不建议使用memcoy，如果是自定义类型数据，则memcpy将会出错。
			for (auto& e : lt)
			{
				push_back(e);
			}
		}

赋值运算符重载函数

我们这里直接使用现代写法：
这里编译器接收右值的时候自动调用其拷贝构造函数，使用swap()来交换这两个对象，因为值传值传参，故交换的是临时拷贝对象。

list<T>& operator=(list<T> lt)	//编译器接收右值的时候自动调用其拷贝构造函数
	{
		swap(lt);	//交换这两个对象
		return *this;	//支持连续赋值
	}

析构函数

对对象进行析构时，首先调用clear()函数清理容器当中的数据，然后将头结点释放，最后将头指针置空即可。

//析构函数
~list()
{
	clear(); //清理容器
	delete _head; //释放头结点
	_head = nullptr; //头指针置空
}

list iterator(迭代器)

begin和end

在这里插入图片描述

iterator begin()
{
	//返回使用头结点后一个结点的地址构造出来的普通迭代器
	return iterator(_head->_next);
}
iterator end()
{
	//返回使用头结点的地址构造出来的普通迭代器
	return iterator(_head);
}

重载一对用于const对象的begin函数和end函数。

const_iterator begin() const
{
	//返回使用头结点后一个结点的地址构造出来的const迭代器
	return const_iterator(_head->_next);
}
const_iterator end() const
{
	//返回使用头结点的地址构造出来的普通const迭代器
	return const_iterator(_head);
}

list element access(访问容器相关函数)

front和back

front和back函数分别用于获取第一个有效数据和最后一个有效数据，因此，实现front和back函数时，直接返回第一个有效数据和最后一个有效数据的引用即可。

T& front()
{
	return *begin(); //返回第一个有效数据的引用
}
T& back()
{
	return *(--end()); //返回最后一个有效数据的引用
}

当然，这也需要重载一对用于const对象的front函数和back函数，因为const对象调用front和back函数后所得到的数据不能被修改。

const T& front() const
{
	return *begin(); //返回第一个有效数据的const引用
}
T& back()
{
	return *(--end()); //返回最后一个有效数据的引用
}
const T& back() const
{
	return *(--end()); //返回最后一个有效数据的const引用
}

list modifiers(修改)

insert

insert函数可以在所给迭代器之前插入一个新结点。
在这里插入图片描述
这里的逻辑与之前我们用C实现链表数据结构时候的思想差不多，具体看见数据结构 | C语言链表讲解（新手入门）.

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

			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;
		}

erase

erase函数可以删除所给迭代器位置的结点。
在这里插入图片描述

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

		return iterator(next);
	}

push_back和pop_back

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

push_back函数就是在头结点前插入结点，而pop_back就是删除头结点的前一个结点。

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

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

push_front和pop_front

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

push_front函数就是在第一个有效结点前插入结点，而pop_front就是删除第一个有效结点。

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

size

_size作为类的成员变量,当每次改变 list 的容量时，_size相应的++ 或者 -- 。

size_t size()const
	{
		return _size;
	}

empty

bool empty()const
	{
		return _size == 0;
	}

swap

swap函数用于交换两个容器，list容器当中存储的实际上就只有链表的头指针，我们将这两个容器当中的头指针交换即可。

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

秒客网