欢迎来到代码驿站！

C代码

当前位置：首页 > 软件编程 > C代码

C++模拟实现list功能

时间：2022-05-01 09:15:04|栏目：C代码|点击： 次

努力的最大好处，就在于你可以选择你想要的生活，而不是被迫随遇而安。

在这里插入图片描述

list介绍

1、 list是可以在**常数范围O(1)**内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代，但list容器不适合用来做排序。
2、list的底层是一个循环双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。

构造函数

在C++98中list的构造函数加上拷贝构造函数为如下四个。下面我们就模拟实现这里的全部的构造函数。当然我们这里并没有像标准库一样使用空间配置器来创建空间，使用的是new运算符，但原理都是创建一块新的空间。

在这里插入图片描述

无参构造函数

这里我们模拟默认的构造函数，默认值为T()，其含义为：该类型的默认值int类型就为0，char类型为'\0',自定义类型会调用其构造函数来初始化这个匿名对象得到默认值。

list()		//无参默认构造函数
{
	this->m_head = new node(T());
	this->m_head->m_next = this->m_head;	//创建头结点，并让头结点的头尾相连形成循环结构
	this->m_head->m_prev = this->m_head;
}

有参构造函数

list(size_t size, const T& val=T())	//n个元素构造函数
{
	this->m_head = new node(T());	//创建头结点，并让头结点的头尾相连形成循环结构
	this->m_head->m_next = this->m_head;
	this->m_head->m_prev = this->m_head;
	while (size--)
	{
		this->push_back(val);
	}
}

注意：

1、该构造函数知道其需要用于存储n个数据的空间，所以我们使用new运算符开辟好空间，后用push_back()函数来尾插入val值。
2、该构造函数还需要实现两个重载函数，如果不实现其重载函数，会导致本来想调用n个元素构造函数时，编译器会调用到我们下面要模拟实现的模板区间构造函数。

list(long size, const T& val = T())	//n个元素构造函数
{
	assert(size > 0);
	this->m_head = new node(T());	//创建头结点，并让头结点的头尾相连形成循环结构
	this->m_head->m_next = this->m_head;
	this->m_head->m_prev = this->m_head;
	while (size--)
	{
		this->push_back(val);
	}
}

list(int size, const T& val = T())	//n个元素构造函数
{
	assert(size > 0);
	this->m_head = new node(T());	//创建头结点，并让头结点的头尾相连形成循环结构
	this->m_head->m_next = this->m_head;
	this->m_head->m_prev = this->m_head;
	while (size--)
	{
		this->push_back(val);
	}
}

可以看到，这两个重载函数与之不同的就是其参数size的类型不同，但这却是必要的，否则当我们使用以下代码时，编译器会优先与模板区间构造函数相匹配。

ZJ::list<int>L(2,1);	//不实现重载版本会调用到模板区间构造函数

并且因为构造函数2当中对参数first和last进行了解引用(*)（而int类型不能进行解引用操作）而报错。

模板区间构造函数

最后就是我们上面一直说到的模板区间构造函数了，因为该迭代器区间可以是其他容器的迭代器区间，该函数接收到的迭代器的类型是不确定的，所以我们这里需要将该构造函数设计为一个函数模板，在函数体内将该迭代器区间的数据一个个尾插到容器当中即可。

template <class InputIterator>
list(InputIterator first, InputIterator last)		//区间构造
{
	this->m_head = new node(T());	//创建头结点
	this->m_head->m_next = this->m_head;
	this->m_head->m_prev = this->m_head;
	while (first != last)
	{
		node* newnode = new node(*first);
		node* tail = this->m_head->m_prev;
		tail->m_next = newnode;
		newnode->m_prev = tail;
		newnode->m_next = this->m_head;
		this->m_head->m_prev = newnode;
		++first;
	}
}

注意：

1、该区间必须是前闭后开[obj.begin()，obj.end());

拷贝构造函数

拷贝构造的思想是我们是很容易想到的，就是遍历一遍我们要拷贝的对象obj链表，并将obj每个元素的值给this对象的每一个对应的结点，并将其每个结点都链接起来。

