C++STL之＜list＞

目录

• 🌈前言
• • 🌸 list
• 🌷1、list的介绍及使用
• • 🌸1.1、list的介绍
  • 🌹1.2、list的使用
  • • 🌹1.2.1、list容器常见的构造函数
    • 🌺1.2.2、list iterator（迭代器的使用）
    • 🌻1.2.3、list capacity
    • 🌼1.2.4、list element access
    • 🌿1.2.5、list modifiers
    • 🍀1.2.5、list迭代器失效问题
• 🍁2、list模拟实现
• • 🍂2.1、模拟实现list（vs2022）
  • 🍃2.2、对mylist接口进行测试
• 🍄 3、list与vector的对比

🌈前言

本篇文章进行STL中list（双向链表）序列容器的学习！！！

---

🌸 class="superseo">list 🌷1、list的介绍及使用 🌸1.1、list的介绍

【list的文档介绍】

1. list是可以在常数范围内在任意位置进行插入和删除的序列容器，并且该容器可以前后双向迭代
2. list的底层是双向链表结构，双向链表中每个元素存储在互不关联的独立节点中，在节点中听过指针指向其前一个元素和后一个元素来进行链接
3. list与forward_list非常相似：最主要的不同在于fowward_list是单链表，只能往前进行迭代，已让其简单高效，而list可以往前和往后进行迭代
4. list与其他容器相比（array、vector、deque），list通常在任意位置进行插入、移除元素的执行效率更好，尾插尾删效率慢，需要迭代一遍
5. list与其他序列容器相比，list和forward_list最大的缺陷是不支持任意位置的访问
   比如：

• 要访问list的第n个元素，必须从已知的位置（头结点或尾节点）迭代到该位置，在这段位置上迭代需要线性时间的开销
• list还需要一些额外的空间，以保持每个节点的相关信息（对于存储类型较小元素的大list来说这可能是一个重要的因素）

list底层原理图(双向链表)：

---

🌹1.2、list的使用

list中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展的能力。以下为list中一些常见的重要接口

---

🌹1.2.1、list容器常见的构造函数

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

举个栗子🌰：

void TestList()
{
	list<int> l1; 		  				// 构造空的list
	list<int> l2(5, 100); 				// 构造5个值为100的list
	list<int> l3(l2); 	  				// 拷贝构造函数
	list<int> l4(l3.begin(), l3.end()); // 使用迭代器来构造list

	int Array[] = { 1, 2, 3, 4 };
	// 以数组为迭代器区间来构造list[Array, Array + 4)
	list<int> l5(Array, Array + sizeof(Array) / sizeof(int));

	// 使用迭代器进行遍历输出
	list<int>::iterator It = l5.begin();
	while (It != l5.end())
	{
		cout << *It << ' ';
		++It;
	}
	cout << endl;

	// 使用C++11基于for范围循环进行遍历输出
	for (auto e : l5)
		cout << e << ' ';
	cout << endl;
}

---

🌺1.2.2、list iterator（迭代器的使用）

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

【注意】

1. begin与end为正向迭代器，对迭代器执行++ *** 作，迭代器向后移动
2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++ *** 作，迭代器向前移动
   

举个栗子🌰：

void print_list(const list<int>& l)
{
	// 注意这里调用的是list的 begin() const，返回list的const_iterator对象
	for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it)
	{
		cout << *it << " ";
		// *it = 10; 编译不通过 --- 被const修饰不能修改
	}
	cout << endl;
}
int main()
{
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	list<int> l(array, array + sizeof(array) / sizeof(array[0]));
	// 使用正向迭代器正向list中的元素
	for (list<int>::iterator it = l.begin(); it != l.end(); ++it)
		cout << *it << " ";
	cout << endl;

	// 使用反向迭代器逆向打印list中的元素
	for (list<int>::reverse_iterator it = l.rbegin(); it != l.rend(); ++it)
		cout << *it << " ";
	cout << endl;
	return 0;
}

---

🌻1.2.3、list capacity

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

举个栗子🌰：

void TestListCapacity()
{
	list<int> v1;
	list<int> v2{ 1, 2, 3, 4 };
	cout << "v1的有效节点个数为: " << v1.size() << '\t'
		<< "v1是否为空: " << v1.empty() << endl;

	cout << "v2的有效节点个数为: " << v2.size() << '\t'
		<< "v是否为空: " << v2.empty() << endl;
}

int main()
{
	TestListCapacity();
	return 0;
}

---

🌼1.2.4、list element access

函数声明	接口说明
front	返回list第一个节点中值（val）的引用
back	返回list最后一个节点中值（val）的引用

举个栗子🌰：

