devbox
weixin_40725706
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

list容器

作者：weixin_40725706 | 2024-07-21 11:03:02

赞

踩

list容器

目录

1.介绍（cv的，网上太多了）

 2.使用

2.1构造函数

2.2迭代器

begin(),end(),rbegin(),rend(),cbegin(),cend(),crbegin(),crend()

遍历方式

2.3 容量

empty()

size()

max_size()

2.4元素遍历

 front()

back()

2.5修改

assign()

push_front()

pop_front()

push_back()

pop_back()

insert()

erase()

swap()

resize()

clear()

2.6操作

 reverse()

sort()

merge()

unique()

remove()

remove_if()

splice()

3.模拟

使用这一块我会写的比较简洁，实在是前面vector和string已经写了很多相同的了

1.介绍（cv的，网上太多了）

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

 2.使用

2.1构造函数

  1. //第一种常用
  2. 	//第一个参数给数量，第二个参数给初始化的值，比如2个3
  3. 	list<int>i(2,3);
  4. 	//3 3
  5. 	//第二种常用
  6. 	//给一个迭代器区间（可以是指针）
  7. 	list<int>i1(i.begin(), i.end());
  8. 	//3 3
  9. 	//第三种常用
  10. 	//拷贝构造
  11. 	list<int>l3(i1);
  12. 	//3 3
  13.  
  14. 当然还有就是无参构造
  15. list()

另外，还有一个就是=的运算符重载

也就是说，可以这样写

  1. 	list<int>i1(3,6);
  2. 	list<int>l3 = i1;//注意，这其实还是拷贝构造，赋值是两个都已存在的实体类之间
  3. 	list<int>j;
  4. 	j = l3;//这才是赋值

2.2迭代器

begin(),end(),rbegin(),rend(),cbegin(),cend(),crbegin(),crend()

我们要知道，list是个双向循环的链表，也就是说，每个节点，都存在着前驱和后驱。

begin()和rend()，指向的就是第一个节点（有效节点）,rbegin()和end()指向的就是头结点（不存有效数据）

begin(),end()如果++，是向后移动，rbegin(),rend()是向前移动

至于加个c，纯粹就是const修饰的迭代器罢了

遍历方式

list没有[]的重载，因为list的每个元素，物理空间不一定连续，那么就不能用指针+-的方式来随机访问，因此这里只能用迭代器遍历的方式

  1. 	list<int>i = { 2,3,4,5,6,6,7,8 };
  2. 	list<int>::iterator it = i.begin();
  3. 	while (it != i.end())
  4. 	{
  5. 		cout << (*it) << " ";
  6. 		it++;
  7. 	}
  8. 或者范围for（但范围for本质还是迭代器）

2.3 容量

empty()

很经典的判断容器里面是否还未空，是返回true，否返回false

size()

返回有效数据个数

max_size()

返回最大能存的数据个数（取决于编译环境）

2.4元素遍历

 front()

返回容器第一个元素，分两种重载，即非const和const（避免权限放大）

back()

返回容器最后一个元素，同样两种重载，非const和const（原因同理）

2.5修改

assign()

  1. 	list<int>i = { 2,3,4,5,6,6,7,8 };
  2. 	//void assign (size_type n, const value_type& val);
  3. 	list<int>c;
  4. 	c.assign(4, 5);
  5. 	//c : 5555
  6. 	//注意是替换，不是追加
  7. 	//template <class InputIterator>
  8. 	//void assign(InputIterator first, InputIterator last);
  9. 	c.assign(i.begin(), i.end());
  10. 	//c:2,3,4,5,6,6,7,8
  11. 	//注意，是替换，不是追加

push_front()

就是在第一个元素前插入一个数据

pop_front()

删除第一个元素

push_back()

在最后插入一个数据

pop_back()

删除最后一个数据