list(const list<T>& obj)		//拷贝构造函数
{
	this->m_head = new node(T());	//创建头结点，并让头结点的头尾相连形成循环结构
	this->m_head->m_next = this->m_head;
	this->m_head->m_prev = this->m_head;
	const_iterator it = obj.begin();
	while (it != obj.end())
	{
		node* newnode = new node(it.m_pnode->m_val);	//创建新结点并把值赋予给它

		node* tail = this->m_head->m_prev;
		tail->m_next = newnode;
		newnode->m_prev = tail;
		newnode->m_next = this->m_head;
		this->m_head->m_prev = newnode;
		++it;
	}
}

赋值运算符重载

根据我们之前的博客的往历，这里我们采用现代写法，及用obj调用拷贝构造函数创建一个临时对象temp，并将temp与我们的this指针指向的对象的指针交换即可。

list<T>& operator=(const list<T>& obj)		//赋值运算符重载
{
	if (this != &obj)	//防止自我赋值
	{
		list<T>temp(obj);
		this->swap(temp);
	}
	return *this;		//返回自己
}

注意：

1、上面的temp临时对象出了if语句时就会自动调用析构函数进行释放内存，故不会造成内存的泄漏等问题。

析构函数

析构函数这里，我就有点偷懒啦，复用了我们下面要模拟实现的pop_front()函数，大致思路就是从头到尾一个一个删除结点，并把头结点也删除并至空。

~list()		//析构函数
{
	iterator it = this->begin();

	while (it != this->end())	//复用我们写的头删，一个一个的删除，当然也可以复用尾删pop_back()和erase()
	{
		++it;
		this->pop_front();
	}

	delete this->m_head;
	this->m_head = nullptr;
}

迭代器

在C++中我们的迭代器有如下几种：

在这里插入图片描述

下面我只模拟begin()和end()迭代器。

iterator begin()
{
	return iterator(this->m_head->m_next);
}

const_iterator begin()	const
{
	return const_iterator(this->m_head->m_next);
}

iterator end()
{
	return iterator(this->m_head);
}

const_iterator end()	const
{
	return const_iterator(this->m_head);
}

上面我们模拟实现了我们的迭代器，并且有普通迭代器和const迭代器。但是我们还要了解迭代器的原理是上面，在之前我们的博客中我们说过并不是每个迭代器都是原生指针，其中我们的list就是封装了一个指针变量来达到实现iterator的结果。

typedef list_iterator<T,T&,T*> iterator;		//普通迭代器
typedef list_iterator<T,const T&,const T*> const_iterator;	//常量迭代器

可能有人会疑惑，上面这两个迭代器不都差不多嘛，只是名字不一样，为什么不直接在类型上加const，而是在模板参数上指定加上const属性呢？我们要知道由于const对象只能调用常函数，但是平时我们使用std::list时是不是可以支持 ++、-- 呢？如果是const对象，它只能调用常函数，一旦加上变成const函数，那我们的const迭代器就不能进行++、?C、' * '等,而我们要达到的效果是可以进行++、?C等，但仅仅是不能其元素的值而已。所以 我们这里封装了一个模板指针。我们通过模板的参数不同来控制它的读取操作。

迭代器构造函数

就是将一个指针传过来，并赋给我们的成员变量m_pnode。

list_iterator(node* pnode)
			:m_pnode(pnode)
		{}

迭代器关系运算符重载

因为我们要实现迭代器的相关遍历操作例如下面的代码：

ZJ::list<int>::iterator it = L1.begin();
it != L1.end()
bool operator!=(const myself&obj) const		//重载！=号
{
	return this->m_pnode != obj.m_pnode;
}

bool operator==(const myself& obj) const	//重载==号
{
	return this->m_pnode == obj.m_pnode;
}

迭代器++ --运算符重载

其中下面返回的myself类型其实就是我们的迭代器这个类的类型，只是我们将其typedef了一下代码如下：

