【C++】list的使用和模拟实现

这篇具有很好参考价值的文章主要介绍了【C++】list的使用和模拟实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1.什么是list

list的底层是一个双向带头循环链表,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素,其遍历只能通过迭代器来实现,范围for的底层也是迭代器。
迭代器是所有容器都可以使用的迭代方式。
与list类似的还有forward_list,底层是单链表,只能朝前迭代,以让其更简单高效。
与vector相比,list在任意位置的插入或删除效率更高,不需要去移动数据。但是其最大的缺陷是不支持随机访问,想要访问list某一个元素,必须从已知的位置(比如头部或者尾部)迭代到该位置,这一块的时间开销较大。
【C++】list的使用和模拟实现

2.list的一些接口

【C++】list的使用和模拟实现
这里的接口看起来都很熟悉,使用起来和前面的string,vector的接口也没有什么差别。
assign:【C++】list的使用和模拟实现
list的assign支持两种使用方式,第一种是利用迭代器来进行切片,第二中则是将链表修改为n个val值。

void test1
{
	list<int> l1;
	list<int> l2;
	l1.assign(5, 10);
	l2.assign(l1.begin(), l1.end());
	for (auto e : l1)
	{
		cout << e << " ";
	}
	cout << endl;
	for (auto e : l2)
	{
		cout << e << " ";
	}
	cout << endl;
}

【C++】list的使用和模拟实现
clear:将除了头节点以外的所有节点全部释放。与析构函数不同,析构会释放包括头节点在内的全部节点。

sort:链表单独提供了一个排序的函数,为什么不直接使用算法库中的sort呢?
【C++】list的使用和模拟实现
这是算法库中的sort,我们可以看到其中的参数类型是RandomAccessIterator,意思是支持随机访问的迭代器,这里就要谈到迭代器的分类,迭代器可分为单向迭代器(单链表,哈希表)、双向迭代器(双向链表),随机访问迭代器(顺序表)。至于为什么算法库中的sort只能支持随机访问的迭代器,这就要从其底层实现说起了。
algorithm中的sort是利用快排实现的,而快排中需要三数取中,由于链表中的迭代器并不连续,所以不支持这种运算。list中的sort采用归并排序来解决了这个问题。

remove:删除list中第一个值为val的元素【C++】list的使用和模拟实现

void test2()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.remove(3);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
}

【C++】list的使用和模拟实现
splice:将一个链表中的一段区间转移到另一个链表的指定位置。
【C++】list的使用和模拟实现

void test3()
{
	list<int> l1;
	list<int> l2;
	l1.push_back(1);
	l1.push_back(2);
	l1.push_back(3);
	l1.push_back(4);
	l2.push_back(5);
	l2.push_back(6);
	l2.push_back(7);
	list<int>::iterator it = ++l1.begin();
	l1.splice(it, l2);
	for (auto e : l1)
	{
		cout << e << " ";
	}
	cout << endl;
}

unique:用于链表的去重,要求去重前链表必须有序,否则会发生错误。

merge:合并两个链表。

void test4()
{
	list<int> l1;
	list<int> l2;
	l1.push_back(1);
	l1.push_back(2);
	l1.push_back(3);
	l1.push_back(4);
	l2.push_back(5);
	l2.push_back(6);
	l2.push_back(7);
	l1.merge(l2);
	for (auto e : l1)
	{
		cout << e << " ";
	}
	cout << endl;
}

【C++】list的使用和模拟实现
list中的迭代器失效:
对于list,insert并不会使迭代器失效,因为list中的节点都有单独的空间,节点并不连续,在进行扩容操作的时候只需要申请新空间,不需要进行异地扩容释放原有的空间。而erase仍然会导致迭代器失效,,erase之后会释放该节点的空间,必然会导致pos指向已经释放的空间,想要继续使用可以用erase的返回值来更新pos。

3.list的模拟实现

3.1 迭代器

在vector中,我们说把迭代器当作一个指针,模拟实现的时候也是利用typedef将指针重命名实现迭代器,但在list中,我们发现迭代器没法这样实现,比如迭代器的+±-,想要通过++找到下一个位置需要连续的空间,而我们又知道list中每一个节点不是连续的,这样++不就没法找到下一个位置了吗?但通过前面类和对象的学习,这点问题难不倒我们,可以用运算符重载将++的行为改变,不是指向当前地址+1,而是指向下一个节点。这样我们就需要用类或结构体将这个指针封装起来,通过重载来改变这个指针的++,–,解引用等行为。
现在来模拟实现一下:

