前言：
在上期，我們學(xué)習(xí)了STL庫(kù)中的第一個(gè)容器--vector ，今天我將給大家介紹的是 庫(kù)中的另外一個(gè)容器--List。其實(shí)，有了之前學(xué)習(xí) vector 的知識(shí)，對(duì)于List 的學(xué)習(xí)成本就很低了。
目錄
（一）基本介紹
1、基本概念
2、list 與 forward_list 的比較
3、特點(diǎn)
（二）list的使用
1、list的構(gòu)造
2、?list iterator的使用
3、list capacity
4、list element access
5、list modifiers
6、list的迭代器失效
1、失效時(shí)機(jī)
2、list與vector迭代器失效對(duì)比：
1??vector
2??list
（三）list的模擬實(shí)現(xiàn)
1、代碼展示
2、注意事項(xiàng)
1??【】不能實(shí)現(xiàn)訪問(wèn)操作
2??sort()
（四）list與vector的對(duì)比
（五）總結(jié)?
（一）基本介紹
1、基本概念
- ?list 是可以在常數(shù)范圍內(nèi)在任意位置進(jìn)行插入和刪除的序列式容器，并且該容器可以前后雙向迭代。
- ?list 的底層是雙向鏈表結(jié)構(gòu)，雙向鏈表中每個(gè)元素存儲(chǔ)在互不相關(guān)的獨(dú)立節(jié)點(diǎn)中，在節(jié)點(diǎn)中通過(guò)指針指向 其前一個(gè)元素和后一個(gè)元素。
2、list 與 forward_list 的比較
list與forward_list非常相似，最主要的區(qū)別如下：
- 最主要的不同在于forward_list是單鏈表，只能朝前迭代，已讓其更簡(jiǎn)單高效。
3、特點(diǎn)
與其他的序列式容器相比(array，vector，deque)，list通常在任意位置進(jìn)行插入、移除元素的執(zhí)行效率更好。
與其他序列式容器相比，list 和 forward_list 最大的缺陷是不支持任意位置的隨機(jī)訪問(wèn)：
- 比如：要訪問(wèn)list 的第6個(gè)元素，必須從已知的位置(比如頭部或者尾部)迭代到該位置，在這段位置上迭代需要線性的時(shí)間開(kāi)銷(xiāo)；
- list還需要一些額外的空間，以保存每個(gè)節(jié)點(diǎn)的相關(guān)聯(lián)信息(對(duì)于存儲(chǔ)類(lèi)型較小元素的大list來(lái)說(shuō)這 可能是一個(gè)重要的因素)
（二）list的使用
list的文檔介紹：文檔介紹
?list中的接口比較多，此處類(lèi)似，只需要掌握如何正確的使用，然后再去深入研究背后的原理，已達(dá)到可擴(kuò)展 的能力。以下為list中一些常見(jiàn)的重要接口。
1、list的構(gòu)造
2、?list iterator的使用
此處，大家可暫時(shí)將迭代器理解成一個(gè)指針，該指針指向list中的某個(gè)節(jié)點(diǎn)。
?
- 1.?begin與end為正向迭代器，對(duì)迭代器執(zhí)行++操作，迭代器向后移動(dòng)
- 2. rbegin(end)與rend(begin)為反向迭代器，對(duì)迭代器執(zhí)行++操作，迭代器向前移動(dòng)
?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-457709.html
3、list capacity
4、list element access
?
?
5、list modifiers
- list中還有一些操作，需要用到時(shí)大家可參閱list的文檔說(shuō)明。?
6、list的迭代器失效
前面已經(jīng)跟大家說(shuō)過(guò)，此處大家可將迭代器暫時(shí)理解成類(lèi)似于指針，迭代器失效即迭代器所指向的節(jié)點(diǎn)的無(wú)效，即該節(jié)點(diǎn)被刪除了。
1、失效時(shí)機(jī)
因?yàn)閘ist的底層結(jié)構(gòu)為帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表，因此在list中進(jìn)行插入時(shí)是不會(huì)導(dǎo)致list的迭代器失效的，只有在刪除時(shí)才會(huì)失效，并且失效的只是指向被刪除節(jié)點(diǎn)的迭代器，其他迭代器不會(huì)受到影響。
???注意???
迭代器有兩種實(shí)現(xiàn)方式，具體應(yīng)根據(jù)容器底層數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)：
- 1??原生指針：比如：vector的迭代器就是原生指針；
- 2??將原生指針進(jìn)行封裝，因迭代器使用形式與指針完全相同，迭代器就是自定義類(lèi)型對(duì)原生指針的封裝，模擬指針的行為。
2、list與vector迭代器失效對(duì)比：
在C++中，當(dāng)使用STL容器中的元素并且對(duì)容器進(jìn)行修改時(shí)，可能會(huì)導(dǎo)致迭代器失效。在這種情況下，如果試圖繼續(xù)使用已經(jīng)失效的迭代器，則程序可能會(huì)產(chǎn)生未定義的行為。
1??vector
在使用vector容器時(shí)，添加或刪除元素可能會(huì)導(dǎo)致迭代器失效。
- 這是因?yàn)関ector容器內(nèi)部使用動(dòng)態(tài)數(shù)組實(shí)現(xiàn)，當(dāng)容器中的元素?cái)?shù)量超過(guò)了其內(nèi)存分配的大小時(shí)，就需要重新分配一塊更大的內(nèi)存，并將原有元素拷貝到新的內(nèi)存中；
- 此時(shí)，原有的迭代器就無(wú)法正確指向其對(duì)應(yīng)的元素，因?yàn)樵氐奈恢靡呀?jīng)改變了；
- 同樣的情況也發(fā)生在刪除元素時(shí)，因?yàn)閯h除元素后，后面的元素會(huì)向前移動(dòng)，導(dǎo)致原有的迭代器失效。
2??list
插入元素不會(huì)導(dǎo)致迭代器失效， 刪除元素時(shí)，只會(huì)導(dǎo)致當(dāng)前迭代 器失效，其他迭代器不受影響。
void Test()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> ll(array, array+sizeof(array)/sizeof(array[0]));
auto it = ll.begin();
while (it != ll.end())
{
// erase()函數(shù)執(zhí)行后，it所指向的節(jié)點(diǎn)已被刪除，因此it無(wú)效
//在下一次使用it時(shí)，必須先給其賦值
ll.erase(it);
++it;
}
}
// 改正
void Test()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> ll(array, array+sizeof(array)/sizeof(array[0]));
auto it = ll.begin();
while (it != ll.end())
{
ll.erase(it++); // it = ll.erase(it);
}
}
（三）list的模擬實(shí)現(xiàn)
要模擬實(shí)現(xiàn)list，必須要熟悉list的底層結(jié)構(gòu)以及其接口的含義，通過(guò)上面的學(xué)習(xí)以及之前對(duì)vector和string的學(xué)習(xí)，我相信大家對(duì)于這些內(nèi)容已基本掌握，現(xiàn)在我們來(lái)模擬實(shí)現(xiàn)list。
1、代碼展示
???如果大家還有不懂的，可以參考我上一篇文章：vector的基本實(shí)現(xiàn)???
- 接下來(lái)我直接給出代碼（這里實(shí)現(xiàn)的風(fēng)格跟上篇實(shí)現(xiàn)vector稍微不一樣）：
#pragma once
namespace zp
{
template<typename T>
class List {
private:
struct Node
{
T _data;
Node* _prev;
Node* _next;
Node(const T& x, Node* p = nullptr, Node* n = nullptr)
:_data(x)
, _prev(p)
, _next(n)
{}
};
public:
class Iterator
{
public:
Iterator(Node* n = nullptr)
:node(n)
{}
T& operator*()
{
return node->_data;
}
Iterator& operator++()
{
node = node->_next;
return *this;
}
Iterator operator++(int)
{
Iterator tmp = *this;
node = node->_next;
//++(*this);
return tmp;
}
Iterator& operator--()
{
node = node->_prev;
return *this;
}
Iterator operator--(int)
{
Iterator tmp = *this;
node = node->_prev;
return tmp;
}
bool operator==(const Iterator& x) const
{
return node == x.node;
}
bool operator!=(const Iterator& x) const
{
return !(*this == x);
}
private:
Node* node;
friend class List<T>;
};
public:
List()
:head(new Node(T()))
, tail(head)
{}
~List()
{
clear();
delete head;
head = nullptr;
}
void push_back(const T& x)
{
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}
Iterator begin() const
{
return head->_next;
}
Iterator end() const
{
return tail;
}
bool empty() const
{
return head->_next == tail;
}
void clear()
{
while (!empty())
{
erase(begin());
}
}
Iterator insert(Iterator it, const T& x)
{
Node* tmp = it.node;
Node* newNode = new Node(x, tmp->_prev, tmp);
tmp->_prev->_next = newNode;
tmp->_prev = newNode;
return newNode;
}
Iterator erase(Iterator pos)
{
Node* tmp = pos.node;
Iterator res(tmp->_next);
tmp->_prev->_next = tmp->_next;
tmp->_next->_prev = tmp->_prev;
delete tmp;
return res;
}
private:
Node* head;
Node* tail;
};
void print_list(const list<int>& lt)
{
list<int>::const_iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
void test_1()
{
list<int> ll;
ll.push_back(1);
ll.push_back(2);
ll.push_back(3);
ll.push_back(4);
ll.push_back(5);
list<int>::iterator it = ll.begin();
while (it != ll.end())
{
(*it) *= 2;
cout << *it << " ";
++it;
}
cout << endl;
list<int>::iterator pos = find(ll.begin(), ll.end(), 4);
if (pos != ll.end())
{
ll.insert(pos, 10);
}
for (auto& e : ll)
{
cout << e << " ";
}
cout << endl;
it = ll.begin();
++it;
ll.erase(it);
}
void test_2()
{
list<int> ll;
ll.push_back(1);
ll.push_back(2);
ll.push_back(3);
ll.push_back(4);
ll.push_back(5);
for (auto e : ll)
{
cout << e << " ";
}
cout << endl;
auto pos = ll.begin();
++pos;
ll.insert(pos, 20);
for (auto e : ll)
{
cout << e << " ";
}
cout << endl;
ll.push_back(100);
ll.push_front(1000);
for (auto e : ll)
{
cout << e << " ";
}
cout << endl;
ll.pop_back();
ll.pop_front();
for (auto e : ll)
{
cout << e << " ";
}
cout << endl;
}
void test_3()
{
list<int> ll;
ll.push_back(1);
ll.push_back(2);
ll.push_back(3);
ll.push_back(4);
ll.push_back(5);
for (auto e : ll)
{
cout << e << " ";
}
cout << endl;
ll.clear();
for (auto e : ll)
{
cout << e << " ";
}
cout << endl;
ll.push_back(0);
ll.push_back(5);
ll.push_back(10);
ll.push_back(15);
for (auto e : ll)
{
cout << e << " ";
}
cout << endl;
}
}
- 上述代碼我定義了一個(gè)List類(lèi)，其中包含了一個(gè)嵌套的Node結(jié)構(gòu)體用于表示雙向鏈表的節(jié)點(diǎn)。使用模板實(shí)現(xiàn)泛型數(shù)據(jù)類(lèi)型，可以存儲(chǔ)任意類(lèi)型的數(shù)據(jù)。List類(lèi)還包含了一個(gè)嵌套的【Iterator】類(lèi)，用于遍歷雙向鏈表。
2、注意事項(xiàng)
1??【】不能實(shí)現(xiàn)訪問(wèn)操作
前面已經(jīng)說(shuō)過(guò)list是鏈表的結(jié)果，因此大家不難理解為什么在list下【】不能訪問(wèn)元素。由于list采用的是鏈接存儲(chǔ)而不是連續(xù)存儲(chǔ)，所以本質(zhì)上它不支持下標(biāo)方式（也就是按偏移量）訪問(wèn)。
?
2??sort()
其次就是list的排序操作，我們還是對(duì)比之前學(xué)習(xí)的vector
在 C++ 中，【list 】和 【vector 】是兩種不同的數(shù)據(jù)結(jié)構(gòu)，它們都提供了 sort() 函數(shù)來(lái)對(duì)其中的元素進(jìn)行排序。但是，它們的底層實(shí)現(xiàn)不同，因此其 sort() 函數(shù)的效率也不同
①vector
- 對(duì)于
vector來(lái)說(shuō)，它是一個(gè)基于連續(xù)內(nèi)存空間的動(dòng)態(tài)數(shù)組，其元素存儲(chǔ)在連續(xù)的內(nèi)存塊中，因此可以通過(guò)指針?biāo)阈g(shù)運(yùn)算等方式快速訪問(wèn)其中的元素。 - 由于其元素是連續(xù)存儲(chǔ)的，因此對(duì)其進(jìn)行排序時(shí)可以使用標(biāo)準(zhǔn)庫(kù)提供的
std::sort()算法，該算法時(shí)間復(fù)雜度為 O(NlogN)，其中 N 為元素個(gè)數(shù)。因此，vector的sort()函數(shù)效率較高。
②list
- 而對(duì)于
list來(lái)說(shuō)，它是一個(gè)基于雙向鏈表的容器，其元素并不是連續(xù)存儲(chǔ)的，因此不能像vector那樣直接進(jìn)行指針?biāo)阈g(shù)運(yùn)算訪問(wèn)其中的元素。 - 由于其底層實(shí)現(xiàn)的原因，
list并沒(méi)有提供sort()函數(shù)，但是可以通過(guò)調(diào)用標(biāo)準(zhǔn)庫(kù)提供的std::list::sort()成員函數(shù)來(lái)對(duì)其中的元素進(jìn)行排序。 - 該函數(shù)采用的是歸并排序（Merge Sort）算法，時(shí)間復(fù)雜度為 O(NlogN)。
- 由于歸并排序需要頻繁的進(jìn)行鏈表節(jié)點(diǎn)的指針操作，因此相較于
vector的sort()函數(shù)而言，list的sort()函數(shù)效率較低。
接下來(lái)，我們通過(guò)代碼來(lái)簡(jiǎn)單的看看到底怎么樣
- 代碼一：
void test_op()
{
srand(time(0));
const int N = 1000000;
vector<int> v;
v.reserve(N);
list<int> lt2;
for (int i = 0; i < N; ++i)
{
auto e = rand();
v.push_back(e);
lt2.push_back(e);
}
int begin1 = clock();
sort(v.begin(), v.end()); //對(duì)vector進(jìn)行sort，調(diào)用的是算法里的快排
int end1 = clock();
int begin2 = clock();
lt2.sort(); //對(duì)list也進(jìn)行sort
int end2 = clock();
printf("vector sort:%d\n", end1 - begin1);
printf("list sort:%d\n", end2 - begin2);
}解釋說(shuō)明：
- 首先我們給出一個(gè)測(cè)試用例?N（我這里賦值的為100w），產(chǎn)生了100w 個(gè)隨機(jī)值；
- 其中一個(gè)放到vector里面，一個(gè)放到list里面；
- 分別對(duì)list和vector進(jìn)行sort，對(duì)比它們的性能看差別有多大
- 注意：是在release模式下進(jìn)行查看
結(jié)果如下：
?結(jié)果：
- 經(jīng)過(guò)幾次反復(fù)的驗(yàn)證，我們可以發(fā)現(xiàn)，vector的效率比list 的效率打上三四倍的樣子，如果在工程里這是一個(gè)巨大的差距
- 代碼二：
void test_op()
{
srand(time(0));
const int N = 1000000;
vector<int> v;
v.reserve(N);
list<int> lt1;
list<int> lt2;
for (int i = 0; i < N; ++i)
{
auto e = rand();
lt1.push_back(e);
lt2.push_back(e);
}
// 拷貝到vector排序，排完以后再拷貝回來(lái)
int begin1 = clock();
for (auto e : lt1)
{
v.push_back(e);
}
sort(v.begin(), v.end());
size_t i = 0;
for (auto& e : lt1)
{
e = v[i++];
}
int end1 = clock();
int begin2 = clock();
lt2.sort();
int end2 = clock();
printf("vector sort:%d\n", end1 - begin1);
printf("list sort:%d\n", end2 - begin2);
}
解釋說(shuō)明：
- 我這里給出兩個(gè)list；
- 對(duì)于給出的list1，我們先把它拷貝到vector中，排序完成之后在拷貝回來(lái)；
- 而對(duì)于list2，我們直接進(jìn)行sort排序；
- 對(duì)比上述的兩個(gè)操作，看效率如何
結(jié)果如下：
?
?結(jié)果：
- 不難發(fā)現(xiàn)，list1拷貝到vector里面在排，排序完成之后在拷貝回來(lái)都比list2要快，因此不難發(fā)現(xiàn)list下sort() 的效率較差。因此很少用，在上述實(shí)現(xiàn)中也沒(méi)有寫(xiě)。
小結(jié)
- 對(duì)于需要頻繁進(jìn)行元素訪問(wèn)操作的情況，建議使用
vector； - 而對(duì)于需要頻繁進(jìn)行元素插入、刪除和排序等操作的情況，建議使用
list。
（四）list與vector的對(duì)比
（五）總結(jié)?
到此，便是本期的全部知識(shí)內(nèi)容了，感謝大家的閱讀與支持?。?！
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-457709.html
?
到了這里，關(guān)于【C++】容器篇（二）——List的基本概述以及模擬實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