typedef list_iterator<T, Ref, Ptr>myself;

这里重载的前置与后置要分别开来，后置需要使用int占位符来占位，不然会发生错误。

myself& operator++()		//重载前置++
{
	//由于我们的list是双向循环链表，我们的++，就是指向下一个结点
	this->m_pnode = this->m_pnode->m_next;
	return *this;
}

myself operator++(int)		//重载后置++
{
	const myself temp(*this);
	this->m_pnode = this->m_pnode->m_next;
	return temp;
}

myself& operator--()		//重载前置--
{
	//由于我们的list是双向循环链表，我们的--就是得到它上一个结点的迭代器
	this->m_pnode = this->m_pnode->m_prev;
	return *this;
}

myself operator--(int)		//重载后置--
{
	const myself temp(*this);
	this->m_pnode = this->m_pnode->m_prev;
	return temp;
}

迭代器 * 运算符重载

由于我们知道Ref是由两种类型的，一种是T&,另一种是const T&,所以当我们的对象是const对象时，我们可以控制它不让其修改。

Ref operator* ()		//重载  *
{
	return this->m_pnode->m_val;
}

迭代器 -> 运算符重载

为什么要重载->运算符呢？这是因为如果我们list中存储的是自定义类型时，我们的迭代器无法使用->去得到其成员。

Ptr operator->()		//重载 ->
{
	return &this->m_pnode->m_val;
}

总结

到了这里可能会有人会问为什么我们不写迭代器的拷贝构造函数和析构函数呢？
答：这是因为我们的迭代器是用来遍历容器中的部分或全部元素，每个迭代器对象代表容器中的确定的地址，并且这些结点元素析构和拷贝并不归我们管，结点应该归我们的list管，所以编译器默认提供的浅拷贝就已经足够了。

容量相关函数

empty()

功能：是用来获取容器中是否为空。
返回值：bool。

bool empty()	const		//判空
{
	return this->begin() == this->end();	//就是begin()与end()同时指向头结点时的情况
}

size() 

功能：是用来获取元素的个数。
返回值：size_t(无符号整型)。
注意：但是在链表中这个接口并不常用。如果频繁的调用该接口会造成性能的下降。

//遍历一遍链表来得到元素个数，为什么使用遍历一遍链表呢？
//这是因为我们使用链表时很少会去知道它的元素个数，但如果频繁的调用该接口会造成性能的下降
//此时我们应该在list类中将增加一个记录元素个数的变量size
//如果有元素插入就增加，删除就减少
size_t size()	const	//获得元素个数
{
	size_t size = 0;
	const_iterator it = this->begin();
	while(it!=this->end())
	{
		++it;
		++size;
	}
	return size;
}

元素访问相关函数

back()

  • 功能：获取最后一个元素的值。
  • 返回值：存储的类型的引用。
T& back()
{
	assert(!this->empty());
	return this->m_head->m_prev->m_val;
}

const T& back()   const
{
	assert(!this->empty());
	return this->m_head->prev->m_val;
}

front() 

  • 功能：获取第一个元素的值。
  • 返回值：存储的类型的引用。
T& front()
{
	assert(!this->empty());
	return  this->m_head->m_next->m_val;
}

const T& front() const
{
	assert(!this->empty());
	return this->m_head->m_next->m_val;
}

修改相关函数

push_back()

  • 功能：在尾部插入一个元素。
  • 返回值：void（无返回值）。
void push_back(const T& val)	//尾插
{
	node* tail = this->m_head->m_prev;	//指向尾部结点
	node* newnode = new node(val);		//创建新结点
	newnode->m_next = tail->m_next;		//将新结点的m_next指向头结点
	newnode->m_prev = tail;				//将新结点m_prev指向tail结点
	tail->m_next = newnode;				//并将原来的尾结点的m_next指向newnode
	this->m_head->m_prev = newnode;		//并将头结点的m_prev指向新的尾
}

push_front() 

  • 功能：在头部插入一个元素。
  • 返回值：void（无返回值）。
