【STL】list用法&试做_底层实现

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

目录

一,list  使用

1. list 文档介绍 

2. 常见接口

1.   list中的sort

2. list  + sort 与 vector  + sort效率对比

3. 关于迭代器失效

4. clear

二,list 实现

1.框架搭建 

2. 迭代器类——核心框架

3. operator->  实现 

4. const——迭代器

5. insert

6. erase

7. clear——实现

8. 拷贝构造 

首先实现迭代器构造函数:

 拷贝构造复用:

9. operator=

10. 全代码 

结语


【STL】list用法&试做_底层实现,C++——从入门到入土,安排!,c++,开发语言,windows,数据结构,list

一,list  使用

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 来说这可能是一个重要的因素)

STL文档网址:list - C++ Reference (cplusplus.com) 

 【STL】list用法&试做_底层实现,C++——从入门到入土,安排!,c++,开发语言,windows,数据结构,list

2. 常见接口

      【STL】list用法&试做_底层实现,C++——从入门到入土,安排!,c++,开发语言,windows,数据结构,list

STL 以设计模板类似,只对特殊处进行讲解。 

1.   list中的sort

 【STL】list用法&试做_底层实现,C++——从入门到入土,安排!,c++,开发语言,windows,数据结构,list

 我们知道算法库里面有sort函数,那为什么list要单独写一个sort ??   原因: 算法库里面的sort使用有前提——数据地址连续。(list的sort底层实现大多是 非递归归并 排序 )

2. list  + sort 与 vector  + sort效率对比

    直接说结论list的sort 接口意义不大

效率实验:

测试组: 用list接受数据并用list的sort进行排序。

对照组:  先用vector接收数据,并用算法库中的sort排序,最后将数据转移到list中。

时间效率结果:

【STL】list用法&试做_底层实现,C++——从入门到入土,安排!,c++,开发语言,windows,数据结构,list

小量两者相差不大,但数据量大时,会有5到10倍的差距。 

3. 关于迭代器失效

前面说过,此处大家可将迭代器暂时理解成类似于指针, 迭代器失效即迭代器所指向的节点的无效,即该节点被删除了。因为 list的底层结构为带头结点的双向循环链表,因此 在list中进行插入时是不会导致list的迭代器失效的,只有在删除时才会失效,并且失效的只是指向被删除节点的迭代器,其他迭代器不会受到影响
void TestListIterator1()
{
   int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
   list<int> l(array, array+sizeof(array)/sizeof(array[0]));
   auto it = l.begin();
   while (it != l.end())
   {
   // erase()函数执行后,it所指向的节点已被删除,因此it无效,在下一次使用it时,必须先给
    其赋值
   l.erase(it); 
   ++it;
   }
}
// 改正
void TestListIterator()
{
  int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
  list<int> l(array, array+sizeof(array)/sizeof(array[0]));
  auto it = l.begin();
  while (it != l.end())
  {
  l.erase(it++); // it = l.erase(it);
  }
}

4. clear

    清除链表数据,保留头结点

【STL】list用法&试做_底层实现,C++——从入门到入土,安排!,c++,开发语言,windows,数据结构,list


二,list 实现

1.框架搭建 

  1 
  2 #include <iostream>
  3 #include <list>
  4 uising namespace std;
  5 namespace my_list
  6 {
  7   template<class T>
  8   struct list_node
  9   {
 10     list_node ( const T& val = T() ) // 针对不同的数据类型,所以用数据类型的仿函数
 11      :_val(val)
 12      ,_prev(nullptr)
 13      ,_next(nullptr)
 14     {}
 15 
 16     T _val;
 17     list_node<T>* _prev ;
 18     list_node<T>* _next ;
 19   };

      template<class T>
 22   class list                                                                                                        
 23   {
 24     typedef list_node<T> Node;
 25   public:
 26     list() // 
 27     {
 28       _head = new Node;
 29       _head->_prev = _head;
 30       _head->_next = _head;
 31     }
   private:
 45     Node* _head;
 46   };
 47 }

2. 迭代器类——核心框架

     之前string, vector在物理内存中是连续的,因此迭代器就跟指针差不多了,解引用一次即可表示数据。list在物理内存上不是连续存储的。list底层是带头的双向链表,通过头结点的指针,对所指向的数据进行操作处理。

