一.list的介紹：

? 1.list是可以在常數范圍內在任意位置進行插入和刪除的序列式容器，并且該容器可以前后雙向迭代。

? 2.list的底層是雙向鏈表結構，帶有哨兵位的頭結點 。

? 4.由于底層是鏈表結構，list通常在任意位置進行插入，刪除元素的執行效率更好。

? 6.在list這個容器里面，是不支持[]等操作的。

list的底層：（雙向帶頭循環鏈表）

二.list的使用：

1.list的構造：

（1）empty container constructor (default constructor)：構造空的list。

list<int> mylist;

（2）?fill constructor：構造一個有n個元素的鏈表，每個元素的值都是val。

list<int> list4(10, 1);
for (auto e : list4) {cout << e << " ";
}
//如上代碼就成功構造了一個有10個1的鏈表

（3）?range constructor：使其元素數量與區間 [first,last) 內的元素數量相同，并且每個元素都是根據該區間內對應位置的元素原位構造（emplace-constructed）而成，保持相同的順序。

vector<int> t1 = { 1,2,3,4,5,6,7,8,9 };
int a[] = { 1,2,3,4 };
list<int> list2(t1.begin(), t1.end());
list<int> list3(a, a + 4);
//值得關注的是，要求傳遞的是迭代器，但是也可以傳數組的指針

（4）copy constructor (and copying with allocator)：拷貝構造。(同其他的容器一模一樣，不多介紹如何使用)

（5）暫時不介紹，后面再介紹。

（6）initializer list constructor：簡單點來說就是把想存進list的值全部用一個花括號括起來，每個值用逗號分隔開，然后用這些值構造一個list。

list<int> list1 = { 1,2,3,4,5,6,7,8,9 };

2.capacity：

其中max_size其實用的不多，這點在vector里面也一樣，上面兩個和其他容器的用法一模一樣。

3.element access:

這兩個函數返回的分別是鏈表的第一個元素和最后一個元素。

4.Modifiers:

?（挑一些特殊和重要的講不講的和其他容器使用差不多）

（1）assign：在 C++ 標準庫中，std::list?的?assign()?方法用于替換鏈表中的所有元素，支持多種賦值方式。它會清空原鏈表，再將新元素賦值給鏈表。

list<int> numbers;
numbers.assign(3, 100);

 std::vector<int> src = {1, 2, 3, 4};std::list<int> numbers;numbers.assign(src.begin(), src.end()); // 鏈表變為 {1, 2, 3, 4}

 std::list<char> chars;chars.assign({'a', 'b', 'c'}); // 鏈表變為 {'a', 'b', 'c'}

（2）emplace_front：在鏈表的首部直接構造一個新元素，跟push_front的功能差不多，但是二者的效率可能會有一些不同。

（3）insert:提供了很多不同的版本：

分別舉例:

int main ()
{std::list<int> mylist;std::list<int>::iterator it;// set some initial values:for (int i=1; i<=5; ++i) mylist.push_back(i); // 1 2 3 4 5it = mylist.begin();++it;       // it points now to number 2           ^mylist.insert (it,10);                        // 1 10 2 3 4 5//在pos位置insert一個val// "it" still points to number 2                      ^mylist.insert (it,2,20);                      // 1 10 20 20 2 3 4 5//在pos位置insert指定數目的val--it;       // it points now to the second 20            ^std::vector<int> myvector (2,30);mylist.insert (it,myvector.begin(),myvector.end());// 1 10 20 30 30 20 2 3 4 5//在pos位置inset一段迭代器區間所對應的值std::cout << "mylist contains:";for (it=mylist.begin(); it!=mylist.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';return 0;
}

list里面的list由于不會擴容，所以沒有迭代器失效的問題，但是返回值也是迭代器。

（4）erase：

erase提供了兩種方式，在pos位置刪除和刪除一段迭代器區間。如同vector一樣，erase有迭代器失效的效果，所以返回的是pos位置的下一個迭代器位置。

（5）swap：交換兩個鏈表的內容：

int main() {std::list<int> a = {1, 2, 3};std::list<int> b = {4, 5};a.swap(b); // 交換 a 和 b 的內容std::cout << "a: ";for (int x : a) std::cout << x << " "; // 輸出: 4 5std::cout << "\nb: ";for (int x : b) std::cout << x << " "; // 輸出: 1 2 3
}

5.operations：

（1）splice：

?std::list?的?splice()?方法用于將一個鏈表的元素轉移到另一個鏈表中，且不會導致元素的復制或移動，而是直接修改鏈表的內部指針，因此效率極高（時間復雜度為 O (1)）。這個函數用到的地方不是很多，但是后面會有大用處。將一個鏈表的元素轉移到另一個鏈表中，另一個鏈表也可以是自己本身。