void push_front(const T& val)	//头插
{
	node* newnode = new node(val);	//创建新结点
	node*  next = this->m_head->m_next;	//指向第一个结点
	newnode->m_next = next;		//将创建的新结点newnode的m_next指向我们原来的第一个元素next
	this->m_head->m_next = newnode;	//在将我们的头结点的m_next指向新创建的结点
	newnode->m_prev = this->m_head;	//在将新结点的m_prev指向头结点
	next->m_prev = newnode;	//在将原先第一个结点元素的m_prev指向新创建的结点
}

pop_back()

  • 功能：在尾部删除一个元素。
  • 返回值：void（无返回值）。
void pop_back()		//尾删
{
	assert(!empty());	//断言 如果list已经为空，则删除不了
	node* tail = this->m_head->m_prev;	//先找到我们要删除的尾结点
	node* prev = tail->m_prev;		//再找到要删除的尾结点的前一个结点
	this->m_head->m_prev = prev;	//将头结点的m_prev指向新的尾prev
	prev->m_next = this->m_head;	//再将prev的m_next指向头结点
	tail->m_next = tail->m_prev = nullptr;	//把要删除的元素的成员至nullptr
	tail->m_val = T();		//将要删除的元素的值置为匿名对象的默认值
	delete tail;			//删除尾结点
}

pop_front()

  • 功能：在头部删除一个元素。
  • 返回值：void（无返回值）。
void pop_front()	//头删
{
	assert(!empty());	//断言 如果list已经为空，则删除不了
	node* delnode = this->m_head->m_next;	//先找到我们要删除的第一个结点位置
	node* next = delnode->m_next;			//在找到删除结点的下一个结点的位置
	this->m_head->m_next = next;			//再将头结点的m_next指向我们新的第一个结点
	next->m_prev = this->m_head;			//再将我们的新的第一个结点的m_prev指向头结点
	delnode->m_next = delnode->m_prev = nullptr;	//把要删除的元素的成员至nullptr
	delnode->m_val = T();		//将要删除的元素的值置为匿名对象的默认值
	delete delnode;		//删除第一个结点
}

insert()

在c++98中我们的insert()函数有如下三种版本：

在这里插入图片描述

下面我们就将其模拟实现：

指定位置插入一个元素

  • 功能：在指定位置插入一个元素。
  • 返回值：插入的元素的位置的迭代器。 
//插入元素到指定位置，返回的是插入的元素的迭代器
iterator insert(iterator pos, const T& val)
{
	assert(pos.m_pnode != nullptr);		//断言 迭代器是否为空指针错误
	node* newnode = new node(val);		//创建新结点

	node* cur = pos.m_pnode;		//记录当前结点的指针
	node* prev = cur->m_prev;		//记录当前结点的前一个结点的指针

	newnode->m_next = cur;
	newnode->m_prev = prev;
	prev->m_next = newnode;
	cur->m_prev = newnode;

	return iterator(newnode);		//返回一个用当前的插入的元素的结点构建的匿名对象的迭代器
}

指定位置插入n个相同的元素

  • 功能：在指定位置插入一个元素。
  • 返回值：void(无返回值)。
void insert(iterator pos, size_t n, const T& val)	//插入n个val
{
	assert(pos.m_pnode != nullptr);		//断言 迭代器是否为空指针错误
	while (n--)
	{
		node* newnode = new node(val);

		node* cur = pos.m_pnode;
		node* prev = cur->m_prev;

		newnode->m_prev = prev;
		prev->m_next = newnode;
		newnode->m_next = cur;
		cur->m_prev = newnode;
	}
}

void insert(iterator pos, int n, const T& val)	//插入n个val
{
	assert(pos.m_pnode != nullptr);		//断言 迭代器是否为空指针错误
	assert(n > 0);
	while (n--)
	{
		node* newnode = new node(val);

		node* cur = pos.m_pnode;
		node* prev = cur->m_prev;

		newnode->m_prev = prev;
		prev->m_next = newnode;
		newnode->m_next = cur;
		cur->m_prev = newnode;
	}
}