首先我们要先构建节点的结构体:

template<class T>
struct list_node
{
	list_node<T>* _next;	// 下一个节点的地址
	list_node<T>* _prev;	// 前一个节点的地址
	T _val;					// 值

	list_node(const T& x = T())
		:_next(nullptr)
		, _prev(nullptr)
		, _val(x)
	{ }
};

迭代器的实现:

template<class T>
struct __list_iterator
{
	typedef list_node<T> node;
	typedef __list_iterator<T> self;
	node* _node;	// 唯一的成员变量:节点的指针

	__list_iterator(node* n)
		:_node(n)
	{ }

	const T& operator*()
	{
		return _node->_val;
	}

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

	self operator++(int)
	{
		self tmp(*this);
		_node = _node->_next;
		return tmp;
	}

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

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

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

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

这样就完成了一个list迭代器的基本构建,接下来就来写一下list的各种函数。

3.2 list主体

3.2.1 构造函数

这里设定list的成员变量为头节点的指针。
无参构造:new一个头节点,然后将该节点的prev和next都指向自己。

template<class T>
class list
{
	typedef list_node<T> node;
public:
	list()
	{
		_head = new node;
		_head->_next = _head;
		_head->_prev = _head;
	}
private:
	node* _head;
};

以迭代器区间作为参数的构造:使用模板实现

template <class Iterator>
list(Iterator first, Iterator last)
{
	_head = new node;
	_head->_next = _head;
	_head->_prev = _head;

	while (first != last)
	{
		push_back(*first);
		++first;
	}
}

这里发现有些代码重复,不妨将其写在另一个函数里,提高复用率。

void empty_init()
{
	_head = new node;
	_head->_next = _head;
	_head->_prev = _head;
}

list()
{
	empty_init();
}

template <class Iterator>
list(Iterator first, Iterator last)
{
	empty_init();

	while (first != last)
	{
		push_back(*first);
		++first;
	}
}

3.2.2 拷贝构造、赋值重载

这里就直接写现代写法了,可读性高,先实现交换函数,再通过临时变量与自身交换。

// 拷贝构造
void swap(list<T>& tmp)
{
	std::swap(_head, tmp._head);
}

list(const list<T>& lt)
{
	empty_init();
	list<T> tmp(lt.begin(), lt.end());
	swap(tmp);
}

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

3.2.3 主体内引入迭代器

依旧通过typedef引入

typedef __list_iterator<T> iterator;

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

iterator end()
{
	return iterator(_head);		// 最后一个节点的下一个节点,就是头节点
}

3.2.4 insert和erase

insert和erase的操作应该都非常熟悉了,在前面数据结构学习的时候练习了不少。

// 因为insert不会引发迭代器失效,这里就没有给它设返回值
void insert(iterator pos, const T& x)
{
	node* cur = pos._node;
	node* prev = cur->_prev;
	node* new_node = new node(x);
	
	prev->_next = new_node;
	new_node->_prev = prev;
	new_node->_next = cur;
	cur->_prev = new_node;
}

iterator erase(iterator pos)
{
	assert(pos != end());		// 不能删除头节点
	node* prev = pos._node->_prev;
	node* next = pos._node->_next;
	prev->_next = next;
	next->_prev = prev;
	delete pos._node;			// 别忘记释放掉空间
	return pos;
}

push_back,pop_back等只需复用insert和erase即可,这里不做赘述。

3.2.5 clear和析构函数

clear:将除了头节点以外的节点全部释放,通过erase和迭代器来一个一个释放。

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

析构函数实现时,可不敢直接delete[] _head,因为节点不是连续的,这样只删掉了头节点,其他节点没有删掉,造成内存泄漏。
只要先用clear将其他节点先释放,在释放头节点即可。

~list()
{
	clear();
	delete _head;
	_head = nullptr;
}

3.3 const迭代器的实现

首先,可不敢直接用const修饰iterator,这样会导致iterator无法++和–,因为我们需要的const迭代器是指iterator指向的内容不可变,而不是iterator不可变。
实现const迭代器和普通迭代器不同的地方就只有operator*这个函数上了,const迭代器需要的是不可改变的返回值。于是就写出了下面一段代码

template<class T>
struct __list_const_iterator
{
	typedef list_node<T> node;
	typedef __list_const_iterator<T> self;
	node* _node;

