C++STL容器之list和常用接口的实现

Love The Way You Lie 2023-06-07 10:35 60阅读 0赞

**目录**

1. list的常用接口

2. list常用接口实现

--------------------

**简介**

> 1. list这个容器的底层是双向带头循环结构实现的  
> 2. list每个不支持随机访问(所以就没有\[\]重载, 迭代器也不能进行加减运算, 只能++和--), 访问元素O(n)的时间复杂度(不如vector, vector可以随机访问, 复杂度为O(1))  
> 3. list在任何位置插入或删除都很快, 都是O(1)的复杂度(比vector优, vector为O(n) )  
> 4. list不再能够像vector那样以原生的普通指针作为迭代器, 因为其节点之间内存是不连续的, 而list的迭代器是需要指向节点, 自加(指向下一个节点), 自减(指向上一个), 取值等操作的, 所以要对原生的普通指针封装成类, 将需要的运算符进行重载  
> 5. 与vector不同的是, list中让迭代器失效的只有erase函数, 插入操作(insert)和合并操作(splice)都不会使迭代器失效  
> 6. 在使用list类模版时，也必须包含相应的头文件：\#include<list>

### 1. list的常用接口 ###

list对象的声明与使用和vector很类似, 这里仅仅介绍一下list的成员函数

**1.常见构造**

<table> 
 <thead> 
  <tr> 
   <th>函数名称</th> 
   <th>函数功能</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <th>list（）</th> 
   <td>构造空的</td> 
  </tr> 
  <tr> 
   <th>list（size_type n, const value_type&amp; val = value_type()）&nbsp;</th> 
   <td>构造并初始化n个val</td> 
  </tr> 
  <tr> 
   <th>list (const list&amp; x)</th> 
   <td>拷贝构造</td> 
  </tr> 
  <tr> 
   <th>template &lt;class InputIterator&gt; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<br> list (InputIterator first, InputIterator last)</th> 
   <td>使用迭代器进行初始化构造</td> 
  </tr> 
 </tbody> 
</table>

**2. list iterator(迭代器)的使用**

<table> 
 <thead> 
  <tr> 
   <th style="width:405px;">函数名称</th> 
   <th style="width:443px;">函数功能</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td style="width:405px;"><strong>iterator <span style="color:#3399ea;">begin</span>()&nbsp;<br> const_iterator<span style="color:#3399ea;"> begin()</span> const&nbsp;</strong></td> 
   <td style="width:443px;">返回第一个元素位置的iterator<br> 返回第一个元素位置的const_iterator</td> 
  </tr> 
  <tr> 
   <td style="width:405px;"><strong>iterator <span style="color:#e579b6;">end</span>()<br> const_iterator <span style="color:#e579b6;">end</span>() const&nbsp;</strong></td> 
   <td style="width:443px;">返回最后一个元素后一个位置的iterator<br> 返回最后一个元素后一个位置的const_iterator</td> 
  </tr> 
  <tr> 
   <td style="width:405px;"><strong>reverse_iterator <span style="color:#3399ea;">rbegin()</span><br> const reverse_iterator <span style="color:#3399ea;">rbegin() </span>const&nbsp;</strong></td> 
   <td style="width:443px;">返回最后一个元素的位置的reverse_iterator<br> 返回最后一个元素的位置的const_reverse_iterator</td> 
  </tr> 
  <tr> 
   <td style="width:405px;"><strong>reverse_iterator <span style="color:#e579b6;">rend()&nbsp;</span><br> const reverse_iterator <span style="color:#e579b6;">rend()</span> const</strong></td> 
   <td style="width:443px;">返回第一个元素前一个位置的reverse_iterator<br> 返回第一个元素前一个位置的const_reverse_iterator</td> 
  </tr> 
  <tr> 
   <td style="width:405px;"><strong>const_iterator <span style="color:#3399ea;">cbegin()</span> const (C++11)</strong></td> 
   <td style="width:443px;">返回第一个元素位置的const_iterator</td> 
  </tr> 
  <tr> 
   <td style="width:405px;"><strong>const_iterator <span style="color:#e579b6;">cend()</span> const&nbsp;(C++11)</strong></td> 
   <td style="width:443px;">返回最后一个元素下一个位置的const_iterator</td> 
  </tr> 
  <tr> 
   <td style="width:405px;"><strong>const_reverse_iterator <span style="color:#3399ea;">crbegin()&nbsp;</span>const&nbsp;&nbsp;(C++11)</strong></td> 
   <td style="width:443px;">返回最后一个元素的位置的const_reverse_iterator</td> 
  </tr> 
  <tr> 
   <td style="width:405px;"><strong>const_reverse_iterator <span style="color:#e579b6;">crend()</span>&nbsp;const&nbsp;(C++11)</strong></td> 
   <td style="width:443px;">返回第一个元素前一个位置的const_reverse_iterator</td> 
  </tr> 
 </tbody> 
