c++----list模拟实现

2024-03-31 10:52:02
开发
17

目录

1. list的基本介绍

2. list的基本使用

2.1 list的构造

2.2 list迭代器

2.3. list容量（capacity）与访问（access)

2.4 list modifiers

2.5 list的迭代器失效

3.list的模拟实现

3.1 构造、析构

3.3 list modifiers

4. list与vector的区别

1. list的基本介绍

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. list的底层是双向带头循环链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝后迭代。
4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

下图是list的底层结构。

从图中可以看出，list底层由一个双向带头循环链表构成。假设有一链表list<int> lt, 头节点为_head则lt.begin()指向_head->next, lt.end()指向_head。

2. list的基本使用

2.1 list的构造

构造函数（ (constructor)）	接口说明
list (size_type n, const value_type& val = value_type())	构造的list中包含n个值为val的元素
list()	构造空的list
list (const list& x)	拷贝构造函数
list (InputIterator first, InputIterator last)	用[first, last)区间中的元素构造list

用法示例

void list_test1()
{
	list<string> lt(5, "xy");//n val构造
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	list<string> llt(lt);//拷贝构造
	for (auto e : llt)
	{
		cout << e << " ";
	}
	cout << endl;

	list<string> lltt(++lt.begin(), --lt.end());//迭代器区间构造
	for (auto e : lltt)
	{
		cout << e << " ";
	}
}

2.2 list迭代器

函数声明	接口说明
begin + end	返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin + rend	返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的 reverse_iterator,即begin位置

用法示例

void list_test2()
{
	list<int> lt{ 1,2,3,4,5};//这样构造很奇特
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	list<int>::iterator it = lt.begin();//正向迭代器
	while (it != lt.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;

	list<int>::reverse_iterator  rit = lt.rbegin();//反向迭代器
	while (rit != lt.rend())
	{
		cout << *rit << " ";
		rit++;
	}
	cout << endl;
}

那么大家肯定会有一个疑问，之前的string，vector迭代器可以++，是因为他们的底层物理空间是连续的，但list底层可是双向带头循环链表啊，它的结构物理空间可是不连续的，我们++，不就错了吗？

不急，我们后面模拟实现的时候细讲。

2.3. list容量（capacity）与访问（access)

函数声明	接口说明
empty	检测list是否为空，是返回true，否则返回false
size	返回list中有效节点的个数

front	返回list的第一个节点中值的引用
back	返回list的最后一个节点中值的引用

用法示例

void list_test3()
{
	list<int> lt{ 1,2,3,4,5 };//这样构造很奇特
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
	cout << "链表是否为空:   ";
	if (lt.empty())
		cout << "true" << endl;
	else
		cout << "false" << endl;

	cout << "size: " << lt.size() << endl;

	cout << "Front Element: " << lt.front() << endl;

	cout << "Back Element: " << lt.back() << endl;

	lt.clear();
	cout << "已执行链表清空操作，链表是否为空:   ";
	if (lt.empty())
		cout << "true" << endl;
	else
		cout << "false" << endl;

}

2.4 list modifiers

函数声明	接口说明
push_front	在list首元素前插入值为val的元素
pop_front	删除list中第一个元素
push_back	在list尾部插入值为val的元素
pop_back	删除list中最后一个元素
insert	在list position 位置中插入值为val的元素
erase	删除list position位置的元素
swap	交换两个list中的元素
clear	清空list中的有效元素

用法示例

void list_test4()
{
	list<int> lt{ 1,2,3,4,5 };//这样构造很奇特
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	lt.push_back(0);
	lt.push_back(0);
	lt.push_front(9);
	lt.push_front(9);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	lt.pop_back();
	lt.pop_front();
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	list<int>::iterator it = lt.begin();
	while (it != lt.end())
	{
		if (*it == 5)
		{
			it = lt.erase(it);
			break;
		}
			
		it++;
	}
	lt.insert(it, 999);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
}

2.5 list的迭代器失效

