【C++學(xué)習(xí)】STL容器——list

這篇具有很好參考價值的文章主要介紹了【C++學(xué)習(xí)】STL容器——list。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

一、list的介紹及使用

1.1 list的介紹

?1.2 list的使用

1.2.1 list的構(gòu)造

?1.2.2??list iterator的使用

1.2.3 list capacity

1.2.4 list element access

1.2.5 list modifiers

1.2.6 list 迭代器失效

二、list的模擬實現(xiàn)

2.1 模擬實現(xiàn)list

三、list和vector的對比

一、list的介紹及使用

1.1 list的介紹

list的文檔介紹

list是可以在常數(shù)范圍內(nèi)在任意位置進行插入和刪除的序列式容器，并且該容器可以前后雙向迭代。
list的底層是雙向鏈表結(jié)構(gòu)，雙向鏈表中每個元素存儲在互不相關(guān)的獨立節(jié)點中，在節(jié)點中通過指針指向其前一個元素和后一個元素。
list與forward_list非常相似：最主要的不同在于forward_list是單鏈表，只能朝前迭代，已讓其更簡單高效。
與其他的序列式容器相比(array，vector，deque)，list通常在任意位置進行插入、移除元素的執(zhí)行效率更好。
與其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的隨機訪問，比如：要訪問list的第6個元素，必須從已知的位置(比如頭部或者尾部)迭代到該位置，在這段位置上迭代需要線性的時間開銷；list還需要一些額外的空間，以保存每個節(jié)點的相關(guān)聯(lián)信息(對于存儲類型較小元素的大list來說這可能是一個重要的因素)

?1.2 list的使用

????????list中的接口比較多，此處類似，只需要掌握如何正確的使用，然后再去深入研究背后的原理，已達到可擴展的能力。以下為list 中一些 常見的重要接口 。

1.2.1 list的構(gòu)造

構(gòu)造函數(shù)（ (constructor) ）	接口說明
list (size_type n, const value_type& val = value_type())	構(gòu)造的 list 中包含 n 個值為 val 的元素
list()	構(gòu)造空的list
list (const list& x)	拷貝構(gòu)造函數(shù)
list (InputIterator ?rst, InputIterator last)	用[?rst, last)區(qū)間中的元素構(gòu)造list

?1.2.2??list iterator的使用

此處，大家可暫時將迭代器理解成一個指針，該指針指向list中的某個節(jié)點。

函數(shù)聲明	接口說明
begin + ?end	返回第一個元素的迭代器+返回最后一個元素下一個位置的迭代器
rbegin + ?rend	返回第一個元素的reverse_iterator,即end位置，返回最后一個元素下一個位置的 reverse_iterator,即begin位置

【C++學(xué)習(xí)】STL容器——list,C++,c++,stl,list

【注意】
1. begin與end為正向迭代器，對迭代器執(zhí)行++操作，迭代器向后移動

2. rbegin(end)與rend(begin)為反向迭代器，對迭代器執(zhí)行++操作，迭代器向前移動??

1.2.3 list capacity

函數(shù)聲明	接口說明
empty	檢測list是否為空，是返回true，否則返回false
size	返回list中有效節(jié)點的個數(shù)

1.2.4 list element access

函數(shù)聲明	接口說明
front	返回list的第一個節(jié)點中值的引用
back	返回list的最后一個節(jié)點中值的引用

1.2.5 list modifiers

函數(shù)聲明	接口說明
push_front	在list首元素前插入值為val的元素
pop_front	刪除list中第一個元素
push_back	在list尾部插入值為val的元素
pop_back	刪除list中最后一個元素
insert	在list position 位置中插入值為val的元素
erase	刪除list position位置的元素
swap	交換兩個list中的元素
clear	清空list中的有效元

1.2.6 list 迭代器失效

????????前面說過，此處大家可將迭代器暫時理解成類似于指針，迭代器失效即迭代器所指向的節(jié)點的無效，即該節(jié)點被刪除了。因為list的底層結(jié)構(gòu)為帶頭結(jié)點的雙向循環(huán)鏈表，因此在list中進行插入時是不會導(dǎo)致list的迭代器失效的，只有在刪除時才會失效，并且失效的只是指向被刪除節(jié)點的迭代器，其他迭代器不會受到影響。

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()函數(shù)執(zhí)行后，it所指向的節(jié)點已被刪除，因此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);
    } 
}

二、list的模擬實現(xiàn)

2.1 模擬實現(xiàn)list

