【C++】STL容器list——雙向帶頭循環(huán)鏈表的簡單實現(xiàn)-創(chuàng)新互聯(lián)

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

在黃驊等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強發(fā)展的系統(tǒng)性、市場前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供做網(wǎng)站、成都網(wǎng)站設(shè)計 網(wǎng)站設(shè)計制作按需定制設(shè)計,公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),成都品牌網(wǎng)站建設(shè),成都全網(wǎng)營銷推廣,成都外貿(mào)網(wǎng)站制作,黃驊網(wǎng)站建設(shè)費用合理。list簡介
  1. list是可以在常數(shù)范圍內(nèi)在任意位置進(jìn)行插入和刪除的序列式容器，并且該容器可以前后雙向迭代。
  2. list的底層是雙向鏈表結(jié)構(gòu)，雙向鏈表中每個元素存儲在互不相關(guān)的獨立節(jié)點中，在節(jié)點中通過指針指向
    其前一個元素和后一個元素。
  3. list與forward_list非常相似：最主要的不同在于forward_list是單鏈表，只能朝前迭代，已讓其更簡單高
    效。
  4. 與其他的序列式容器相比(array，vector，deque)，list通常在任意位置進(jìn)行插入、移除元素的執(zhí)行效率
    更好。
  5. 與其他序列式容器相比，list和forward_list大的缺陷是不支持任意位置的隨機訪問，比如：要訪問list
    的第6個元素，必須從已知的位置(比如頭部或者尾部)迭代到該位置，在這段位置上迭代需要線性的時間
    開銷；list還需要一些額外的空間，以保存每個節(jié)點的相關(guān)聯(lián)信息(對于存儲類型較小元素的大list來說這
    可能是一個重要的因素)
結(jié)點類定義

代碼如下：

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

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

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

迭代器類定義

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

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

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

	Ref operator*()  // 迭代器結(jié)構(gòu)體的解引用運算符重載，返回指針指向的結(jié)構(gòu)體里面存儲的data
	{return _pnode->_data;
	}
	Ptr operator->()
	{return &_pnode->_data;
	}
	Self& operator++() //前置++，返回一個迭代器對象，并且讓指向結(jié)點的指針指向其next
	{_pnode = _pnode->_next;
		return *this;
	}
	Self operator++(int)
	{Self tmp(*this);
		_pnode = _pnode->_next;
		return tmp;
	}
	Self& operator--() //前置--，返回一個迭代器對象，并且讓指向結(jié)點的指針指向其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;
	}

};

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

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

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

鏈表類成員及其方法定義 私有類成員
private:
	Node* _head;
	size_t _size;

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

幾個重命名
typedef ListNodeNode; 
typedef __list_iteratoriterator; 
typedef __list_iteratorconst_iterator;

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

迭代器

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

iterator begin()
{return iterator(_head->_next);  //返回begin迭代器，用哨兵位的next來傳參生成匿名對象，因為哨兵位的下一個是第一個有效對象
}

iterator end()
{return iterator(_head);  //返回end迭代器，用哨兵位來傳參生成匿名對象，因為哨兵位就是雙向循環(huán)鏈表最后一個有效位置的下一個
}
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ò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)造的對象初始化，然后借助第一個迭代器區(qū)間的構(gòu)造初始化一個工具人，最后交換二者成員即可。

賦值運算符重載函數(shù)
List& operator=(Listlt)
{swap(lt);
	return *this;
}

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

size()
size_t size() const
{return _size;
}

因為我們增加了成員變量進(jìn)行記錄，所以可以直接返回變量值，否則就要對list進(jìn)行遍歷計數(shù)。

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

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

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

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

析構(gòu)函數(shù)
~List()
{clear();
	delete _head;
	_head = nullptr;
}

因為我們前面實現(xiàn)了clear函數(shù)，所以這里直接調(diào)用即可，然后將哨兵結(jié)點釋放、置空。

插入函數(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);
}

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

刪除函數(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é)點從鏈表中摘出并將其delete掉，修改size后返回刪除節(jié)點下一個位置的迭代器。

頭刪頭插&尾刪尾插
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ù)用實現(xiàn)好的插入和刪除即可。

結(jié)束語

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

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

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

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

廣告

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

成都定制網(wǎng)站網(wǎng)頁設(shè)計