文章目錄

• list簡介
• 結(jié)點(diǎn)類定義
• 迭代器類定義
• 鏈表類成員及其方法定義
• • 私有類成員
  • 幾個(gè)重命名
  • 迭代器
  • 構(gòu)造函數(shù)
  • 拷貝構(gòu)造函數(shù)
  • 賦值運(yùn)算符重載函數(shù)
  • size()
  • empty()
  • clear()
  • 析構(gòu)函數(shù)
  • 插入函數(shù)
  • 刪除函數(shù)
  • 頭刪頭插&尾刪尾插
• 結(jié)束語

在黃驊等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場(chǎng)前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供做網(wǎng)站、成都網(wǎng)站設(shè)計(jì) 網(wǎng)站設(shè)計(jì)制作按需定制設(shè)計(jì),公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),成都品牌網(wǎng)站建設(shè),成都全網(wǎng)營銷推廣,成都外貿(mào)網(wǎng)站制作,黃驊網(wǎng)站建設(shè)費(fèi)用合理。list簡介

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

結(jié)點(diǎn)類定義

代碼如下：

templatestruct ListNode  //定義結(jié)點(diǎn)內(nèi)容
{ListNode* _prev;  // 前指針
	ListNode* _next;  // 后指針
	T _data;  //模板類型數(shù)據(jù)

	ListNode(const T& n)  //結(jié)點(diǎn)的構(gòu)造函數(shù)
		: _prev(0)
		, _next(0)
		, _data(n)
	{}
};

這里我們用struct來定義結(jié)點(diǎn)類，因?yàn)閟truct默認(rèn)所有成員均為public。然后雙向鏈表每個(gè)結(jié)點(diǎn)包含三項(xiàng)，分別是向前指針，向后指針和要存放的內(nèi)容。最后還需要實(shí)現(xiàn)結(jié)點(diǎn)的構(gòu)造函數(shù)以方便后面new結(jié)點(diǎn)時(shí)進(jìn)行調(diào)用。

迭代器類定義

我們知道，前面兩個(gè)容器string和vector他們存放數(shù)據(jù)的內(nèi)存都是連續(xù)的，因此支持隨機(jī)存取，也就可以重載[]來進(jìn)行訪問，而解引用(*)就可以直接訪問對(duì)應(yīng)內(nèi)存里的內(nèi)容。但是到了鏈表這里，我們就不能再簡單的使用解引用符號(hào)來訪問數(shù)據(jù)元素了，因?yàn)閮?nèi)存不再連續(xù)，數(shù)據(jù)在內(nèi)存上的前后關(guān)系也不確定。因此我們想要統(tǒng)一迭代器的使用方式，就需要對(duì)list的迭代器進(jìn)行封裝，代碼如下：

templatestruct __list_iterator
{typedef ListNodeNode; //將剛才定義好的鏈表節(jié)點(diǎn)進(jìn)行重命名，命名為Node
	typedef __list_iteratorSelf;
	Node* _pnode;  // 在迭代器里創(chuàng)建一個(gè)指向結(jié)點(diǎn)的指針

	__list_iterator(Node* p)  //迭代器的構(gòu)造函數(shù)，需要傳入一個(gè)指向結(jié)點(diǎn)的指針
		:_pnode(p)  //用傳入的指針來初始化迭代器
	{}

	Ref operator*()  // 迭代器結(jié)構(gòu)體的解引用運(yùn)算符重載，返回指針指向的結(jié)構(gòu)體里面存儲(chǔ)的data
	{return _pnode->_data;
	}
	Ptr operator->()
	{return &_pnode->_data;
	}
	Self& operator++() //前置++，返回一個(gè)迭代器對(duì)象，并且讓指向結(jié)點(diǎn)的指針指向其next
	{_pnode = _pnode->_next;
		return *this;
	}
	Self operator++(int)
	{Self tmp(*this);
		_pnode = _pnode->_next;
		return tmp;
	}
	Self& operator--() //前置--，返回一個(gè)迭代器對(duì)象，并且讓指向結(jié)點(diǎn)的指針指向其next
	{_pnode = _pnode->_prev;
		return *this;
	}
	Self operator--(int)
	{Self tmp(*this);
		_pnode = _pnode->_prev;
		return tmp;
	}
	bool operator!=(const Self& it) const
	{return _pnode != it._pnode;
	}
	bool operator==(const Self& it) const
	{return _pnode == it._pnode;
	}

};