void TestList()
{
	list<int> v{ 1, 2, 3, 4, 5 };

	// 输出list中第一个节点的数据
	cout << v.front() << endl;
	
	// 输出list中最后一个节点的数据
	cout << v.back() << endl;

	// 将list第一个节点数据修改成100
	v.front() = 100;
	for (auto It = v.begin(); It != v.end(); ++It)
		cout << *It << ' ';
	cout << endl;

	// 将list最后一个节点数据修改成200
	v.back() = 200;
	for (auto It = v.begin(); It != v.end(); ++It)
		cout << *It << ' ';
	cout << endl;
}

int main()
{
	TestList();
	return 0;
}

注意：二个接口返回的是这个数据的引用，引用可以充当左值…

---

🌿1.2.5、list modifiers

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

举个栗子🌰1️⃣：

void PrintList(list<int>& l)
{
	for (auto& e : l)
		cout << e << " ";
	cout << endl;
}

void TestList1()
{
	// 测试push_back、pop_back、pusk_front、pop_front
	int array[] = { 1, 2, 3 };
	list<int> L(array, array + sizeof(array) / sizeof(array[0]));
	// 在list的尾部插入4，头部插入0

	L.push_back(4);
	L.push_front(0);
	PrintList(L);

	// 删除list尾部节点和头部节点
	L.pop_back();
	L.pop_front();
	PrintList(L);
}

举个栗子🌰2️⃣：

// 测试insert、erase接口
void TestList2()
{
	int Array1[] = { 1, 2, 3 };
	list<int> L(Array1, Array1 + sizeof(Array1) / sizeof(Array1[0]));
	
	// 获取list中第二个节点
	auto pos = ++L.begin();
	cout << *pos << endl;

	// 在pos前插入值为4的元素
	L.insert(pos, 4);
	PrintList(L);

	// 在pos前插入5个值为5的元素
	L.insert(pos, 5, 5);
	PrintList(L);

	// 在pos前插入[v.begin(), v.end)区间中的元素
	vector<int> v{ 7, 8, 9 };
	L.insert(pos, v.begin(), v.end());
	PrintList(L);

	// 删除pos位置上的元素
	L.erase(pos);
	PrintList(L);

	// 删除list中[begin, end)区间中的元素，即删除list中的所有元素
	L.erase(L.begin(), L.end());
	PrintList(L);
}

举个栗子🌰3️⃣：

void PrintList(list<int>& l)
{
	for (auto& e : l)
		cout << e << " ";
	cout << endl;
}

void TestList3()
{
	// 测试swap、clear接口
	// 用数组来构造list
	int array1[] = { 1, 2, 3 };
	list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));
	PrintList(l1);

	list<int> l2{ 3, 2, 1 };
	PrintList(l2);

	// 交换l1和l2中的元素
	l1.swap(l2);
	PrintList(l1);
	PrintList(l2);

	// 将l2中的元素清空
	l2.clear();
	cout << l2.size() << endl;
}

---

🍀1.2.5、list迭代器失效问题

迭代器失效：

• 前面说过，大家可以将迭代器暂时理解成原生态指针，迭代器失效即所指向的节点已被销毁或释放，即该节点被删除了。
• list的底层结构为双向链表，因此在list中进行插入时，是不会导致list迭代器失效的（list底层存储空间不连续
• 只有在删除节点时才会失效，并且失效的知识指向被删除节点的迭代器，其他迭代器不受影响

举个栗子🌰：

// 错误写法
void TestListIterator1()
{
	int Array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	list<int> l(Array, Array + sizeof(Array) / sizeof(int));

	auto It = l.begin();
	while (It != l.end())
	{
		// erase()接口被执行后，It所指向的节点已被删除，导致It迭代器无效，在下一次使用时，必须重新赋值
		l.erase(It);
		++It;
	}
}

// 正确写法
void TestListIterator2()
{
	int Array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	list<int> l(Array, Array + sizeof(Array) / sizeof(int));

	auto It = l.begin();
	while (It != l.end())
	{
		// erase()接口被执行后，对It重新赋值
		l.erase(It++); // It = l.erase(It)
	}
}

🍁2、list模拟实现 🍂2.1、模拟实现list（vs2022）

list.h

#ifndef LIST_H_
#define LIST_H_

#include 
#include 
#include 

namespace mylist
{
	// 首先，构造节点模板类
	template <typename T>
	struct ListNode
	{
		ListNode<T>* _Pre; // 前驱指针域
		ListNode<T>* _Next; // 后驱指针域
		T _val; // 数据

		//构造函数
		ListNode(const T& val = T())
			: _Pre(nullptr)
			, _Next(nullptr)
			, _val(val)
		{}
	};

