C++中如何實現(xiàn)list

這篇文章將為大家詳細講解有關C++中如何實現(xiàn)list，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

list的介紹

list的優(yōu)點：

• list頭部、中間插入不再需要挪動數(shù)據(jù)，O(1)效率高

• list插入數(shù)據(jù)是新增節(jié)點，不需要增容
  

list的缺點：

• 不支持隨機訪問,訪問某個元素效率O(N)

• 底層節(jié)點動態(tài)開辟，小節(jié)點容易造成內(nèi)存碎片，空間利用率低，緩存利用率低。

模擬實現(xiàn)list

我們先來看看官方文檔中對于list的描述

我們先大致了解一下list的遍歷

迭代器

對于迭代器我們可以用while循環(huán)+begin（）end（）。同時還可以用迭代器區(qū)間。

當然迭代器區(qū)間的方式只適用于內(nèi)存連續(xù)的結構比如數(shù)組stringvector等

它們的原生指針就可以當作迭代器來用。

范圍for

其實范圍for和迭代器的底層是完全一樣的，我們只有寫好迭代器，才能用范圍for，而且這里的迭代器必須和庫里的命名一樣才可以用范圍for

我們再來了解一下有關算法函數(shù)中，我們最常用的函數(shù)

• swap

• find

• sort
  

我們主要看看sort函數(shù)

sort函數(shù)在官方庫中是用快排寫的，其中快排的精髓就是三數(shù)取中的優(yōu)化操作。

sort默認是排升序 如果想排降序需要使用functional文件中的greater()這個模板函數(shù)，我們以vector來舉例。

對于list，我們極度不推薦使用algorithm文件中的sort函數(shù)，上文提到了sort函數(shù)是使用的快速排序的手段進行排序的，而其關鍵在于三數(shù)取中這樣的操作，那么三數(shù)取中這樣的操作只有在內(nèi)存連續(xù)的數(shù)據(jù)結構中才能操作，如果給你一個head，給你一個tail，你如果能找到中間的結點？很明顯是很復雜的。

我們這里list迭代器是不支持隨機訪問，他不是隨即迭代器。

而vector string這樣的迭代器是支持隨機訪問的，所以他們用快排很有優(yōu)勢。

我們可以看到這三個函數(shù)的迭代器是不同的，它們是繼承關系，隨機的支持雙向，雙向支持單向，反過來就不行。

當然除了這幾種迭代器，還有輸入輸出迭代器，也叫可讀可寫迭代器，他們是最弱的迭代器，一個單向迭代器都可以支持可讀可寫的功能。也就是說，可讀可寫迭代器在繼承的最上端。所有人都包含了他倆。

但是雖然他們功能很弱，但他們在一些重要的特性上有至關重要的作用，那就是迭代器的萃取。這個和復雜，暫時不去管它們。

總結上面兩段話：

當我們使用迭代器遍歷的時候，我們需要知道的是，begin（）代表了第一個結點，end（）代表了頭結點。

這里再穿插一個小知識，我們再官方文檔中總能看到max_size這樣的變量，
它的意義是整形的最大值除以一個節(jié)點的大小，也就是得出的節(jié)點個數(shù)
無符號整形最大是2^32-1，也就是42億多，對于int類型的vector，就是42億除以4得到的值，對于list，就是42億除以三個指針的大小得到的值。

我們還知道再vector中，我們在insert的擴容插入，還有erase的刪除時，會導致迭代器失效的問題。那么對于list我們還要去關注迭代器失效的問題嗎？

我們再insert的時候，插入數(shù)據(jù)并不會影響到其他的數(shù)據(jù)的地址，只是影響鏈接的關系，所以不會引起迭代器失效

但是對于erase，當我們刪除對應的結點之后，他會變成野指針。所以我們erase的時候通常去接收它的返回值，也就是下一個結點的迭代器。

當然庫中還有一些我們不常用的函數(shù)

splice 接合函數(shù)，把一個list的數(shù)據(jù)轉(zhuǎn)移到另一個list

這里不是拷貝，是轉(zhuǎn)移。

還有remove，找到就刪，沒找到就沒什么反應。

unique 去重，這里又一個小小的bug，只有連續(xù)的重復數(shù)據(jù)才會刪除。

聰明的同學會反應過來，這里sort+unique可以解決這樣的問題。當然沒反應過來的同學也很聰明。

這里顯然還是那個問題，我們不建議堆鏈表進行排序，效率是很低的。

list的成員函數(shù)是用的歸并排序。為什么不用algorithm中的sort快排呢？原因我們上文已經(jīng)解釋過了。

