欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++?list常用接口和模擬實現(xiàn)實例代碼

 更新時間:2025年04月07日 11:34:35   作者:只有月亮知道  
C++中l(wèi)ist容器底層實現(xiàn)是使用帶頭雙向循環(huán)鏈表的結(jié)構(gòu),通過指針指向前一個和后一個節(jié)點,它也具有雙向鏈表的優(yōu)缺點,下面給大家介紹C++?list常用接口和模擬實現(xiàn)代碼,感興趣的朋友一起看看吧

C++中l(wèi)ist容器底層實現(xiàn)是使用帶頭雙向循環(huán)鏈表的結(jié)構(gòu),通過指針指向前一個和后一個節(jié)點。它也具有雙向鏈表的優(yōu)缺點,比如優(yōu)點是對于在任意位置插入和刪除不用移動數(shù)據(jù),缺點是不能任意位置的隨機訪問,必須遍歷到要訪問的節(jié)點才可以;并且list還需要額外的空間來存儲前一個和后一個節(jié)點的信息。

下面了解一下list的常用接口

1.構(gòu)造函數(shù)

//構(gòu)造空的list
list()
//拷貝構(gòu)造
list (const list& x);
//迭代器構(gòu)造,使用模板能適合不同的類型
template <class InputIterator>
list (InputIterator first, InputIterator last);
//構(gòu)造n個值為val的list
list (size_type n, const value_type& val = value_type())

2.迭代器

//返回開始位置的迭代器
iterator begin();
const_iterator begin() const;
//返回結(jié)束位置的迭代器
iterator end();
const_iterator end() const;

需要注意的是這里的迭代器在底層并不是原生指針,具體實現(xiàn)在后文給出。

3.容量操作

//判斷是否為空
bool empty() const;
//返回有效節(jié)點的個數(shù)
size_type size() const;

4.元素獲取

//返回首元素的引用
reference front();
const_reference front() const;
//返回末尾元素的引用
reference back();
const_reference back() const;

5.增刪改查

//頭插
void push_front (const value_type& val);
//尾插
void push_back (const value_type& val);
//頭刪
void pop_front();
//尾刪
void pop_back();
//在任意位置插入
iterator insert (iterator position, const value_type& val);
//在任意位置刪除
iterator erase (iterator position);
//交換兩個鏈表中的元素
void swap (list& x);
//清空鏈表中的元素
void clear();

在了解了鏈表的增刪查改之后我們思考一個問題

list是否會像vector和string一樣出現(xiàn)迭代器失效的原因?由于這里是鏈式結(jié)構(gòu),它的內(nèi)存在物理空間上并不連續(xù),因此如果僅僅是插入一個元素并不會出現(xiàn)迭代器失效的問題,只有刪除時會發(fā)生迭代器失效的問題,并且這里只有刪除節(jié)點的迭代器會失效。

下面給出list的模擬實現(xiàn)

1.節(jié)點list_node設(shè)計

節(jié)點的結(jié)構(gòu)就是雙向鏈表的結(jié)構(gòu),這里也可以寫成結(jié)構(gòu)直接默認類成員公有的也可以。

template<class T>
	class list_node
	{
	public:
		list_node<T>* _next;
		list_node<T>* _prev;
		T _val;
		list_node(const T& val = T())//默認匿名對象
			:_next(nullptr)
			,_prev(nullptr)
			,_val(val)
		{}
	};

2.迭代器設(shè)計

關(guān)于const的迭代器設(shè)計與之前的string和vector都有所不同,對于節(jié)點的指針進行了又一層的封裝。因為這里要支持->箭頭和的重載。我們對于一個指針變量進行解引用通常是要訪問其中存儲的數(shù)據(jù)的內(nèi)容(_val);而->是要訪問數(shù)據(jù)內(nèi)容的成員。從這個特性就可以得到一個結(jié)論,在實現(xiàn)list迭代器時,重載解引用和箭頭的返回類型不同,那么我們要怎樣控制呢?