	/*
	List 的迭代器
	迭代器有两种实现方式，具体应根据容器底层数据结构实现:
		1、原生态指针，比如：vector
		2、将原生态指针进行封装，因迭代器使用形式与指针完全相同，因此自定义的类中必须实现以下
	方法：
		1、指针可以解引用，迭代器的类必须重载operator*()
		2、指针可以通过->访问其所指向的空间成员，也必须重载operator->()
		3、指针可以++向后移动，迭代器类必须重载operator++()与operator++(int)
		   至于operator--()和operator--(int)释放需要重载，根据具体结构来抉择
		   list可以向后查找，所以需要重载，如果是forword_list(单链表)就不用重载

	*/

	// 封装一个迭代器
	template <typename T, typename Ref, typename Ptr>
	class ListIterator
	{
		// 类型重命名
		typedef ListIterator<T, Ref, Ptr> Self; // 迭代器本身
		typedef ListNode<T>* PNode;
	public:
		PNode _PNode; // 指向节点的指针

		//--------------------------------------------------------------- constructor（构造）
		ListIterator(PNode x = nullptr)
			: _PNode(x)
		{}

		ListIterator(const Self& s)
			: _PNode(s._PNode)
		{}

		// Compare operator
		bool operator ==(const Self& s) { return _PNode == s._PNode; }
		bool operator !=(const Self& s) { return _PNode != s._PNode; }

		// ---------------------------------------------------------------- * -> operator
		// *重载是对迭代器取值，取的是节点的数据值
		T& operator*() { return _PNode->_val; }
		T* operator->() { return &(operator*()); }

		// -----------------------------------------------------------------  ++ -- operator
		Self& operator++()
		{
			_PNode = _PNode->_Next;
			return *this;
		}
		Self operator++(int)
		{
			Self tmp(*this);
			_PNode = _PNode->_Next;
			return tmp;
		}

		Self& operator--()
		{
			_PNode = _PNode->_Pre;
			return *this;
		}
		Self operator--(int)
		{
			Self tmp(*this);
			_PNode = _PNode->_Pre;
			return tmp;
		}
	};

	template <typename T>
	class list
	{
		//------------------------------------------------------------------------- typedef
		typedef ListNode<T>* PNode;
		typedef ListIterator<T, T*, T&> iterator; // 普通迭代器
		typedef ListIterator<T, const T&, const T&> const_iterator; // 常量迭代器
	
	public:
		//-------------------------------------------------------------------------- iterator
		iterator begin() { return iterator(_pHead->_Next); }
		iterator end() { return iterator(_pHead); }
		const_iterator cbegin() { return const_iterator(_pHead->_Next); }
		const_iterator cend() { return const_iterator(_pHead); }
		//-------------------------------------------------------------------------- constuctor(构造)
		list() { CreatNode(); } // 构造空list

		list(size_t n, const T& val = T())
		{
			CreatNode();
			for (int i = 0; i < n; ++i)
				push_back(val);
		}

		list(const list<T>& l)
		{
			CreatNode();

			/*list temp(l.cbegin(), l.cend());
			this->swap(temp);*/

			PNode cur = l._pHead->_Next;
			while (cur != l._pHead)
			{
				push_back(cur->_val);
				cur = cur->_Next;
			}
		}