說了這么多，來看看代碼吧。

先來看看頭文件吧！

#pragma once

#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;

namespace LL
{
	我們先寫結點類，這里用類模板，并且是用struct實現(xiàn)，默認內(nèi)容是公開的,其他的類都可以調(diào)用 
	template<class T>
	其中結點類中要有三個變量，一個存值，兩個指針
	struct _list_node
	{
		T _val;
		_list_node<T>*  _next;
		_list_node<T>*  _prev;

		結點類中除了要有三個變量，還需要有一個構造函數(shù)。當我們定義一個新結點的時候，進行構造函數(shù)初始化
		我們這里的參數(shù)是一個缺省的val值 ，其中缺省參數(shù)給的是匿名構造函數(shù)。最好以const接收。
		_list_node(const T& val = T())
			:_val(val)
			, _next(nullptr)
			, _prev(nullptr)
		{}
	};

	這里實現(xiàn)迭代器類。首先我們依舊是使用類模板 ，我們這里給三個模板參數(shù)，同時類還是用struct來實現(xiàn)
	在迭代器類中，我們主要實現(xiàn) 1、構造 2、解引用操作  3、！= 和== 操作  3、前置++后置++ --操作
	template<class T, class Ref, class Ptr> 這里三個模板參數(shù)是什么意思呢?當我們需要const迭代器和非const迭代器的時候我們可以根據(jù)第二個參數(shù)的不同來實例化出不同的迭代器，就不需要寫兩個迭代器了
	typedef _list_iterator<T,T&,T*> iterator;
	typedef _list_iterator<T,cosnt T&,const T*> const_iterator; 我們可以根據(jù)模板參數(shù)實例化出不同的迭代器。
	struct _list_iterator
	{
		typedef _list_node<T>  node;
		typedef _list_iterator<T, Ref, Ptr>  self;

		node* _pnode;

		構造函數(shù)，把node傳進來，然后把值賦給我們內(nèi)部創(chuàng)建的_pnode,總不能亂修改外部指針吧。
		_list_iterator(node * node)
			:_pnode(node)
		{}

		這里我們不需要實現(xiàn)拷貝構造、operator=、析構，直接用編譯器生成的，對于內(nèi)置類型直接進行淺拷貝
		我們發(fā)現(xiàn)淺拷貝指針對于list來說完全沒問題。