事實上在這里只需要控制模板參數(shù)就可以實現(xiàn)這種效果。具體代碼如下

template<class T,class Ref ,class Ptr>
	class _list_iterator
	{
	public:
        //這里事實上迭代器只是借用節(jié)點進行訪問,而不是管理這些節(jié)點,鏈表才管理節(jié)點    
		typedef list_node<T> Node;
		typedef _list_iterator<T, Ref,Ptr> self;
		Node* _node;
		_list_iterator(Node* node)
			:_node(node)
		{}
		Ref operator*()//這里控制解引用的返回類型
		{
			return _node->_val;
		}
		Ptr operator->()
		{
			return &_node->_val;
		}
		//前置++
		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& it) const
		{
			return _node != it._node;
		}
		bool operator==(const self& it) const
		{
			return _node == it._node;
		}
	};

這里的Ref控制解引用的返回類型,Ptr控制箭頭的返回類型;并且在這個類中利用typedef的方法控制自增和自減的返回類型。

并且這樣寫還有一點好處是,對于普通的迭代器使用正常的模板參數(shù)即可,對于const迭代器使用const的模板參數(shù)即可。

3.常用接口的模擬實現(xiàn)

template<class T>
	class list
	{
		typedef list_node<T> Node;
	public:
		typedef _list_iterator<T,T&,T*> iterator;//內(nèi)嵌類
		typedef _list_iterator<T,const T&,const T*> const_iterator;
		//這里const迭代器的設(shè)計是錯誤的,因為const迭代器是希望指向內(nèi)容不被修改
		//這樣的設(shè)計是迭代器本身不能修改
		//typedef const _list_iterator<T> const_iterator;
		iterator begin() 
		{
			return _head->_next;//單參數(shù)的構(gòu)造函數(shù)支持隱式類型轉(zhuǎn)換
		}
		const_iterator begin() const
		{
			return _head->_next;
		}
		iterator end()
		{
			return _head;
		}
		const_iterator end() const
		{
			return _head;
		}
		void empty_init()
		{
			_head = new Node;
			_head->_prev = _head;
			_head->_next = _head;
		}
		list()
		{
			empty_init();
		}
		//lt2(lt1)
		list(const list<T>& lt)
		//list(const list& lt)//不推薦這樣使用
		{
			empty_init();
			//遍歷lt1,直接把lt2尾插到lt1
			//這里傳引用效率高
			for (const auto& e : lt)
			{
				push_back(e);
			}
		}
		void swap(list<T>& lt)
		{
			std::swap(_head, lt._head);
		}
		list<T>& operator=(list<T> lt)
		//list& operator=(list lt)//這里與上面的拷貝構(gòu)造同理
		{
			swap(lt);
			return *this;
		}
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}
		void push_back(const T& x)
		{
			insert(end(), x);
		}
		void pop_back()
		{
			erase(--end());//這里調(diào)用--,頭節(jié)點的prev就是尾
		}
		void push_front(const T& x)
		{
			insert(begin(), x);
		}
		void pop_front()
		{
			erase(begin());
		}
		iterator insert(iterator pos, const T& x)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* newnode = new Node(x);
			prev->_next = newnode;
			newnode->_next = cur;
			cur->_prev = newnode;
			newnode->_prev = prev;
			return newnode;
		}
		iterator erase(iterator pos)//這里會有迭代器失效,返回下一個位置的迭代器
		{
			assert(pos != end());
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;
			prev->_next = next;
			next->_prev = prev;
			delete cur;
			return next;
		}
		size_t size()
		{
			size_t sz = 0;
			iterator it = begin();
			while (it != end())
			{
				++sz;
				++it;
			}
			return sz;
		}
	private:
		Node* _head;
	};

這里的常用接口實現(xiàn)都類似與數(shù)據(jù)結(jié)構(gòu)中的帶頭的雙向鏈表。需要注意的就是爹迭代器失效的問題。

最后總結(jié)一下vector和list的各自優(yōu)劣

