目錄
??前言??
?? 介紹
?? 使用
??? 構(gòu)造
??? 迭代器iterator
??? capacity
??? modifiers
??? 迭代器失效
?? 模擬實(shí)現(xiàn)
??? 迭代器的實(shí)現(xiàn)
?? 代碼展示
?? 和vector的區(qū)別
?? 總結(jié)
??前言??
? ? ? ? 歡迎收看本期【C++雜貨鋪】，本期內(nèi)容將講解STL中關(guān)于list的內(nèi)容，會(huì)分為一下幾個(gè)方面進(jìn)行講解：第一，什么是list，和其他容器的比較；第二，list的常用接口的介紹；第三，從底層除法，模擬實(shí)現(xiàn)簡(jiǎn)易版list；最后，對(duì)比和vecotr的主要區(qū)別。
? ? ? ? 以上就是本期要講解的全部?jī)?nèi)容了，講解之前需要你有數(shù)據(jù)結(jié)構(gòu)中鏈表的儲(chǔ)備知識(shí)，是為了更好的理解講解內(nèi)容。此外，模擬實(shí)現(xiàn)需要類和對(duì)象，模板等儲(chǔ)備知識(shí)，如果只是想簡(jiǎn)單使用可以只看前兩章。
? ? ? ? 如果你還沒有類和對(duì)象及模板的知識(shí)，可以閱覽下面這幾篇文章：【C++雜貨鋪】詳解類和對(duì)象 [上]-CSDN博客
【C++雜貨鋪】詳解類和對(duì)象 [中]-CSDN博客
【C++雜貨鋪】詳解類和對(duì)象 [下]-CSDN博客
【C++雜貨鋪】模板-CSDN博客
?? 介紹
? ? ? ? list是可以在常熟范圍內(nèi)在任意位置進(jìn)行插入和刪除的序列式容器，并且該容器可以前后雙向迭代。
????????list底層是雙向鏈表結(jié)構(gòu)，雙向鏈表中每個(gè)元素存儲(chǔ)在互不關(guān)聯(lián)的獨(dú)立節(jié)點(diǎn)中，在節(jié)點(diǎn)通過指針指向其前一個(gè)元素和后一個(gè)元素。
? ? ? ? 和其他的序列式容器相比（vector，array，deque），list通常在任意位置進(jìn)行插入，移動(dòng)元素的執(zhí)行效率更好。
? ? ? ? 與之相對(duì)的，list的最大缺陷是不支持在任意位置的隨機(jī)訪問。
?? 使用
? ? ? ? list接口較多，這里簡(jiǎn)單介紹一些常用的重要接口。
? ? ? ? 下面是官方文檔的鏈接，對(duì)于容器的學(xué)習(xí)還是要多看文檔的。
????????list - C++ Reference (cplusplus.com)
??? 構(gòu)造
??? 迭代器iterator
??? capacity
??? modifiers
??? 迭代器失效
? ? ? ? 迭代器失效即迭代器所指向的節(jié)點(diǎn)無效，即該節(jié)點(diǎn)被刪除。因?yàn)?strong>list底層是帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表，因此在list中進(jìn)行插入時(shí)是不會(huì)導(dǎo)致迭代器失效的，只有在刪除時(shí)才會(huì)失效，并且失效只是指向所刪除結(jié)點(diǎn)的迭代器，其他迭代器不會(huì)受到影響。
void TestListIterator1()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> l(array, array+sizeof(array)/sizeof(array[0]));
auto it = l.begin();
while (it != l.end())
{
// erase()函數(shù)執(zhí)行后，it所指向的節(jié)點(diǎn)已被刪除，因此it無效，在下一次使用it時(shí)，必須先給
其賦值
l.erase(it);
++it;
}
}
// 改正
void TestListIterator()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> l(array, array+sizeof(array)/sizeof(array[0]));
auto it = l.begin();
while (it != l.end())
{
l.erase(it++); // it = l.erase(it);
}
}?? 模擬實(shí)現(xiàn)
? ? ? ? 對(duì)于list的模擬實(shí)現(xiàn)最難實(shí)現(xiàn)的就是迭代器的實(shí)現(xiàn)。所以下面將重點(diǎn)講解迭代器內(nèi)容。
??? 迭代器的實(shí)現(xiàn)
????????迭代器就是通過模擬指針，提供一種統(tǒng)一的方法來使用容器。
? ? ? ? 對(duì)于vecotr這樣的容器，迭代器可以直接是指針，但對(duì)于list這樣的容器，不能直接使用原生指針，因?yàn)榈讓觾?nèi)存地址不是連續(xù)的。
? ? ? ? 指針++，并不能實(shí)現(xiàn)node = node->next這樣的操作。這里就要用到C++的重要組成部分了，運(yùn)算符重載和實(shí)現(xiàn)了類。通過將指針封裝成類，來實(shí)現(xiàn)運(yùn)算符重載。
? ? ? ? 這里迭代器使用三個(gè)模板參數(shù)，第一個(gè)表示數(shù)據(jù)data的類型，第二表示數(shù)據(jù)data的引用，第三個(gè)表示數(shù)據(jù)data的地址。
template<class T,class Ref,class Ptr>
struct ListIterator
{
typedef ListNode<T> Node;
typedef ListIterator<T,Ref,Ptr> iterator;
//構(gòu)造函數(shù)
ListIterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->data;
}
Ptr operator->()
{
return &_node->data;
}
//++it
iterator& operator++()
{
_node = _node->_next;
return *this;
}
iterator operator++(int)
{
iterator temp(*this);
_node = _node->_next;
return temp;
}
//--it
iterator& operator--()
{
_node = _node->_prev;
return *this;
}
iterator operator--(int)
{
iterator temp(*this);
_node = _node->_prev;
return temp;
}
// !=
bool operator!=(const iterator& it)
{
return _node != it._node;
}
bool operator==(const iterator & it)
{
return _node == it._node;
}
Node* _node;
};?? 代碼展示
? ? ? ? 下面將list的實(shí)現(xiàn)，放在exercise命名空間中。
namespace exercise
{
//節(jié)點(diǎn)類
template<class T>
struct ListNode
{
typedef ListNode<T> Node;
Node* _next;
Node* _prev;
T data;
ListNode(const T& val = T())
:_next(nullptr)
,_prev(nullptr)
,data(val)
{}
};
template<class T,class Ref,class Ptr>
struct ListIterator
{
typedef ListNode<T> Node;
typedef ListIterator<T,Ref,Ptr> iterator;
//構(gòu)造函數(shù)
ListIterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->data;
}
Ptr operator->()
{
return &_node->data;
}
//++it
iterator& operator++()
{
_node = _node->_next;
return *this;
}
iterator operator++(int)
{
iterator temp(*this);
_node = _node->_next;
return temp;
}
//--it
iterator& operator--()
{
_node = _node->_prev;
return *this;
}
iterator operator--(int)
{
iterator temp(*this);
_node = _node->_prev;
return temp;
}
// !=
bool operator!=(const iterator& it)
{
return _node != it._node;
}
bool operator==(const iterator & it)
{
return _node == it._node;
}
Node* _node;
};
//list類
template<class T>
class list
{
typedef ListNode<T> Node;
public:
typedef ListIterator<T,T&,T*> iterator;
typedef ListIterator<T,const T&,const T*> const_iterator;
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list()
{
empty_init();
}
list(const list<T>& l)
{
empty_init();
for (auto& e : l)
{
push_back(e);
}
}
void swap(list<T>& temp)
{
std::swap(_head,temp._head);
std::swap(_size, temp._size);
}
list<T>& operator=(list<T> temp)
{
swap(temp);
return *this;
}
void clear()
{
iterator it = _head->_next;
while (it != _head)
{
it = erase(it);
}
}
~list()
{
clear();
delete _head;
_head = nullptr;
_size = 0;
}
iterator begin()
{
return _head->_next;
}
iterator end()
{
return _head;
}
const_iterator begin() const
{
return _head->_next;
}
const_iterator end() const
{
return _head;
}
/*void push_back(const T& val)
{
Node* newnode = new Node(val);
Node* tail = _head->_prev;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;
tail->_next = newnode;
}*/
void push_back(const T& val)
{
insert(end(), val);
}
void insert(iterator pos, const T& val)
{
Node* newnode = new Node(val);
Node* prev = pos._node->_prev;
Node* next = pos._node;
newnode->_prev = prev;
prev->_next = newnode;
newnode->_next = next;
next->_prev = newnode;
_size++;
}
iterator erase(iterator pos)
{
Node* prev = pos._node->_prev;
Node* next = pos._node->_next;
delete pos._node;
prev->_next = next;
next->_prev = prev;
_size--;
return next;
}
void pop_back()
{
erase(--end());
}
size_t size()
{
return _size;
}
private:
Node* _head;
size_t _size;
};
}?? 和vector的區(qū)別
?? 總結(jié)
? ? ? ? 以上，就是本期【C++雜貨鋪】的主要內(nèi)容了，包含了list的介紹，list常用接口以及模擬實(shí)現(xiàn)list。
? ? ? ? 如果感覺本期內(nèi)容有幫助到你，歡迎點(diǎn)贊，收藏，關(guān)注Thanks?(?ω?)?文章來源：http://www.zghlxwxcb.cn/news/detail-851024.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-851024.html
到了這里，關(guān)于【C++雜貨鋪】詳解list容器的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
