C++數(shù)據(jù)結(jié)構(gòu)之list詳解
前言
list相較于vector來(lái)說(shuō)會(huì)顯得復(fù)雜，它的好處是在任意位置插入,刪除都是一個(gè)O(1)的時(shí)間復(fù)雜度。
一、list的節(jié)點(diǎn)
template <class T>
struct __list_node {
typedef void* void_pointer;
void_pointer next;
void_pointer prev;
T data;
};
這個(gè)是在stl3.0版本下的list的節(jié)點(diǎn)的定義，節(jié)點(diǎn)里面有一個(gè)前指針，一個(gè)后指針，有一個(gè)數(shù)據(jù)data。這里只能知道他是一個(gè)雙向鏈表，我們可以再稍微看一下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)建了一個(gè)頭結(jié)點(diǎn)，并且是一個(gè)循環(huán)的結(jié)構(gòu)。
綜上：list的總體結(jié)構(gòu)是一個(gè)帶頭循環(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 >當(dāng)中定義一個(gè)iterator對(duì)象，然后讓他去訪問(wèn)我們的節(jié)點(diǎn)
- 并且他所支持的操作有++，解引用，當(dāng)然還有 --等等
stl3.0當(dāng)中的迭代器實(shí)現(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;
}
大家感興趣可以先看看上面的，我們先用一個(gè)簡(jiǎn)述版的來(lái)帶大家簡(jiǎn)要實(shí)現(xiàn)一下
template<class T>
class __list_node
{
public:
__list_node(const T& val = T())//用一個(gè)全缺省比較好
:_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;
};
這里的實(shí)現(xiàn)是不完整的，但是很適合說(shuō)明問(wèn)題。通過(guò)我們?nèi)ブ剌dopertaor++，和重載opertaor*，可以讓我們像指針一樣去訪問(wèn)一個(gè)節(jié)點(diǎn)，讓我們可以跟vector和string一樣用同樣的接口就能實(shí)現(xiàn)對(duì)數(shù)據(jù)的訪問(wèn)，這是非常厲害的一個(gè)技術(shù)。
注意點(diǎn)：
- 我們通過(guò)對(duì)節(jié)點(diǎn)的操作，重載了operator++等接口實(shí)現(xiàn)了對(duì)一個(gè)節(jié)點(diǎn)的訪問(wèn)，訪問(wèn)的時(shí)候?qū)嶋H上也就是創(chuàng)建迭代器對(duì)象，對(duì)我們的數(shù)據(jù)進(jìn)行訪問(wèn)，所以我們封裝的時(shí)候是將節(jié)點(diǎn)的指針進(jìn)行封裝。
- list相比vector，正因?yàn)樗麄兊牡讓咏Y(jié)構(gòu)不相同，list的迭代器在插入操作和接合操作（splice）
都不會(huì)造成迭代器失效，只有刪除的時(shí)候，只有那個(gè)被刪除元素的迭代器失效，而不影響后面的，而vector就統(tǒng)統(tǒng)失效了。
模板參數(shù)為什么是三個(gè)
2.1 const 迭代器
有這樣一種情況，我們需要const對(duì)象去遍歷，假如我們有個(gè)函數(shù)叫做print_list（const list< int >& lt）;
傳參： 其中傳參中const是因?yàn)椴粫?huì)對(duì)對(duì)象進(jìn)行修改，加引用是因?yàn)椴挥蒙羁截悾岣咝省?br />
功能： 這個(gè)函數(shù)就是去打印鏈表里面的內(nèi)容的。但是按照我們上面的實(shí)現(xiàn)，會(huì)出現(xiàn)什么問(wèn)題呢。
這很正常，在const迭代器就去生成const迭代器對(duì)象，在vector，string這些迭代器就是原生指針的時(shí)候我們只需要typedef const T* const_iterator,那如果我們?cè)谖覀兩傻膌ist也做類似的操作，來(lái)看看結(jié)果。
結(jié)果我們發(fā)現(xiàn)，好像沒(méi)多大問(wèn)題，但是我們嘗試修改const迭代器里面的內(nèi)容時(shí)，卻發(fā)現(xiàn)能修改成功。const迭代器怎么能修改里面的數(shù)據(jù)呢？這就有問(wèn)題了?。?！說(shuō)明我們的有一個(gè)巨大的隱患在里面。
2.2 修改方法
最簡(jiǎn)單的方法當(dāng)然就是再寫多一個(gè)迭代器，把__list_iterator換成__list_const_iterator 之類的，但是我們認(rèn)真觀察的話，實(shí)際上這兩個(gè)類很多東西是重復(fù)的，只有在operator*，operator->時(shí)所需要的返回值，我們需要找到一種方法去讓const對(duì)象的返回值也是const對(duì)象，答案就是添加多兩個(gè)個(gè)模板參數(shù)。
以下以添加一個(gè)模板參數(shù)為例，實(shí)現(xiàn)一個(gè)Ref operator*()；
template<class T>
class __list_node
{
public:
__list_node(const T& val = T())//用一個(gè)全缺省比較好
:_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;
};
一圖了解：也就是我們的測(cè)試端test函數(shù)中定義list< int >::const_iterator cit= l.begin();的時(shí)候迭代器對(duì)象就會(huì)識(shí)別到定義的const迭代器，它的第二個(gè)模板參數(shù)放的就是const T&，這樣子我們operator*（）返回的時(shí)候只需要返回第二個(gè)模板參數(shù)就可以了。
同理，我們要用到的接口operator->當(dāng)中也會(huì)有const對(duì)象和普通對(duì)象調(diào)用的情況。我們這里把實(shí)現(xiàn)的代碼放出來(lái)，有需要的自取。
–》碼云鏈接《–
二、美中不足
list上面說(shuō)的仿佛都是優(yōu)點(diǎn)
任意位置的O(1)時(shí)間的插入刪除，迭代器失效的問(wèn)題變少了。但他又有哪些不足呢
- 不支持隨機(jī)訪問(wèn)
- 排序的效率慢，庫(kù)中的sort用的是歸并排序–>快排需要三數(shù)取中，對(duì)于鏈表來(lái)說(shuō)實(shí)現(xiàn)出來(lái)效率也低，所以當(dāng)鏈表的元素需要進(jìn)行排序的時(shí)候，我們通常也都會(huì)拷貝到vector當(dāng)中，再用vector當(dāng)中的排序。
- 同理鏈表的逆置效率也不高！
三、迭代器的分類
迭代器從功能角度來(lái)看的話分為：const迭代器/普通迭代器 + 正反向。
從容器底層結(jié)構(gòu)角度分為：?jiǎn)蜗?，雙向，隨機(jī)。
- 單向： 單鏈表迭代器（forward_list）/哈希表迭代器；這些只支持單向++；
- 雙向： 雙鏈表迭代器/map迭代器；這些支持的++/- -操作；
- 隨機(jī)迭代器： string/vector/deque；這些是支持++/- -/+/-操作的，類似原生指針一般。
我們來(lái)看一下部分函數(shù)的，比如sort當(dāng)中的模板參數(shù)寫成RandomAccessIterator，就是想要明示使用者他這里需要的是一個(gè)隨機(jī)的迭代器，在它的底層會(huì)調(diào)用到迭代器的+操作，所以這個(gè)時(shí)候如果你傳的是一個(gè)雙向或者單向的迭代器就不行了?。?/p>
//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);
比如說(shuō)reverse函數(shù)聲明，它的模板參數(shù)是BidirectionalIterator，也就是需要一個(gè)支持雙向的迭代器，這個(gè)時(shí)候其實(shí)我們就可以傳隨機(jī)迭代器和雙向迭代器，從上面的迭代器支持的操作可以看到，隨機(jī)迭代器是支持雙向迭代器的所有操作的。
同理，如果是一個(gè)需要單向迭代器的地方，我們就可以傳一個(gè)雙向，隨機(jī)，單向迭代器了！！
std::reverse template <class BidirectionalIterator> void reverse (BidirectionalIterator first, BidirectionalIterator last);
從stl3.0當(dāng)中的stl_iterator.h，我們可以看出當(dāng)中的繼承關(guān)系。這個(gè)我們之后再講。
注意：difference_type為兩個(gè)迭代器之間的距離。類型ptrdiff_t為無(wú)符號(hào)整形。
3.x std::find的一個(gè)報(bào)錯(cuò)
當(dāng)我們實(shí)現(xiàn)了自己的數(shù)據(jù)結(jié)構(gòu)，如list，我們?nèi)绻脦?kù)里的std：find查找我們實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)當(dāng)中的數(shù)據(jù)會(huì)報(bào)錯(cuò)。博主的測(cè)試版本為vs2013，在其他版本可能不做檢查，不會(huì)報(bào)錯(cuò)。
void test_list()
{
list<int> l;
l.push_back(5);
list<int>::iterator it = std::find(l.begin(), l.end(), 5);
}
報(bào)錯(cuò)：這里的報(bào)錯(cuò)說(shuō)的是iterator_category不在我們的迭代器當(dāng)中，這個(gè)是對(duì)我們迭代器類型的一個(gè)檢查。
stl_list.h當(dāng)中為迭代器添加了如下聲明來(lái)解決這個(gè)問(wèn)題。
解決方案： 我們可以用stl3.0版本下stl_list.h當(dāng)中的迭代器的聲明。也可以用release版本下，都是可以跑過(guò)的。
typedef bidirectional_iterator_tag iterator_category; typedef T value_type; typedef Ptr pointer; typedef Ref reference; typedef ptrdiff_t difference_type;
總結(jié)
list的講解就到這里啦，看到這里不妨一鍵三連。
到此這篇關(guān)于C++數(shù)據(jù)結(jié)構(gòu)之list詳解的文章就介紹到這了,更多相關(guān)C++ list 內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Qt數(shù)據(jù)庫(kù)應(yīng)用之實(shí)現(xiàn)圖片轉(zhuǎn)pdf
這篇文章主要為大家詳細(xì)介紹了如何利用Qt實(shí)現(xiàn)圖片轉(zhuǎn)pdf功能，文中的示例代碼講解詳細(xì)，對(duì)我們學(xué)習(xí)或工作有一定參考價(jià)值，需要的可以了解一下2022-06-06
C語(yǔ)言關(guān)鍵字const和指針的結(jié)合使用
這篇文章主要介紹了C語(yǔ)言關(guān)鍵字const和指針的結(jié)合,本文給大家介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-02-02
這篇文章主要介紹了C語(yǔ)言之system函數(shù)案例詳解,本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
sizeof操作符以字節(jié)形式給出了其操作數(shù)的存儲(chǔ)大小2013-04-04
要搞清一個(gè)指針需要搞清指針的四方面的內(nèi)容：指針的類型，指針?biāo)赶虻念愋?，指針的值或者叫指針?biāo)赶虻膬?nèi)存區(qū)，還有指針本身所占據(jù)的內(nèi)存區(qū)2013-09-09
這篇文章主要介紹了 C語(yǔ)言宏定義使用實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下，希望能夠給你帶來(lái)幫助2021-09-09
這篇文章主要為大家詳細(xì)介紹了利用mmap實(shí)現(xiàn)文件拷貝功能，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-10-10
C語(yǔ)言中的char是用于聲明單個(gè)字符的關(guān)鍵字,這篇文章主要給大家介紹了關(guān)于C語(yǔ)言char類型中存儲(chǔ)的相關(guān)資料,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-01-01
下面小編就為大家分享一篇C++代碼實(shí)現(xiàn)鏈隊(duì)列的示例，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧，希望能夠給你帶來(lái)幫助2021-09-09
C++ 中"priority_queue" 優(yōu)先級(jí)隊(duì)列實(shí)例詳解
這篇文章主要介紹了C++ 中"priority_queue" 優(yōu)先級(jí)隊(duì)列實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下2017-04-04