这里我们将迭代器理解为指针，list的迭代器失效是因为指针所指向的空间被销毁，导致指针变为野指针。list的底层是双向带头循环链表，因此list不存在插入导致迭代器失效的问题。list的迭代器失效出现在erase内，如果该节点被删除，空间已被销毁，那么就必须更新迭代器，否则迭代器失效。

3.list的模拟实现

list的模拟实现存在几个难点，首先是使用了大量的typedef，这会让人头晕眼花，其次是模板迭代器的构建。我们快来看看吧。

注意：list的迭代器由于list底层空间不连续的问题，因此要实现和vector一样的迭代器效果（即支持*it，it++）需要对操作符进行重载，所以要封装Node*。

list需要创建一个类内类Node，用list访问Node类的变量。

下面是ListNode类，类内包含双链表节点的三要素。

template<class T>
struct ListNode//节点的创建
{
	T _Date;
	ListNode<T>* _next;
	ListNode<T>* _prev;

	ListNode(const T& x=T())//节点的构造函数
		:_Date(x)
		,_next(nullptr)
		,_prev(nullptr)
	{}
};

3.1 构造、析构

这里的构造函数为简易版本，只支持创建空链表。

void list_init()//初始化每一个节点
{
	_head = new Node;//new调用Node的默认构造，不传参
	_head->_next = _head;
	_head->_prev = _head;
}
list()
{
	list_init();
}
list(list<T>& lt)//拷贝构造
{
	list_init();//创建头节点

	for (const auto& e : lt)
	{
		push_back(e);
	}
}

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

//list& operator=(list lt)
list<T>& operator=(list<T> lt)
{
	swap(lt);
	return *this;
}
void clear()
{
	list<T>::iterator it = this->begin();
	while (it != end())
	{
		it = erase(it);
	}
}
~list()
{
	delete _head;
	_head = nullptr;
}

3.2 迭代器

前面说，要对++等操作符进行重载，这时需要重新定义iterator类封装节点的指针，通过指针对节点进行操作。且iterator类需要支持普通对象与const对象的访问，因此需要定义成模板类。

模板类iterator

template<class T,class Ref,class Ptr>
struct _list_iterator//迭代器本质就是指针，这里封装Node*,对Node的指针进行操作，重载++等操作符
{
	typedef ListNode<T> Node;
	typedef _list_iterator<T,Ref,Ptr> self;
	//typedef _list_iterator<T> self;
	Node* _node;//成员变量

public:
	_list_iterator(Node* node)//构造函数，直接用node构建
		:_node(node)
	{}
	//没有参数int ，前置＋＋
	self& operator++()//重载++
	{
		_node = _node->_next;
		return *this;
	}

	self operator++(int)//后置++
	{
		Node* tmp = _node;
		_node = _node->_next;
		return tmp;
	}


	self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}

	//返回临时对象，出函数即销毁，不可传引用
	self operator--(int)//后置--
	{
		Node* tmp = _node;
		_node = _node->_prev;
		return tmp;
	}
	Ptr operator->()
	{
		return &_node->_Date;
	}
	Ref operator*()
	{
		return _node->_Date;
	}
	bool operator!=(const self& s)
	{
		return _node != s._node;
	}
	bool operator==(const self& s)
	{
		return _node == s._node;
	}
};

list类内的迭代器函数

typedef _list_iterator<T,T&,T*> iterator; //普通对象的迭代器
typedef _list_iterator<T,const T&,const T*> const_iterator;  //const对象的迭代器
iterator begin()//指向头节点的下一个
{
	
	return _head->_next;
}

iterator end()//指向头节点
{
	return _head;
}

const_iterator begin() const//指向头节点的下一个
{

	return _head->_next;
}

const_iterator end() const//指向头节点
{
	return _head;
}

这里模板参数有三个，分别是T，T&，T*，这是为什么呢？

T&：因为重载普通迭代器的*时，返回值需要设为引用类型，以便于外界可以更改。

T*：重载->时，由于list的->逻辑不能自洽，list的重载->需要返回数据的地址

