C++數(shù)據(jù)結(jié)構(gòu)之list詳解

更新時間：2021年11月22日 10:32:22 作者：^jhao^

list是一種序列式容器。list容器完成的功能實際上和數(shù)據(jù)結(jié)構(gòu)中的雙向鏈表是極其相似的，list中的數(shù)據(jù)元素是通過鏈表指針串連成邏輯意義上的線性表，也就是list也具有鏈表的主要優(yōu)點，即：在鏈表的任一位置進行元素的插入、刪除操作都是快速的

前言

list相較于vector來說會顯得復(fù)雜，它的好處是在任意位置插入,刪除都是一個O(1)的時間復(fù)雜度。

一、list的節(jié)點

template <class T>
struct __list_node {
  typedef void* void_pointer;
  void_pointer next;
  void_pointer prev;
  T data;
};

這個是在stl3.0版本下的list的節(jié)點的定義，節(jié)點里面有一個前指針，一個后指針，有一個數(shù)據(jù)data。這里只能知道他是一個雙向鏈表，我們可以再稍微看一下list關(guān)于它的構(gòu)造函數(shù)。

class list  --> list() { empty_initialize(); 

  void empty_initialize() { 
    node = get_node();
    node->next = node;
    node->prev = node;
  }

再看一下它的list(),可以看出他調(diào)用的empty_initialize（），是創(chuàng)建了一個頭結(jié)點，并且是一個循環(huán)的結(jié)構(gòu)。

綜上：list的總體結(jié)構(gòu)是一個帶頭循環(huán)雙向鏈表

二、list的迭代器

迭代器通常是怎么使用的，看一下下面這段代碼。

int main()
{
	list<int> l;
	l.push_back(1);
	l.push_back(2);
	l.push_back(3);
	l.push_back(4);
	l.push_back(5);
	l.push_back(6);

	list<int>::iterator it = l.begin();
	while (it != l.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	return 0;
}

我們從list< int >當中定義一個iterator對象，然后讓他去訪問我們的節(jié)點
并且他所支持的操作有++，解引用，當然還有 --等等

stl3.0當中的迭代器實現(xiàn)：

template<class T, class Ref, class Ptr>
struct __list_iterator {
  typedef __list_iterator<T, T&, T*>             iterator;
  typedef __list_iterator<T, const T&, const T*> const_iterator;
  typedef __list_iterator<T, Ref, Ptr>           self;

  typedef bidirectional_iterator_tag iterator_category;
  typedef T value_type;
  typedef Ptr pointer;
  typedef Ref reference;
  typedef __list_node<T>* link_type;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;

  link_type node;

  __list_iterator(link_type x) : node(x) {}
  __list_iterator() {}
  __list_iterator(const iterator& x) : node(x.node) {}

  bool operator==(const self& x) const { return node == x.node; }
  bool operator!=(const self& x) const { return node != x.node; }
  reference operator*() const { return (*node).data; }

#ifndef __SGI_STL_NO_ARROW_OPERATOR
  pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */

  self& operator++() { 
    node = (link_type)((*node).next);
    return *this;
  }
  self operator++(int) { 
    self tmp = *this;
    ++*this;
    return tmp;
  }
  self& operator--() { 
    node = (link_type)((*node).prev);
    return *this;
  }
  self operator--(int) { 
    self tmp = *this;
    --*this;
    return tmp;
  }

大家感興趣可以先看看上面的，我們先用一個簡述版的來帶大家簡要實現(xiàn)一下

	template<class T>
	class __list_node
	{
	public:
		__list_node(const T& val = T())//用一個全缺省比較好
			:_next(nullptr)
			,_pre(nullptr)
			,node(val)
		{}
	public:
		__list_node<T>* _next;
		__list_node<T>* _pre;
		T node;
	};

	template<class T>
	class __list_itertaor//這里是迭代器
	{
	public:
		typedef __list_node<T>  Node;
		__list_itertaor(Node* node)
		{
			_node = node;
		}

		bool operator!=(const __list_itertaor<T>& it)
		{
			return _node != it._node;
		}
		__list_itertaor<T>& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		T& operator*()
		{
			return _node->node;
		}
	private:
		Node* _node;
	};

這里的實現(xiàn)是不完整的，但是很適合說明問題。通過我們?nèi)ブ剌dopertaor++，和重載opertaor*，可以讓我們像指針一樣去訪問一個節(jié)點，讓我們可以跟vector和string一樣用同樣的接口就能實現(xiàn)對數(shù)據(jù)的訪問，這是非常厲害的一個技術(shù)。

注意點：

我們通過對節(jié)點的操作，重載了operator++等接口實現(xiàn)了對一個節(jié)點的訪問，訪問的時候?qū)嶋H上也就是創(chuàng)建迭代器對象，對我們的數(shù)據(jù)進行訪問，所以我們封裝的時候是將節(jié)點的指針進行封裝。
list相比vector，正因為他們的底層結(jié)構(gòu)不相同，list的迭代器在插入操作和接合操作（splice）都不會造成迭代器失效，只有刪除的時候，只有那個被刪除元素的迭代器失效，而不影響后面的，而vector就統(tǒng)統(tǒng)失效了。

模板參數(shù)為什么是三個

2.1 const 迭代器

有這樣一種情況，我們需要const對象去遍歷，假如我們有個函數(shù)叫做print_list（const list< int >& lt）;
傳參：其中傳參中const是因為不會對對象進行修改，加引用是因為不用深拷貝，提高效率。
功能：這個函數(shù)就是去打印鏈表里面的內(nèi)容的。但是按照我們上面的實現(xiàn)，會出現(xiàn)什么問題呢。

在這里插入圖片描述

這很正常，在const迭代器就去生成const迭代器對象，在vector，string這些迭代器就是原生指針的時候我們只需要typedef const T* const_iterator,那如果我們在我們生成的list也做類似的操作，來看看結(jié)果。

在這里插入圖片描述

結(jié)果我們發(fā)現(xiàn)，好像沒多大問題，但是我們嘗試修改const迭代器里面的內(nèi)容時，卻發(fā)現(xiàn)能修改成功。const迭代器怎么能修改里面的數(shù)據(jù)呢？這就有問題了?。。≌f明我們的有一個巨大的隱患在里面。

在這里插入圖片描述

2.2 修改方法

最簡單的方法當然就是再寫多一個迭代器，把__list_iterator換成__list_const_iterator 之類的，但是我們認真觀察的話，實際上這兩個類很多東西是重復(fù)的，只有在operator*，operator->時所需要的返回值，我們需要找到一種方法去讓const對象的返回值也是const對象，答案就是添加多兩個個模板參數(shù)。
以下以添加一個模板參數(shù)為例，實現(xiàn)一個Ref operator*()；

template<class T>
	class __list_node
	{
	public:
		__list_node(const T& val = T())//用一個全缺省比較好
			:_next(nullptr)
			,_pre(nullptr)
			,node(val)
		{}
	public:
		__list_node<T>* _next;
		__list_node<T>* _pre;
		T node;
	};

