【C++】学习STL中的list

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

❤️前言

        大家好!,今天为大家带来的一篇博客是关于STL中的list,内容主要包括list的介绍使用、list的模拟实现。以及list与vector的对比。

正文

list的介绍和使用

        首先,让我们看看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 - C++ Reference (cplusplus.com)https://legacy.cplusplus.com/reference/list/list/?kw=list        list的简单使用在我们学会了vector的使用之后只要多看看list的文档并多加使用就可以很熟悉,因此在这里就不多讲了。

        需要提一提的是,由于存储在其中的元素的内存并不是连续的,list并不支持随机访问,也没有提供重载方括号。并且因此它并不适合算法库中的sort()和reverse(),于是在我们想要对list进行排序或者逆置的时候,应该使用list自带的接口,它们的名字与算法库中的一样。

        除此之外,使用list时也可能遇到迭代器失效的问题,这时候我们需要重新为迭代器赋值来解决这个问题。

list的模拟实现

        list的模拟实现分为三个部分,分别为:list的节点、list的迭代器、list本体。

list_node的模拟实现

        首先我们模拟实现list的节点,双向链表需要节点具有前后两个指针:

template<typename T>
struct list_node
{
    // 我们初学类模板时常常会忘记写<T>
    // 这里需要注意,模板名带上尖括号之后才会成为类型名
	list_node<T>* _prev;
	list_node<T>* _next;
	T _val;

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

list迭代器的模拟实现

        然后我们要接着模拟实现list的迭代器,这里我们有一个很重要的设计,就是设置多个模板参数,对应数据类型,数据的引用类型,数据的指针类型。

        设计的思路:当我们设计迭代器类的时候,不仅要考虑普通的迭代器,还要考虑const迭代器,它并不是简单的在迭代器类声明对象前加上const关键字就可以。因为我们的const迭代器并不意味着我们不能改动这个迭代器对象本身,而是我们不能改动此迭代器所指向的数据。因此我们需要对迭代器类的一些接口的返回值类型做改动,也就是 * 号和 -> ,原因是这两个重载运算符会提供操作数据的方式。这种设计很好的减少了代码的冗余,使我们不用再另写一份const迭代器。

        除此之外,迭代器实现中比较独特的一点就是->运算符的重载,我们可以看到这里的运算符重载返回值为节点值的地址,那么我们获得了节点数据的地址之后继续要访问节点值的成员,应该要再使用一次->运算符,那么在具体应用中我们就需要使用两个箭头,也就是 iterator->->member ,但是这不符合我们使用->运算符的习惯,于是编译器就为我们简化了一下,只要使用一次箭头,编译器自己会正确识别这样的写法。

	template<typename T, typename Ref, typename Ptr>
	struct _list_iterator
	{
		typedef list_node<T> Node;
		typedef _list_iterator<T, Ref, Ptr> self;

		Node* _node;

		_list_iterator(Node* node)
			:_node(node)
		{}

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

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

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

		self operator++(int)
		{
			_node = _node->_next;
			return _node->_prev;
		}

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

		self operator--(int)
		{
			_node = _node->_prev;
			return _node->_next;
		}

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

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

               除了正向迭代器之外,我们还有一个反向迭代器,反向迭代器的使用规则与正向迭代器完全相反,如果我们直接重新定义一个反向迭代器的类模板,那么我们就需要为每一种迭代器都再写一份反向迭代器,这样代码会非常的冗余。于是这里就引出了一个新的概念——适配器模式。

        由于反向迭代器的规则与迭代器完全相反,反向迭代器的许多地方其实是可以复用对应正向迭代器本身的接口。那么我们就将迭代器类型作为一个模板参数传入,然后在反向迭代器内部创建一个正向迭代器,之后就可以直接对其进行相反的操作,这样我们就得到了一个可以复用的反向迭代器模板。代码如下:

template<class Iterator, class Ref, class Ptr>
struct Reverse_iterator
{
	typedef Reverse_iterator<Iterator, Ref, Ptr> self;

	Reverse_iterator(Iterator it)
		:_it(it)
	{}

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

	self& operator++()
	{
		return --_it;
	}

	self operator++(int)
	{
		return _it--;
	}

	self& operator--()
	{
		return ++_it;
	}

	self operator--(int)
	{
		return _it++;
	}

	bool operator!=(const self& rit) const
	{
		return _it != rit._it;
	}
		
	bool operator==(const self& rit) const
	{
		return _it == rit._it;
	}

private:
	Iterator _it;
};

list本身的实现

        list本身的实现非常简单,我们之前在数据结构时期已经学过了链表的相关知识,写个双向循环链表应该是不在话下。简单代码如下:

template<typename 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;
	typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;

	reverse_iterator rbegin()
	{
		return (iterator)_head->_prev;
	}

	reverse_iterator rend()
	{
		return (iterator)_head;
	}

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

	iterator end()
	{
		return _head;
	}

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

	const_iterator end() const
	{
		return _head;
	}

	list<T>()
	{
		_head = new Node;
		_head->_next = _head;
		_head->_prev = _head;
	}

	list<T>(const list<T>& lt)
	{
		_head = new Node;
		_head->_next = _head;
		_head->_prev = _head;

		for (auto& x : lt)
		{
			push_back(x);
		}
	}

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