????????要模擬實現(xiàn)list，必須要熟悉list的底層結(jié)構(gòu)以及其接口的含義，通過上面的學(xué)習(xí)，這些內(nèi)容已基本掌握，現(xiàn)在我們來模擬實現(xiàn)list，代碼如下：

#pragma once
#include <iostream>
using namespace std;
#include <assert.h>

namespace casso
{
	// List的節(jié)點類
	template<class T>
	struct ListNode
	{
		ListNode(const T& val = T())
			: _prev(nullptr)
			, _next(nullptr)
			, _val(val)
		{}

		ListNode<T>* _prev;
		ListNode<T>* _next;
		T _val;
	};

	/*
	List 的迭代器
	迭代器有兩種實現(xiàn)方式，具體應(yīng)根據(jù)容器底層數(shù)據(jù)結(jié)構(gòu)實現(xiàn)：
	  1. 原生態(tài)指針，比如：vector
	  2. 將原生態(tài)指針進行封裝，因迭代器使用形式與指針完全相同，因此在自定義的類中必須實現(xiàn)以下方法：
		 1. 指針可以解引用，迭代器的類中必須重載operator*()
		 2. 指針可以通過->訪問其所指空間成員，迭代器類中必須重載oprator->()
		 3. 指針可以++向后移動，迭代器類中必須重載operator++()與operator++(int)
			至于operator--()/operator--(int)釋放需要重載，根據(jù)具體的結(jié)構(gòu)來抉擇，雙向鏈表可以向前             移動，所以需要重載，如果是forward_list就不需要重載--
		 4. 迭代器需要進行是否相等的比較，因此還需要重載operator==()與operator!=()
	*/
	template<class T, class Ref, class Ptr>
	class ListIterator
	{
		typedef ListNode<T> Node;
		typedef ListIterator<T, Ref, Ptr> Self;

		// Ref 和 Ptr 類型需要重定義下，實現(xiàn)反向迭代器時需要用到
	public:
		typedef Ref Ref;
		typedef Ptr Ptr;
	public:
		//
		// 構(gòu)造
		ListIterator(Node* node = nullptr)
			: _node(node)
		{}

		//
		// 具有指針類似行為
		Ref operator*() 
		{ 
			return _node->_val;
		}

		Ptr operator->() 
		{ 
			return &(operator*()); 
		}

		//
		// 迭代器支持移動
		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		Self operator++(int)
		{
			Self temp(*this);
			_node = _node->_next;
			return temp;
		}

		Self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

		Self operator--(int)
		{
			Self temp(*this);
			_node = _node->_prev;
			return temp;
		}

		//
		// 迭代器支持比較
		bool operator!=(const Self& l)const
		{ 
			return _node != l._node;
		}

		bool operator==(const Self& l)const
		{ 
			return _node != l._node;
		}

		Node* _node;
	};

	template<class Iterator>
	class ReverseListIterator
	{
		// 注意：此處typename的作用是明確告訴編譯器，Ref是Iterator類中的一個類型，而不是靜態(tài)成員變量
		// 否則編譯器編譯時就不知道Ref是Iterator中的類型還是靜態(tài)成員變量
		// 因為靜態(tài)成員變量也是按照 類名::靜態(tài)成員變量名 的方式訪問的
	public:
		typedef typename Iterator::Ref Ref;
		typedef typename Iterator::Ptr Ptr;
		typedef ReverseListIterator<Iterator> Self;
	public:
		//
		// 構(gòu)造
		ReverseListIterator(Iterator it)
			: _it(it)
		{}

		//
		// 具有指針類似行為
		Ref operator*()
		{
			Iterator temp(_it);
			--temp;
			return *temp;
		}

		Ptr operator->()
		{
			return &(operator*());
		}

		//
		// 迭代器支持移動
		Self& operator++()
		{
			--_it;
			return *this;
		}

		Self operator++(int)
		{
			Self temp(*this);
			--_it;
			return temp;
		}

		Self& operator--()
		{
			++_it;
			return *this;
		}

		Self operator--(int)
		{
			Self temp(*this);
			++_it;
			return temp;
		}

		//
		// 迭代器支持比較
		bool operator!=(const Self& l)const
		{
			return _it != l._it;
		}

		bool operator==(const Self& l)const
		{
			return _it != l._it;
		}

		Iterator _it;
	};

	template<class T>
	class list
	{
		typedef ListNode<T> Node;

	public:
		// 正向迭代器
		typedef ListIterator<T, T&, T*> iterator;
		typedef ListIterator<T, const T&, const T&> const_iterator;

