前言

list中的接口比較多，與string和vector類(lèi)似，只需要掌握如何正確的使用，然后再去深入研究背后的原理，已達(dá)到可擴(kuò)展的能力。本文只介紹list中一些常見(jiàn)的重要接口。

注意：使用list時(shí)需要包含頭文件< list >。

一，list的介紹

1. list是可以在常數(shù)范圍內(nèi)在任意位置進(jìn)行插入和刪除的序列式容器，并且該容器可以前后雙向迭代。
2. list的底層是雙向鏈表結(jié)構(gòu)，雙向鏈表中每個(gè)元素存儲(chǔ)在互不相關(guān)的獨(dú)立節(jié)點(diǎn)中，在節(jié)點(diǎn)中通過(guò)指針指向
   其前一個(gè)元素和后一個(gè)元素。
3. list與forward_list非常相似：最主要的不同在于forward_list是單鏈表，只能朝前迭代，已讓其更簡(jiǎn)單高
   效。
4. 與其他的序列式容器相比(array，vector，deque)，list通常在任意位置進(jìn)行插入、移除元素的執(zhí)行效率
   更好。
5. 與其他序列式容器相比，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的基本使用

2.1 list的構(gòu)造

void TestList1()
{list<int> l1;                         // 構(gòu)造空的l1list<int> l2(4, 100);                 // l2中放4個(gè)值為100的元素list<int> l3(l2.begin(), l2.end());  // 用l2的[begin(), end()）左閉右開(kāi)的區(qū)間構(gòu)造l3list<int> l4(l3);                    // 用l3拷貝構(gòu)造l4// 以數(shù)組為迭代器區(qū)間構(gòu)造l5int array[] = { 16,2,77,29 };list<int> l5(array, array + sizeof(array) / sizeof(int));// 列表格式初始化C++11list<int> l6{ 1,2,3,4,5 };// 用迭代器方式打印l5中的元素list<int>::iterator it = l5.begin();while (it != l5.end()){cout << *it << " ";++it;}       cout << endl;// C++11范圍for的方式遍歷for (auto& e : l5)cout << e << " ";cout << endl;
}

2.2 list迭代器的使用

string和vector的是隨機(jī)迭代器，list的迭代器是雙向迭代器，不是隨機(jī)迭代器，所以只支持 ++ 和 - -，由于效率原因不支持 + 和 -。

// 注意：遍歷鏈表只能用迭代器和范圍for
void PrintList(const list<int>& l)
{// 注意這里調(diào)用的是list的 begin() const，返回list的const_iterator對(duì)象for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it){cout << *it << " ";// *it = 10; 編譯不通過(guò)}cout << endl;
}void TestList2()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array + sizeof(array) / sizeof(array[0]));// 使用正向迭代器正向list中的元素// list<int>::iterator it = l.begin();   // C++98中語(yǔ)法auto it = l.begin();                     // C++11之后推薦寫(xiě)法while (it != l.end()){cout << *it << " ";++it;}cout << endl;// 使用反向迭代器逆向打印list中的元素// list<int>::reverse_iterator rit = l.rbegin();auto rit = l.rbegin();while (rit != l.rend()){cout << *rit << " ";++rit;}cout << endl;
}

【注意】
1.begin與end為正向迭代器，對(duì)迭代器執(zhí)行++操作，迭代器向后移動(dòng)
2.rbegin(end)與rend(begin)為反向迭代器，對(duì)迭代器執(zhí)行++操作，迭代器向前移動(dòng)

2.3 list的頭插，頭刪，尾插和尾刪

// push_back/pop_back/push_front/pop_front
void TestList3()
{int array[] = { 1, 2, 3 };list<int> L(array, array + sizeof(array) / sizeof(array[0]));// 在list的尾部插入4，頭部插入0L.push_back(4);L.push_front(0);PrintList(L);// 刪除list尾部節(jié)點(diǎn)和頭部節(jié)點(diǎn)L.pop_back();L.pop_front();PrintList(L);
}

2.4 list的插入和刪除

/ insert /erase 
void TestList4()
{int array1[] = { 1, 2, 3 };list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));// 獲取鏈表中第二個(gè)節(jié)點(diǎn)auto pos = ++L.begin();cout << *pos << endl;// 在pos前插入值為4的元素L.insert(pos, 4);PrintList(L);// 在pos前插入5個(gè)值為5的元素L.insert(pos, 5, 5);PrintList(L);// 在pos前插入[v.begin(), v.end)區(qū)間中的元素vector<int> v{ 7, 8, 9 };L.insert(pos, v.begin(), v.end());PrintList(L);// 刪除pos位置上的元素L.erase(pos);PrintList(L);// 刪除list中[begin, end)區(qū)間中的元素，即刪除list中的所有元素L.erase(L.begin(), L.end());PrintList(L);
}

2.5 list 的 resize/swap/clear

// resize/swap/clear
void TestList5()
{// 用數(shù)組來(lái)構(gòu)造listint array1[] = { 1, 2, 3 };list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));PrintList(l1);// 交換l1和l2中的元素list<int> l2;l1.swap(l2);PrintList(l1);PrintList(l2);// 將l2中的元素清空l2.clear();cout << l2.size() << endl;
}