（2）remove：

??std::list?的?remove()?方法用于刪除鏈表中所有等于特定值的元素。它會遍歷整個鏈表，移除所有匹配的元素，并自動調整鏈表結構，保持元素間的連續性。需要傳遞的參數就是要刪除的值val

? remove_if就是和上面的作用差不多，但是需要滿足一定的條件。

（3）unique：

std::list?的?unique()?方法用于移除鏈表中相鄰的重復元素，只保留其中一個。它會遍歷鏈表，將相鄰且值相等的元素壓縮為單個元素，從而使鏈表中的元素唯一（僅針對相鄰元素）。

（4）merge：

std::list?的?merge()?方法用于將另一個有序鏈表合并到當前鏈表中，合并后當前鏈表仍保持有序。使用這個函數的前提是，兩個鏈表必須已經按相同順序排序。

int main() {std::list<int> a = {1, 3, 5};std::list<int> b = {2, 4, 6};// 將 b 合并到 a 中，a 仍保持有序a.merge(b);// 輸出: 1 2 3 4 5 6for (int num : a) {std::cout << num << " ";}// b 變為空鏈表std::cout << "\nb size: " << b.size(); // 輸出: 0
}

合并之后被合并的那個鏈表會變成空的鏈表。

（5）sort：

由于迭代器類型的原因，sort不能使用<algorithm>頭文件里面的sort，所以單獨寫了一個sort，但是在list里面的這個sort是歸并排序，在進行大量數據排序的時候效率并沒有算法庫里面的sort效率高，因此使用的時候經常將list里面的元素放到vector里面，如何排好序后再assign回list里面。

原因在下面解釋。

（6）reverse：

不能使用算法庫里面的reverse的原因和sort一樣。

三.迭代器類型：

?迭代器有很多種，是根據容器的底層來決定的。inputiterator（輸入迭代器），forwarditerator（前向迭代器），bidirectioniterator（雙向迭代器），randmaccessiterator（隨機訪問迭代器）。

?inputiterator迭代器和forwarditerator都是只支持++，*的操作，雙向迭代器支持++，--，*的操作，隨機迭代器支持不僅支持前面所有的，還支持額外的隨機訪問，比如+n，> , <, 迭代器之間的減法等操作。

一個容器是否能使用算法庫里面的函數，需要看迭代器類型，在前面列舉的類型里面，按順序是包含關系。這是按照迭代器的功能來劃分的。

那么為什么list容器不能調用sort函數呢，list容器是雙向迭代器，而sort要求的是隨機迭代器，所以不能調用，反之，如果有一個隨機迭代器的容器，那么它是可以取使用要求是雙向迭代器的函數的。

四.補充一些知識：

---->? ?計算機的存儲體系如圖所示：

? ? ? ? ? ? ??

? ? ?->平時最關注的就是主存以及本地磁盤。

? ? ?->其中主存是帶電的，存儲速度很快，沒有電就不能存儲數據，一旦斷電，RAM （主存一般指ram，然后ram又分為dram和sram）中存儲的數據就會立即丟失，這就是為什么主存是易失性存儲器。而本地磁盤是不帶電的，沒有電它也可以存儲數據，在斷電后仍能保存數據，屬于非易失性存儲器。

? ? ->我們書寫一個順序表或者鏈表，它都是存放在主存（也就是通常說的內存）里面的，數據結構就是在內存中對數據進行管理，所以當然是在主存上的。我們對順序表，鏈表的數據進行遍歷和修改的時候，是cpu來完成的，但是cpu是不能直接訪問內存的，形象一點說，這是因為它太“快”了，而它覺得內存太慢了。這時候就有一個cpu高速緩存的概念了：? ? ??

cpu的機制是這樣的，比如說我要訪問一個指針，cpu先進緩存，如果這個指針在緩存里面，那么就叫做“命中”，這樣cpu就可以直接訪問了。如果“不命中”的情況下，內存的數據（當然不可能是內存的全部數據）會先進入緩存里面，然后再讓cpu去“命中”。在這樣的條件下就有一個緩存命中率的概念產生，對于順序表和鏈表先說結論就是順序表的緩存命中率高，而鏈表的緩存命中率低。內存在把數據給緩存的時候，假設要用的數據是4個字節，它就會從內存里面多拿連續的一部分給緩存（這是局部性原理預取相鄰的數據的效果，但是具體多取多少，這是又是硬件等多方面因素決定的）。稍微應用一下豆包的話來類比一下這個局部性原理：

由于順序表的結構優勢，使得在上述原理下“命中率”變高，雖然在鏈表的一個節點的后面會多拿一些數據，但是包含下一個節點的概率不大，所以鏈表的“命中率低”。

--------取自《深度理解計算機系統》--------。