??前言
? ? ? ? 大家好！，今天為大家?guī)淼囊黄┛褪顷P(guān)于STL中的list，內(nèi)容主要包括list的介紹使用、list的模擬實(shí)現(xiàn)。以及l(fā)ist與vector的對比。
正文
list的介紹和使用
? ? ? ? 首先，讓我們看看list的文檔介紹：
- list是可以在常數(shù)范圍內(nèi)在任意位置進(jìn)行插入和刪除的序列式容器，并且該容器可以前后雙向迭代。
- list的底層是雙向鏈表結(jié)構(gòu)，雙向鏈表中每個(gè)元素存儲(chǔ)在互不相關(guān)的獨(dú)立節(jié)點(diǎn)中，在節(jié)點(diǎn)中通過指針指向其前一個(gè)元素和后一個(gè)元素。
- list與forward_list非常相似：最主要的不同在于forward_list是單鏈表，只能朝前迭代，已讓其更簡單高效。
- 與其他的序列式容器相比(array，vector，deque)，list通常在任意位置進(jìn)行插入、移除元素的執(zhí)行效率更好。
- 與其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的隨機(jī)訪問，比如：要訪問list的第6個(gè)元素，必須從已知的位置(比如頭部或者尾部)迭代到該位置，在這段位置上迭代需要線性的時(shí)間開銷；list還需要一些額外的空間，以保存每個(gè)節(jié)點(diǎn)的相關(guān)聯(lián)信息(對于存儲(chǔ)類型較小元素的大list來說這可能是一個(gè)重要的因素)
? ? ? ? 官方網(wǎng)站list的文檔介紹如下：
list - C++ Reference (cplusplus.com)https://legacy.cplusplus.com/reference/list/list/?kw=list? ? ? ? list的簡單使用在我們學(xué)會(huì)了vector的使用之后只要多看看list的文檔并多加使用就可以很熟悉，因此在這里就不多講了。
? ? ? ? 需要提一提的是，由于存儲(chǔ)在其中的元素的內(nèi)存并不是連續(xù)的，list并不支持隨機(jī)訪問，也沒有提供重載方括號。并且因此它并不適合算法庫中的sort()和reverse()，于是在我們想要對list進(jìn)行排序或者逆置的時(shí)候，應(yīng)該使用list自帶的接口，它們的名字與算法庫中的一樣。
? ? ? ? 除此之外，使用list時(shí)也可能遇到迭代器失效的問題，這時(shí)候我們需要重新為迭代器賦值來解決這個(gè)問題。
list的模擬實(shí)現(xiàn)
? ? ? ? list的模擬實(shí)現(xiàn)分為三個(gè)部分，分別為：list的節(jié)點(diǎn)、list的迭代器、list本體。
list_node的模擬實(shí)現(xiàn)
? ? ? ? 首先我們模擬實(shí)現(xiàn)list的節(jié)點(diǎn)，雙向鏈表需要節(jié)點(diǎn)具有前后兩個(gè)指針：
template<typename T>
struct list_node
{
// 我們初學(xué)類模板時(shí)常常會(huì)忘記寫<T>
// 這里需要注意，模板名帶上尖括號之后才會(huì)成為類型名
list_node<T>* _prev;
list_node<T>* _next;
T _val;
list_node<T>(const T& x = T())
:_prev(nullptr)
,_next(nullptr)
,_val(x)
{}
};list迭代器的模擬實(shí)現(xiàn)
? ? ? ? 然后我們要接著模擬實(shí)現(xiàn)list的迭代器，這里我們有一個(gè)很重要的設(shè)計(jì)，就是設(shè)置多個(gè)模板參數(shù)，對應(yīng)數(shù)據(jù)類型，數(shù)據(jù)的引用類型，數(shù)據(jù)的指針類型。
? ? ? ? 設(shè)計(jì)的思路：當(dāng)我們設(shè)計(jì)迭代器類的時(shí)候，不僅要考慮普通的迭代器，還要考慮const迭代器，它并不是簡單的在迭代器類聲明對象前加上const關(guān)鍵字就可以。因?yàn)槲覀兊腸onst迭代器并不意味著我們不能改動(dòng)這個(gè)迭代器對象本身，而是我們不能改動(dòng)此迭代器所指向的數(shù)據(jù)。因此我們需要對迭代器類的一些接口的返回值類型做改動(dòng)，也就是 * 號和 -> ，原因是這兩個(gè)重載運(yùn)算符會(huì)提供操作數(shù)據(jù)的方式。這種設(shè)計(jì)很好的減少了代碼的冗余，使我們不用再另寫一份const迭代器。
? ? ? ? 除此之外，迭代器實(shí)現(xiàn)中比較獨(dú)特的一點(diǎn)就是->運(yùn)算符的重載，我們可以看到這里的運(yùn)算符重載返回值為節(jié)點(diǎn)值的地址，那么我們獲得了節(jié)點(diǎn)數(shù)據(jù)的地址之后繼續(xù)要訪問節(jié)點(diǎn)值的成員，應(yīng)該要再使用一次->運(yùn)算符，那么在具體應(yīng)用中我們就需要使用兩個(gè)箭頭，也就是 iterator->->member ，但是這不符合我們使用->運(yùn)算符的習(xí)慣，于是編譯器就為我們簡化了一下，只要使用一次箭頭，編譯器自己會(huì)正確識別這樣的寫法。
template<typename T, typename Ref, typename Ptr>
struct _list_iterator
{
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)
{
_node = _node->_next;
return _node->_prev;
}
self& operator--()
{
_node = _node->_prev;
return *this;
}
self operator--(int)
{
_node = _node->_prev;
return _node->_next;
}
bool operator!=(const self& it) const
{
return _node != it._node;
}
bool operator==(const self& it) const
{
return _node == it._node;
}
};
? ? ? ? ? ? ? ?除了正向迭代器之外，我們還有一個(gè)反向迭代器，反向迭代器的使用規(guī)則與正向迭代器完全相反，如果我們直接重新定義一個(gè)反向迭代器的類模板，那么我們就需要為每一種迭代器都再寫一份反向迭代器，這樣代碼會(huì)非常的冗余。于是這里就引出了一個(gè)新的概念——適配器模式。
? ? ? ? 由于反向迭代器的規(guī)則與迭代器完全相反，反向迭代器的許多地方其實(shí)是可以復(fù)用對應(yīng)正向迭代器本身的接口。那么我們就將迭代器類型作為一個(gè)模板參數(shù)傳入，然后在反向迭代器內(nèi)部創(chuàng)建一個(gè)正向迭代器，之后就可以直接對其進(jìn)行相反的操作，這樣我們就得到了一個(gè)可以復(fù)用的反向迭代器模板。代碼如下：
template<class Iterator, class Ref, class Ptr>
struct Reverse_iterator
{
typedef Reverse_iterator<Iterator, Ref, Ptr> self;
Reverse_iterator(Iterator it)
:_it(it)
{}
Ref operator*()
{
return *_it;
}
Ptr operator->()
{
return &_it->_node->_val;
}
self& operator++()
{
return --_it;
}
self operator++(int)
{
return _it--;
}
self& operator--()
{
return ++_it;
}
self operator--(int)
{
return _it++;
}
bool operator!=(const self& rit) const
{
return _it != rit._it;
}
bool operator==(const self& rit) const
{
return _it == rit._it;
}
private:
Iterator _it;
};list本身的實(shí)現(xiàn)
? ? ? ? list本身的實(shí)現(xiàn)非常簡單，我們之前在數(shù)據(jù)結(jié)構(gòu)時(shí)期已經(jīng)學(xué)過了鏈表的相關(guān)知識，寫個(gè)雙向循環(huán)鏈表應(yīng)該是不在話下。簡單代碼如下：
template<typename T>
class list
{
typedef list_node<T> Node;
public:
typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;
typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;
reverse_iterator rbegin()
{
return (iterator)_head->_prev;
}
reverse_iterator rend()
{
return (iterator)_head;
}
iterator begin()
{
return _head->_next;
}
iterator end()
{
return _head;
}
const_iterator begin() const
{
return _head->_next;
}
const_iterator end() const
{
return _head;
}
list<T>()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
list<T>(const list<T>& lt)
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
for (auto& x : lt)
{
push_back(x);
}
}
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
// 復(fù)用insert的代碼
void push_back(const T& x)
{
//Node* tail = _head->_prev;
//Node* newnode = new Node(x);
//newnode->_next = tail->_next;
//newnode->_prev = tail;
//tail->_next = newnode;
//_head->_prev = newnode;
//_size++;
insert(end(), x);
}
// 復(fù)用erase的代碼
void pop_back()
{
//Node* tail = _head->_prev;
//Node* nexttail = tail->_prev;
//_head->_prev = nexttail;
//nexttail->_next = _head;
//delete tail;
//_size--;
erase(--end());
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_front()
{
erase(begin());
}
// pos之前位置插入
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(x);
newnode->_prev = prev;
newnode->_next = cur;
prev->_next = newnode;
cur->_prev = newnode;
_size++;
return newnode;
}
iterator erase(iterator pos)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
_size--;
return next;
}
size_t size()
{
return _size;
}
void clear()
{
auto it = begin();
while (it != end())
{
it = erase(it);
}
}
~list<T>()
{
clear();
delete _head;
_head = nullptr;
}
private:
Node* _head;
size_t _size = 0;
};list和vector的對比
? ? ? ? list和vector的底層數(shù)據(jù)結(jié)構(gòu)分別是鏈表和數(shù)組，它們的區(qū)別也就是鏈表與數(shù)組的區(qū)別。它們之間的不同點(diǎn)如下：
- list的迭代器不支持隨機(jī)訪問和加減等操作，但是vector的迭代器支持
- list的內(nèi)存空間不是連續(xù)的，而vector的內(nèi)存空間是連續(xù)的
- list在中間和開頭插入刪除的效率要比vector高得多
- list的查詢效率較低
? ? ? ? 總的來說，這兩種容器各有優(yōu)缺點(diǎn)，我們要根據(jù)使用場景進(jìn)行靈活選擇。文章來源：http://www.zghlxwxcb.cn/news/detail-691992.html
??結(jié)語
? ? ? ? ok，那么這篇拖了許久的博客也終于是寫完了，臨近開學(xué)，希望大家開學(xué)快樂呀！文章來源地址http://www.zghlxwxcb.cn/news/detail-691992.html
到了這里，關(guān)于【C++】學(xué)習(xí)STL中的list的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