		// 反向迭代器
		typedef ReverseListIterator<iterator> reverse_iterator;
		typedef ReverseListIterator<const_iterator> const_reverse_iterator;
	public:
		///
		// List的構(gòu)造
		list()
		{
			CreateHead();
		}

		list(int n, const T& value = T())
		{
			CreateHead();
			for (int i = 0; i < n; ++i)
				push_back(value);
		}

		template <class Iterator>
		list(Iterator first, Iterator last)
		{
			CreateHead();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		list(const list<T>& l)
		{
			CreateHead();

			// 用l中的元素構(gòu)造臨時的temp,然后與當(dāng)前對象交換
			list<T> temp(l.begin(), l.end());
			this->swap(temp);
		}

		list<T>& operator=(list<T> l)
		{
			this->swap(l);
			return *this;
		}

		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}

		///
		// List的迭代器
		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); 
		}

		reverse_iterator rbegin()
		{
			return reverse_iterator(end());
		}

		reverse_iterator rend()
		{
			return reverse_iterator(begin());
		}

		const_reverse_iterator rbegin()const
		{
			return const_reverse_iterator(end());
		}

		const_reverse_iterator rend()const
		{
			return const_reverse_iterator(begin());
		}

		///
		// List的容量相關(guān)
		size_t size() const
		{
			Node* cur = _head->_next;
			size_t count = 0;
			while (cur != _head)
			{
				count++;
				cur = cur->_next;
			}

			return count;
		}

		bool empty() const
		{
			return _head->_next == _head;
		}

		void resize(size_t newsize, const T& data = T())
		{
			size_t oldsize = size();
			if (newsize <= oldsize)
			{
				// 有效元素個數(shù)減少到newsize
				while (newsize < oldsize)
				{
					pop_back();
					oldsize--;
				}
			}
			else
			{
				while (oldsize < newsize)
				{
					push_back(data);
					oldsize++;
				}
			}
		}
		
		// List的元素訪問操作
		// 注意：List不支持operator[]
		T& front()
		{
			return _head->_next->_val;
		}

		const T& front() const
		{
			return _head->_next->_val;
		}

		T& back()
		{
			return _head->_prev->_val;
		}

		const T& back() const
		{
			return _head->_prev->_val;
		}

		
		// List的插入和刪除
		void push_back(const T& val) 
		{ 
			insert(end(), val); 
		}

		void pop_back() 
		{ 
			erase(--end()); 
		}

		void push_front(const T& val) 
		{ 
			insert(begin(), val); 
		}

		void pop_front() 
		{ 
			erase(begin()); 
		}

		// 在pos位置前插入值為val的節(jié)點
		iterator insert(iterator pos, const T& val)
		{
			Node* pNewNode = new Node(val);
			Node* pCur = pos._node;
			// 先將新節(jié)點插入
			pNewNode->_prev = pCur->_prev;
			pNewNode->_next = pCur;
			pNewNode->_prev->_next = pNewNode;
			pCur->_prev = pNewNode;
			return iterator(pNewNode);
		}

		// 刪除pos位置的節(jié)點，返回該節(jié)點的下一個位置
		iterator erase(iterator pos)
		{
			// 找到待刪除的節(jié)點
			Node* pDel = pos._node;
			Node* pRet = pDel->_next;

			// 將該節(jié)點從鏈表中拆下來并刪除
			pDel->_prev->_next = pDel->_next;
			pDel->_next->_prev = pDel->_prev;
			delete pDel;

			return iterator(pRet);
		}

		void clear()
		{
			Node* cur = _head->_next;
			
			// 采用頭刪除刪除
			while (cur != _head)
			{
				_head->_next = cur->_next;
				delete cur;
				cur = _head->_next;
			}

			_head->_next = _head->_prev = _head;
		}

		void swap(casso::list<T>& l)
		{
			std::swap(_head, l._head);
		}

	private:
		void CreateHead()
		{
			_head = new Node;
			_head->_prev = _head;
			_head->_next = _head;
		}
	private:
		Node* _head;
	};
}


///
// 對模擬實現(xiàn)的list進行測試
// 正向打印鏈表
template<class T>
void PrintList(const casso::list<T>& l)
{
	auto it = l.begin();
	while (it != l.end())
	{
		cout << *it << " ";
		++it;
	}

	cout << endl;
}

// 測試List的構(gòu)造
void TestCassoList1()
{
	casso::list<int> l1;
	casso::list<int> l2(10, 5);
	PrintList(l2);

	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	casso::list<int> l3(array, array + sizeof(array) / sizeof(array[0]));
	PrintList(l3);

	casso::list<int> l4(l3);
	PrintList(l4);

	l1 = l4;
	PrintList(l1);
}