	list<T>& operator=(list<T> lt)
	{
		swap(lt);

		return *this;
	}

    // 复用insert的代码
	void push_back(const T& x)
	{
		//Node* tail = _head->_prev;
		//Node* newnode = new Node(x);

		//newnode->_next = tail->_next;
		//newnode->_prev = tail;

		//tail->_next = newnode;
		//_head->_prev = newnode;
		//_size++;

		insert(end(), x);
	}

    // 复用erase的代码
	void pop_back()
	{
		//Node* tail = _head->_prev;
		//Node* nexttail = tail->_prev;

		//_head->_prev = nexttail;
		//nexttail->_next = _head;
		//delete tail;
		//_size--;

		erase(--end());
	}

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

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

	// pos之前位置插入
	iterator insert(iterator pos, const T& x)
	{
		Node* cur = pos._node;
		Node* prev = cur->_prev;
		Node* newnode = new Node(x);

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

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

		_size++;

		return newnode;
	}

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

		prev->_next = next;
		next->_prev = prev;
			
		delete cur;
		_size--;

		return next;
	}

	size_t size()
	{
		return _size;
	}

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

	~list<T>()
	{
		clear();

		delete _head;
		_head = nullptr;
	}

private:
	Node* _head;
	size_t _size = 0;
};

list和vector的对比

        list和vector的底层数据结构分别是链表和数组,它们的区别也就是链表与数组的区别。它们之间的不同点如下:

  • list的迭代器不支持随机访问和加减等操作,但是vector的迭代器支持
  • list的内存空间不是连续的,而vector的内存空间是连续的
  • list在中间和开头插入删除的效率要比vector高得多
  • list的查询效率较低

        总的来说,这两种容器各有优缺点,我们要根据使用场景进行灵活选择。

🍀结语

        ok,那么这篇拖了许久的博客也终于是写完了,临近开学,希望大家开学快乐呀!文章来源地址https://www.toymoban.com/news/detail-691992.html

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

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

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

相关文章

  • 【C++】学习C++STL中的数组——vector

            好久不见大家!今天的这篇博客是关于我对于STL(C++标准模板库)中的容器vector的学习和理解,希望大家能够喜欢。          vector是STL中的一种序列容器,对应着数据结构中的顺序表,也可以说是数组。在我们正式学习了解vector之前,我们先看看C++官网对其的文档介

    2024年02月10日
    浏览(37)
  • 【041】从零开始:逐步学习使用C++ STL中的stack容器

    💡 作者简介:一个热爱分享高性能服务器后台开发知识的博主,目标是通过理论与代码实践的结合,让世界上看似难以掌握的技术变得易于理解与掌握。技能涵盖了多个领域,包括C/C++、Linux、Nginx、MySQL、Redis、fastdfs、kafka、Docker、TCP/IP、协程、DPDK等。 👉 🎖️ CSDN实力新星

    2024年02月16日
    浏览(41)
  • C++:STL--List

    STL容器的代码设计中, 模板编程 和 代码复用的思想贯穿始终 ,代码复用可以将各个成员接口统一起来从而 大大增加程序的可读性和可维护性 ,模板编程使得容器类可以 根据需要用于存储各种不同类型的数据 . C++STL标准库中的list使用的数据结构是带头双向循环链表 ; 链表的头

    2024年02月10日
    浏览(43)
  • C++ STL list

    ✅1主页:我的代码爱吃辣 📃2知识讲解:C++之 STL list介绍和模拟实现 ☂️3开发环境:Visual Studio 2022 💬4前言:上次我们详细的介绍了vector,今天我们继续来介绍一下TSTL中的另外一个容器list。list在基础的功能和结构上就是一个双向带头的循环链表,实现起来基本不难,但是

    2024年02月13日
    浏览(34)
  • 【C++】STL---list

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

    2024年02月11日
    浏览(37)
  • stl中的list模拟实现

    首先我们要清楚list是一个带头双向循环的链表。 在下面代码中我们用到了 模板 ,并且用的是 struct 没有用 class ,这是因为我们使用struct时相当于 这一个类是公开的 ,当然我们也可以使用class但是得使用友元函数比较麻烦。 我们可以查看stl的源码进行查看,如下: 我们可以

    2024年02月02日
    浏览(41)
  • 【C++入门到精通】C++入门 —— vector (STL)

    前面我们讲了C语言的基础知识,也了解了一些数据结构,并且讲了有关C++的命名空间的一些知识点以及关于C++的缺省参数、函数重载,引用 和 内联函数也认识了什么是类和对象以及怎么去new一个 ‘对象’ ,也相信大家都掌握的不错,接下来博主将会带领大家继续学习有关

    2024年02月13日
    浏览(47)
  • 【C++入门到精通】C++入门 —— deque(STL)

    文章绑定了VS平台下std::deque的源码,大家可以下载了解一下😍 前面我们讲了C语言的基础知识,也了解了一些数据结构,并且讲了有关C++的命名空间的一些知识点以及关于C++的缺省参数、函数重载,引用 和 内联函数也认识了什么是类和对象以及怎么去new一个 ‘对象’ ,以及

    2024年02月12日
    浏览(42)
  • <C++> STL_list

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

    2024年02月10日
    浏览(40)
  • C++ STL->list模拟实现

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

    2024年02月20日
    浏览(41)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包