struct _list_iterator  // 由于List的迭代器,表层是通过头结点进行操作,数据在头里面,一层解引用
 25     {                      // 解决不了问题
 26       typedef list_node<T> Node;
 27       typedef _list_iterator iterator;
 28       Node* _node; // 迭代器类,内部只要一个结点的指针即可
 29 
 30       _list_iterator(Node* x)
 31         : _node(x)
 32       {}
 33 
 34       // 重载迭代器*,因为结点的解引用,只是得到结点。目的:支持读,写
 35       T& operator*()
 36       {                                                                                                             
 37         return _node->_val;  
 38       }  
 39       // 重载迭代器++,list不是连续的空间,地址++不合理;目的:++后为下一个迭代器位置,且支持读,写
 40       iterator&  operator++() // 前置++  
 41       {  
 42          _node = _node->_next;
 43          return *this;
 44       }
 45       
 46 
 47       bool operator!=(const iterator& v) const 
 48       {
 49          return _node != v._node;
 50       }

大家是否有注意到吗? 我们的迭代器框架里没有写析构与拷贝构造?其实里面暗藏玄鸡。

      首先是析构: 1.  _node指针属于链表,我们不能随便释放空间。2.  自定义类型,系统自动调用自定义类型的析构函数。

      其次是拷贝: 我们只需要目标的地址,值拷贝就行,不需要深拷贝,所以不用写。 

3. operator->  实现 

    假设T是自定义类型,需要读取里面成员函数,甚至是成员变量。那么一般的写法: (*it).a1, 既然是指针写箭头会更方便 

//  实现
        T& operator*()
		{
			return _node->_data;
		}

		T* operator->()
		{
			return &(operator*()); //这个挺怪异的,马上讲解
		}

// 测试
void test2()
{
	struct pos
	{
		int a1 = 1;
		int a2 = 2;
	};
	my_list::list<pos> x;
	my_list::list<pos>::iterator it = x.begin();
	while (it != x.end())
	{
		cout << (*it).a1;
		cout << it->a1;
	}
}

【STL】list用法&试做_底层实现,C++——从入门到入土,安排!,c++,开发语言,windows,数据结构,list

4. const——迭代器

         普通迭代器, 解引用得到数据本体;而const迭代器,解引用得到本体,但不能对本体进行修改。为了提高代码复用率,下面是实现思路:

【STL】list用法&试做_底层实现,C++——从入门到入土,安排!,c++,开发语言,windows,数据结构,list

迭代器代码:

#include <iostream>
#include <string>
using namespace std;

namespace my_list
{
	template <class T>
	struct list_node // 不用修改
	{
		list_node(const T& data = T())
			: _data(data)
			, _next(nullptr)
			, _prv(nullptr)
		{}

		T _data;
		list_node* _next;
		list_node* _prv;
	};

	template <class T, class Ref, class Ptr>
	struct list_iterator  // 迭代器,仅修改会返回能写的函数,*, ->
	{
		typedef list_node<T> Node;
		typedef list_iterator< T, Ref, Ptr> iterator;

		Node* _node;

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

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

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

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

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

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

		Ptr operator->()
		{
			return &(operator*());
		}

	};


	template <class T>  // 提供const迭代器类型+ const迭代器的begin(),end()
	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);
		}

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

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


		list()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prv = _head;
		}

		void push_back( const T& val)
		{
			Node* tmp = new Node(val);
			tmp->_data = val;
			tmp->_next = _head;
			tmp->_prv = _head->_prv;
			_head->_prv->_next = tmp;
			_head->_prv = tmp;
		}

	private:
		Node* _head;
	};
}

5. insert

    