void insert(iterator pos, long n, const T& val)	//插入n个val
{
	assert(pos.m_pnode != nullptr);		//断言 迭代器是否为空指针错误
	assert(n > 0);
	while (n--)
	{
		node* newnode = new node(val);

		node* cur = pos.m_pnode;
		node* prev = cur->m_prev;

		newnode->m_prev = prev;
		prev->m_next = newnode;
		newnode->m_next = cur;
		cur->m_prev = newnode;
	}
}

注意：这里的insert在指定位置插入为什么要实现三种重载版本呢？这与上面的构造函数问题是相同类型的，都是与模板区间构造有关，这里就不多赘述了。
指定位置插入区间内的元素

  • 功能：在指定位置插入区间内的元素。
  • 返回值：void(无返回值)。
  • 注意：

1、该区间必须是前闭后开;

template <class InputIterator>
void insert(iterator pos, InputIterator first, InputIterator last)	//区间插入
{
	assert(pos.m_pnode != nullptr);		//断言 迭代器是否为空指针错误
	while (first != last)
	{
		node* newnode = new node(*first);

		node* cur = pos.m_pnode;
		node* prev = cur->m_prev;

		newnode->m_prev = prev;
		prev->m_next = newnode;
		newnode->m_next = cur;
		cur->m_prev = newnode;
		++first;
	}
}

erase()

在C++98中erase()有两种版本，一个是删除指定位置，另一个是删除区间内的元素。如下图所示：

在这里插入图片描述

删除指定位置

  • 功能：删除指定位置的元素。
  • 返回值：删除指定位置的元素的下一个结点的迭代器。
//删除指定位置的元素，返回下一个元素的迭代器，但要注意的是：
//如果删除的最后一个元素，此时返回的是头结点也就是end()位置的迭代器
iterator erase(iterator pos)			
{
	assert(pos.m_pnode != nullptr);		//断言 迭代器是否为空指针错误
	assert(pos != end());				//断言 list内元素为空及删除头结点的情况
	
	node* next = pos.m_pnode->m_next;
	node* prev = pos.m_pnode->m_prev;

	prev->m_next = next;
	next->m_prev = prev;

	pos.m_pnode->m_next = pos.m_pnode->m_prev = nullptr;
	pos.m_pnode->m_val = T();
	delete pos.m_pnode;

	return iterator(next);		
}

删除区间内的元素

  • 功能：删除区间内的元素。
  • 返回值：删除区间内的元素的下一个结点的迭代器。也就是返回last迭代器这个位置。
  • 注意：

1、该区间必须是前闭后开;

iterator erase(iterator first, iterator last)		//区间删除
{
	node* prev = first.m_pnode->m_prev;
	node* next = last.m_pnode;

	while (first != last)
	{
		node* cur = first.m_pnode;
		++first;
		cur->m_next = cur->m_prev = nullptr;
		cur->m_val = T();
		delete cur;
		cur = nullptr;
	}

	prev->m_next = next;
	next->m_prev = prev;

	return iterator(next);
}

clear()

  • 功能：用于清空我们list中的所有元素的值，但不是要把list对象也删除。
  • 返回值：void（无返回值）。
void clear()		//清空元素，而不是把整个链表删除掉
	{
		iterator it = this->begin();	

		while (it != this->end())	
		//复用我们写的头删，一个一个的删除，当然也可以复用尾删pop_back()和erase()
		{
			++it;
			this->pop_front();
		}
	}

swap()

  • 功能：swap顾名思义就是交换的意思，这里我们将这个swap作为我们的成员函数，用来交换两个list链表。
  • 返回值: void（无返回值）。
void swap(list<T>& obj)
{
	node* temp = this->m_head;
	this->m_head = obj.m_head;
	obj.m_head = temp;
}

完整代码如下

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<assert.h>
using  namespace std;