// PushBack()/PopBack()/PushFront()/PopFront()
void TestCassoList2()
{
	// 測試PushBack與PopBack
	casso::list<int> l;
	l.push_back(1);
	l.push_back(2);
	l.push_back(3);
	PrintList(l);

	l.pop_back();
	l.pop_back();
	PrintList(l);

	l.pop_back();
	cout << l.size() << endl;

	// 測試PushFront與PopFront
	l.push_front(1);
	l.push_front(2);
	l.push_front(3);
	PrintList(l);

	l.pop_front();
	l.pop_front();
	PrintList(l);

	l.pop_front();
	cout << l.size() << endl;
}

// 測試insert和erase
void TestCassoList3()
{
	int array[] = { 1, 2, 3, 4, 5 };
	casso::list<int> l(array, array + sizeof(array) / sizeof(array[0]));

	auto pos = l.begin();
	l.insert(l.begin(), 0);
	PrintList(l);

	++pos;
	l.insert(pos, 2);
	PrintList(l);

	l.erase(l.begin());
	l.erase(pos);
	PrintList(l);

	// pos指向的節(jié)點已經(jīng)被刪除，pos迭代器失效
	cout << *pos << endl;

	auto it = l.begin();
	while (it != l.end())
	{
		it = l.erase(it);
	}
	cout << l.size() << endl;
}

// 測試反向迭代器
void TestCassoList4()
{
	int array[] = { 1, 2, 3, 4, 5 };
	casso::list<int> l(array, array + sizeof(array) / sizeof(array[0]));

	auto rit = l.rbegin();
	while (rit != l.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;

	const casso::list<int> cl(l);
	auto crit = l.rbegin();
	while (crit != l.rend())
	{
		cout << *crit << " ";
		++crit;
	}
	cout << endl;
}

2.2 list的反向迭代器
????????通過前面例子知道，反向迭代器的++就是正向迭代器的--，反向迭代器的--就是正向迭代器的++，因此反向迭代器的實現(xiàn)可以借助正向迭代器，即：反向迭代器內(nèi)部可以包含一個正向迭代器，對正向迭代器的接口進行包裝即可。

template<class Iterator> 
class ReverseListIterator 
{
    // 注意：此處typename的作用是明確告訴編譯器，Ref是Iterator類中的類型，而不是靜態(tài)成員變量   
    // 否則編譯器編譯時就不知道Ref是Iterator中的類型還是靜態(tài)成員變量
    // 因為靜態(tài)成員變量也是按照 類名::靜態(tài)成員變量名 的方式訪問的 
public:
    typedef typename Iterator::Ref Ref;
    typedef typename Iterator::Ptr Ptr;
    typedef ReverseListIterator<Iterator> Self; 
public:
    //
    // 構(gòu)造
    ReverseListIterator(Iterator it) : _it(it){}          
    //
    // 具有指針類似行為
    Ref operator*()
    {
        Iterator temp(_it);
        --temp;
        return *temp;
    }    
    Ptr operator->()
    {
        return &(operator*());
    }
    //
    // 迭代器支持移動
    Self& operator++()
    {
        --_it;
        return *this;
    }
    Self operator++(int)
    {
        Self temp(*this);
        --_it;
        return temp;
    }
    Self& operator--()
    {
        ++_it;
        return *this;
    }
    Self operator--(int)
    {
        Self temp(*this);
        ++_it;
        return temp;
    }
    //
    // 迭代器支持比較
    bool operator!=(const Self& l) const
    {
        return _it != l._it;
    }
    bool operator==(const Self& l) const
    {
        return _it != l._it;
    }
    Iterator _it;
};

三、list和vector的對比

????????vector與list都是STL中非常重要的序列式容器，由于兩個容器的底層結(jié)構(gòu)不同，導(dǎo)致其特性以及應(yīng)用場景不同，其主要不同如下：

	vector	list
底層結(jié)構(gòu)	動態(tài)順序表，一段連續(xù)空間	帶頭結(jié)點的雙向循環(huán)鏈表
隨機訪問	支持隨機訪問，訪問某個元素效率O(1)	不支持隨機訪問，訪問某個元素效率O(N)
插入和刪除	任意位置插入和刪除效率低，需要搬移元素，時間復(fù)雜度為O(N)，插入時有可能需要增容，增容：開辟新空間，拷貝元素，釋放舊空間，導(dǎo)致效率更低	任意位置插入和刪除效率高，不需要搬移元素，時間復(fù)雜度為 O(1)
空間利用率	底層為連續(xù)空間，不容易造成內(nèi)存碎片，空間利用率高，緩存利用率高	底層節(jié)點動態(tài)開辟，小節(jié)點容易造成內(nèi)存碎片，空間利用率低，緩存利用率低
迭代器	原生態(tài)指針	對原生態(tài)指針(節(jié)點指針)進行封裝
迭代器失效	在插入元素時，要給所有的迭代器重新賦值，因為插入元素有可能會導(dǎo)致重新擴容，致使原來迭代器失效，刪除時，當(dāng)前迭代器需要重新賦值否則會失效	插入元素不會導(dǎo)致迭代器失效，刪除元素時，只會導(dǎo)致當(dāng)前迭代器失效，其他迭代器不受影響
使用場景	需要高效存儲，支持隨機訪問，不關(guān)心插入刪除效率	大量插入和刪除操作，不關(guān)心隨機訪問

最后：

list的構(gòu)造使用、迭代器的使用、插入和刪除代碼演示：文章來源地址http://www.zghlxwxcb.cn/news/detail-631118.html

#include <iostream>
using namespace std;
#include <list>
#include <vector>



// list的構(gòu)造
void TestList1()
{
    list<int> l1;                         // 構(gòu)造空的l1
    list<int> l2(4, 100);                 // l2中放4個值為100的元素
    list<int> l3(l2.begin(), l2.end());  // 用l2的[begin(), end()）左閉右開的區(qū)間構(gòu)造l3
    list<int> l4(l3);                    // 用l3拷貝構(gòu)造l4

    // 以數(shù)組為迭代器區(qū)間構(gòu)造l5
    int array[] = { 16,2,77,29 };
    list<int> l5(array, array + sizeof(array) / sizeof(int));

    // 列表格式初始化C++11
    list<int> l6{ 1,2,3,4,5 };

    // 用迭代器方式打印l5中的元素
    list<int>::iterator it = l5.begin();
    while (it != l5.end())
    {
        cout << *it << " ";
        ++it;
    }       
    cout << endl;

    // C++11范圍for的方式遍歷
    for (auto& e : l5)
        cout << e << " ";

    cout << endl;
}


// list迭代器的使用
// 注意：遍歷鏈表只能用迭代器和范圍for
void PrintList(const list<int>& l)
{
    // 注意這里調(diào)用的是list的 begin() const，返回list的const_iterator對象
    for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it)
    {
        cout << *it << " ";
        // *it = 10; 編譯不通過
    }

    cout << endl;
}

