【C++】STL—容器—list介绍

素颜马尾好姑娘i 2022-12-20 05:56 192阅读 0赞

### 文章目录 ###

*  1、list的概念
 *  2、list的使用
 *   *  2.1 list的构造
     *  2.2 list迭代器的使用
     *  2.3 list节点个数
     *  2.4 list元素访问
     *  2.5 list元素修改
     *  2.6 list迭代器失效
 *  3.list的模拟实现
 *  4.list和vector的区别

# 1、list的概念 #

list是带头结点的循环双向链表，是可以在常数范围内在任意位置进行插入和删除的序列式容器。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70_pic_center]

# 2、list的使用 #

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

## 2.1 list的构造 ##

#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;
    }

## 2.2 list迭代器的使用 ##

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

#include <iostream>
    using namespace std;
    #include <list>
    
    int main()
    {
        
    	int array[]={
        1,2,3,4,5,6,7,8,9,0};
    	list<int> l(array,array + sizeof(array) / sizeof(array[0]));
    	// 使用正向迭代器正向list中的元素
    	for(list<int>::iterator it = l.begin();it != l.end();++it)
    		cout<<*it<<" ";
    	cout<<endl;
    
    	// 使用反向迭代器逆向打印list中的元素
    	for(list<int>::reverse_iterator it = l.rbegin();it !=l.rend();++it)
    		cout<<*it<<" ";
    	cout<<endl;
    	return 0;
    }

## 2.3 list节点个数 ##

l.empty()//检测list是否为空，是返回true，否则返回false
    l.size()//返回list中有效节点的个数

## 2.4 list元素访问 ##

l.front()//返回list的第一个节点中值的引用
    l.back()//返回list的最后一个节点中值的引用

## 2.5 list元素修改 ##

#include <list>
    
    void PrintList(list<int>& l)
    {
        
    	for(auto& e:l)
    		cout<<e<<" ";
    	cout<<endl;
    }
    
    void TestList1()
    {
        
    	int array[] = {
        1,2,3};
    	list<int> 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);
    }
    
    void TestList2()
    {
        
    	int array1[] = {
        1,2,3};
    	list<int> L(array1,array1+sizeof(array1)/sizeof(array1[0]));
    
    	// 获取链表中第二个节点
    	auto pos = ++L.begin();
    	cout<<*pos<<endl;
    
    	// 在pos前插入值为4的元素
    	L.insert(pos,4);
    	PrintList(L);
    
    	// 在pos前插入5个值为5的元素
    	L.insert(pos,5,5);
    	PrintList(L);
    
    	// 在pos前插入[v.begin(), v.end)区间中的元素
    	vector<int> v{
        7,8,9};
    	L.insert(pos,v.begin(),v.end());
    	PrintList(L);
    
    	// 删除pos位置上的元素
    	L.erase(pos);
    	PrintList(L);
    
    	// 删除list中[begin, end)区间中的元素，即删除list中的所有元素
    	L.erase(L.begion(),L.end());
    	PrintList(L);
    }
    
    void TestList3()
    {
        
    	int array1[]={
        1,2,3};
    	list<int> l1(array1,array1+sizeof(array1)/sizeof(array1[0]));
    	PrintList(l1);
    
    	// 交换l1和l2中的元素
    	l1.swap(l2);
    	PrintList(l1);
    	PrintList(l2);
    
    	// 将l2中的元素清空
    	l2.clear();
    	cout<<l2.size()<<endl;
    }

## 2.6 list迭代器失效 ##

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

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

# 3.list的模拟实现 #

