360度无死角刨析C++STL中list的使用和实现，list与vector的对比

·1. list的介绍及使用
·2. list的深度剖析及模拟实现
·3. list与vector的对比

1. list的介绍及使用

1.1 list的介绍

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

1.2 list的使用

1.2.1 list的构造

void test_list1()
{
	std::list<int> l1; // 构造空的l1
	std::list<int> l2(4, 100); // l2中放4个值为100的元素
	std::list<int> l3(l2.begin(), l2.end()); // 用l2的[begin(), end()）左闭右开的区间构造l3
	std::list<int> l4(l3); // 用l3拷贝构造l4
	int array[] = { 16,2,77,29 };
	std::list<int> l5(array, array + sizeof(array) / sizeof(int));// 以数组为迭代器区间构造l5
	for (std::list<int>::iterator it = l5.begin(); it != l5.end(); it++)
		std::cout << *it << " ";// 用迭代器方式打印l5中的元素
	std::cout << endl;
	// C++11范围for的方式遍历
	for (auto& e : l5)
		std::cout << e << " ";
	std::cout << endl;
}

注：上例l5中，数组就是原生指针，可以当作天然迭代器使用，其实vector/string的迭代器也是原生指针.

1.2.2 list iterator的使用

此图为List的底层抽象模型，需牢记！

注：

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

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

常见的迭代器分为三种:
单向迭代器(forwardIterator):++ forward_list,unordered_map
双向迭代器(BidirectionalIterator):++/-- list
随机迭代器(RandomAccessIterator):++/--/+/- vector,string

1.2.3 list capacity

1.2.4 list element access

1.2.5 list modifiers

template<class Con>
void PrintList(const Con& l)
{
	for (auto& e : l)
		cout << e << " ";
	cout << endl;
}
void test_list4()
{
	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);
}

void test_list5()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	PrintList(lt);
 
	list<int>::iterator pos = find(lt.begin(), lt.end(), 3);
	lt.insert(pos, 30);
	PrintList(lt); 
	//vector insert会导致pos迭代器失效的问题，list不会
	cout << *pos << endl;
	//vector erase会导致pos迭代器失效，list也会
	lt.erase(pos);
	PrintList(lt);
	cout << *pos << endl;//将pos位置删除过后，pos位置为野指针，会造成非法访问的问题
}

void test_list6()
{
	list lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(2);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(4);
	lt.push_back(4);
	lt.push_back(2);
	lt.push_back(2);
	PrintList(lt);
 
	//排序加去重
	lt.sort();//一般情况不太建议使用list的排序，效率不是很高，list底层采用的是归并排序
	lt.unique();//去重只会去掉连续的相同的数据
	PrintList(lt);
}

void test_list7()
{
	// 用数组来构造list
	int array1[] = { 1, 2, 3 };
	list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));
	PrintList(l1);
	//
	list<int> lt2;
	lt2.push_back(1);
	lt2.push_back(2);
	lt2.push_back(3);
	lt2.push_back(4);
	// 交换l1和l2中的元素
	l1.swap(lt2);
	PrintList(l1);
	PrintList(lt2);
	// 将l2中的元素清空
	lt2.clear();
	cout << lt2.size() << endl;
}

1.2.6 list的迭代器失效

迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为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);
	}
}

2. list的模拟实现

2.1 模拟实现list

要模拟实现list，必须要熟悉list的底层结构以及其接口的含义，通过上面的学习，这些内容已基本掌握，现在我们来模拟实现list。

namespace Bernard
{
/*
List 的迭代器
迭代器有两种实现方式，具体应根据容器底层数据结构实现：
一. 原生态指针(物理空间是连续的)，比如：vector,string
二. 将原生态指针进行封装，因迭代器使用形式与指针完全相同，因此在自定义的类中必须实现以下
方法：
1. 指针可以解引用，迭代器的类中必须重载operator*()
2. 指针可以通过->访问其所指空间成员，迭代器类中必须重载oprator->()
3. 指针可以++向后移动，迭代器类中必须重载operator++()与operator++(int)
至于operator--()/operator--(int)是否需要重载，根据具体的结构来抉择，双向链表可
以向前移动，所以需要重载，如果是forward_list就不需要重载--
4. 迭代器需要进行是否相等的比较，因此还需要重载operator==()与operator!=()
有了上面这样的方式，让使用者不需要关系容器底层结构到底是数组，链表，树形结构等等
封装隐藏了底层的细节，让我们可以用简单统一的方式去访问修改容器，这就是迭代器真正的价值所在
*/
 