(1)底層結(jié)構(gòu):vector是連續(xù)存儲的,是一個動態(tài)的順序表;list是不連續(xù)存儲,是一個帶頭的雙向循環(huán)鏈表

(2)隨機訪問:vector支持[]隨機訪問;list不支持隨機訪問

(3)插入和刪除效率:vector的插入和刪除需要移動數(shù)據(jù);list的插入和刪除不需要移動數(shù)據(jù)。

(4)空間利用率:vector底層是連續(xù)的存儲空間,不容易造成內(nèi)存碎片的問題,空間利用率高;list底層是不連續(xù)的存儲空間,小的節(jié)點容易出現(xiàn)內(nèi)存碎片的問題,空間利用率低。

(5)迭代器:vector的迭代器是原生指針;list的迭代器對原生指針進行了再一層的封裝。

(6)迭代器失效的問題:vector再插入和刪除時都會導致迭代器失效,需要重新賦值;list只有再刪除時才會導致迭代器失效。

到此這篇關(guān)于C++ list常用接口和模擬實現(xiàn)實例代碼的文章就介紹到這了,更多相關(guān)C++ list常用接口內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • C++中返回指向函數(shù)的指針示例

    C++中返回指向函數(shù)的指針示例

    int (*ff(int)) (int *,int);表示:ff(int)是一個函數(shù),帶有一個int型的形參,該函數(shù)返回int (*) (int *,int),它是一個指向函數(shù)的指針,所指向的函數(shù)返回int型并帶有兩個分別是Int*和int型的形參
    2013-09-09
  • C和C++中的基本數(shù)據(jù)類型的大小及表示范圍詳解

    C和C++中的基本數(shù)據(jù)類型的大小及表示范圍詳解

    這篇文章主要介紹了C和C++中的基本數(shù)據(jù)類型的大小及表示范圍詳解,基本數(shù)據(jù)類型有int、long、long long、float、double、char、string,正文有詳細介紹,歡迎參考
    2018-01-01
  • C++將字符串格式化的幾種方式總結(jié)

    C++將字符串格式化的幾種方式總結(jié)

    這篇文章主要介紹了C++將字符串格式化的幾種方式總結(jié),具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2023-01-01
  • C語言 strcpy和memcpy區(qū)別詳細介紹

    C語言 strcpy和memcpy區(qū)別詳細介紹

    這篇文章主要介紹了C語言 strcpy和memcpy區(qū)別詳細介紹的相關(guān)資料,需要的朋友可以參考下
    2017-01-01
  • Qt拖放操作和打印操作的實現(xiàn)

    Qt拖放操作和打印操作的實現(xiàn)

    本文主要介紹了Qt拖放操作和打印操作的實現(xiàn),文中通過示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2022-04-04
  • 算法之排序算法的算法思想和使用場景總結(jié)

    算法之排序算法的算法思想和使用場景總結(jié)

    這篇文章主要介紹了算法之排序算法的算法思想和使用場景總結(jié),本文講解了插入排序、交換排序、選擇排序等幾大類排序算法的特點、思想和使用場景,需要的朋友可以參考下
    2014-08-08
  • OpenCV選擇圖像中矩形區(qū)域并保存

    OpenCV選擇圖像中矩形區(qū)域并保存

    這篇文章主要為大家詳細介紹了OpenCV選擇圖像中矩形區(qū)域并保存的方法,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2019-01-01
  • C++編譯/編輯器對OIer的必要功能(推薦)

    C++編譯/編輯器對OIer的必要功能(推薦)

    這篇文章主要介紹了C++編譯/編輯器對OIer的必要功能,本文給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2020-04-04
  • C語言排序算法之插入排序

    C語言排序算法之插入排序

    這篇文章主要為大家詳細介紹了C語言排序算法之插入排序,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2018-01-01
  • C++特殊成員函數(shù)以及其生成機制詳解

    C++特殊成員函數(shù)以及其生成機制詳解

    這篇文章主要給大家介紹了關(guān)于C++特殊成員函數(shù)以及其生成機制的相關(guān)資料,文中通過實例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
    2022-02-02

最新評論