简介 

STL中的List与顺序表vector类似，同样是一种序列式容器，其原型是带头节点的双向循环链表。

List的使用

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

List的构造

构造的使用 

list l1;  无参构造 list l2(5, 10);//放5个值为10的数据 list l3(l2.begin(), l2.end());   迭代器构造 list l4(l3);  拷贝构造

构造的实现 

无参构造

template struct list_node { 	T _data; 	list_node* _next; 	list_node* _prev;  	list_node(const T& data = T()) 		:_data(data) 		, _next(nullptr) 		, _prev(nullptr) 	{} };  template typedef list_node Node; typedef list_iterator Self; Node* _node;  list() { 	_head = new Node; 	_head->_next = _head; 	_head->_prev = _head; 	_size = 0; }   private: 	Node* _head; 	size_t _size;

迭代器iterator

概念

此处我们可以将iterator理解为指针，指向list中的某一个节点。

以图示为例，list头节点的begin()迭代器扮演了指针的角色指向了下一个节点，依次往后。

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

iterator的使用

由于链表节点之间不连续的性质，我们对其进行遍历时也必须使用迭代器或范围for.

我们以链表的遍历打印（顺序和倒序）为例，代码如下：

正序 int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; list l(array, array + sizeof(array) / sizeof(array[0])); // 使用正向迭代器正向list中的元素 // list::iterator it = l.begin();   // C++98中语法 auto it = l.begin();                     // C++11之后推荐写法 while (it != l.end()) {     cout << *it << " ";     ++it; } cout << endl;  倒序 // 使用反向迭代器逆向打印list中的元素  // list::reverse_iterator rit = l.rbegin(); auto rit = l.rbegin();//此句是现代写法，C++11后才支持  while (rit != l.rend()) {     cout << *rit << " ";     ++rit; } cout << endl;

 iterator的实现

begin() 与 end()