	template<class T>
	struct _list_node
	{
		T _val;
		_list_node<T>* _next;
		_list_node<T>* _prev;
 
		_list_node(const T& val=T())//给T的匿名对象缺省值
			:_val(val)
			,_next(nullptr)
			,_prev(nullptr)
		{}//给出节点的构造函数,初始化值
	};
 
 
	// typedef _list_iterartor<T, T&, T*> iterator;
	// typedef _list_iterartor<T, const T&, const T*> const_iterator;
	template<class T,class Ref,class Ptr>//这里的函数模板这样设计的目的是为了实现迭代器的const版本和普通版本
	struct _list_iterartor//这里为什么要设计为struct的类型呢，因为struct默认为public
	{
		typedef _list_node<T> node;//将节点的指针typedef 一下
		typedef _list_iterartor<T, Ref, Ptr> self;//将迭代器typedef减少代码量，增强可读性
		node* _pnode;//定义迭代器指针
 
		_list_iterartor(node* pnode)
			:_pnode(pnode)
		{}
 
		// 拷贝构造、operator=、析构我们不写，编译器默认浅拷贝生成就可以用
 
		Ref& operator*()//Ref为解引用的值的引用
		{
			return _pnode->_val;//返回这个节点的值
		}
		Ptr operator->()//Ptr为节点的指针
		{
			return &_pnode->_val;//返回节点的地址
		}
		bool operator!=(const self& s) const
		{
			return _pnode != s._pnode;
		}
		bool operator==(const self& s) const
		{
			return _pnode == s._pnode;
		}
		// ++it -> it.operator++(&it)
		self& operator++()//前置++
		{
			_pnode = _pnode->_next;
			return *this;
		}
		// it++ -> it.operator++(&it, 0)增加占位参数
		self operator++(int)//后置++//注意后置++不能返回引用，因为出了作用域tmp销毁了
		{
			self tmp(*this);//用self构造一个tmp
			_pnode = _pnode->_next;
			return tmp;//返回++之前的值
		}
		self& operator--()//前置--
		{
			_pnode = _pnode->_prev;
			return *this;
		}
		self operator--(int)//后置--//注意后置--不能返回引用，因为出了作用域tmp销毁了
		{
			self tmp(*this);//用self构造一个tmp
			_pnode = _pnode->_prev;
			return tmp;//返回--之前的值
		}
	};
 