【STL】list用法&试做_底层实现,C++——从入门到入土,安排!,c++,开发语言,windows,数据结构,list

 我们实现最简单的1:

        // 在当前位置插入一个数据,当前数据向后移
		iterator insert(iterator pos, const T& data)
		{
			Node* cur = pos._node;
			Node* prv = cur->_prv;
			Node* newnode = new Node(data);

			newnode->_next = cur;
			newnode->_prv = prv;
			prv->_next = newnode;
			cur->_prv = newnode;

			return iterator(newnode);
		}

 这样头插,push_back也能复用insert:

        void push_back( const T& val)
		{
			/*Node* tmp = new Node(val);
			tmp->_data = val;
			tmp->_next = _head;
			tmp->_prv = _head->_prv;
			_head->_prv->_next = tmp;
			_head->_prv = tmp;*/

			insert(iterator(_head), val);  // 头插同理
		}
        void push_front(const T& val)
		{
			insert(iterator(_head->_next), val);
		}

6. erase

 【STL】list用法&试做_底层实现,C++——从入门到入土,安排!,c++,开发语言,windows,数据结构,list

删除迭代器pos位置,然后返回下一个迭代器。

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

			prv->_next = next;
			next->_prv = prv;
			delete cur;
			return iterator(next);
		}

  这里只完成迭代器的核心代码,其他小功能就只做代码分享。

7. clear——实现

    完成clear的同时,list析构函数也能复用。

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

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

8. 拷贝构造 

传统写法: 自己对数据一个个拷贝。

现代写法: 利用迭代器构造函数,然后交换一下_head结点即可。 

首先实现迭代器构造函数:

        template <class input_iterator>
		list( input_iterator begin,  input_iterator end)
		{
			list_initial(); // 对头结点进行初始化
			while (begin != end)
			{
				push_back(*begin);
				++begin;
			}
		}

 拷贝构造复用:

       void swap(list<T>& x)  // 顺便实现一个swap
		{
			std::swap(x._head, _head);
		}

		list(const list<T>& x)
		{
			list_initial();
			list tmp(x.begin(), x.end());
			swap(tmp);
		}
         // tmp 调用析构时,会将this的_headfree掉

9. operator=

        list<T>& operator=(list<T> tmp) // 拷贝构造
		{
			swap(tmp);
			return *this;
		}

10. 全代码 

#include <iostream>
#include <string>
using namespace std;

namespace my_list
{
	template <class T>
	struct list_node
	{
		list_node(const T& data = T())
			: _data(data)
			, _next(nullptr)
			, _prv(nullptr)
		{}

		T _data;
		list_node* _next;
		list_node* _prv;
	};

	template <class T, class Ref, class Ptr>
	struct list_iterator
	{
		typedef list_node<T> Node;
		typedef list_iterator< T, Ref, Ptr> iterator;

		Node* _node;

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

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

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

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

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

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

		Ptr operator->()
		{
			return &(operator*());
		}

	};


	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;

		void list_initial()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prv = _head;
		}

		list()
		{
			list_initial();
		}

		template <class input_iterator>
		list( input_iterator begin,  input_iterator end)
		{
			list_initial(); // 对头结点进行初始化
			while (begin != end)
			{
				push_back(*begin);
				++begin;
			}
		}

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

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

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

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



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

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

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


		void push_back( const T& val)
		{
			/*Node* tmp = new Node(val);
			tmp->_data = val;
			tmp->_next = _head;
			tmp->_prv = _head->_prv;
			_head->_prv->_next = tmp;
			_head->_prv = tmp;*/

			insert(iterator(_head), val);  // 头插同理
		}

		void push_front(const T& val)
		{
			insert(iterator(_head->_next), val);
		}

		// 在当前位置插入一个数据,当前数据向后移
		iterator insert(iterator pos, const T& data)
		{
			Node* cur = pos._node;
			Node* prv = cur->_prv;
			Node* newnode = new Node(data);

			newnode->_next = cur;
			newnode->_prv = prv;
			prv->_next = newnode;
			cur->_prv = newnode;

			return iterator(newnode);
		}

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

			prv->_next = next;
			next->_prv = prv;
			delete cur;
			return iterator(next);
		}
		
		iterator Pop_back()
		{
			erase(iterator(_head->_prv));
			return _head;
		}

		iterator Pop_front()
		{
			Node* next = _head->_next->_next;
			erase(iterator(_head->_next));
			return next;
		}

	     list<T>& operator=(list<T> tmp)
		{
			swap(tmp);
			return *this;
		}
	private:
		Node* _head;
	};
}