	__list_const_iterator(node* n)
		:_node(n)
	{ }

	const T& operator*()
	{
		return _node->_val;
	}

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

	self operator++(int)
	{
		self tmp(*this);
		_node = _node->_next;
		return tmp;
	}

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

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

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

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

上述代码和普通迭代器相比只增加了几个const,却又要重新写这样一大堆代码,显得很冗余,怎么才能使它变得简洁一些呢?
可以通过增加模板参数,通过手动填入参数来选择你是普通迭代器还是const迭代器。
增加了一个Ref模板参数,这样当Ref=T&时就是普通迭代器,Ref=const T&时就是const迭代器。

template<class T, class Ref>
struct __list_iterator
{
	typedef list_node<T> node;
	typedef __list_iterator<T, Ref> self;
	node* _node;

	__list_iterator(node* n)
		:_node(n)
	{ }

	Ref operator*()
	{
		return _node->_val;
	}

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

	self operator++(int)
	{
		self tmp(*this);
		_node = _node->_next;
		return tmp;
	}

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

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

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

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

然后在list中加入这样一行代码,就可以尽情使用const迭代器了。

typedef __list_iterator<T, const T&> const_iterator;

3.4 实现迭代器的operator->

当list的中元素的类型为自定义类型时,打印*it会报错,因为该自定义类型没有重载流插入,但是要重载的话就必须每写一个自定义类型都重载一个流插入,很麻烦。还可以用(*it).x的方式来获取,不过这种方式不太符合平常的使用习惯,平常面对这种情况更喜欢去用->,所以我们需要在迭代器中重载一个operator->()。

struct Point
{
	int x = 0;
	int y = 0;
};

void list_test6()
{
	list<Point> lt;
	lt.push_back(Point());
	list<Point>::iterator it = lt.begin();
	cout << *it << endl;		// 会报错,Point没有重载流插入
}

operator->()的实现:

T* operator->()
{
	return &_node->_val;		//node->_val就是那个结构体,返回结构体的指针
}

根据这样的实现方式,在使用时应该是像“it->->x”这样使用,但实际上只需要一个->,是因为编译器为了可读性省略掉了一个->。
再考虑到const迭代器,因为->也是要返回内容,所以要保障返回值不可修改,所以再像前面一样添加一个模板参数Ptr实例化时根据T和const T区分即可。
于是呢,我们就实现了最终的迭代器。

template<class T, class Ref, class Ptr>
struct __list_iterator
{
	typedef list_node<T> node;
	typedef __list_iterator<T, Ref, Ptr> self;
	node* _node;

	__list_iterator(node* n)
		:_node(n)
	{ }

	Ref operator*()
	{
		return _node->_val;
	}

	Ptr operator->()
	{
		return &_node->_val;
	}

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

	self operator++(int)
	{
		self tmp(*this);
		_node = _node->_next;
		return tmp;
	}

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

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

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

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

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;

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

	const_iterator begin() const
	{
		return const_iterator(_head->_next);
	}

	iterator end()
	{
		return iterator(_head);
	}

	const_iterator end() const
	{
		return const_iterator(_head);
	}

	void empty_init()
	{
		_head = new node;
		_head->_next = _head;
		_head->_prev = _head;
	}

	list()
	{
		empty_init();
	}

	template <class Iterator>
	list(Iterator first, Iterator last)
	{
		empty_init();

		while (first != last)
		{
			push_back(*first);
			++first;
		}
	}

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

	list(const list<T>& lt)
	{
		empty_init();
		list<T> tmp(lt.begin(), lt.end());
		swap(tmp);
	}

	~list()
	{
		clear();
		delete _head;
		_head = nullptr;
	}

	list<T>& operator=(list<T> lt)
	{
		swap(lt);
		return *this;
	}

	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());
	}

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