namespace ZJ
{
	template<class T>	
	class list_node		//结点
	{
	public:
		list_node(T val=T())		//构造函数
			:m_val(val)
			,m_prev(nullptr)
			,m_next(nullptr)
		{}
	public:
		T m_val;		//值
		list_node<T>* m_prev;	//指向前一个的指针
		list_node<T>* m_next;	//指向下一个的指针

	};

	template<class T,class Ref,class Ptr>		//封装一个node型指针，制作成迭代器类
	class list_iterator
	{
	public:
		typedef list_node<T> node;
		typedef list_iterator<T, Ref, Ptr>myself;
		list_iterator(node* pnode)
			:m_pnode(pnode)
		{}

		Ref operator* ()		//重载  *
		{
			return this->m_pnode->m_val;
		}

		Ptr operator->()		//重载 ->
		{
			return &this->m_pnode->m_val;
		}

		bool operator!=(const myself&obj) const		//重载！=号
		{
			return this->m_pnode != obj.m_pnode;
		}

		bool operator==(const myself& obj) const	//重载==号
		{
			return this->m_pnode == obj.m_pnode;
		}

		myself& operator++()		//重载前置++
		{
			this->m_pnode = this->m_pnode->m_next;
			return *this;
		}

		myself operator++(int)		//重载后置++
		{
			const myself temp(*this);
			this->m_pnode = this->m_pnode->m_next;
			return temp;
		}

		myself& operator--()		//重载前置--
		{
			this->m_pnode = this->m_pnode->m_prev;
			return *this;
		}

		myself operator--(int)		//重载后置--
		{
			const myself temp(*this);
			this->m_pnode = this->m_pnode->m_prev;
			return temp;
		}

	public:
		node* m_pnode;
	};

	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;	//常量迭代器

	public:
		list()		//无参默认构造函数
		{
			this->m_head = new node(T());
			this->m_head->m_next = this->m_head;
			this->m_head->m_prev = this->m_head;
		}

		list(size_t size, const T& val=T())	//n个元素构造函数
		{
			this->m_head = new node(T());
			this->m_head->m_next = this->m_head;
			this->m_head->m_prev = this->m_head;
			while (size--)
			{
				this->push_back(val);
			}
		}

		list(long size, const T& val = T())	//n个元素构造函数
		{
			assert(size > 0);
			this->m_head = new node(T());
			this->m_head->m_next = this->m_head;
			this->m_head->m_prev = this->m_head;
			while (size--)
			{
				this->push_back(val);
			}
		}

		list(int size, const T& val = T())	//n个元素构造函数
		{
			assert(size > 0);
			this->m_head = new node(T());
			this->m_head->m_next = this->m_head;
			this->m_head->m_prev = this->m_head;
			while (size--)
			{
				this->push_back(val);
			}
		}

		template <class InputIterator>
		list(InputIterator first, InputIterator last)		//区间构造
		{
			this->m_head = new node(T());
			this->m_head->m_next = this->m_head;
			this->m_head->m_prev = this->m_head;
			while (first != last)
			{
				node* newnode = new node(*first);
				node* tail = this->m_head->m_prev;
				tail->m_next = newnode;
				newnode->m_prev = tail;
				newnode->m_next = this->m_head;
				this->m_head->m_prev = newnode;
				++first;
			}
		}
		
		list(const list<T>& obj)		//拷贝构造函数
		{
			this->m_head = new node(T());
			this->m_head->m_next = this->m_head;
			this->m_head->m_prev = this->m_head;
			const_iterator it = obj.begin();
			while (it != obj.end())
			{
				node* newnode = new node(it.m_pnode->m_val);

				node* tail = this->m_head->m_prev;
				tail->m_next = newnode;
				newnode->m_prev = tail;
				newnode->m_next = this->m_head;
				this->m_head->m_prev = newnode;
				++it;
			}
		}

		list<T>& operator=(const list<T>& obj)		//赋值运算符重载
		{
			if (this != &obj)
			{
				list<T>temp(obj);
				this->swap(temp);
			}
			return *this;
		}