</table>

**3.容量操作**

<table> 
 <tbody> 
  <tr> 
   <td>size_t size() const</td> 
   <td>返回元素个数</td> 
  </tr> 
  <tr> 
   <td>bool empty() const</td> 
   <td>判空, 为空返回true</td> 
  </tr> 
  <tr> 
   <td>void clear()</td> 
   <td>清空</td> 
  </tr> 
 </tbody> 
</table>

**4. 元素访问**

<table style="width:500px;"> 
 <thead> 
  <tr> 
   <th>函数名称</th> 
   <th style="text-align:center;">函数功能</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <th>reference front()&nbsp;</th> 
   <td>返回list的第一个节点中值的引用</td> 
  </tr> 
  <tr> 
   <th>const_reference front() const&nbsp;</th> 
   <td>返回list的第一个节点中值的const引用</td> 
  </tr> 
  <tr> 
   <th>reference back()&nbsp;</th> 
   <td>返回list的最后一个节点中值的引用</td> 
  </tr> 
  <tr> 
   <th>const_reference back() const&nbsp;</th> 
   <td>返回list的最后一个节点中值的const引用</td> 
  </tr> 
 </tbody> 
</table>

**5.list** **修改操作**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70][]

### **2. list常用接口实现**     ###

namespace myNode {
    	template<class T>
    	class ListNode {
    	public:
    		T m_data;
    		ListNode* m_prev;
    		ListNode* m_next;
    	};
    }
    
    
    template<class T>
    class ListIterator {
    	typedef myNode::ListNode<T>* PNode;
    	typedef ListIterator<T> Iterator;//类名太长,起个别名
    public:
    	//
    	PNode m_pnode;
    	//
    	ListIterator(const PNode p = nullptr) :m_pnode(p) {}
    	ListIterator(const Iterator& s) :m_pnode(s.m_pnode) {}
    	T& operator*() {
    		return m_pnode->m_data;
    	}
    	T* operator->() {
    		return &(operator*());
    	}
    	Iterator& operator++() {
    		m_pnode = m_pnode->m_next;
    		return *this;
    	}
    	Iterator operator++(int) {
    		Iterator tmp = *this;
    		m_pnode = m_pnode->m_next;
    		return tmp;
    	}
    	Iterator& operator--() {
    		m_pnode = m_pnode->m_prev;
    		return *this;
    	}
    	Iterator operator--(int) {
    		Iterator tmp = *this;
    		m_pnode = m_pnode->m_prev;
    		return tmp;
    	}
    	bool operator==(const Iterator& x)const{
    		return m_pnode == x.m_pnode;
    	}
    	bool operator!=(const Iterator& x)const{
    		return m_pnode != x.m_pnode;
    	}
    };
    
    
    template<class T, class Iterator>
    class ListReverseIterator {
    	typedef myNode::ListNode<T>* PNode;
    	typedef ListReverseIterator<T,Iterator> ReverseIterator;
    public:
    	//
    	PNode m_pnode;
    	//
    	ListReverseIterator(PNode p = nullptr) :m_pnode(p) {}
    	ListReverseIterator(const ReverseIterator& s) :m_pnode(s.m_pnode) {}
    	T& operator*() {
    		return m_pnode->m_data;
    	}
    	T* operator->() {
    		return &(operator*());
    	}
    	ReverseIterator& operator--() {
    		m_pnode = m_pnode->m_next;
    		return *this;
    	}
    	ReverseIterator operator--(int) {
    		ReverseIterator tmp = *this;
    		m_pnode = m_pnode->m_next;
    		return tmp;
    	}
    	ReverseIterator& operator++() {
    		m_pnode = m_pnode->m_prev;
    		return *this;
    	}
    	ReverseIterator operator++(int) {
    		ReverseIterator tmp = *this;
    		m_pnode = m_pnode->m_prev;
    		return tmp;
    	}
    	bool operator==(ReverseIterator& x) {
    		return m_pnode == x.m_pnod;
    	}
    	bool operator!=(ReverseIterator& x) {
    		return m_pnode != x.m_pnode;
    	}
    };
    
    
    template<class T>
    class List {
    	typedef myNode::ListNode<T> Node;
    	typedef ListIterator<T> Iterator;
    	typedef ListIterator<T> const_Iterator;
    	typedef ListReverseIterator<T, Iterator> ReverseIterator;
    	typedef ListReverseIterator<T, const_Iterator> constReverseIterator;
    	Node* m_phead;
    	inline void createhead(const T& val = T()) {
    		m_phead = new Node;
    		m_phead->m_data = val;
    		m_phead->m_prev = m_phead;
    		m_phead->m_next = m_phead;
    		m_size = 0;
    	}
    	size_t m_size;
    public:
    	List(){
    		createhead();
    	}
    	List(size_t n, const T& val = T()) {
    		createhead();
    		insert(m_phead, n, val);
    	}
    	List(List<T>& x) {
    		createhead();
    		insert(m_phead, x.begin(), x.end());
    	}
    	List(Iterator first, Iterator last) {
    		createhead();
    		insert(m_phead, first, last);
    	}
    	~List() {
    		clear();
    		if (m_phead) {
    			delete m_phead;
    		}
    		m_size = 0;
    	}
    	Iterator begin() {
    		return Iterator(m_phead->m_next);
    	}
    	Iterator end() {
    		return Iterator(m_phead);
    	}
    	ReverseIterator rbegin() {
    		return ReverseIterator(m_phead);
    	}
    	ReverseIterator rend() {
    		return ReverseIterator(m_phead);
    	}
    	bool empty() const {
    		return m_phead->m_next == m_phead;
    	}
    	size_t size() const {
    		return m_size;
    	}
    	void clear() {
    		/*Node* tmp;
    		for (Node* i = m_phead->m_next; i != m_phead; i = tmp) {
    			tmp = i->m_next;
    			tmp->m_prev = i->m_prev;
    			i->m_prev->m_next = tmp;
    			i->m_next = i->m_prev = nullptr;
    			delete i;
    		}
    		m_size = 0;*/
    		erase(begin(), end());
    	}
    	Iterator insert(Iterator pos, const T& val) {
    		Iterator Pos = pos.m_pnode->m_prev;
    		dealinsert(pos, val);
    		return Pos;
    	}
    	Iterator insert(Iterator pos, size_t n, const T& val = T()) {
    		Iterator Pos = pos.m_pnode->m_prev;
    		while (n--) {
    			insert(pos, val);
    		}
    		return Pos;
    	}
    	Iterator insert(Iterator pos, Iterator first, Iterator last) {
    		Iterator Pos = pos.m_pnode->m_prev;
    		for (Iterator val = first; val != last; ++val) {
    			insert(pos, *val);
    		}
    		return Pos;
    	}
    	T& front() {
    		return m_phead->m_next->m_data;
    	}
    	T& back() {
    		return m_phead->m_prev->m_data;
    	}
    	const T& front()const {
    		return m_phead->m_next->m_data;
    	}
    	const T& back() const{
    		return m_phead->m_prev->m_data;
    	}
    	void push_back(const T& val) {
    		/*Node* newnode = new Node;
    		newnode->m_data = val;
    		newnode->m_prev = m_phead->m_prev;
    		newnode->m_next = m_phead;
    		m_phead->m_prev->m_next = newnode;
    		m_phead->m_prev = newnode;
    		++m_size;*/
    		dealinsert(--begin(), val);
    	}
    	void pop_back() {
    		/*Node* tmp = m_phead->m_prev;
    		m_phead->m_prev->m_prev->m_next = m_phead;
    		m_phead->m_prev = m_phead->m_prev->m_prev;
    		delete tmp;
    		--m_size;*/
    		erase(--end());
    	}
    	void push_front(const T& val) {
    		/*Node* newnode = new Node;
    		newnode->m_data = val;
    		newnode->m_prev = m_phead;
    		newnode->m_next = m_phead->m_next;
    		m_phead->m_next->m_prev = newnode;
    		m_phead->m_next = newnode;
    		++m_size;*/
    		dealinsert(++end(), val);
    	}
    	void pop_front() {
    		/*Node* tmp = m_phead->m_next;
    		m_phead->m_next = tmp->m_next;
    		tmp->m_next->m_prev = m_phead;
    		delete tmp;
    		--m_size;*/
    		erase(begin());
    	}
    	Iterator erase(Iterator position) {
    		Node* tmp = position.m_pnode;
    		++position;
    		tmp->m_prev->m_next = tmp->m_next;
    		tmp->m_next->m_prev = tmp->m_prev;
    		delete tmp;
    		--m_size;
    		return position;
    	}
    	Iterator erase(Iterator first, Iterator last) {
    		/*Node* tmp;
    		for (Node* i = first.m_pnode; i != last.m_pnode; i = tmp) {
    			tmp = i->m_next;
    			tmp->m_prev = i->m_prev;
    			i->m_prev->m_next = tmp;
    			i->m_next = i->m_prev = nullptr;
    			delete i;
    			--m_size;
    		}*/
    		for (; first != last;) {
    			first = erase(first);
    		}
    		return ++last;
    	}
    	void swap(List<T>& x) {
    		Node* tmp;
    		tmp = x.m_phead;
    		x.m_phead = m_phead;
    		m_phead = tmp;
    	}
    private:
    	inline void dealinsert(Iterator& pos, const T& val) {
    		Node* tmp = pos.m_pnode->m_prev;
    		Node* newnode = nullptr;
    		newnode = new Node;
    		newnode->m_data = val;
    		newnode->m_prev = tmp;
    		newnode->m_next = pos.m_pnode;
    		pos.m_pnode->m_prev = newnode;
    		tmp->m_next = newnode;
    		tmp = newnode;
    		++m_size;
    	}
    };