	template<class T>
	class list
	{
		typedef _list_node<T> node;
	public:
		typedef _list_iterartor<T, T&, T*> iterator;//注意这里命名的变化与上一层迭代器的不同
		typedef _list_iterartor<T, const T&, const T*> const_iterator;//利用模板的特性封装出const的版本
		iterator begin()//begin节点为第一个数据的位置
		{
			return iterator(_head->_next);//利用iterator去构造出begin位置节点返回
		}
		const_iterator begin()const
		{
			return const_iterator(_head->_next);
		}
		iterator end()//end节点为最后一个节点的下一个位置，在双向带头节点中，即为头结点的位置
		{
			return iterator(_head);//利用iterator去构造出end位置节点返回
		}
		const_iterator end()const
		{
			return const_iterator(_head);
		}
		list()
		{
			//_head = new node(T());//如果节点的构造函数没有给默认缺省值，这里就给T的匿名对象
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
		}
		// copy(lt)
		list(const list<T>& l)//拷贝构造
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
			//上面三个步骤是在构造必备的头结点
			for (const auto& e : l)//这里为什么要传const和&,传const是不允许修改，加&是防止T是一个特别大的类型，造成大量的拷贝
			{
				push_back(e);
			}
			//然后利用for循环将l链表里面的节点依次尾插到该节点中
		}
		//copy = lt1;
/*		list<T>& operator=(const list<T>& l)//传统版本的赋值拷贝写法
		{
			if (*this != &l)
			{
				clear();//先清理
				for (const auto& e : l)
				{
					push_back(e);
				}//再转移值
			}
			return *this;
		}*/
		//现代版本写法
		list<T>& operator=(list<T> l)//利用传值传参有一次拷贝,l为拷贝的对象，出了作用域会销毁
		{
			swap(_head, l._head);//交换头结点,最后将this指针进行返回即可
			return *this;
		}
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				//it = erase(it);//采用此种方式利用erase返回下一个位置的指针特性
				erase(it++);//链表也可采用此种方式，利用it++返回的是++之前的值同样可以
			}
		}
		void insert(iterator pos, const T& val)//在pos位置之前插入val
		{
			assert(pos._pnode);//这个pos位置的指针不能为空
			node* cur = pos._pnode;//注意这一步不能少，迭代器封装了pos位置的指针,并且小心这里的pos是迭代器对象，要用.不能使用->
			node* prev = cur->_prev;
			node* newnode = new node(val);
 
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;
		}
		iterator erase(iterator pos)//删除pos位置的值
		{
			assert(pos._pnode);//pos节点不能为空
			assert(pos != end());//不能删除头结点
			node* cur = pos._pnode;
			node* prev = cur->_prev;
			node* next = cur->_next;
 
			delete cur;
			prev->_next = next;
			next->_prev = prev;
			return iterator(next);///因为迭代器又是用指针构造的，传next的指针给iterator去构造返回删除后的下一个位置
		}
		void push_back(const T& val)
		{
			insert(end(), val);
		}
		void push_front(const T& val)
		{
			insert(begin(), val);
		}
		void pop_back()
		{
			erase(--end());
		}
		void pop_front()
		{
			erase(begin());
		}
		bool empty()
		{
			return begin() == end();//begin和end相等就为空
		}
		size_t size()//计算节点的个数
		{
			size_t sz = 0;
			iterator it = begin();
			while (it != end())
			{
				++sz;
				++it;
			}
			return sz;
		}
	private:
		node* _head;//定义头结点
	};
}

2.2 对模拟的bite::list进行测试

    void PrintList(const list<int>& lt)
	{
		list<int>::const_iterator it = lt.begin();
		while (it != lt.end())
		{
			// *it += 1; // ?
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}
 
	class Date
	{
	public:
		int _year = 0;
		int _month = 1;
		int _day = 1;
	};
 
	void test_list1()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
 
		list<int>::iterator it = lt.begin();
		while (it != lt.end())
		{
			*it += 1;
			cout << *it << " ";
			++it;
		}
		cout << endl;
 
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
 
		PrintList(lt);
	}
 
	void test_list2()
	{
		list<Date> lt;
		lt.push_back(Date());
		lt.push_back(Date());
		lt.push_back(Date());
 
		list<Date>::iterator it = lt.begin();
		while (it != lt.end())
		{
			//cout << (*it)._year << " " << (*it)._month <<" " <<(*it)._day<<endl;
			cout << it->_year << " " << it->_month << " " << it->_day << endl;
//it->_year       =       it.operator->()
//相当于是it->->_year  ？ 上面operator->的返回值是Ptr,也就是Date*/T*,通过指针再去解引用一层出来也就相当于是两个箭头
//第一个箭头是去访问对象(T*)中的成员,但是两个箭头程序的可读性很差，为了可读性编译器做了特殊处理
			++it;
		}
		cout << endl;
	}
 
	void test_list3()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		PrintList(lt);
 
		list<int> copy(lt);
		PrintList(copy);
 
		list<int> lt1;
		lt1.push_back(10);
		lt1.push_back(20);
		copy = lt1;
		PrintList(copy);
		PrintList(lt1);
		lt.clear();
		PrintList(lt);
	}

总结：通过上面对list的模拟实现，应该有几点感悟：

1.迭代器底层实现其实就是层层封装，并不是什么特别高大上的东西，也就是指针

2.STL库中list迭代器的设计，有一个非常巧妙的地方，也就是通过类模板，这样的模板体现了面向对象语言的优势

3.弄懂List的底层实现需要层层递进，每一个细节都需要掌握到位才可以理解里面的奥妙

3. list与vector的对比

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