整個(gè)迭代器唯一的成員變量就是一個(gè)指向結(jié)點(diǎn)的指針，在這個(gè)類里面我們實(shí)現(xiàn)了以下這些函數(shù)：

1. 構(gòu)造函數(shù)：因?yàn)轭愔兄话粋€(gè)指針，所以構(gòu)造函數(shù)就是通過傳入指針進(jìn)行初始化
2. 解引用重載函數(shù)：返回指針指向結(jié)點(diǎn)的數(shù)據(jù)，這樣在外界看來就和解引用直接獲得數(shù)據(jù)一樣了
3. 類成員訪問運(yùn)算符重載函數(shù)：因?yàn)镾TL容器可以裝各種類型的數(shù)據(jù)，因此也當(dāng)然可以存儲(chǔ)結(jié)構(gòu)體類型的數(shù)據(jù)，因此迭代器里面存放的自然就是結(jié)構(gòu)體的指針，但迭代器自己作為類，他并不能直接使用此運(yùn)算符，所以必須對(duì)此運(yùn)算符進(jìn)行重載。我們看到重載后函數(shù)會(huì)返回對(duì)應(yīng)的地址，而我們想通過地址進(jìn)行數(shù)據(jù)訪問是需要再用一次類成員訪問運(yùn)算符的，就比如it->->類成員，但是這樣雖然好理解但是可讀性很差，所以在這里編譯器替我們進(jìn)行了處理，只要進(jìn)行了重載，用一個(gè)運(yùn)算符即可，也就是it->類成員
4. 前后置++和- -，就是重載成將指針指向前一個(gè)結(jié)點(diǎn)或后一個(gè)結(jié)點(diǎn)，前置返回修改后的，后置返回修改前的
5. 相等和不相等就是返回兩個(gè)迭代器內(nèi)的指針值是否相等

這里還涉及到后續(xù)const迭代器的實(shí)現(xiàn)，主要是借助模板的功能，我們后面會(huì)提到。

鏈表類成員及其方法定義 私有類成員

private:
	Node* _head;
	size_t _size;

正常來講一個(gè)鏈表有個(gè)哨兵位就夠了，這里增加一個(gè)size變量主要是為了能夠降低調(diào)用size()方法的代價(jià)。如果沒有這個(gè)成員變量，那么每次調(diào)用此方法都會(huì)遍歷一次鏈表，代價(jià)較高。

幾個(gè)重命名

typedef ListNodeNode; 
typedef __list_iteratoriterator; 
typedef __list_iteratorconst_iterator;

這里我們分別重命名了結(jié)點(diǎn)，通過給迭代器類傳入兩套不同的參數(shù)以實(shí)現(xiàn)非const迭代器和const迭代器并將他們進(jìn)行重命名。

迭代器

迭代器包括const迭代器和非const迭代器，代碼如下：

iterator begin()
{return iterator(_head->_next);  //返回begin迭代器，用哨兵位的next來傳參生成匿名對(duì)象，因?yàn)樯诒坏南乱粋€(gè)是第一個(gè)有效對(duì)象
}

iterator end()
{return iterator(_head);  //返回end迭代器，用哨兵位來傳參生成匿名對(duì)象，因?yàn)樯诒痪褪请p向循環(huán)鏈表最后一個(gè)有效位置的下一個(gè)
}
const_iterator begin() const
{return const_iterator(_head->_next);
}

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

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

void empty_initialize()
{_head = new Node(T());
	_head->_next = _head;
	_head->_prev = _head;

	_size = 0;
}
List()
{empty_initialize();
}

默認(rèn)構(gòu)造的內(nèi)容很簡單，就是生成一個(gè)哨兵位，其前后指針均指向自己。

拷貝構(gòu)造函數(shù)

templateList(InputIterator first, InputIterator last)
{empty_initialize();
	while (first != last)
	{push_back(*first);
		++first;
	}
}
void swap(List& lt)
{std::swap(_head, lt._head);
	std::swap(_size, lt._size);
}
List(const List& lt)
{empty_initialize();
	Listtmp(lt.begin(), lt.end());
	swap(tmp);
}