测试入口:

#include<iostream>
    #include"list.h"
    using namespace std;
    class Solution {
    public:
    	void Print_vector(List<int>& v) {
    		for (auto i : v) {
    			cout << i << ' ';
    		}
    		cout << endl;
    	}
    };
    int main() {
    	List<int> mylist_1;
    	List<int> mylist_2(5, 10);
    	for (int i = 0; i < 10; i++) {
    		mylist_1.push_back(i + 1);
    	}
    	List<int> mylist_3(mylist_2);
    	List<int> mylist_4(mylist_2.begin(), --mylist_2.end());
    	List<int> mylist_5(mylist_3.begin(), --mylist_3.end());
    	List<int> mylist_6;
    	mylist_6.push_back(-1);
    	auto  j = mylist_6.begin();
    	cout << *j << endl;
    	auto i = mylist_6.insert(mylist_6.begin(), mylist_1.begin(), mylist_1.end());
    	//mylist_6.pop_back();
    	cout << *i << endl;
    	cout << *j << endl;
    	Solution p;
    	cout << "mylist_1:";
    	p.Print_vector(mylist_1);
    	cout << "mylist_2:";
    	p.Print_vector(mylist_2);
    	cout << "mylist_3:";
    	p.Print_vector(mylist_3);
    	cout << "mylist_4:";
    	p.Print_vector(mylist_4);
    	cout << "mylist_5:";
    	p.Print_vector(mylist_5);
    	cout << "mylist_6:";
    	p.Print_vector(mylist_6);
    	mylist_6.pop_back();
    	cout << "mylist_6:";
    	p.Print_vector(mylist_6);
    	mylist_6.push_front(100);
    	cout << "mylist_6:";
    	p.Print_vector(mylist_6);
    	mylist_6.erase(mylist_6.begin(), ++++mylist_6.begin());
    	cout << "mylist_6:";
    	p.Print_vector(mylist_6);
    	cout << "mylist_1的元素个数:";
    	cout << mylist_1.size() << endl;
    	cout << "清空mylist_1\n";
    	mylist_1.clear();
    	mylist_1.empty() ? cout << "mylist_1为空" << endl : cout << "mylist_1为空" << endl;
    	cout << "mylist_1的元素个数:";
    	cout << mylist_1.size() << endl;
    	cout << "交换mylist_5和mylist_6\n";
    	mylist_6.swap(mylist_5);
    	cout << "mylist_5:";
    	p.Print_vector(mylist_5);
    	cout << "mylist_6:";
    	p.Print_vector(mylist_6);
    	system("pause");
    	return 0;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70]: /images/20230601/0bc3fe390873452db3b195c4452fb3e2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 1]: /images/20230601/7d61cb91a290448a8899f5817489ea3e.png