list基本概念

定義

鏈表（list）是一種物理存儲單元上非連續的存儲結構，可以將數據進行鏈式存儲，數據元素的邏輯順序是通過鏈表中的指針鏈接實現的。STL中的鏈表是一個雙向循環鏈表。

結構

鏈表的組成：鏈表由一系列結點組。

結點的組成：一個是存儲數據元素的數據域，另一個是存儲下一個結點地址的指針域

雙向迭代器

由于鏈表的存儲方式并不是連續的內存空間，因此鏈表list中的迭代器只支持前移和后移，屬于雙向迭代器

優點

• 采用動態存儲分配，不會造成內存浪費和溢出
• 鏈表執行插入和刪除操作十分方便，修改指針即可，不需要移動大量元素

缺點

• 鏈表靈活，但是空間(指針域) 和 時間（遍歷）額外耗費較大

> 鏈表在每個節點都需要存儲額外的指針域，會消耗更多的內存空間。此外，由于鏈表是非連續存儲的，訪問特定位置的元素需要從頭或尾按順序遍歷鏈表，時間復雜度為O(n)，相對于向量的常數時間訪問O(1)，效率較低。

List和vector區別

存儲結構

list是一個雙向鏈表，每個節點包含一個值和前后指針；
而vector是一個動態數組，使用連續的內存塊來存儲元素。

內存管理

由于list使用動態內存分配，可以在任意位置高效地插入和刪除元素，但同時會產生額外的指針開銷；
而vector使用連續的內存塊，盡管插入和刪除操作需要移動元素，但內存訪問位置更加連續，可以提供更好的緩存性能。

迭代器穩定性

在list中，插入或刪除元素不會影響已存在的迭代器的有效性；
而在vector中，當插入或刪除元素時，可能會導致迭代器失效，需要重新獲取。

隨機訪問效率

由于vector使用連續的內存塊，可以通過索引隨機訪問元素，并具有較好的性能；
而list為了訪問指定位置的元素，需要從頭或從尾按順序遍歷鏈表，效率較低。

在插入和刪除頻繁的場景下，list可能更適合；
而在需要快速隨機訪問元素或者容器規模較大的情況下，vector可能更合適。

list構造函數——創建list容器

函數原型

• list<T> lst; //list采用采用模板類實現,對象的默認構造形式：
• list(beg,end); //構造函數將[beg, end)區間中的元素拷貝給本身。
• list(n,elem); //構造函數將n個elem拷貝給本身。
• list(const list &lst); //拷貝構造函數。
  list構造方式同其他幾個STL常用容器一致

示例

#include <list>
#include <iostream>
#include <list>int main() {// 示例1：使用默認構造函數創建空的liststd::list<int> myList1;// 示例2：使用迭代器構造函數將數組中的元素拷貝到list中int arr[] = {1, 2, 3, 4, 5};std::list<int> myList2(arr, arr + sizeof(arr) / sizeof(int));// 示例3：使用元素數量和元素值構造liststd::list<int> myList3(3, 10); // 包含三個值為10的元素// 示例4：使用拷貝構造函數創建一個副本std::list<int> myList4(myList3);// 輸出list中的元素std::cout << "myList1: ";for (const auto& element : myList1) {std::cout << element << " ";}std::cout << std::endl;std::cout << "myList2: ";for (const auto& element : myList2) {std::cout << element << " ";}std::cout << std::endl;std::cout << "myList3: ";for (const auto& element : myList3) {std::cout << element << " ";}std::cout << std::endl;std::cout << "myList4: ";for (const auto& element : myList4) {std::cout << element << " ";}std::cout << std::endl;return 0;
}

輸出
myList1:
myList2: 1 2 3 4 5
myList3: 10 10 10
myList4: 10 10 10

list 賦值和交換

函數原型

• assign(beg, end); //將[beg, end)區間中的數據拷貝賦值給本身。
• assign(n, elem); //將n個elem拷貝賦值給本身。
• list& operator=(const list &lst); //重載等號操作符
• swap(lst); //將lst與本身的元素互換。

示例：