		~list()		//析构函数
		{
			iterator it = this->begin();

			while (it != this->end())	//复用我们写的头删，一个一个的删除，当然也可以复用尾删pop_back()和erase()
			{
				++it;
				this->pop_front();
			}

			delete this->m_head;
			this->m_head = nullptr;
		}

		iterator begin()
		{
			return iterator(this->m_head->m_next);
		}

		const_iterator begin()	const
		{
			return const_iterator(this->m_head->m_next);
		}

		iterator end()
		{
			return iterator(this->m_head);
		}

		const_iterator end()	const
		{
			return const_iterator(this->m_head);
		}

		bool empty()	const		//判空
		{
			return this->begin() == this->end();	//就是begin()与end()同时指向头结点时的情况
		}

		//遍历一遍链表来得到元素个数，为什么使用遍历一遍链表呢？
		//这是因为我们使用链表时很少会去知道它的元素个数，但如果频繁的调用该接口会造成性能的下降
		//此时我们应该在list类中将增加一个记录元素个数的变量size
		//如果有元素插入就增加，删除就减少
		size_t size()	const	//获得元素个数
		{
			size_t size = 0;
			const_iterator it = this->begin();
			while(it!=this->end())
			{
				++it;
				++size;
			}
			return size;
		}

		T& back()
		{
			assert(!this->empty());
			return this->m_head->m_prev->m_val;
		}

		const T& back()   const
		{
			assert(!this->empty());
			return this->m_head->prev->m_val;
		}

		T& front()
		{
			assert(!this->empty());
			return  this->m_head->m_next->m_val;
		}

		const T& front() const
		{
			assert(!this->empty());
			return this->m_head->m_next->m_val;
		}

		void push_front(const T& val)	//头插
		{
			node* newnode = new node(val);
			node*  next = this->m_head->m_next;
			newnode->m_next = next;
			this->m_head->m_next = newnode;
			newnode->m_prev = this->m_head;
			next->m_prev = newnode;
		}

		void push_back(const T& val)	//尾插
		{
			node* tail = this->m_head->m_prev;
			node* newnode = new node(val);
			newnode->m_next = tail->m_next;
			newnode->m_prev = tail;
			tail->m_next = newnode;
			this->m_head->m_prev = newnode;
		}


		//插入元素到指定位置，返回的是插入的元素的迭代器
		iterator insert(iterator pos, const T& val)
		{
			assert(pos.m_pnode != nullptr);		//断言 迭代器是否为空指针错误
			node* newnode = new node(val);		//创建新结点

			node* cur = pos.m_pnode;		//记录当前结点的指针
			node* prev = cur->m_prev;		//记录当前结点的前一个结点的指针

			newnode->m_next = cur;
			newnode->m_prev = prev;
			prev->m_next = newnode;
			cur->m_prev = newnode;

			return iterator(newnode);		//返回一个用当前的插入的元素的结点构建的匿名对象的迭代器
		}

		void insert(iterator pos, size_t n, const T& val)	//插入n个val
		{
			assert(pos.m_pnode != nullptr);		//断言 迭代器是否为空指针错误
			while (n--)
			{
				node* newnode = new node(val);

				node* cur = pos.m_pnode;
				node* prev = cur->m_prev;

				newnode->m_prev = prev;
				prev->m_next = newnode;
				newnode->m_next = cur;
				cur->m_prev = newnode;
			}
		}

		void insert(iterator pos, int n, const T& val)	//插入n个val
		{
			assert(pos.m_pnode != nullptr);		//断言 迭代器是否为空指针错误
			assert(n > 0);
			while (n--)
			{
				node* newnode = new node(val);

				node* cur = pos.m_pnode;
				node* prev = cur->m_prev;

				newnode->m_prev = prev;
				prev->m_next = newnode;
				newnode->m_next = cur;
				cur->m_prev = newnode;
			}
		}