#pragma once
    
    namespace bite
    {
        
    	template<class T>
    	struct ListNode
    	{
        
    		ListNode(const T& value = T())
    			: next(nullptr)
    			, prev(nullptr)
    			, data(value)
    		{
        }
    
    		ListNode<T>* next;
    		ListNode<T>* prev;
    		T data;
    	};
    
    	template<class T>
    	struct ListIterator
    	{
        
    		typedef ListNode<T> Node;
    		typedef ListIterator<T> Self;
    	public:
    		ListIterator(Node* ptr = nullptr)
    			: _ptr(ptr)
    		{
        }
    
    		// 具有指针类似的操作
    		T& operator*()
    		{
        
    			return _ptr->data;
    		}
    
    		T* operator->()
    		{
        
    			return &_ptr->data;
    		}
    
    		//
    		// 迭代器要能够移动
    		Self& operator++()
    		{
        
    			_ptr = _ptr->next;
    			return *this;
    		}
    
    		Self operator++(int)
    		{
        
    			Self temp(*this);
    			_ptr = _ptr->next;
    			return temp;
    		}
    
    		Self& operator--()
    		{
        
    			_ptr = _ptr->prev;
    			return *this;
    		}
    
    		Self operator--(int)
    		{
        
    			Self temp(*this);
    			_ptr = _ptr->prev;
    			return temp;
    		}
    
    		
    		// 迭代器要能够进行比较
    		bool operator!=(const Self& s)const
    		{
        
    			return _ptr != s._ptr;
    		}
    
    		bool operator==(const Self& s)const
    		{
        
    			return _ptr == s._ptr;
    		}
    
    		Node* _ptr;
    	};
    
    	// 反向迭代器：直接将正向迭代器进行封装
    	//        反向迭代器的++就是正向迭代器的--
    	//        反向迭代器的--就是正向迭代器的++
    	template<class T, class Iterator>
    	struct ListReverseIterator
    	{
        
    		typedef ListNode<T> Node;
    		typedef ListReverseIterator<T, Iterator> Self;
    	public:
    		ListReverseIterator(Node* pNode = nullptr)
    			: _it(pNode)
    		{
        }
    
    		ListReverseIterator(Iterator it)
    			: _it(it)
    		{
        }
    
    		T& operator*()
    		{
        
    			Iterator temp(_it);
    			--temp;
    			return *temp;
    		}
    
    		T* operator->()
    		{
        
    			return &(*_it);
    		}
    
    		Self& operator++()
    		{
        
    			--_it;
    			return *this;
    		}
    
    		Self operator++(int)
    		{
        
    			_it--;
    			return *this;
    		}
    
    		Self& operator--()
    		{
        
    			++_it;
    			return *this;
    		}
    
    		Self operator--(int)
    		{
        
    			_it++;
    			return *this;
    		}
    
    		bool operator!=(const Self& s)
    		{
        
    			return _it != s._it;
    		}
    
    		bool operator==(const Self& s)
    		{
        
    			return _it == s._it;
    		}
    	private:
    		Iterator _it;
    	};
    
    	template<class T>
    	class list
    	{
        
    		typedef ListNode<T> Node;
    	public:
    		typedef ListIterator<T> iterator;
    		typedef ListReverseIterator<T, iterator> reverse_iterator;
    	public:
    		list()
    		{
        
    			CreatHead();
    		}
    
    		list(int n, const T& data)
    		{
        
    			CreatHead();
    			for (int i = 0; i < n; ++i)
    				push_back(data);
    		}
    		
    		template<class Iterator>
    		list(Iterator first, Iterator last)
    		{
        
    			CreatHead();
    			while (first != last)
    			{
        
    				push_back(*first);
    				++first;
    			}
    		}
    
    		list(list<T>& L)
    		{
        
    			CreatHead();
    			auto it = L.begin();
    			while (it != L.end())
    			{
        
    				push_back(*it);
    				++it;
    			}
    		}
    
    		~list()
    		{
        
    			clear();
    			delete head;
    			head = nullptr;
    		}
    
    		///
    		// iterator
    		iterator begin()
    		{
        
    			// 构造一个匿名对象返回了
    			return iterator(head->next);
    		}
    
    		iterator end()
    		{
        
    			return iterator(head);
    		}
    
    		reverse_iterator rbegin()
    		{
        
    			return reverse_iterator(end());
    		}
    
    		reverse_iterator rend()
    		{
        
    			return reverse_iterator(begin());
    		}
    
    		
    		// capacity
    		size_t size()const
    		{
        
    			size_t count = 0;
    			Node* pCur = head->next;
    			while (pCur != head)
    			{
        
    				++count;
    				pCur = pCur->next;
    			}
    
    			return count;
    		}
    
    		bool empty()const
    		{
        
    			return head->next == head;
    		}
    
    		// T()
    		// 如果T是内置类型，比如int，int()--->0 该默认值都是0
    		// 如果T是自定义类型，比如Date，Date()调用无参构造函数或者全缺省的构造函数
    		void resize(size_t newsize, const T& data = T())
    		{
        
    			size_t oldsize = size();
    			if (newsize <= oldsize)
    			{
        
    				for (size_t i = newsize; i < oldsize; ++i)
    					pop_back();
    			}
    			else
    			{
        
    				for (size_t i = oldsize; i < newsize; ++i)
    					push_back(data);
    			}
    		}
    
    		/
    		// acess
    		T& front()
    		{
        
    			return *begin();
    		}
    
    		const T& front()const
    		{
        
    			return *begin();
    		}
    
    		T& back()
    		{
        
    			return head->prev->data;
    		}
    
    		const T& back()const
    		{
        
    			return head->prev->data;
    		}
    
    		//
    		void push_front(const T& data)
    		{
        
    			insert(begin(), data);
    		}
    
    		void pop_front()
    		{
        
    			erase(begin());
    		}
    
    		void push_back(const T& data)
    		{
        
    			insert(end(), data);
    		}
    
    		void pop_back()
    		{
        
    			erase(--end());
    		}
    
    		iterator insert(iterator pos, const T& data)
    		{
        
    			Node* newNode = new Node(data);
    			newNode->next = pos._ptr;
    			newNode->prev = pos._ptr->prev;
    			pos._ptr->prev = newNode;
    			newNode->prev->next = newNode;
    
    			return iterator(newNode);
    		}
    
    		iterator erase(iterator pos)
    		{
        
    			Node* posNode = pos._ptr;
    			Node* pRet = posNode->next;
    			if (posNode != head)
    			{
        
    				posNode->prev->next = posNode->next;
    				posNode->next->prev = posNode->prev;
    				delete posNode;
    			}
    
    			return iterator(pRet);
    		}
    
    		iterator erase(iterator first, iterator last)
    		{
        
    			while (first != last)
    			{
        
    				first = erase(first);
    			}
    
    			return end();
    		}
    
    		void clear()
    		{
        
    			erase(begin(), end());
    		}
    
    		void swap(const list<T>& L)
    		{
        
    			std::swap(head, L.head);
    		}
    
    	private:
    		void CreatHead()
    		{
        
    			head = new Node;
    			head->next = head;
    			head->prev = head;
    		}
    	private:
    		ListNode<T>* head;
    	};
    }
    
    
    #include <iostream>
    using namespace std;
    
    void TestMyList1()
    {
        
    	bite::list<int> L1;
    	bite::list<int> L2(10, 5);
    	cout << L2.size() << endl;
    	auto it = L2.begin();
    	while (it != L2.end())
    	{
        
    		cout << *it << " ";
    		++it;
    	}
    	cout << endl;
    
    	int array[] = {
         1, 2, 3, 4, 5 };
    	bite::list<int> L3(array, array+5);
    	for (auto e : L3)
    	{
        
    		cout << e << " ";
    	}
    	cout << endl;
    
    	bite::list<int> L4(L3);
    }
    
    // size()
    // resize()
    void TestMyList2()
    {
        
    	int array[] = {
         1, 2, 3, 4, 5 };
    	bite::list<int> L{
        array, array+5};
    
    	cout << L.size() << endl;
    
    	L.resize(10, 6);
    	cout << L.size() << endl;
    	for (auto e : L)
    	{
        
    		cout << e << " ";
    	}
    	cout << endl;
    
    	L.resize(3);
    	cout << L.size() << endl;
    	for (auto e : L)
    	{
        
    		cout << e << " ";
    	}
    	cout << endl;
    }
    
    void TestMyList()
    {
        
    	int array[] = {
         1, 2, 3, 4, 5 };
    	bite::list<int> L{
         array, array + 5 };
    
    	auto it = L.rbegin();
    	while (it != L.rend())
    	{
        
    		cout << *it << " ";
    		++it;
    	}
    	cout << endl;
    
    	cout << L.front() << endl;
    	cout << L.back() << endl;
    
    	L.clear();
    	if (L.empty())
    		cout << L.size() << endl;
    }
    
    
    struct A
    {
        
    	int a;
    	int b;
    	int c;
    };
    
    void TestMyList3()
    {
        
    	bite::list<A> L;
    	A a{
         1, 2, 3 };
    	L.push_back(a);
    
    	A* pa = &a;
    	pa->a = 10;
    
    	auto it = L.begin();
    	it->a = 100;
    	it.operator->()->a = 200;  // it->->a;错误
    	it.operator++();  // ++it;
    }

# 4.list和vector的区别 #

相同点：都是STL提供的容器  
不同点：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70_pic_center 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/05fbef53efa848ae95373fde6f03234f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/b3c1a1aad3a945d0bc72161847b39666.png