#include <iostream>
#include <list>int main() {std::list<int> myList1 = {1, 2, 3};std::list<int> myList2 = {4, 5, 6};std::cout << "Before swap:" << std::endl;std::cout << "myList1: ";for (const auto& element : myList1) {std::cout << element << " ";}std::cout << std::endl;std::cout << "myList2: ";for (const auto& element : myList2) {std::cout << element << " ";}std::cout << std::endl;// 使用swap函數交換兩個list的元素myList1.swap(myList2);std::cout << "After swap:" << std::endl;std::cout << "myList1: ";for (const auto& element : myList1) {std::cout << element << " ";}std::cout << std::endl;std::cout << "myList2: ";for (const auto& element : myList2) {std::cout << element << " ";}std::cout << std::endl;return 0;
}

輸出
Before swap:
myList1: 1 2 3
myList2: 4 5 6
After swap:
myList1: 4 5 6
myList2: 1 2 3

list 大小操作

函數原型

• size(); //返回容器中元素的個數

• empty(); //判斷容器是否為空

• resize(num); //重新指定容器的長度為num，若容器變長，則以默認值0填充新位置。

  ? //如果容器變短，則末尾超出容器長度的元素被刪除。

• resize(num, elem); //重新指定容器的長度為num，若容器變長，則以elem值填充新位置。

  //如果容器變短，則末尾超出容器長度的元素被刪除。

示例

#include <iostream>
#include <list>int main() {std::list<int> myList = {1, 2, 3, 4, 5};// 使用size函數獲取容器中元素的個數std::cout << "Size of myList: " << myList.size() << std::endl;// 使用empty函數判斷容器是否為空if (myList.empty()) {std::cout << "myList is empty." << std::endl;} else {std::cout << "myList is not empty." << std::endl;}// 使用resize函數改變容器的長度為7，默認填充0myList.resize(7);std::cout << "myList after resize to size 7 with default value:" << std::endl;for (const auto& element : myList) {std::cout << element << " ";}std::cout << std::endl;// 使用resize函數改變容器的長度為10，使用值9填充新位置myList.resize(10, 9);std::cout << "myList after resize to size 10 with value 9:" << std::endl;for (const auto& element : myList) {std::cout << element << " ";}std::cout << std::endl;// 使用resize函數將容器的長度改為3myList.resize(3);std::cout << "myList after resize to size 3:" << std::endl;for (const auto& element : myList) {std::cout << element << " ";}std::cout << std::endl;return 0;
}

輸出
Size of myList: 5
myList is not empty.
myList after resize to size 7 with default value:
1 2 3 4 5 0 0
myList after resize to size 10 with value 9:
1 2 3 4 5 0 0 9 9 9
myList after resize to size 3:
1 2 3

在示例中，我們創建了一個list對象myList并初始化它的元素。
然后，我們使用size函數輸出容器的大小，使用empty函數判斷容器是否為空。
接著，我們使用resize函數將容器的大小分別改變為7、10和3。
當容器變大時，新位置會用默認值0或指定的值9進行填充；
當容器變小時，末尾超出容器長度的元素會被刪除。最終，我們打印出修改后的容器內容

list 插入和刪除

函數原型

• push_back(elem);//在容器尾部加入一個元素
• pop_back();//刪除容器中最后一個元素
• push_front(elem);//在容器開頭插入一個元素
• pop_front();//從容器開頭移除第一個元素
• insert(pos,elem);//在pos位置插elem元素的拷貝，返回新數據的位置。
• insert(pos,n,elem);//在pos位置插入n個elem數據，無返回值。
• insert(pos,beg,end);//在pos位置插入[beg,end)區間的數據，無返回值。
• clear();//移除容器的所有數據
• erase(beg,end);//刪除[beg,end)區間的數據，返回下一個數據的位置。
• erase(pos);//刪除pos位置的數據，返回下一個數據的位置。
• remove(elem);//刪除容器中所有與elem值匹配的元素。

注意
插入多個數據無返回值，刪除返回下一個數據位置
beg end 均為迭代器

示例