		template<typename iterator>
		list(iterator* first, iterator* last)
		{
			CreatNode();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

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

		~list()
		{
			clear();
			delete _pHead;
			_pHead = nullptr;
		}
		
		//-------------------------------------------------------------------------- list capacity
		size_t size()
		{
			size_t size = 0;
			PNode cur = _pHead->_Next;
			while (cur != _pHead)
			{
				++size;
				cur = cur->_Next;
			}
			return size;
		}
		bool empty() { return _pHead->_Next == nullptr; }

		//-------------------------------------------------------------------------- list Moidfy
		// 增删查改 随机插入 随机删除
		void push_back(const T& val)
		{
			PNode newNode = new ListNode<T>(val);
			PNode tailPrev = _pHead->_Pre;

			tailPrev->_Next = newNode;
			newNode->_Pre = tailPrev;

			newNode->_Next = _pHead;
			_pHead->_Pre = newNode;
		}

		void pop_back()
		{
			// 存储尾节点后一个节点
			PNode tailprev = _pHead->_Pre->_Pre;
			// 当只有一个节点时，需要独自进行处理
			if (_pHead->_Next->_Next == nullptr)
			{
				delete _pHead->_Next;
				_pHead->_Next = _pHead;
				_pHead->_Pre = _pHead;
			}
			else
			{
				delete _pHead->_Pre;
				tailprev->_Next = _pHead;
				_pHead->_Pre = tailprev;
			}
		}

		void push_front(const T& val)
		{
			PNode newNode = new ListNode<T>(val);

			PNode next = _pHead->_Next;
			_pHead->_Next = newNode;
			newNode->_Pre = _pHead;
			newNode->_Next = next;
			next->_Pre = newNode;
		}

		void pop_front()
		{
			PNode next = _pHead->_Next->_Next;
			if (next == nullptr)
			{
				delete _pHead->_Next;
				_pHead->_Next = _pHead;
				_pHead->_Pre = _pHead;
			}
			else
			{
				PNode nextnode = _pHead->_Next;
				_pHead->_Next = next;
				next->_Pre = _pHead;
				delete nextnode;
			}
		}

		PNode find(const T& val)
		{
			PNode cur = _pHead->_Next;
			while (cur != _pHead->_Pre)
			{
				if (cur->_val == val)
					return cur;
				cur = cur->_Next;
			}
			return nullptr;
		}

		iterator insert(iterator pos, const T& val)
		{
			PNode newNode = new ListNode<T>(val);
			PNode Posprev = pos._PNode->_Pre;

			Posprev->_Next = newNode;
			newNode->_Pre = Posprev;
			
			newNode->_Next = pos._PNode;
			pos._PNode->_Pre = newNode;

			return iterator(newNode);
		}

		iterator erase(iterator pos)
		{
			PNode Posnext = pos._PNode->_Next;
			PNode Posprev = pos._PNode->_Pre;

			Posprev->_Next = Posnext;
			Posnext->_Pre = Posprev;
			delete pos._PNode;

			return iterator(Posnext);
		}

		//-------------------------------------------------------------------------- list Access
		T& front() { return _pHead->_Next->_val; }
		const T& front()const { return _pHead->_Next->_val; }
		T& back() { return _pHead->_Pre->_val; }
		const T& back()const { return _pHead->_Pre->_val; }

		//-------------------------------------------------------------------------- 其他辅助接口
		void clear()
		{
			PNode cur = _pHead->_Next;

			while (cur != _pHead)
			{
				PNode curNext = cur->_Next;
				delete cur;
				cur = curNext;
			}
			_pHead->_Next = _pHead;
			_pHead->_Pre = _pHead;
		}

		void swap(list<T>& l)
		{
			std::swap(_pHead, l._pHead);
		}
	private:
		void CreatNode()
		{
			// 带头双向循环链表为空时一开始前后驱指针都指向自己
			_pHead = new ListNode<T>;
			_pHead->_Next = _pHead;
			_pHead->_Pre = _pHead;
		}
		//--------------------------------------------------------------------------
	private:
		PNode _pHead;
	};
}

#endif

🍃2.2、对mylist接口进行测试

list.cpp

#include "list.h"
using namespace std;

// 正向打印list
template <typename T>
void Printlist(mylist::list<T>& l)
{
	auto It = l.cbegin();
	while (It != l.cend())
	{
		cout << *It << ' ';
		++It;
	}
	cout << endl;
}

// 测试list构造
void Test_list_constructor()
{
	mylist::list<int> l1;
	mylist::list<int> l2(10, 5);
	Printlist<int>(l2);

	int Array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	mylist::list<int> l3(Array, Array + sizeof(Array) / sizeof(int));
	Printlist(l3);

	mylist::list<int> l4(l3);
	Printlist(l4);

	l1 = l4;
	Printlist(l1);
}

// 测试pusk_back、pop_back、pusk_front、pop_front
void Testlist2()
{
	// 测试push_back、pop_back
	mylist::list<int> l;
	for (int i = 0; i < 5; ++i)
		l.push_back(i);
	Printlist(l);

	for (int i = 0; i < 5; ++i)
		l.pop_back();

	cout << l.size() << endl;

	// 测试pusk_front、pop_front
	for (int i = 0; i < 5; ++i)
		l.push_front(i);
	Printlist(l);

	for (int i = 0; i < 5; ++i)
		l.pop_front();

	cout << l.size() << endl;

}

void Testlist3()
{
	int array[] = { 1, 2, 3, 4, 5 };
	mylist::list<int> l(array, array + sizeof(array) / sizeof(array[0]));
	auto pos = l.begin();
	l.insert(l.begin(), 0);
	Printlist(l);

	++pos;
	l.insert(pos, 2);
	Printlist(l);

	l.erase(l.begin());
	l.erase(pos);
	Printlist(l);

	// pos指向的节点已经被删除，pos迭代器失效
	cout << *pos << endl;

	auto it = l.begin();
	while (it != l.end())
		it = l.erase(it);

	cout << l.size() << endl;
}

int main()
{
	Test_list_constructor();
	Testlist2();
	Testlist3();
	return 0;
}

---

🍄 3、list与vector的对比

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：

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