这里需要着重解释一下，如果是list<int>,那么重载->完全没有问题，但如果是list<Date>呢？

Node的数据域是自定义类型，又该怎么办呢？

因此我们返回Node.Date的地址，然后再解引用，如果是内置类型不受影响，如果是自定义类型，稍加控制就ok了。

我们来看看示例：

struct AA
{
	int _a1;
	int _a2;

	AA(int a1 = 1, int a2 = 1)
		:_a1(a1)
		, _a2(a2)
	{}
};
void test_list5()
{
	list<AA> lt;
	AA aa1;
	lt.push_back(aa1);

	lt.push_back(AA());

	AA aa2(2, 2);
	lt.push_back(aa2);

	lt.push_back(AA(2, 2));

	list<AA>::iterator it = lt.begin();
	while (it != lt.end())
	{
		std::cout << (*it)._a1 << ":" << (*it)._a2 << std::endl;
		std::cout << it.operator*()._a1 << ":" << it.operator*()._a2 << std::endl;

		std::cout << it->_a1 << ":" << it->_a2 << std::endl;
		std::cout << it.operator->()->_a1 << ":" << it.operator->()->_a2 << std::endl;

		++it;
	}
	std::cout << std::endl;
}

Node的数据域存放的是AA类对象，Node* ptr，ptr->Date就是AA类的实例化对象，此时返回AA对象的地址，也就是AA* p,p->就可以访问AA类对象的成员了。

3.3 list modifiers

这里需要注意erase的迭代器失效问题。

void push_back(const T& x=T())
{
	Node* node = new Node;
	Node* tail = _head->_prev;
	node->_Date = x;

	tail->_next = node;
	node->_next = _head;
	_head->_prev = node;
	node->_prev = tail;
}

iterator insert(iterator pos,const T& x = T())//不存在迭代器失效问题
{
	Node* node = new Node;
	node->_Date = x;
	Node* cur = pos._node;
	Node* prev = cur->_prev;

	cur->_prev = node;
	node->_next = cur;
	node->_prev = prev;
	prev->_next = node;

	return node;
}

iterator erase(iterator pos)//这里的pos有可能会产生迭代器失效问题
{
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* next = cur->_next;

	prev->_next = next;
	next->_prev = prev;
	delete cur;
	cur = nullptr;
	return next;//更新pos
}

4. list与vector的区别

list与vector都是c++STL序列容器的重要组成部分，由于底层结构的不同，造成了他们的功能和特性有所不同，详见下表。

vector	list
底层结构	动态顺序表，一段连续空间	带头结点的双向循环链表
随机访问	支持随机访问，访问某个元素效率O(1)	不支持随机访问，访问某个元素效率O(N)
插入和删除	任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低	任意位置插入和删除效率高，不需要搬移元素，时间复杂度为 O(1)
空间利用率	底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高	底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低
迭代器	原生态指针	对原生态指针(节点指针)进行封装
迭代器失效	在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效	插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响
使用场景	需要高效存储，支持随机访问，不关心插入删除效率	大量插入和删除操作，不关心随机访问

5.完整代码

template<class T>
struct ListNode//节点的创建
{
	T _Date;
	ListNode<T>* _next;
	ListNode<T>* _prev;

	ListNode(const T& x=T())//节点的构造函数
		:_Date(x)
		,_next(nullptr)
		,_prev(nullptr)
	{}
};

template<class T,class Ref,class Ptr>
struct _list_iterator//迭代器本质就是指针，这里封装Node*,对Node的指针进行操作，重载++等操作符
{
	typedef ListNode<T> Node;
	typedef _list_iterator<T,Ref,Ptr> self;
	//typedef _list_iterator<T> self;
	Node* _node;//成员变量

public:
	_list_iterator(Node* node)//构造函数，直接用node构建
		:_node(node)
	{}
	//没有参数int ，前置＋＋
	self& operator++()//重载++
	{
		_node = _node->_next;
		return *this;
	}