void TestList2()
{
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    list<int> l(array, array + sizeof(array) / sizeof(array[0]));
    // 使用正向迭代器正向list中的元素
    // list<int>::iterator it = l.begin();   // C++98中語法
    auto it = l.begin();                     // C++11之后推薦寫法
    while (it != l.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    // 使用反向迭代器逆向打印list中的元素
    // list<int>::reverse_iterator rit = l.rbegin();
    auto rit = l.rbegin();
    while (rit != l.rend())
    {
        cout << *rit << " ";
        ++rit;
    }
    cout << endl;
}


// list插入和刪除
// push_back/pop_back/push_front/pop_front
void TestList3()
{
    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尾部節(jié)點和頭部節(jié)點
    L.pop_back();
    L.pop_front();
    PrintList(L);
}

// insert /erase 
void TestList4()
{
    int array1[] = { 1, 2, 3 };
    list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));

    // 獲取鏈表中第二個節(jié)點
    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)區(qū)間中的元素
    vector<int> v{ 7, 8, 9 };
    L.insert(pos, v.begin(), v.end());
    PrintList(L);

    // 刪除pos位置上的元素
    L.erase(pos);
    PrintList(L);

    // 刪除list中[begin, end)區(qū)間中的元素，即刪除list中的所有元素
    L.erase(L.begin(), L.end());
    PrintList(L);
}

// resize/swap/clear
void TestList5()
{
    // 用數(shù)組來構(gòu)造list
    int array1[] = { 1, 2, 3 };
    list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));
    PrintList(l1);

    // 交換l1和l2中的元素
    list<int> l2;
    l1.swap(l2);
    PrintList(l1);
    PrintList(l2);

    // 將l2中的元素清空
    l2.clear();
    cout << l2.size() << endl;
}

到了這里，關(guān)于【C++學(xué)習(xí)】STL容器——list的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！