结语

   本小节就到这里了,感谢小伙伴的浏览,如果有什么建议,欢迎在评论区评论,如果给小伙伴带来一些收获请留下你的小赞,你的点赞和关注将会成为博主创作的动力文章来源地址https://www.toymoban.com/news/detail-602948.html

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

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

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

相关文章

  • STL——list用法

    1、list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。 2、list就是一个带头双向循环链表, list通常在任意位置进行插入、移除元素的执行效率更好。 3、 list最大的缺陷是不支持任意位置的随机访问。 有了前面使用string和vector的

    2024年02月12日
    浏览(44)
  • C++入门之stl六大组件--List源码深度剖析及模拟实现

    文章目录 前言 一、List源码阅读 二、List常用接口模拟实现 1.定义一个list节点 2.实现一个迭代器 2.2const迭代器 3.定义一个链表,以及实现链表的常用接口 三、List和Vector 总结 本文中出现的模拟实现经过本地vs测试无误,文件已上传gitee,地址:list: 模仿实现stl的list - Gitee.com 首

    2024年02月13日
    浏览(51)
  • 【C++】STL---list基本用法介绍

    个人主页:平行线也会相交💪 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创 收录于专栏【C++之路】💌 本专栏旨在记录C++的学习路线,望对大家有所帮助🙇‍ 希望我们一起努力、成长,共同进步。🍓 list 是STL中的一种 容器 ,底层其实就是一个 双向链

    2024年02月16日
    浏览(45)
  • 【C++入门】STL容器--vector底层数据结构剖析

    目录  前言  1. vector的使用       vector的构造  vector迭代器  vector空间相关的接口  vector 功能型接口  find  swap  insert  erase 2. vector内部数据结构剖析 reserve  push_back和pop_back size、capacity、empty、operator[ ];  insert和erase resize swap  拷贝构造和赋值重载 构造函数补充  迭代器

    2024年01月25日
    浏览(57)
  • 【C++入门到精通】C++入门 —— list (STL)

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

    2024年02月12日
    浏览(40)
  • 【C++STL基础入门】list基本使用

    STL(Standard Template Library)是C++标准库的一个重要组成部分,提供了一套丰富的数据结构和算法,可以大大简化C++程序的开发过程。其中,list容器是STL提供的一种双向链表实现的数据结构,具有高效的插入和删除操作,适用于需要频繁插入和删除元素的场景。本文将介绍list容

    2024年02月07日
    浏览(72)
  • C++ STL sort函数的底层实现

    sort函数 的底层用到的是 内省式排序 以及 插入排序 ,内省排序首先从快速排序开始,当递归深度超过一定深度(深度为排序元素数量的对数值)后转为堆排序。 先来回顾一下以上提到的3中排序方法: 快速排序:先选一个基准值(一般为首值),将比它大的数置于其右侧,

    2024年02月15日
    浏览(40)
  • C++ stl容器vector的底层模拟实现

    目录 前言:   1.成员变量,容量与大小 2.构造函数 无参构造: 带参的使用值进行构造:  使用迭代器区间进行构造: 3.交换 4.拷贝构造 5.赋值重载 6.迭代器 7.扩容 reserve: resize: 8.插入与删除 insert: erase: insert迭代器失效问题: erase迭代器失效问题: 9.头插头删 10.[]重载

    2024年04月15日
    浏览(42)
  • C++ stl容器string的底层模拟实现

    目录 前言: 1.成员变量 2.构造函数与拷贝构造函数 3.析构函数 4.赋值重载 5.[]重载 6.比较关系重载 7.reserve 8.resize 9.push_back,append和重载+= 10.insert 11.erase 12.find 14.迭代器 15.流插入,流提取重载 16.swap 17.c_str 18.完整代码+测试 总结: 1.成员变量 首先注意的就是_str,不能是const类型

    2024年04月23日
    浏览(44)
  • 【STL】stack与queue的底层原理及其实现

    (图片来自知乎) 1.stack是一种 容器适配器 ,模拟了栈的数据结构。数据只能从一端进去,另一端出来( 先进后出 )。 2.stack适配器 默认是由 deque 容器实现 的,也可以显示要求stack的底层封装的容器类型。由于栈的特性, array 和 forward_list 不能用来构造stack适配器 。 3.st

    2024年04月10日
    浏览(46)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包