		解引用，解引用我們返回值寫為Ref ，這樣可以根據(jù)const和非const，并且就是引用返回可讀可修改，如果ref為const，那就不可修改只可讀。
		這里不需要傳入?yún)?shù)，我們直接進行調(diào)用，返回值當然為對應的val引用.
		Ref operator * ()
		{
			return _pnode->_val;
		}
		同理的我們寫一下這個指針解引用，這里返回值依舊用模板參數(shù)，很方便啊。我們應該返回一個地址。
		Ptr operator ->()
		{
			return &(_pnode->_val);
		}

		！= 和 == ，當我們使用迭代器的時候，需要比較兩個迭代器是否相等來進行循環(huán)條件判定，所以這是必要的。
		我們這里返回值當然是bool，參數(shù)傳入我們的迭代器，比較迭代器內(nèi)的節(jié)點是否相等。再加上const最好。
		bool operator != (const self& s) const
		{
			return _pnode != s._pnode;
		}
		bool operator == (const self& s) const
		{
			return _pnode == s._pnode;
		}
		接著我們實現(xiàn)前置后置++--
		前置 ++ it  我們返回值是 原迭代器
		self& operator++()
		{
			_pnode = _pnode->_next;
			return *this;
		}
		后置 ++ it ，我們需要進行傳參，第一個參數(shù)就是默認的this，第二個參數(shù)為0
		it ++ --> it.operator ++(&it,0);我們可以缺省掉第二個參數(shù)，因為默認是從參數(shù)列表末尾開始匹配的。
		當然返回值就不能返回引用了，因為這里我們要用臨時變量進行返回,我們先用傳入的it拷貝構造一個臨時迭代器。然后在進行++操作。
		因為后置加加是先賦值再++所以我們先用臨時變量保存一下之前的迭代器，再給之前的迭代器++，最后再返回未修改的臨時迭代器。
		self operator++(int)
		{
			self tmp(*this);
			_pnode = _pnode->_next;
			return tmp;
		}

		self& operator--()
		{
			_pnode = _pnode->_prev;
			return *this;
		}
		self operator--(int)
		{
			self tmp(*this);
			_pnode = _pnode->_prev;
			return tmp;
		}


	};




	接下來我們開始寫list類,當然也要用類模板來寫，里面要實現(xiàn)1、迭代器 2、構造 3、push_back 。我們這里的list是帶頭雙向循環(huán)列表
	template <class T>
	class list
	{
		我們先來實現(xiàn)一下迭代器,我們首先需要typedef 我們的迭代器 ，所以先實現(xiàn)迭代器。然后需要定義const和非const的beginend ,
		這里需要記住end和begin要有非const和cosnt，因為無法同時滿足可修改和可讀。比如const迭代器調(diào)用只能掉const的end，非const的迭代器雖然可以調(diào)用const的end，但是導致權限縮小，無法修改內(nèi)容。
		typedef _list_node<T> node;
	public:
		typedef _list_iterator<T, T&, T*> iterator;
		typedef _list_iterator<T, const T&, const T*> const_iterator;

		iterator begin()                   //begin指頭結點后第一個結點，end指頭結點。
		{
			return iterator(_head->_next); //這里調(diào)用的是匿名構造然后直接返回。
		}
		const_iterator begin() const
		{
			return const_iterator(_head->_next);
		}

		iterator end()
		{
			return iterator(_head);
		}
		const_iterator end() const
		{
			return const_iterator(_head);
		}


		構造函數(shù)，這里直接進行頭結點的創(chuàng)建（自己鏈自己）
		list()
		{
			_head = new node(T());    當然可以有這種寫法，我們用匿名構造一個頭結點，可以是各種類型。這里和上文中，結點的構造函數(shù)是一樣的，我們寫一個就好了。
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
		}

		push_back 我們傳入一個要插入的值，創(chuàng)建新節(jié)點進行鏈接的更新。
		void push_back(const T& val)
		{
			node* newnode = new node(val);   //這里因為我們在結點的構造函數(shù)中寫了模板參數(shù)類型匿名構造，可以傳任意類型。
			node* tail = _head->_prev;
			tail->_next = newnode;
			newnode->_prev = tail;
			newnode->_next = _head;
			_head->_prev = newnode;

		}

		拷貝構造  1、創(chuàng)造新的頭結點，把傳入的list循環(huán)賦值給新的頭結點。
		list(const list<T>& l)
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
			const_iterator it = l.begin();
			while (it != l.end())
			{
				push_back(*it);
				++it;
			}
		}

		insert，在指定位置插入元素，我們不用返回值，參數(shù)是pos迭代器和val
		先給一個cur 存pos位置的結點，然后定義一個我們的prev，為了之后和新節(jié)點鏈接。2、創(chuàng)建新節(jié)點，更新鏈接就好了。
		void insert(iterator pos, const T& val)   //這里不需要用const 因為，const迭代器對應了constlist ，const list怎么會來插入數(shù)據(jù)呢？
		{
			node* cur = pos._pnode;
			node* prev = cur->_prev;
			node* newnode = new node(val);

			newnode->_next = cur;
			newnode->_prev = prev;
			prev->_next = newnode;
			cur->_prev = newnode;
		}

		erase ,返回下一個位置的迭代器，傳入一個pos
		1、保存指向結點，并找到前后的兩節(jié)點 2、更新鏈接 刪除掉當前節(jié)點。3、返回迭代器。這里需要強轉(zhuǎn)，從指針轉(zhuǎn)成迭代器類型。
		iterator erase(iterator pos)
		{
			node* cur = pos._pnode;
			node* prev = cur->_prev;
			node* next = cur->_next;
			
			prev->_next = next;
			next->_prev = prev;
			delete cur;
			return (iterator)next;
		}


		那我們在賦值運算符重載的時候需要先清理掉自身的結點，所以我們實現(xiàn)一下clear
		clear 清空list中除了頭結點以外的所有結點。很好實現(xiàn)，我們循環(huán)erase就好了，erase返回下一個的迭代器，所以接收其返回值就好了。
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

		賦值運算符重載，返回值是類型的引用 ，參數(shù)傳入list
		1、首先判斷是否給自己賦值，否則我們刪除后會發(fā)生野指針的問題 2、條件成立我們先清除現(xiàn)在的一切，然后循環(huán)賦值。最后返回*this；
		list<T>& operator = (list<T>& l)
		{
			if (this != &l)
			{
				clear ();
				iterator it = l.begin();
				while (it != l.end())
				{
					push_back(*it);
					it++;
				}
				
			}
			return *this;
		}

		析構：析構要做的就是析構一切，先clear，在delete 頭，并給頭賦空
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
			cout << "析構執(zhí)行成功" << endl;
		}

		獲得第一個元素，返回一定是類型的引用,這里應該有兩個版本，否則當const對象調(diào)用的時候，會無法調(diào)用。這里返回也要返回const，否則你給人家偷偷擴大了權限。
		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,傳入list。我們只需要交換一下頭結點就可以了
		void swap(list<T>& l)
		{
			::swap(_head, l._head);
		}

		void push_back_insert(const T& val)
		{
			insert(end(), val);
		}

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

		void pop_front_erase()
		{
			erase(begin());
		}
		void pop_back_erase()
		{
			erase(--end());
		}

		求結點個數(shù)循環(huán)計數(shù)
		size_t size()
		{
			size_t count = 0;
			auto it = begin();
			while (it != end())
			{
				++it;
				++count;

			}
			return count;
		}

		bool empty()
		{
			return begin() == end();		
		}

		resize ,開辟n個空間并賦初始值，用匿名構造賦值。
		1、計算舊結點個數(shù)，如果就空間比新的空間大，我們就刪除多余的空間2、否則就從新空間開始給其賦初值。
		void resize(size_t newsize, T& val = T())
		{
			size_t oldsize = size();
			if (oldsize > newsize)
			{
				for (int i = newsize; i < oldsize; i++)
				{
					pop_back_erase();
				}
			}
			else
			{
				for (int i = oldsize; i < newsize; i++)
				{
					push_back_insert(val);
				}
			}
		}




	private:
		node* _head;
	};

}

