本篇基于https://cplusplus.com/reference/list/list/講解

認識

list是一個帶頭結點的雙向循環鏈表

翻譯總結：

1. 序列容器：list是一種序列容器，允許在序列的任何位置進行常數時間的插入和刪除操作。
2. 雙向迭代：list支持雙向迭代，即可以向前和向后遍歷元素。
3. 雙鏈表實現：list容器內部通過雙鏈表實現。每個元素都包含指向前一個元素和后一個元素的鏈接。
4. 非連續存儲：與數組或vector不同，list中的元素可以存儲在不同的、不連續的內存位置。
5. 內存開銷：由于需要額外的內存來存儲每個元素的鏈接信息，list相對于數組或vector會消耗更多的內存。
6. 與forward_list的區別：list與forward_list相似，但forward_list是單鏈表，只能單向迭代，而list是雙鏈表，可以雙向迭代。
7. 插入和刪除性能：與其他標準序列容器（如array、vector和deque）相比，list在已知迭代器位置的容器內插入、提取和移動元素時表現更好，尤其是在需要頻繁修改序列內容的情況下。
8. 訪問性能：與array、vector和deque相比，list的主要缺點是缺乏通過位置直接訪問元素的能力。訪問特定位置的元素需要從已知位置（如序列的開始或結束）開始迭代，這需要線性時間。
9. 適用場景：list適用于需要頻繁在序列中間插入和刪除元素的場景，以及需要雙向迭代的場景。對于需要頻繁訪問特定位置元素的場景，list可能不是最佳選擇。

接口

在string、vector的基礎上不作過多說明，僅強調差異的內容

遍歷

由于底層不是數組，由其訪問性能得知（ 訪問性能：與array、vector和deque相比，list的主要缺點是缺乏通過位置直接訪問元素的能力。訪問特定位置的元素需要從已知位置（如序列的開始或結束）開始迭代，這需要線性時間。）
不再支持operator[]，只支持迭代器遍歷和范圍for。

// list::begin
#include <iostream>
#include <list>int main ()
{int myints[] = {75,23,65,42,13};std::list<int> mylist (myints,myints+5);std::cout << "mylist contains:";for (std::list<int>::iterator it=mylist.begin(); it != mylist.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';return 0;
}

支持頭刪、頭插

string、vector這兩個底層是數組的結構進行頭刪會導致大量的數據挪動，所以盡量避免頭插頭刪，只在必要時使用insert實現，但對于list，不會產生大量挪動消耗，因此有單獨的頭插頭刪函數。

容量操作

沒有reserve，因為list是一個一個結點開辟、一個一個結點刪除的

額外增加的鏈表相關接口

remove 刪除特定的值

注意其與erase的區別

// remove from list
#include <iostream>
#include <list>int main ()
{int myints[]= {17,89,7,14};std::list<int> mylist (myints,myints+4);mylist.remove(89);std::cout << "mylist contains:";for (std::list<int>::iterator it=mylist.begin(); it!=mylist.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';return 0;
}

remove_if 條件刪除

merge 歸并

兩個有序list合并以后仍然有序

（1）void merge(list<T>& x);
（2）使用自定義比較函數：void merge(list<T>& x, Compare comp);
這里，x 是要合并到當前列表的另一個列表，comp 是一個自定義的比較函數，它接受兩個參數并返回一個布爾值，指示第一個參數是否應該在第二個參數之前。

#include <iostream>
#include <list>// 自定義的比較函數
bool mycomparison (double first, double second)
{ return ( int(first)<int(second) ); }int main ()
{std::list<double> first, second;first.push_back (3.1);first.push_back (2.2);first.push_back (2.9);second.push_back (3.7);second.push_back (7.1);second.push_back (1.4);//先讓兩個列表是有序的first.sort();second.sort();
//（1）first.merge(second);// (second is now empty)合并后second變為空second.push_back (2.1);
//（2）first.merge(second,mycomparison);std::cout << "first contains:";for (std::list<double>::iterator it=first.begin(); it!=first.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';return 0;
}

unique 去重

前提是有序的list！！原因和去重函數的底層實現有關

// list::unique
#include <iostream>
#include <cmath>
#include <list>// a binary predicate implemented as a function:
bool same_integral_part (double first, double second)
{ return ( int(first)==int(second) ); }// a binary predicate implemented as a class:
struct is_near {bool operator() (double first, double second){ return (fabs(first-second)<5.0); }
};int main ()
{double mydoubles[]={ 12.15,  2.72, 73.0,  12.77,  3.14,12.77, 73.35, 72.25, 15.3,  72.25 };std::list<double> mylist (mydoubles,mydoubles+10);mylist.sort();             //  2.72,  3.14, 12.15, 12.77, 12.77,// 15.3,  72.25, 72.25, 73.0,  73.35mylist.unique();           //  2.72,  3.14, 12.15, 12.77// 15.3,  72.25, 73.0,  73.35mylist.unique (same_integral_part);  //  2.72,  3.14, 12.15// 15.3,  72.25, 73.0mylist.unique (is_near());           //  2.72, 12.15, 72.25std::cout << "mylist contains:";for (std::list<double>::iterator it=mylist.begin(); it!=mylist.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';return 0;
}

sort

默認排升序

• 為什么標準庫里有sort，且vector都沒有單獨實現sort，list卻要單獨實現？

1. 迭代器按功能分類為單向、雙向、隨機迭代器，分類由容器的底層結構決定，底層連續存儲的，更好支持加減
2. 三種迭代器有兼容關系：要求單向，可以用雙向和隨機，要求雙向，可以用隨機。
   包含大小：隨機>雙向>單向
3. 算法的迭代器類型參數名字，暗示了其需要的迭代器類型要求
   std::sort需要隨機迭代器，而list的迭代器是雙向迭代器，所以list無法使用標準庫的sort
   reverse需要雙向迭代器，find需要只讀迭代器InputIterator（實際上代表單向、雙向、隨機迭代器都可以）

• 這個成員函數sort效率如何？
  效率遠不如std::sort。所以數據多的時候盡量不要使用這個sort
  當數據量為1000000時，拷貝到vector去排序再拷貝回來，vector的性能都好很多。
  

reverse 反轉

splice 粘貼

把一個鏈表中的數據轉移到另一個鏈表里去

注意list迭代器要求是雙向迭代器，無法通過begin（）+幾或-幾來控制位置

// splicing lists
#include <iostream>
#include <list>int main ()
{std::list<int> mylist1, mylist2;std::list<int>::iterator it;// set some initial values:for (int i=1; i<=4; ++i)mylist1.push_back(i);      // mylist1: 1 2 3 4for (int i=1; i<=3; ++i)mylist2.push_back(i*10);   // mylist2: 10 20 30it = mylist1.begin();++it;                         // points to 2mylist1.splice (it, mylist2); // mylist1: 1 10 20 30 2 3 4// mylist2 (empty)// "it" still points to 2 (the 5th element)mylist2.splice (mylist2.begin(),mylist1, it);// mylist1: 1 10 20 30 3 4// mylist2: 2// "it" is now invalid.it = mylist1.begin();std::advance(it,3);           // "it" points now to 30mylist1.splice ( mylist1.begin(), mylist1, it, mylist1.end());// mylist1: 30 3 4 1 10 20
//實現一個list中的元素調整————輸入該list的迭代器std::cout << "mylist1 contains:";for (it=mylist1.begin(); it!=mylist1.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';std::cout << "mylist2 contains:";for (it=mylist2.begin(); it!=mylist2.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';return 0;
}