带你攻克STL —— 如何正确使用list(重难点剖析及其模拟实现)

矫情吗；* 2022-12-10 14:35 92阅读 0赞

### 文章目录 ###

*  list介绍
 *  正确使用list
 *   *  构造函数
     *  iterator
     *  list 其他常用接口
     *  迭代器失效问题
 *  list模拟实现

# list介绍 #

简单理解list，list就是一个封装了的双向链表，使得用户可以更加便捷使用。

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

读者可以结合vector进行对比：[带你攻克STL —— 如何正确使用vector (重难点剖析及其模拟实现)][STL _ _vector]

# 正确使用list #

## 构造函数 ##

list有以下五种常用的构造函数

1.  list() 声明一个空列表；
2.  list(n) 声明一个有n个元素的列表，每个元素都是由其默认构造函数T()构造出来的
3.  list(n,val) 声明一个由n个元素的列表，每个元素都是由其复制构造函数T(val)得来的
4.  list(n,val) 声明一个和上面一样的列表
5.  list(first,last) 声明一个列表，其元素的初始值来源于由区间所指定的序列中的元素

#include <iostream>
    #include <list>
    int main ()
    {
        
     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
     // 以数组为迭代器区间构造l5
     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 << " ";
     std::cout<<endl;
     
     // C++11范围for的方式遍历
     for(auto& e : l5)
     std::cout<< e << " ";
     
     std::cout<<endl;
     return 0; }

## iterator ##

list迭代器分为正向和反向迭代器(const 与 非const)  
begin + end：返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器  
rbegin + rend：返回第一个元素的reverse\_iterator,即end位置，返回最后一个元素下一个位置的

list<int>::const_iterator it = l.begin();
    list<int>::const_iterator it = l.begin();
    list<int>::reverse_iterator it = l.rbegin();

## list 其他常用接口 ##

1.  empty 检测list是否为空，是返回true，否则返回false
2.  size 返回list中有效节点的个数
3.  push\_front 在list首元素前插入值为val的元素
4.  pop\_front 删除list中第一个元素
5.  push\_back 在list尾部插入值为val的元素
6.  pop\_back 删除list中最后一个元素
7.  insert 在list position 位置中插入值为val的元素
8.  erase 删除list position位置的元素
9.  swap 交换两个list中的元素
10. clear 清空list中的有效元素

## 迭代器失效问题 ##

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

# list模拟实现 #

#include <iostream>
    namespace mylist {
        
    	//节点模板
    	template<class T> 
    	struct __list_node {
        
    		__list_node<T>* _next;
    		__list_node<T>* _prev;
    		T _data;
    		
    		__list_node(const T& x = T())
    			:_next(nullptr)
    			, _prev(nullptr)
    			, _data(x)
    		{
        }
    	};
    
    	//迭代器模板
    	template<class T,class Ref, class Ptr>
    	struct __list_iterator {
        
    		typedef __list_node<T> Node;
    		typedef __list_iterator<T,Ref,Ptr> 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++(int) {
        
    			Self tmp(*this);
    			++(*this);
    			return tmp;
    		}
    		Self& operator--() {
        
    			_node = _node->_next;
    			return *this;
    		}
    		Self operator--(int) {
        
    			Self tmp(*this);
    			--(*this);
    			return tmp;
    		}
    		bool operator!=(const Self& it) {
        
    			return _node != it._node;
    		}
    		bool operator==(const Self& it) {
        
    			return _node == it._node;
    		}
    	};
    
    	//list类模板
    	template<class T>
    	class list {
        
    		typedef __list_node<T> Node;
    	public:
    		typedef __list_iterator<T, T&, T*> iterator;//一个const一个非const
    		typedef __list_iterator<T, const T&, const T*> const_iterator;
    
    		iterator begin() {
        
    			return iterator(_head->_next);
    		}
    		iterator end() {
        
    			return iterator(_head);
    		}
    		const_iterator begin() const {
        
    			return const_iterator(_head->_next);
    		}
    		const_iterator end() const {
        
    			return const_iterator(_head);
    		}
    		list() {
        
    			_head = new Node;
    			_head->_next = _head;
    			_head->_prev = _head;
    		}
    		list(const list<T>& l1) {
        
    			_head = new Node;
    			_head->_next = _head;
    			_head->_prev = _head;
    			const_iterator it = l1.begin();
    			/*while (it != l1.end()) {
    				push_back(*it);
    				++it;
    			}*/
    			for (auto e : l1) {
        
    				push_back(e);
    			}
    		}
    		
    		//赋值运算符重载的现代写法和传统写法
    		/*list<T> operator=(const list<T> l1) {
    			if (*this != l1) {
    				clear();
    				const_iterator it = l1.begin();
    				for (auto e : v) {
    					push_back(e);
    				}
    			}
    			return *this;
    		}*/
    		list<T> operator=(const list<T> l1) {
        
    			swap(_head, l1._head);
    			return *this;
    
    		}
    		void clear() {
        
    			iterator it = begin();
    			while (it != end()) {
        
    				//it = erase(it);
    				erase(it++);
    			}
    		}
    		iterator erase(iterator pos) {
        ///到底要不要返回值
    			//assert(pos != end());
    			Node* cur = pos._node;
    			Node* prev = cur->_prev;
    			Node* next = cur->_next;
    			delete cur;
    			prev->_next = next;
    			next->_prev = prev;
    			return iterator(next);
    		}
    		void insert(iterator pos, const T& x) {
        
    			Node* cur = pos._node;
    			Node* prev = cur->_prev;
    			Node* newNode = new Node(x);
    
    			prev->_next = newNode;
    			newNode->_prev = prev;
    			newNode->_next = cur;
    			cur->_prev = newNode;
    		}
    		void push_back(const T& x) {
        
    			insert(end(), x);
    		}
    		void pop_back() {
        
    			erase(--end());
    		}
    		void push_front(const T& x) {
        
    			insert(begin(), x);
    		}
    		void pop_front() {
        
    			erase(begin());
    		}
    		~list() {
        
    			clear();
    			delete _head;
    			_head = nullptr;
    		}
    	private:
    		Node* _head;
    	};
    	void print_list(const list<int>& l1) {
        
    		list<int>::const_iterator it = l1.begin();
    		while (it != l1.end()) {
        
    			std::cout << *it << " ";
    			++it;
    		}
    		std::cout << std::endl;
    	}
    }
    int main() {
        
    	mylist::list<int> l1;
    	l1.push_back(11);
    	l1.push_back(12);
    	l1.push_back(13);
    	l1.push_back(14);
    	mylist::print_list(l1);
    	l1.clear();
    	l1.push_front(1);
    	mylist::print_list(l1);
    
    	system("pause");
    	return 0;
    }

[STL _ _vector]: https://blog.csdn.net/ifwecande/article/details/108811572