#include <iostream>
#include <list>int main() {std::list<int> myList = {1, 2, 3, 4, 5};std::cout << "Initial myList:" << std::endl;for (const auto& element : myList) {std::cout << element << " ";}std::cout << std::endl;// 在容器尾部加入一個元素myList.push_back(6);// 刪除容器中最后一個元素myList.pop_back();// 在容器開頭插入一個元素myList.push_front(0);// 從容器開頭移除第一個元素myList.pop_front();// 在指定位置插入元素的拷貝auto it = myList.begin();std::advance(it, 2);myList.insert(it, 7);// 在指定位置插入多個相同元素it = myList.begin();std::advance(it, 3);myList.insert(it, 3, 8);// 在指定位置插入另一個區間的元素std::list<int> newElements = {9, 10};it = myList.begin();std::advance(it, 4);myList.insert(it, newElements.begin(), newElements.end());std::cout << "myList after modifications:" << std::endl;for (const auto& element : myList) {std::cout << element << " ";}std::cout << std::endl;// 移除容器的所有數據myList.clear();std::cout << "myList after clear:" << std::endl;if (myList.empty()) {std::cout << "myList is empty." << std::endl;} else {std::cout << "myList is not empty." << std::endl;}return 0;
}

list 數據存取

函數原型

• front(); //返回第一個元素。
• back(); //返回最后一個元素。

?

注意

list容器的迭代器是雙向迭代器，不支持隨機訪問，沒有索引，不能跳躍訪問 ，也不可以通過[]或者at方式訪問數據

示例

#include <list>//數據存取
void test01()
{list<int>L1;L1.push_back(10);L1.push_back(20);L1.push_back(30);L1.push_back(40);//cout << L1.at(0) << endl;//錯誤 不支持at訪問數據//cout << L1[0] << endl; //錯誤  不支持[]方式訪問數據cout << "第一個元素為： " << L1.front() << endl;cout << "最后一個元素為： " << L1.back() << endl;//list容器的迭代器是雙向迭代器，不支持隨機訪問list<int>::iterator it = L1.begin();//it = it + 1;//錯誤，不可以跳躍訪問，即使是+1
}int main() {test01();system("pause");return 0;
}

list 反轉和排序

函數原型

• reverse(); //反轉鏈表
• sort(); //鏈表排序 //默認的排序規則 從小到大 升序

示例

#include <iostream>
#include <list>int main() {std::list<int> myList = {5, 2, 4, 1, 3};// 反轉鏈表myList.reverse();std::cout << "Reversed list: ";for (const auto& element : myList) {std::cout << element << " ";}std::cout << std::endl;// 鏈表排序myList.sort();std::cout << "Sorted list: ";for (const auto& element : myList) {std::cout << element << " ";}std::cout << std::endl;return 0;
}

輸出
Reversed list: 3 1 4 2 5
Sorted list: 1 2 3 4 5

高級排序——在排序規則上再進行一次邏輯規則制定

• 對于自定義數據類型，必須要指定排序規則，否則編譯器不知道如何進行排序
• 高級排序只是在排序規則上再進行一次邏輯規則制定，并不復雜

#include <iostream>
#include <vector>
#include <algorithm>struct Student {std::string name;int age;int score;
};bool compareStudents(const Student& student1, const Student& student2) {// 先按分數降序排序if (student1.score != student2.score) {return student1.score > student2.score;}// 如果分數相同，則按年齡升序排序if (student1.age != student2.age) {return student1.age < student2.age;}// 如果分數和年齡都相同，則按姓名的字典序升序排序return student1.name < student2.name;
}int main() {// 創建學生對象std::vector<Student> students = {{"Alice", 20, 90}, {"Bob", 18, 85}, {"Charlie", 19, 90}};// 使用自定義的排序規則對學生進行排序std::sort(students.begin(), students.end(), compareStudents);// 輸出排序結果for (const auto& student : students) {std::cout << "Name: " << student.name << ", Age: " << student.age << ", Score: " << student.score << std::endl;}return 0;
}

首先，我們定義了一個名為Student的結構體，包含學生的姓名、年齡和分數。
接下來，我們實現了一個名為compareStudents的自定義比較函數。
該函數根據學生的分數、年齡和姓名進行排序。
首先按照分數降序排序，如果分數相同，則按照年齡升序排序，最后按照姓名的字典序升序排序。
在主函數中，我們創建了一個存儲學生對象的vector，并初始化了幾個學生對象。
然后，我們使用std::sort函數對學生對象進行排序，傳入自定義的比較函數作為參數。
最后，我們遍歷排序后的學生對象，并輸出姓名、年齡和分數。