insert()

  1. 	list<int>i = { 2,3,4,5,6,6,7,8 };
  2. 	//第一种
  3. 	//iterator insert (iterator position, const value_type& val);
  4. 	//在迭代器指定位置插入一个数据
  5. 	list<int>::iterator it = i.begin();
  6. 	while (it != i.end())
  7. 	{
  8. 		if ((*it) == 4)break;
  9. 		it++;
  10. 	}
  11. 	
  12. 	it=i.insert(it, 4);
  13. 	cout << (*it);
  14. 	cout << endl;
  15. 	//这个重载还会返回迭代器，比如插入了一个4，那返回的就是指向这个4的迭代器
  16. 	//i: 2,3,4,4,5,6,6,7,8
  17.  
  18. 	//第二种
  19. 	//void insert (iterator position, size_type n, const value_type& val);
  20. 	//注意，这个重载是插入多个相同值的元素
  21. 	i.insert(it, 4,6);
  22. 	//i:2 3 4 6 6 6 6 4 5 6 6 7 8
  23. 	it = i.begin();
  24. 	list<int>c;
  25. 	//第三种,迭代器区间
  26. 	//template <class InputIterator>
  27. 	//void insert(iterator position, InputIterator first, InputIterator last);
  28. 	c.insert(c.begin(),i.begin(), i.end());
  29. 	//c::2 3 6 6 6 6 4 4 5 6 6 7 8

erase()

  1. 	list<int>i = { 2,3,4,5,6,6,7,8 };
  2. 	list<int>::iterator it = i.begin();
  3. 	while ((*it) != 4)it++;
  4. 	//第一种
  5. 	//iterator erase (iterator position);
  6. 	//删除迭代器指向数据，返回删除之后，新的原相对位置的数据的迭代器
  7. 	it=i.erase(it);
  8. 	//i:2 3 5 6 6 7 8
  9.  
  10. 	//第二种，删除迭代器区间的元素
  11. 	//iterator erase (iterator first, iterator last);
  12. 	while ((*it) != 6)it++;
  13. 	i.erase(it, i.end());
  14. 	//i:2 3 5
  15.

swap()

简单的交换

resize()

扩容

  1. void resize (size_type n, value_type val = value_type());
  2. 给n个空间大小，初始化值val
  3. 这里是调用无参构造

clear()

清空容器

2.6操作

 reverse()

经典的逆置函数

  1. 	list<int>i = { 2,3,4,5,6,6,7,8 };
  2. 	i.reverse();
  3. 	//i:8 7 6 6 5 4 3 2

sort()

排序，默认从小到大排，你可以自己写个规则,用法跟algorithm的sort()一样

之所以单独提供，是因为链表的物理空间不连续，而算法库的sort是针对连续物理空间的

而且算法库用的是快排，而链表这里用的是归并

平时用的话，速度还不如直接拷贝到vector，用算法库的sort之后，再拷贝回链表快

merge()

合并两个有序的链表，注意一定要有序，然后根据规则（默认从小到大），跟algorithm的sort()一样.

unique()

去重，注意，相同的必须紧邻，所以你可以先sort()，如果为了适配自定义类型，可以自己写个规则，跟algorithm的sort()一样

remove()

跟erase的最大区别就是，不用给迭代器，只用给值，相当于容器自己找


remove_if()

满足条件才删除

splice()

  1. 	list<int>i = { 2,3,4,5,6,6,7,8 };
  2. 	list<int>b = { 6,7,8,9,0,34,12,1 };
  3. 	//第一种
  4. 	//void splice (iterator position, list& x);
  5. 	//直接把x的所有节点都转移过去，x变空
  6. 	i.splice(i.begin(), b);
  7. 	//i:6 7 8 9 0 34 12 1 2 3 4 5 6 6 7 8
  8.  
  9. 	//void splice (iterator position, list& x, iterator i);
  10. 	list<int>c= { 6,7,8,9,0,34,12,1 };
  11. 	i.splice(i.begin(), c, c.begin());
  12. 	//i:6 6 7 8 9 0 34 12 1 2 3 4 5 6 6 7 8
  13. 	//是将第二个参数指向的链表中的最后一个参数的位置的值转移过去
  14. 	//c的第一个6会没掉
  15. 	
  16. 	//void splice (iterator position, list& x, iterator first, iterator last);
  17. 	//这个就不示范了，就是把一个区间的节点转移过去

注意，可以自己转移自己，就是在一个链表里面转移

