C++ list深度刨析及模拟实现

以你之姓@ 2022-11-25 04:16 149阅读 0赞

## 1.list的介绍及使用 ##

### 1：list的介绍 ###

[官方文档][Link 1]

> 1：list是可以在常数范围内任意位置插入和删除的序列式容器，并且该容器可以前后双向迭代；  
> 2：list的底层是双向链表结构，双向链表的每个节点存储在互不相关的独立节点中，在节点中通过指针指向其前一个和后一个元素；  
> 3：list与forward\_list非常相似：最主要的是forward\_list是单链表，只能朝前迭代，以让其更简单高效；  
> 4：与其他序列式容器相比（array,vector,deque）,list通常在任意位置进行插入，移除圆度的执行效率更好；  
> 5：与其他序列式容器相比，list和forward\_list的最大缺陷是不支持任意位置的随机访问，需要从头遍历；list还需要一些额外的空间，以保存每个节点的相关联信息（对于存储元素较小的大list来说这可能是个重要的因素）；

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTEzMDc3_size_16_color_FFFFFF_t_70]

### 2：list的使用 ###

#### 2.1：list的构造 ####

<table> 
 <thead> 
  <tr> 
   <th>构造函数（ (constructor)）</th> 
   <th>接口说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>list()</td> 
   <td>构造空的list</td> 
  </tr> 
  <tr> 
   <td>list (size_type n, const value_type&amp; val = value_type())</td> 
   <td>构造的list中包含n个值为val的元素</td> 
  </tr> 
  <tr> 
   <td>list (const list&amp; x)</td> 
   <td>拷贝构造函数</td> 
  </tr> 
  <tr> 
   <td>list (InputIterator ﬁrst, InputIterator last)</td> 
   <td>用[ﬁrst, last)区间中的元素构造list</td> 
  </tr> 
 </tbody> 
</table>

#### 2.2：list iterator 的使用 ####

<table> 
 <thead> 
  <tr> 
   <th>函数声明</th> 
   <th>接口说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>begin + end</td> 
   <td>返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器</td> 
  </tr> 
  <tr> 
   <td>rbegin + rend</td> 
   <td>返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的 reverse_iterator,即begin位置</td> 
  </tr> 
 </tbody> 
</table>

**注意**

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

#### 2.3：list capacity ####

<table> 
 <thead> 
  <tr> 
   <th>函数声明</th> 
   <th>接口说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>empty</td> 
   <td>检测list是否为空，是返回true，否则返回false</td> 
  </tr> 
  <tr> 
   <td>size</td> 
   <td>返回list中有效节点的个数</td> 
  </tr> 
 </tbody> 
</table>

#### 2.4：list element access （元素访问） ####

<table> 
 <thead> 
  <tr> 
   <th>函数声明</th> 
   <th>接口说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>front</td> 
   <td>返回list的第一个节点中值的引用</td> 
  </tr> 
  <tr> 
   <td>back</td> 
   <td>返回list的最后一个节点中值的引用</td> 
  </tr> 
 </tbody> 
</table>

#### 2.5：list modifiers ####

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

## 2：list的模拟实现 ##