iterator begin() { 	/*	iterator it(_head->_next); 		return it;*/ 		//return iterator(_head->_next); 	return _head->_next; 最直接的写法 }  iterator end() { 	return _head; }

list接口

list capacity（容量）

目录

empty判空

bool empty() const { 	return _size == 0; }

size

size_t size() const { 	return _size; }

 list element access（成员访问）

目录

front 

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

back

void pop_back() { 	erase(--end()); }

list modifiers（链表调整）

目录

 insert

void insert(iterator pos, const T& x) { 	Node* cur = pos._node; 	Node* prev = cur->_prev;  	Node* newnode = new Node(x);  	// prev newnode cur 	newnode->_next = cur; 	cur->_prev = newnode; 	newnode->_prev = prev; 	prev->_next = newnode;  	++_size; }

接下来的插入复用insert代码即可。

push_front

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

push_back

void push_back(const T& x) { 	insert(end(), x); }

erase

void erase(iterator pos) { 	assert(pos != end());  	Node* prev = pos._node->_prev; 	Node* next = pos._node->_next;  	prev->_next = next; 	next->_prev = prev; 	delete pos._node;  	--_size; }

同理，头删尾删代码复用删除代码即可。

pop_front

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

pop_back

void pop_back() { 	erase(--end()); }

clear

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

swap

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

使用

插入和删除

void TestList3() {     int array[] = { 1, 2, 3 };     list 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); }

clear

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

swap 

list& operator=(list lt) { 	swap(lt); 	return *this; }

list迭代器失效

        与顺序表类似，list的迭代器失效也是由于iterator指向的节点发生了变化，可能不是我们想要的节点。迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

        在这里，我们仍然举个例子：

void TestListIterator1() {     int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };     list l(array, array + sizeof(array) / sizeof(array[0]));     auto it = l.begin();     while (it != l.end())     {         // erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给         //其赋值         l.erase(it);         ++it;     } }  

同样地，我们只要将l.erase(it)前加上“it = ”即可：

void TestListIterator1() {     int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };     list l(array, array + sizeof(array) / sizeof(array[0]));     auto it = l.begin();     while (it != l.end())     {         // erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给         //其赋值         it = l.erase(it);         ++it;     } } 

list与vector的对比 

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

List实现总代码 

#pragma once #include  #include  #include  using namespace std;  namespace Frenemy { 	template 	struct list_node 	{ 		T _data; 		list_node* _next; 		list_node* _prev;  		list_node(const T& data = T()) 			:_data(data) 			, _next(nullptr) 			, _prev(nullptr) 		{} 	};  	template 	struct list_iterator 	{ 		typedef list_node Node; 		typedef list_iterator Self; 		Node* _node;  		list_iterator(Node* node) 			:_node(node) 		{}  		Ref operator*() 		{ 			return _node->_data; 		}  		Ptr operator->() 		{ 			return &_node->_data; 		}  		Self& operator++() 		{ 			_node = _node->_next; 			return *this; 		}  		Self& operator--() 		{ 			_node = _node->_prev; 			return *this; 		}  		Self operator++(int) 		{ 			Self tmp(*this); 			_node = _node->_next;  			return tmp; 		}  		Self& operator--(int) 		{ 			Self tmp(*this); 			_node = _node->_prev;  			return tmp; 		}  		bool operator!=(const Self& s) const 		{ 			return _node != s._node; 		}  		bool operator==(const Self& s) const 		{ 			return _node == s._node; 		} 	};   	template 	class list 	{ 		typedef list_node Node; 	public: 		/*typedef list_iterator iterator; 		typedef list_const_iterator const_iterator;*/  		typedef list_iterator iterator; 		typedef list_iterator const_iterator;  		iterator begin() 		{ 			/*	iterator it(_head->_next); 				return it;*/ 				//return iterator(_head->_next); 			return _head->_next; 		}  		iterator end() 		{ 			return _head; 		}  		const_iterator begin() const 		{ 			return _head->_next; 		}  		const_iterator end() const 		{ 			return _head; 		}  		void empty_init() 		{ 			_head = new Node; 			_head->_next = _head; 			_head->_prev = _head; 			_size = 0; 		}  		list() 		{ 			empty_init(); 		}  		list(initializer_list il) 		{ 			empty_init(); 			for (auto& e : il) 			{ 				push_back(e); 			} 		}  		// lt2(lt1) 		list(const list& lt) 		{ 			empty_init();  			for (auto& e : lt) 			{ 				push_back(e); 			} 		}  		// lt1 = lt3 		list& operator=(list lt) 		{ 			swap(lt); 			return *this; 		}  		~list() 		{ 			clear(); 			delete _head; 			_head = nullptr; 		}  		void clear() 		{ 			auto it = begin(); 			while (it != end()) 			{ 				it = erase(it); 			} 		}  		// 16:18继续 		void swap(list& lt) 		{ 			std::swap(_head, lt._head); 			std::swap(_size, lt._size); 		}  		void push_back(const T& x) 		{  			insert(end(), x); 		}  		void push_front(const T& x) 		{ 			insert(begin(), x); 		}  		iterator insert(iterator pos, const T& x) 		{ 			Node* cur = pos._node; 			Node* prev = cur->_prev; 			Node* newnode = new Node(x);  			// prev newnode cur 			newnode->_next = cur; 			cur->_prev = newnode; 			newnode->_prev = prev; 			prev->_next = newnode;  			++_size;  			return newnode; 		}  		void pop_back() 		{ 			erase(--end()); 		}  		void pop_front() 		{ 			erase(begin()); 		}  		iterator erase(iterator pos) 		{ 			assert(pos != end());  			Node* prev = pos._node->_prev; 			Node* next = pos._node->_next;  			prev->_next = next; 			next->_prev = prev; 			delete pos._node;  			--_size;  			return next; 		}  		size_t size() const 		{ 			return _size; 		}  		bool empty() const 		{ 			return _size == 0; 		} 	private: 		Node* _head; 		size_t _size; 	};  	struct AA 	{ 		int _a1 = 1; 		int _a2 = 1; 	};  	// 按需实例化 	// T* const ptr1 	// const T* ptr2 	template 	void print_container(const Container& con) 	{ 		// const iterator -> 迭代器本身不能修改 		// const_iterator -> 指向内容不能修改,不能进行权限放大，只能进行权限缩小 		typename Container::const_iterator it = con.begin(); 		//auto it = con.begin(); 		while (it != con.end()) 		{ 			//*it += 10;  			cout << *it << " "; 			++it; 		} 		cout << endl;  		for (auto e : con) 		{ 			cout << e << " "; 		} 		cout << endl; 	}  	void test_list1() 	{ 		list lt; 		lt.push_back(1); 		lt.push_back(2); 		lt.push_back(3); 		lt.push_back(4);  		list::iterator it = lt.begin(); 		while (it != lt.end()) 		{ 			*it += 10;  			cout << *it << " "; 			++it; 		} 		cout << endl;  		for (auto e : lt) 		{ 			cout << e << " "; 		} 		cout << endl; 		print_container(lt);  		list lta; 		lta.push_back(AA()); 		lta.push_back(AA()); 		lta.push_back(AA()); 		lta.push_back(AA()); 		list::iterator ita = lta.begin(); 		while (ita != lta.end()) 		{ 			//cout << (*ita)._a1 << ":" << (*ita)._a2 << endl; 			// 特殊处理，本来应该是两个->才合理，为了可读性，省略了一个-> 			cout << ita->_a1 << ":" << ita->_a2 << endl; 			cout << ita.operator->()->_a1 << ":" << ita.operator->()->_a2 << endl;  			++ita; 		} 		cout << endl; 	}  	void test_list2() 	{ 		list lt1; 		lt1.push_back(1); 		lt1.push_back(2); 		lt1.push_back(3); 		lt1.push_back(4);  		list lt2(lt1);  		print_container(lt1); 		print_container(lt2);  		list lt3; 		lt3.push_back(10); 		lt3.push_back(20); 		lt3.push_back(30); 		lt3.push_back(40);  		lt1 = lt3; 		print_container(lt1); 		print_container(lt3); 	}  	void func(const list& lt) 	{ 		print_container(lt); 	}  	void test_list3() 	{ 		// 直接构造 		list lt0({ 1,2,3,4,5,6 }); 		// 隐式类型转换 		list lt1 = { 1,2,3,4,5,6,7,8 }; 		const list& lt3 = { 1,2,3,4,5,6,7,8 };  		func(lt0); 		func({ 1,2,3,4,5,6 });  		print_container(lt1);		 	} }