	self operator++(int)//后置++
	{
		Node* tmp = _node;
		_node = _node->_next;
		return tmp;
	}


	self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}

	//返回临时对象，出函数即销毁，不可传引用
	self operator--(int)//后置--
	{
		Node* tmp = _node;
		_node = _node->_prev;
		return tmp;
	}
	Ptr operator->()
	{
		return &_node->_Date;
	}
	Ref operator*()
	{
		return _node->_Date;
	}
	bool operator!=(const self& s)
	{
		return _node != s._node;
	}
	bool operator==(const self& s)
	{
		return _node == s._node;
	}
};

template<class T>
class list
{
	typedef ListNode<T> Node;  //typedef
public:
	typedef _list_iterator<T,T&,T*> iterator; //普通对象的迭代器
	typedef _list_iterator<T,const T&,const T*> const_iterator;  //const对象的迭代器
	iterator begin()//指向头节点的下一个
	{
		
		return _head->_next;
	}

	iterator end()//指向头节点
	{
		return _head;
	}

	const_iterator begin() const//指向头节点的下一个
	{

		return _head->_next;
	}

	const_iterator end() const//指向头节点
	{
		return _head;
	}
	void list_init()//初始化每一个节点
	{
		_head = new Node;//new调用Node的默认构造，不传参
		_head->_next = _head;
		_head->_prev = _head;
	}
	list()
	{
		list_init();
	}
	list(list<T>& lt)//拷贝构造
	{
		list_init();//创建头节点

		for (const auto& e : lt)
		{
			push_back(e);
		}
	}

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

	//list& operator=(list lt)
	list<T>& operator=(list<T> lt)
	{
		swap(lt);
		return *this;
	}
	void clear()
	{
		list<T>::iterator it = this->begin();
		while (it != end())
		{
			it = erase(it);
		}
	}
	~list()
	{
		delete _head;
		_head = nullptr;
	}
	void push_back(const T& x=T())
	{
		Node* node = new Node;
		Node* tail = _head->_prev;
		node->_Date = x;

		tail->_next = node;
		node->_next = _head;
		_head->_prev = node;
		node->_prev = tail;
	}

	iterator insert(iterator pos,const T& x = T())//不存在迭代器失效问题
	{
		Node* node = new Node;
		node->_Date = x;
		Node* cur = pos._node;
		Node* prev = cur->_prev;

		cur->_prev = node;
		node->_next = cur;
		node->_prev = prev;
		prev->_next = node;

		return node;
	}

	iterator erase(iterator pos)//这里的pos有可能会产生迭代器失效问题
	{
		Node* cur = pos._node;
		Node* prev = cur->_prev;
		Node* next = cur->_next;

		prev->_next = next;
		next->_prev = prev;
		delete cur;
		cur = nullptr;
		return next;//更新pos
	}

	size_t size()const//返回size
	{
		int cnt = 0;
		list<int>::const_iterator it = begin();
		while (it != end())
		{
			cnt++;
			it++;
		};
		return cnt;
	}
	bool empty()const//判空
	{
		return _head ->_next== _head;
	}


private:
	Node* _head;//成员变量为ListNode* 即访问节点的指针
};

原文地址:https://blog.csdn.net/weixin_60358305/article/details/137154894 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1774268385237012480.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部

相关推荐

C++ list模拟实现

2024-03-31 10:52:02 34 阅读
C++ list模拟实现

2024-03-31 10:52:02 29 阅读
C++ list模拟实现

2024-03-31 10:52:02 21 阅读
c++----list模拟实现

2024-03-31 10:52:02 18 阅读
【C++】list模拟实现

2024-03-31 10:52:02 19 阅读
C++list模拟实现

2024-03-31 10:52:02 40 阅读
【C++】List模拟实现

2024-03-31 10:52:02 9 阅读
【C++】list模拟实现

2024-03-31 10:52:02 6 阅读
【C++】list模拟实现

2024-03-31 10:52:02 7 阅读
【c++】STl-list使用&&list模拟实现

2024-03-31 10:52:02 26 阅读