3.模拟

反向迭代器，我在这里先不实现，等后面另一篇文章的时候再补充上去

  1. #pragma once
  2. #include<assert.h>
  3. namespace manba {
  4. 	//注意，这个是节点的类，我们实现的是双向带头链表，所以要有前驱和后驱
  5. 	template<class T>
  6. 	struct ListNode {
  7. 		ListNode<T>* _next;//前驱
  8. 		ListNode<T>* _prev;//后驱
  9. 		//注意<>在类里面，是可以忽略的，但我们严谨一些
  10. 		T _data;//存数据
  11. 		ListNode(const T& x=T())//默认构造函数，方便后面调用,因为不确定参数类型，所以默认值
  12. 			//直接用T类型的默认构造即可，不管是内置还是自定义都可以符合
  13. 			:_next(nullptr)
  14. 			, _prev(nullptr)
  15. 			, _data(x)
  16. 		{}
  17. 	};
  18. 	
  19. 	//这里通过Ref，第二个模板参数，简约的实现了const迭代器和正常迭代器的转换
  20. 	//ptr控制的是配合重载->，区分const迭代器和普通迭代器
  21. 	template<class T,class Ref,class Ptr>
  22. 	struct _list_iterator {
  23. 		typedef ListNode<T> Node;
  24. 		//注意，类名<T>才是一个链表节点类型，这里重命名一下，方便后面少写点
  25. 		typedef _list_iterator<T,Ref,Ptr> self;
  26. 		//跟上面一个同理,这里是一个链表迭代器类型
  27. 		Node* _node;
  28. 		//迭代器本质还是指针，只是因为原始指针针对物理空间不连续的容器，无法实现++
  29. 		//而我们无法重载指针，所以我们采用封装的方式，将指针封装起来，将封装起来的迭代器
  30. 		//重载前后置++，前后置--，解引用*等运算符，理由前驱后驱指针，实现向前向后走
  31.  
  32.  
  33. 		_list_iterator(Node* node)//这里是默认构造，方便各种调用
  34. 			:_node(node)
  35. 		{}
  36.  
  37.  
  38. 		//前置++
  39. 		self& operator++()
  40. 		{
  41. 			_node = _node->_next;
  42. 			return *this;
  43. 		}
  44. 		
  45. 		//后置++
  46. 		//注意，这里我们返回的时候不用&，因为tmp是局部变量，函数结束后会销毁，所以直接返回迭代器类型
  47. 		self operator++(int)
  48. 		{
  49. 			self tmp(*this);
  50. 			_node = _node->_next;
  51. 			return tmp;
  52. 		}
  53.  
  54. 		//前置--
  55. 		self& operator--() {
  56. 			_node = _node->_prev;
  57. 			return *this;
  58. 		}
  59.  
  60. 		//后置--，理由同理
  61. 		self operator--(int)
  62. 		{
  63. 			self tmp(*this);
  64. 			_node = _node->_prev;
  65. 			return tmp;
  66. 		}
  67.  
  68. 		//解引用,利用ref，实现const迭代器和普通迭代器
  69. 		Ref operator*()
  70. 		{
  71. 			return _node->_data;
  72. 		}
  73. 		//不等于
  74. 		bool operator !=(const self& s)
  75. 		{
  76. 			return _node != s._node;
  77. 		}
  78. 		//等于
  79. 		bool operator==(const self& s)
  80. 		{
  81. 			return _node == s._node;
  82. 		}
  83. 		Ptr operator->()
  84. 		{
  85. 			return &_node->_data;
  86. 		}
  87. 		/*struct AA {
  88. 			int b;
  89. 			AA(int a = 1)
  90. 				:b(a)
  91. 			{
  93. 			}
  94. 		};*/
  95. 		/*manba::List<manba::AA> l1;
  96. 		l1.push_back(3);
  97. 		l1.push_back(7);
  98. 		l1.push_back(9);
  99. 		l1.push_back(12);
  100. 		manba::List<manba::AA>::iterator it = l1.begin();
  101. 		while (it != l1.end())
  102. 		{
  104. 			cout << it.operator->()->b << endl;
  105. 			cout<<it->b<<endl;
  106. 			it++;
  107. 		}
  108. 		cout << endl;*/
  109. 	};
  110.  
  111. 	//const迭代器
  112. 	//template<class T>
  113. 	//struct _list_const_iterator {
  114. 	//	typedef ListNode<T> Node;
  115. 	//	//注意，类名<T>才是一个链表节点类型，这里重命名一下，方便后面少写点
  116. 	//	typedef _list_const_iterator<T> self;
  117. 	//	//跟上面一个同理,这里是一个链表迭代器类型
  118. 	//	Node* _node;
  119. 	//	//迭代器本质还是指针，只是因为原始指针针对物理空间不连续的容器，无法实现++
  120. 	//	//而我们无法重载指针，所以我们采用封装的方式，将指针封装起来，将封装起来的迭代器
  121. 	//	//重载前后置++，前后置--，解引用*等运算符，理由前驱后驱指针，实现向前向后走
  122.  
  123.  
  124. 	//	_list_const_iterator(Node* node)//这里是默认构造，方便各种调用
  125. 	//		:_node(node)
  126. 	//	{}
  127.  
  128.  
  129.  
  130. 	//	//前置++
  131. 	//	self& operator++()
  132. 	//	{
  133. 	//		_node = _node->_next;
  134. 	//		return *this;
  135. 	//	}
  136.  
  137. 	//	//后置++
  138. 	//	//注意，这里我们返回的时候不用&，因为tmp是局部变量，函数结束后会销毁，所以直接返回迭代器类型
  139. 	//	self operator++(int)
  140. 	//	{
  141. 	//		self tmp(*this);
  142. 	//		_node = _node->_next;
  143. 	//		return tmp;
  144. 	//	}
  145.  
  146. 	//	//前置--
  147. 	//	self& operator--() {
  148. 	//		_node = _node->_prev;
  149. 	//		return *this;
  150. 	//	}
  151.  
  152. 	//	//后置--，理由同理
  153. 	//	self operator--(int)
  154. 	//	{
  155. 	//		self tmp(*this);
  156. 	//		_node = _node->_prev;
  157. 	//		return tmp;
  158. 	//	}
  159.  
  160. 	//	//解引用
  161. 	//	const T& operator*()
  162. 	//	{
  163. 	//		return _node->_data;
  164. 	//	}
  165. 	//	//不等于
  166. 	//	bool operator !=(const self& s)
  167. 	//	{
  168. 	//		return _node != s._node;
  169. 	//	}
  170. 	//	//等于
  171. 	//	bool operator==(const self& s)
  172. 	//	{
  173. 	//		return _node == s._node;
  174. 	//	}
  175. 	//};
  176. 	template<class T>
  177. 	class List {
  178. 		typedef ListNode<T> Node;
  179. 	public:
  180. 		
  181. 		typedef _list_iterator<T,T&,T*> iterator;
  182. 		//typedef _list_const_iterator<T> const_iterator;
  183. 		
  184. 		//这里迭代器直接传const类型的模板参数
  185. 		typedef _list_iterator<T, const T&,const T*> const_iterator;
  186. 		//跟上面一样
  187. 		//空链表初始化
  188. 		void empty_init() {
  189. 			_head = new Node;
  190. 			_head->_next = _head;
  191. 			_head->_prev = _head;
  192. 		}
  193. 		//默认构造函数
  194. 		List() {
  195. 			empty_init();
  196. 		}
  197. 		//拷贝构造函数
  198. 		//List(const List<T> &cp)
  199. 		List(List<T>& cp)
  200. 		{
  201. 			empty_init();
  202. 			for (const auto& e : cp)
  203. 			{
  204. 				push_back(e);
  205. 			}
  206. 		}
  207.  
  208. 		//交换函数,交换物理地址
  209. 		void swap(List<T>&t)
  210. 		{
  211. 			std::swap(_head, t._head);
  212. 		}
  213. 		//赋值
  214. 		//第一种
  215. 		//List<T>& operator=(const List<T>& t2)
  216. 		/*List<T>& operator=( List<T>& t2)
  217. 		{
  218. 			
  219. 			if (this != &t2)
  220. 			{
  221. 				clear();
  222. 				for (const auto& e : t2)
  223. 				{
  224. 					push_back(e);
  225. 				}
  226. 			}
  227. 			return *this;
  228. 		}*/
  229. 		//第二种
  230. 		//这个方法的妙处在于，因为外面要赋值的链表是直接通过拷贝构造直接给了t2链表
  231. 		// ，也就是传值。
  232. 		//而拷贝构造我们用的是深拷贝，这样t2的空间和外面的类是不一样的，如此，直接
  233. 		//让this链表和t2交换，函数结束之后，t2作为局部变量，t2会自动调用析构函数。
  234. 		List<T>& operator=(List<T> t2)
  235. 		{
  236. 			swap(t2);
  237. 			return *this;
  238. 		}
  239.  
  240. 		//返回第一个有效节点的迭代器
  241. 		iterator begin()
  242. 		{
  243. 			return _head->_next;
  244. 		}
  245.  
  246. 		iterator end()
  247. 		{
  248. 			return _head;
  249. 		}
  250. 		//返回第一个有效节点的const迭代器
  251. 		const_iterator begin() const
  252. 		{
  253. 			return _head->_next;
  254. 		}
  255.  
  256. 		const_iterator end() const
  257. 		{
  258. 			return _head;
  259. 		}
  260. 		//尾插
  261. 		void push_back(const T& x)
  262. 		{
  263. 			insert(iterator(_head), x);
  264. 		}
  265. 		//头插
  266. 		void push_front(const T& x)
  267. 		{
  268. 			insert(begin(), x);
  269. 		}
  270. 		//尾删
  271. 		void pop_back()
  272. 		{
  273. 			erase(--end());
  274. 		}
  275. 		//头删
  276. 		void pop_front()
  277. 		{
  278. 			erase(begin());
  279. 		}
  280.  
  281. 		//在指定位置前面插入
  282. 		//vector 迭代器在insert会失效，list不会
  283. 		iterator insert(iterator pos, const T& x)
  284. 		{
  285. 			Node* cur = pos._node;
  286. 			Node* prev = cur->_prev;
  287. 			Node* newnode = new Node(x);
  288. 			prev->_next = newnode;
  289. 			newnode->_prev = prev;
  290. 			newnode->_next = cur;
  291. 			cur->_prev = newnode;
  292. 			return iterator(newnode);
  293. 		}
  294. 		//删除指定位置
  295. 		iterator erase(iterator pos)
  296. 		{
  297. 			assert(pos != end());
  298. 			Node* cur = pos._node;
  299. 			Node* prev = cur->_prev;
  300. 			Node* next = cur->_next;
  301. 			prev->_next = next;
  302. 			next->_prev = prev;
  303. 			delete cur;
  304. 			return next;
  305. 		}  
  306. 		//注意，vector在insert和erase处都会有迭代器失效的风险，所以要注意返回值。
  307. 		//而list在insert处不会，不用担心，但是erase处就要考虑这个问题了，要注意接收返回值。
  308. 		//更详细的，可以参考我在vector文章里，vector的模拟中对insert和erase的模拟。
  309. 		//另外补充一下，vector处的erase会出现迭代器失效，主要是针对vs的强制检查和如果删除了最后一个
  310. 		//元素，会导致迭代器超出了数组有效范围。
  311. 		//而对于list的erase，因为链表底层物理不一定是连续的，这样原迭代器封装的指针指向的空间是非法空间，
  312. 		//所以要注意返回值。
  313.  
  314. 		//清空链表
  315. 		void clear()
  316. 		{
  317. 			iterator it = begin();
  318. 			while (it != end())
  319. 			{
  320. 				it = erase(it);
  321. 			}
  322. 		}
  323.  
  324. 		//析构函数
  325. 		~List()
  326. 		{
  327. 			clear();
  328. 			delete _head;
  329. 			_head = nullptr;
  330. 		}
  331. 	private:
  332. 		Node* _head;
  333. 		//头结点，注意，整个list是左闭右开，head是也是end()返回的
  334.  
  335. 	};
  336. 	
  337. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/860603
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号