		void insert(iterator pos, long n, const T& val)	//插入n个val
		{
			assert(pos.m_pnode != nullptr);		//断言 迭代器是否为空指针错误
			assert(n > 0);
			while (n--)
			{
				node* newnode = new node(val);

				node* cur = pos.m_pnode;
				node* prev = cur->m_prev;

				newnode->m_prev = prev;
				prev->m_next = newnode;
				newnode->m_next = cur;
				cur->m_prev = newnode;
			}
		}

		template <class InputIterator>
		void insert(iterator pos, InputIterator first, InputIterator last)	//区间插入
		{
			assert(pos.m_pnode != nullptr);		//断言 迭代器是否为空指针错误
			while (first != last)
			{
				node* newnode = new node(*first);

				node* cur = pos.m_pnode;
				node* prev = cur->m_prev;

				newnode->m_prev = prev;
				prev->m_next = newnode;
				newnode->m_next = cur;
				cur->m_prev = newnode;
				++first;
			}
		}

		void pop_front()	//头删
		{
			assert(!empty());	//断言 如果list已经为空，则删除不了
			node* delnode = this->m_head->m_next;
			node* next = delnode->m_next;
			this->m_head->m_next = next;
			next->m_prev = this->m_head;
			delnode->m_next = delnode->m_prev = nullptr;
			delnode->m_val = T();
			delete delnode;
		}

		void pop_back()		//尾删
		{
			assert(!empty());	//断言 如果list已经为空，则删除不了
			node* tail = this->m_head->m_prev;
			node* prev = tail->m_prev;
			this->m_head->m_prev = prev;
			prev->m_next = this->m_head;
			tail->m_next = tail->m_prev = nullptr;
			tail->m_val = T();
			delete tail;
		}


		//删除指定位置的元素，返回下一个元素的迭代器，但要注意的是：
		//如果删除的最后一个元素，此时返回的是头结点也就是end()位置的迭代器
		iterator erase(iterator pos)			
		{
			assert(pos.m_pnode != nullptr);		//断言 迭代器是否为空指针错误
			assert(pos != end());				//断言 list内元素为空及删除头结点的情况
			
			node* next = pos.m_pnode->m_next;
			node* prev = pos.m_pnode->m_prev;

			prev->m_next = next;
			next->m_prev = prev;

			pos.m_pnode->m_next = pos.m_pnode->m_prev = nullptr;
			pos.m_pnode->m_val = T();
			delete pos.m_pnode;

			return iterator(next);		
		}

		iterator erase(iterator first, iterator last)		//区间删除
		{
			node* prev = first.m_pnode->m_prev;
			node* next = last.m_pnode;

			while (first != last)
			{
				node* cur = first.m_pnode;
				++first;
				cur->m_next = cur->m_prev = nullptr;
				cur->m_val = T();
				delete cur;
				cur = nullptr;
			}

			prev->m_next = next;
			next->m_prev = prev;

			return iterator(next);
		}

		void clear()		//清空元素，而不是把整个链表删除掉
		{
			iterator it = this->begin();	

			while (it != this->end())	//复用我们写的头删，一个一个的删除，当然也可以复用尾删pop_back()和erase()
			{
				++it;
				this->pop_front();
			}
		}

		void swap(list<T>& obj)
		{
			node* temp = this->m_head;
			this->m_head = obj.m_head;
			obj.m_head = temp;
		}
	private:
		node* m_head;		//头指针
	};
}

上一篇：Linux线程管理必备:解析互斥量与条件变量的详解

栏    目：C代码

下一篇：基于ROS 服务通信模式详解

本文标题：C++模拟实现list功能

本文地址：http://www.codeinn.net/misctech/200679.html

更多C代码

阅读排行

推荐教程

广告投放 | 联系我们 | 版权申明

重要申明：本站所有的文章、图片、评论等，均由网友发表或上传并维护或收集自网络，属个人行为，与本站立场无关。

如果侵犯了您的权利，请与我们联系，我们将在24小时内进行处理、任何非本站因素导致的法律后果，本站均不负任何责任。

联系QQ：914707363 | 邮箱：codeinn#126.com(#换成@)

Copyright © 2020 代码驿站 版权所有