#include<iostream>
    
    using namespace std;
    
    template <class T>
    struct ListNode
    { 
    	T _value;
    	ListNode<T>* _next;
    	ListNode<T>* _prev;
    
    	ListNode(const T& val = T())
    		:_value(val)
    		, _next(nullptr)
    		, _prev(nullptr)
    	{ }
    };
    
    template <class T,class Ref,class Ptr >
    struct Listiterator
    { 
    	typedef ListNode<T> node;
    	
    	Listiterator()
    		:_node(node)
    	{ }
    
    	//解引用
    	Ref operator*(){ 
    		return _node->_value;	
    	}
    
    	//++
    	Listiterator<T>& operator++(){ 
    		_node = _node->_next;
    		return *this;
    	}
    
    	//--
    	Listiterator<T>& operator--(){ 
    		_node = _node->_prev;
    		return *this;
    	}
    
    	//判断
    	bool operator!=(const Listiterator<T>& it){ 
    		return _node != it._node;
    	}
    
    	//-> //根据指针可以使用->来写
    	Ptr operator->()
    	{ 
    		return &_node->_value;
    	}
    
    
    	node* _node;
    };
    
    //const迭代器（冗余）
    /*template <class T> struct ConstListiterator { typedef ConstListNode<T> node; ConstListiterator() :_node(node) {} //解引用 const T& operator*(){ return _node->_value; } //++ Listiterator<T>& operator++(){ _node = _node->_next; return *this; } //-- Listiterator<T>& operator--(){ _node = _node->_prev; return *this; } //判断 bool operator!=(const Listiterator<T>& it){ return _node != it._node; } //-> //根据指针可以使用->来写 const T* operator->() { return &_node->_value; } node* _node; }; */
    template <class T>
    class List{ 
    public:
    	typedef ListNode<T> Node;
    
    	//根据不同的参数来区分const和非const迭代器
    	typedef Listiterator<T,T&,T*> iterator;//迭代器
    	typedef Listiterator<T,const T&,const T*> const_iterator;//const迭代器
    
    	//迭代器使用
    	//可读可写
    	iterator begin()
    	{ 
    		return iterator(_header->_next);
    	}
    
    	iterator end(){ 
    		return iterator(_header);
    	}
    	//只读
    	const_iterator begin()
    	{ 
    		return const_iterator(_header->_next);
    	}
    
    	const_iterator end(){ 
    		return const_iterator(_header);
    	}
    
    	//构造函数 
    	List()
    		:_header(new Node)
    	{ 
    		//构建循环结构
    		_header->_next = _header->_prev = _header;
    	}
    
    	//尾插
    	void push_back(const T& val){ 
    		/*Node* cur = new Node(val; Node* prev = _header->_prev; //链接 prev->_next = cur; cur->_prev = prev; _header->_prev = cur; cur->_next = _header;*/
    
    		insert(end(), val);
    	}
    
    	//头插
    	void push_front(const T& val){ 
    		/*Node* cur = new Node(val); Node* next = _header->_next; next->_prev = cur; cur->_next = next; _header->_next = cur; cur->_prev = _header;*/
    		insert(begin(), val);
    	}
    
    	//insert
    	void inert(iterator it, const T& val){ 
    		Node* cur = new Node(val);
    
    		Node* node = it._node;
    		Node* prev = node->_prev;
    
    		cur->_prev = prev;
    		prev->_next = cur;
    
    		node->_prev = cur;
    		cur->_next = node;
    	}
    
    	//erase(删除之后迭代器会失效)
    	iterator erase(iterator pos){ 
    		//不能删除头节点
    		if (pos == end())
    			return pos;
    		Node* node = pos._node;
    		Node* prev = node->_prev;
    		Node* next = node->_next;
    
    		delete node;
    
    		prev->_next = next;
    		next->_prev = prev;
    
    		return iterator(next);//需要创建迭代器对象
    	}
    
    	//尾删
    	void pop_back(){ 
    		erase(--end());
    	}
    
    	//头删
    	void pop_front(){ 
    		erase(begin());
    	}
    
    	//size
    	size_t size()
    	{ 
    		size_t coubt = 0;
    		for (const auto& e : *this){ 
    			++count;
    		}
    		return count;
    	}
    
    
    	//clear
    	void clear(){ 
    		//清空所有非头结点
    		Node* cur = _header->_next;
    		while (cur != _header){ 
    			Node* next = cur->_next;
    			delete cur;
    			cur = next;
    		}
    		//重新构建
    		_header->_next = _header->_prev = _header;
    	}
    
    	//拷贝构造
    	List(const List<T>& lis)
    		:_header(new Node)
    	{ 
    		_header->_next = _header->_prev = _header;
    
    		//深拷贝（尾插）
    		for (const auto& e : lis)
    			push_back(e);
    	}
    
    	//赋值运算符
    	List<T>& operator=(List<T> lis){ 
    		swap(_header, lis->_header);
    		return *this;
    	}
    	//析构函数
    	~List(){ 
    		clear();
    		delete _header;
    		_header = nullptr;
    	}
    private:
    	Node* _header;
    };
    
    int main()
    { 
    	return 0;
    }

### list的迭代器 ###

**迭代器又两种实现方式：**

> 1：原生态指针，如：vector；  
> 2：将原生态指针进行封装；

因为list并不支持原生态指针，所以list迭代器的实现方式为封装原生态指针：

> 1.  指针可以解引用，迭代器的类中必须重载operator\*()
> 2.  指针可以通过->访问其所指空间成员，迭代器类中必须重载oprator->()
> 3.  指针可以++向后移动，迭代器类中必须重载operator++()与operator++(int), 至于operator–()/operator–(int)释放需要重载，根据具体的结构来抉择，双向链表可以向前移动，所以需要重载，如果是forward\_list就不需要重载-
> 4.  迭代器需要进行是否相等的比较，因此还需要重载operator==()与operator!=()

## list迭代器失效 ##

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

**解决方法还是在使用之前重新获取迭代器；**

[Link 1]: http://www.cplusplus.com/reference/list/list/?kw=list
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTEzMDc3_size_16_color_FFFFFF_t_70]: /images/20221124/05022c4536b64859b890d1a26f4a10e3.png