拷貝構(gòu)造函數(shù)提供兩種，第一種是迭代器區(qū)間的，比較好理解。第二種是我們常用的簡潔寫法，先將調(diào)用拷貝構(gòu)造的對(duì)象初始化，然后借助第一個(gè)迭代器區(qū)間的構(gòu)造初始化一個(gè)工具人，最后交換二者成員即可。

賦值運(yùn)算符重載函數(shù)

List& operator=(Listlt)
{swap(lt);
	return *this;
}

內(nèi)容很簡單，和前面兩個(gè)容器的實(shí)現(xiàn)方式類似，都是通過傳值調(diào)用來隱式調(diào)用拷貝構(gòu)造，讓臨時(shí)對(duì)象來和調(diào)用賦值重載的對(duì)象進(jìn)行成員變量交換以實(shí)現(xiàn)賦值。

size()

size_t size() const
{return _size;
}

因?yàn)槲覀冊(cè)黾恿顺蓡T變量進(jìn)行記錄，所以可以直接返回變量值，否則就要對(duì)list進(jìn)行遍歷計(jì)數(shù)。

empty()

bool empty() const
{return _size == 0;
}

這里既可以使用_size，也可以判斷頭結(jié)點(diǎn)的前后指針是否指向自己。

clear()

void clear()
{iterator cur = begin();
	while (cur != end())
	{cur = erase(cur);
	}
	_size = 0;
}

此函數(shù)的主要功能就是清除掉所有非哨兵結(jié)點(diǎn)，然后將size置為0。

析構(gòu)函數(shù)

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

因?yàn)槲覀兦懊鎸?shí)現(xiàn)了clear函數(shù)，所以這里直接調(diào)用即可，然后將哨兵結(jié)點(diǎn)釋放、置空。

插入函數(shù)

iterator insert(iterator pos, const T& n)
{Node* newnode = new Node(n);

	Node* cur = pos._pnode;
	Node* prev = cur->_prev;
	//prev   newnode   cur
	newnode->_prev = prev;
	prev->_next = newnode;
	newnode->_next = cur;
	cur->_prev = newnode;

	++_size;
	return iterator(newnode);
}

先申請(qǐng)一個(gè)新結(jié)點(diǎn)，然后就是雙向鏈表的插入操作，然后給size加一，最后以新結(jié)點(diǎn)為參數(shù)生成迭代器匿名對(duì)象做為返回值。

刪除函數(shù)

iterator erase(iterator pos)
{assert(pos != iterator(_head));

	Node* next = pos._pnode->_next;
	Node* prev = pos._pnode->_prev;
	prev->_next = next;
	next->_prev = prev;

	delete[] pos._pnode;
	--_size;
	return iterator(next);
}

首先判斷鏈表非空，然后將想要?jiǎng)h除的結(jié)點(diǎn)從鏈表中摘出并將其delete掉，修改size后返回刪除節(jié)點(diǎn)下一個(gè)位置的迭代器。

頭刪頭插&尾刪尾插

void push_back(const T& n)
{insert(end(), n);
}
void push_front(const T& n) 
{insert(begin(), n);
}
void pop_front()
{erase(begin());
}		
void pop_back()
{erase(--end());
}

復(fù)用實(shí)現(xiàn)好的插入和刪除即可。

結(jié)束語

至此關(guān)于list類的簡單實(shí)現(xiàn)的全部內(nèi)容已呈現(xiàn)完畢，如本文有不足或遺漏之處還請(qǐng)大家指正，筆者感激不盡；同時(shí)也歡迎大家在評(píng)論區(qū)進(jìn)行討論，一起學(xué)習(xí)，共同進(jìn)步！

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站題目：【C++】STL容器list——雙向帶頭循環(huán)鏈表的簡單實(shí)現(xiàn)-創(chuàng)新互聯(lián)
本文URL：http://jinyejixie.com/article22/dhccjc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供自適應(yīng)網(wǎng)站、手機(jī)網(wǎng)站建設(shè)、電子商務(wù)、App開發(fā)、品牌網(wǎng)站制作、定制開發(fā)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)