list实际上是数据结构中的带头双向循环链表

由于链表的存储方式并不是连续的内存空间，因此链表list中的迭代器只支持前移(++)和后移(--)，属于双向迭代器。

一、常见接口

官方文档：list - C++ Reference (cplusplus.com)

1.1 构造函数

void test1() {         list l1;                         // 构造空的l1     list l2(4, 100);                 // l2中放4个值为100的元素     list l3(l2.begin(), l2.end());  // 用l2的[begin(), end()）左闭右开的区间构造l3     list l4(l3);                    // 用l3拷贝构造l4 }

1.2 访问与遍历

void test1() { 	list l1; 	l1.push_back(1); 	l1.push_back(2); 	l1.push_back(3); 	l1.push_back(4); 	l1.push_back(5);  	list::iterator it = l1.begin(); 	while (it != l1.end()) 	{ 		cout << *it << " "; 		++it; 	} 	cout << endl;  	for (auto e : l1) 	{ 		cout << e << " "; 	} 	cout << endl;  }

1.3 容量操作

1.4 增删查改

//插入和删除 void test1() { 	list L; 	//尾插 	L.push_back(10); 	L.push_back(20); 	L.push_back(30); 	//头插 	L.push_front(100); 	L.push_front(200); 	L.push_front(300); 	//尾删 	L.pop_back(); 	printList(L); 	//头删 	L.pop_front(); 	printList(L); 	//插入 	list::iterator it = L.begin(); 	L.insert(++it, 1000); 	//删除 	it = L.begin(); 	L.erase(++it); 	//移除 	L.push_back(10000); 	L.push_back(10000); 	L.push_back(10000);     // 	L.remove(10000);     //清空 	L.clear(); } //迭代器的底层不是原生指针 //迭代器分类 //单向：forward	-	++ //双向：bidirectional	-	++/-- //随机：random	-	++/--/+/- void test2() { 	list l1; 	l1.push_back(1); 	l1.push_back(2); 	l1.push_back(3); 	l1.push_back(4); 	l1.push_back(5);  	//如何在特定位置插入？ 	auto it = l1.begin(); 	int k = 3; 	while (--k) 	{ 		++it; 	} 	l1.insert(it, 6); 	for (auto e : l1) 	{ 		cout << e << " "; 	} 	cout << endl; 	l1.erase(it); 	for (auto e : l1) 	{ 		cout << e << " "; 	} 	cout << endl; }

二、模拟实现

2.1 迭代器失效

迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。与vector类的失效不同。

2.2 迭代器实现

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; 	}  	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; 	}  	Ptr operator->() 	{ 		return &_node->_data;  	}  	bool operator!=(const Self& s) const 	{ 		return _node != s._node; 	}  	bool operator==(const Self& s) const 	{ 		return _node == s._node; 	} };

2.3 源代码

#pragma once #include #include  using namespace std;  namespace paradiso { 	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; 		}  		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; 		}  		Ptr operator->() 		{ 			return &_node->_data;  		}  		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_iterator const_iterator;  		iterator begin() 		{ 			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; 		} 		void swap(list& lt) 		{ 			std::swap(_head, lt._head); 			std::swap(_size, lt._size); 		} 		list() 		{ 			empty_init(); 		} 		list(list& lt) 		{ 			empty_init(); 			for (auto& e : lt) 			{ 				push_back(e); 			} 		} 		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); 				++it; 			} 		} 		void push_back(const T& x) 		{ 			Node* newnode = new Node(x); 			Node* tail = _head->_prev;  			tail->_next = newnode; 			newnode->_prev = tail; 			newnode->_next = _head; 			_head->_prev = newnode;  			++_size;  			//insert(end(), x); 		}  		void push_front(const T& x) 		{ 			insert(begin(), x); 		}  		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; 		}  		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; 	}; }