	template<class T,class Ref>
	class __list_itertaor
	{
	public:
		typedef __list_node<T>  Node;
		__list_itertaor(Node* node)
		{
			_node = node;
		}

		bool operator!=(const __list_itertaor<T,Ref>& it)
		{
			return _node != it._node;
		}
		__list_itertaor<T,Ref>& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		Ref operator*()//返回Ref，返回值就有區(qū)別啦
		{
			return _node->node;
		}
	private:
		Node* _node;
	};

	template<class T>
	class list
	{
		typedef __list_node<T>  Node;
	public:
		typedef __list_itertaor<T,T&> iterator;
		typedef __list_itertaor<T, const T&> const_iterator;//修改
		iterator begin()
		{
			return iterator(_node->_next);
		}
		iterator end()
		{
			return iterator(_node);
		}
		const_iterator begin()const
		{
			return const_iterator(_node->_next);
		}
		const_iterator end()const
		{
			return const_iterator(_node);
		}
		list()
		{
			_node = new Node;
			_node->_next = _node;
			_node->_pre = _node;
		}
		void push_back(const T& val)
		{
			Node* newnode = new Node(val);
			Node* tail = _node->_pre;
			tail->_next = newnode;
			newnode->_pre = tail;
			newnode->_next = _node;
			_node->_pre = newnode;
		}
	private:
		Node* _node;
	};

一圖了解：也就是我們的測試端test函數(shù)中定義list< int >::const_iterator cit= l.begin();的時候迭代器對象就會識別到定義的const迭代器，它的第二個模板參數(shù)放的就是const T&，這樣子我們operator*（）返回的時候只需要返回第二個模板參數(shù)就可以了。

在這里插入圖片描述

同理，我們要用到的接口operator->當中也會有const對象和普通對象調(diào)用的情況。我們這里把實現(xiàn)的代碼放出來，有需要的自取。

–》碼云鏈接《–

二、美中不足

list上面說的仿佛都是優(yōu)點

任意位置的O(1)時間的插入刪除，迭代器失效的問題變少了。但他又有哪些不足呢

不支持隨機訪問
排序的效率慢，庫中的sort用的是歸并排序–>快排需要三數(shù)取中，對于鏈表來說實現(xiàn)出來效率也低，所以當鏈表的元素需要進行排序的時候，我們通常也都會拷貝到vector當中，再用vector當中的排序。
同理鏈表的逆置效率也不高！

三、迭代器的分類

迭代器從功能角度來看的話分為：const迭代器/普通迭代器 + 正反向。

從容器底層結(jié)構(gòu)角度分為：單向，雙向，隨機。

單向：單鏈表迭代器（forward_list）/哈希表迭代器；這些只支持單向++；
雙向：雙鏈表迭代器/map迭代器；這些支持的++/- -操作；
隨機迭代器： string/vector/deque；這些是支持++/- -/+/-操作的，類似原生指針一般。

我們來看一下部分函數(shù)的，比如sort當中的模板參數(shù)寫成RandomAccessIterator，就是想要明示使用者他這里需要的是一個隨機的迭代器，在它的底層會調(diào)用到迭代器的+操作，所以這個時候如果你傳的是一個雙向或者單向的迭代器就不行了??！

//sort的函數(shù)聲明
template <class RandomAccessIterator>
  void sort (RandomAccessIterator first, RandomAccessIterator last);
custom (2)	
template <class RandomAccessIterator, class Compare>
  void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

比如說reverse函數(shù)聲明，它的模板參數(shù)是BidirectionalIterator，也就是需要一個支持雙向的迭代器，這個時候其實我們就可以傳隨機迭代器和雙向迭代器，從上面的迭代器支持的操作可以看到，隨機迭代器是支持雙向迭代器的所有操作的。
同理，如果是一個需要單向迭代器的地方，我們就可以傳一個雙向，隨機，單向迭代器了！！

std::reverse
template <class BidirectionalIterator>
  void reverse (BidirectionalIterator first, BidirectionalIterator last);

從stl3.0當中的stl_iterator.h，我們可以看出當中的繼承關(guān)系。這個我們之后再講。

在這里插入圖片描述

注意：difference_type為兩個迭代器之間的距離。類型ptrdiff_t為無符號整形。

3.x std::find的一個報錯

當我們實現(xiàn)了自己的數(shù)據(jù)結(jié)構(gòu)，如list，我們?nèi)绻脦炖锏膕td：find查找我們實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)當中的數(shù)據(jù)會報錯。博主的測試版本為vs2013，在其他版本可能不做檢查，不會報錯。

void test_list()
	{

		list<int> l;
		l.push_back(5);
		list<int>::iterator it = std::find(l.begin(), l.end(), 5);
	}

報錯：這里的報錯說的是iterator_category不在我們的迭代器當中，這個是對我們迭代器類型的一個檢查。

在這里插入圖片描述

stl_list.h當中為迭代器添加了如下聲明來解決這個問題。

在這里插入圖片描述

解決方案：我們可以用stl3.0版本下stl_list.h當中的迭代器的聲明。也可以用release版本下，都是可以跑過的。

		typedef bidirectional_iterator_tag iterator_category;
		typedef T value_type;
		typedef Ptr pointer;
		typedef Ref reference;
		typedef ptrdiff_t difference_type;

在這里插入圖片描述