我們來測試一下我們的函數(shù)

#include "List.h"

//printlist 打印不需要返回什么，參數(shù)是一個模板參數(shù)類型的列表
template<class Con>
void PrintContainer(const Con& c)
{
	Con::const_iterator it = c.begin();
	while (it != c.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

}

void test_list1()
{
	cout << "list1使用pushback插入數(shù)據(jù)的打印" << endl;
	LL::list<int> lt1;
	lt1.push_back(1);
	lt1.push_back(2);
	lt1.push_back(3);
	lt1.push_back(4);
	lt1.push_back(5);
	lt1.push_back(6);
	PrintContainer(lt1);
	//for (auto e : lt)
	//{
	//	cout << e << " ";

	//}
	//cout << endl;

	//LL::list<int>::iterator it = lt.begin();
	//while (it != lt.end())
	//{
	//	(*it)++;
	//	cout << *it << " ";
	//	++it;
	//}
	//cout << endl;


	cout << "拷貝構造list2的打印" << endl;
	LL::list<int> lt2(lt1);
	PrintContainer(lt2);
	
	//cout << "在list2的2位置前insert一個0并打印" << endl;
	//LL::list<int>::iterator pos = find(lt2.begin(), lt2.end(),2);		
	//lt2.insert(pos,0);
	//PrintContainer(lt2);

	//cout << "在list2的2位置前insert一個0并打印" << endl;
	//lt2.erase(pos);
	//PrintContainer(lt2);

	cout << "用list2給list3賦值,并打印" << endl;
	LL::list<int> lt3;
	lt3 = lt2;
	PrintContainer(lt3);

	cout << "獲得list3的第一個元素和最后一個元素" << endl;
	cout << lt3.front() <<"  ";
	cout << lt3.back() << endl;

	cout << "整一個全是0的list4，并打印" << endl;
	LL::list<int> lt4;
	lt4.push_back(0);
	lt4.push_back(0);
	lt4.push_back(0);
	lt4.push_back(0);
	lt4.push_back(0);
	lt4.push_back(0);
	PrintContainer(lt4);

	cout << "交換鏈表list1和list4、并打印" << endl;
	lt1.swap(lt4);
	PrintContainer(lt4);


	cout << "頭刪list4" << endl;
	lt4.pop_front_erase();
	PrintContainer(lt4);
	cout << "頭插list4" << endl;
	lt4.push_front_insert(0);
	PrintContainer(lt4);
	cout << "尾刪list4" << endl;
	lt4.pop_back_erase();
	PrintContainer(lt4);
	cout << "尾插list4" << endl;
	lt4.push_back_insert(0);
	PrintContainer(lt4);


	cout << "list4的節(jié)點個數(shù)" << endl;
	cout << lt4.size() << endl;

	cout << "判斷是list1是否為空鏈表" << endl;
	cout << lt1.empty() << endl;




	cout << "    " << endl;
	cout << "    " << endl;
	cout << "    " << endl;
	cout << "    " << endl;

	cout << "    " << endl;
	cout << "    " << endl;
}


int main()
{

	test_list1();
	return 0;
}

關于“C++中如何實現(xiàn)list”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。