	void insert(iterator pos, const T& x)
	{
		node* cur = pos._node;
		node* prev = cur->_prev;
		node* new_node = new node(x);
		prev->_next = new_node;
		new_node->_prev = prev;
		new_node->_next = cur;
		cur->_prev = new_node;
	}

	iterator erase(iterator pos)
	{
		assert(pos != end());
		node* prev = pos._node->_prev;
		node* next = pos._node->_next;
		prev->_next = next;
		next->_prev = prev;
		delete pos._node;
		return pos;
	}

private:
	node* _head;
};

4.总结list迭代器的实现

通过list迭代器的实现,我们知道不能把迭代器简单理解为一个指针,而是通过运算符重载等把它包装成一个行为和指针极为相似的东西,让不论底层数据结构是怎样的容器都能够通过迭代器来实现读写数据,由此可以感受到类封装的强大。文章来源地址https://www.toymoban.com/news/detail-490982.html

到了这里,关于【C++】list的使用和模拟实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++:list使用以及模拟实现

    list是一个类模板,加类型实例化才是具体的类 。 list是可以 在任意位置进行插入和删除 的序列式容器。 list的 底层是双向循环链表结构 ,链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。 与其他序列式容器相比, list最大的

    2024年02月11日
    浏览(39)
  • 【C++】list的使用和模拟实现

    list的底层是一个双向带头循环链表,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素,其遍历只能通过迭代器来实现,范围for的底层也是迭代器。 迭代器是所有容器都可以使用的迭代方式。 与list类似的还有forward_list,底

    2024年02月09日
    浏览(49)
  • C++:List的使用和模拟实现

                                                            创作不易,感谢三连!! list的文档介绍 1. list是可以 在常数范围内在任意位置进行插入和删除的序列式容器 ,并且该容器 可以前后双向迭代。 2. list的 底层是双向链表结构, 双向链表中每个元素存储在互不相

    2024年03月25日
    浏览(40)
  • 【C++】list的使用与模拟实现

    目录 一、list介绍 二、list的使用  1、list的构造 2、list capacity 3、list element access 4、list iterator 5、list modifiers 5.1、insert 6、list Operations 6.1、sort 7、list的迭代器失效 三、list模拟实现 1、push_back 2、iterator 3、const iterator 4、Ptr 5、insert 及其复用 6、erase 及其复用 7、clear 8、构造函

    2023年04月26日
    浏览(41)
  • 【C++干货铺】list的使用 | 模拟实现

    ========================================================================= 个人主页点击直达: 小白不是程序媛 C++专栏: C++干货铺 代码仓库: Gitee ========================================================================= 目录 list的介绍及使用 list的介绍 list的使用 list的构造 list迭代器的使用 list的增删查改

    2024年02月04日
    浏览(37)
  • [C++入门]---List的使用及模拟实现

    list 是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。 list 的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向 其前一个元素和后一个元素。 list 与 forward_list 非常相似:最主要的不

    2024年02月07日
    浏览(36)
  • 【C++】list的介绍及使用 | 模拟实现list(万字详解)

    目录 一、list的介绍及使用 什么是list? list的基本操作 增删查改 获取list元素 不常见操作的使用说明 ​编辑 接合splice ​编辑 移除remove 去重unique 二、模拟实现list 大框架 构造函数 尾插push_back 迭代器__list_iterator list的迭代器要如何跑起来 iterator的构造函数 begin()与end() opera

    2024年02月06日
    浏览(48)
  • 【C++初阶】11. list的使用及模拟实现

    list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。 list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。 list与forward_list非常相似:最主要的不同在

    2024年02月12日
    浏览(42)
  • C++ STL之list的使用及模拟实现

    英文解释: 也就是说: list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。 list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。 list与forward_list非常

    2024年01月24日
    浏览(81)
  • 【STL源码分析】c++,List双向链表源码分析。自己实现list双向链表。

    参考链接:https://blog.csdn.net/man_sion/article/details/71003095? 先抽取要实现的功能,由于迭代器有些麻烦,就不使用了。要实现的功能有,push_back,pop_back,insert(指定位置,指定值),insert(指定位置,list,区间值),reverse,clear,getsize,begin,end,构造和析构函数,empty。 相关力扣题目:设计

    2024年02月03日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包