突破編程_C++_STL教程（ list 的實戰應用）

1 std::list 的排序

1.1 基礎類型以及 std::string 類型的排序

std::list的排序可以通過調用其成員函數sort()來實現。sort()函數使用默認的比較操作符（<）對std::list中的元素進行排序。這意味著，如果元素類型定義了<操作符，std::list將使用它來比較元素。

例如，如果有一個std::list<int>，則可以這樣排序它：

#include <list>  
#include <algorithm>  int main() 
{std::list<int> myList = { 4, 2, 5, 1, 3 };myList.sort();// myList現在包含{1, 2, 3, 4, 5}  return 0;
}

如果 list 里面的元素類型沒有定義<操作符，或者需要使用自定義的比較函數，則可以通過傳遞一個比較函數或對象給sort()函數來實現。這個比較函數或對象應該接受兩個參數（即需要比較的兩個元素）并返回一個布爾值，指示第一個參數是否應該在排序后出現在第二個參數之前。

例如有一個std::list<std::string>，并且需要按照字符串的長度來排序它，可以這樣做：

#include <list>  
#include <algorithm>  
#include <string>  bool compareByStringLength(const std::string& a, const std::string& b) {return a.size() < b.size();
}int main() 
{std::list<std::string> myList = { "apple", "banana", "cherry", "date" };myList.sort(compareByStringLength);// myList現在按照字符串長度排序，可能包含{"date", "apple", "cherry", "banana"}  return 0;
}

上面代碼中定義了一個名為 compareByStringLength 的比較函數，它比較兩個字符串的長度。然后將這個函數作為參數傳遞給 sort() 函數，以按照字符串長度對 std::list 進行排序。

1.2 自定義類型的排序

如果需要對 std::list 中的自定義類型進行排序，則需要提供一個自定義的比較函數或比較對象，該函數或對象定義了如何比較兩個自定義類型的對象。這個比較函數或對象應該接受兩個參數并返回一個布爾值，用于確定第一個參數是否應該在排序后出現在第二個參數之前。

下面是一個例子，展示了如何對 std::list 中的自定義類型進行排序：

#include <list>  
#include <string>  
#include <iostream>  
#include <algorithm>  // 自定義類型  
struct Person {std::string name;int age;// 構造函數  Person(const std::string& name, int age) : name(name), age(age) {}// 為了方便輸出，重載<<操作符  friend std::ostream& operator<<(std::ostream& os, const Person& person) {os << "Name: " << person.name << ", Age: " << person.age;return os;}
};// 自定義比較函數，用于排序Person對象  
bool comparePersonByAge(const Person& a, const Person& b) {return a.age < b.age; // 按年齡升序排序  
}int main() 
{// 創建一個包含Person對象的std::list  std::list<Person> people = {{"Alice", 25},{"Bob", 20},{"Charlie", 30},{"David", 25}};// 使用自定義比較函數對people進行排序  people.sort(comparePersonByAge);// 輸出排序后的結果  for (const auto& person : people) {std::cout << person << std::endl;}return 0;
}

上面代碼的輸出為：

Name: Bob, Age: 20
Name: Alice, Age: 25
Name: David, Age: 25
Name: Charlie, Age: 30

上面代碼中定義了一個 Person 結構體，它包含 name 和 age 兩個成員。然后創建了一個 comparePersonByAge 函數，它接受兩個 Person 對象并比較它們的年齡。這個函數將用于 std::list 的 sort 成員函數來按照年齡對 Person 對象進行排序。

最后，在main函數中，創建了一個 std::list<Person>并初始化了幾個 Person 對象。然后調用 sort 成員函數并傳遞 comparePersonByAge 函數作為比較對象，從而對 people 列表進行排序。

注意：如果需要按照降序排序，可以在comparePersonByAge函數中將比較操作從<改為>。此外，如果自定義類型定義了<操作符，也可以直接使用默認的排序而不需要提供自定義比較函數。

2 std::list 的主要應用場景

以下是一些std::list的主要應用場景：

（1）頻繁插入和刪除操作： std::list 允許在序列中的任意位置進行常數時間的插入和刪除操作。這使得它非常適合需要頻繁添加或移除元素的場景，如日志記錄、任務隊列、事件處理等。

（2）雙向迭代： std::list 支持雙向迭代，這意味著可以輕松地遍歷列表，向前或向后移動。這種特性在處理需要前后關聯的數據時非常有用，如文本編輯器中的撤銷與重做操作。

（3）保持元素順序： std::list 通過鏈表結構保持元素的插入順序。這對于需要維護元素原始順序的場景（如數據庫查詢結果、事件歷史記錄等）非常有用。

（4）動態數據結構： 當數據結構的大小經常變化時，std::list 是一個很好的選擇。與基于數組的容器（如 std::vector）相比，std::list 在插入和刪除元素時不需要移動大量數據，因此性能更高。

（5）內存管理： 在某些情況下，可能希望更好地控制內存使用。std::list 允許管理每個元素的內存分配，這在處理大量數據或需要精確控制內存使用的場景中非常有用。

（6）與線程安全容器結合使用： std::list 可以與其他線程安全容器（如 std::list<std::unique_ptr<T>>）結合使用，以在多線程環境中安全地管理資源。

2.1 std::list 應用于任務隊列

std::list 在任務隊列的應用場景中特別有用，特別是當需要頻繁地在隊列的任意位置插入和刪除任務時。由于 std::list 的雙向鏈表結構，它支持在常數時間內完成這些操作，這使得它成為處理動態任務隊列的理想選擇。

下面是一個簡單的示例，展示了如何使用 std::list 來實現一個任務隊列：

#include <iostream>  
#include <list>  
#include <thread>  
#include <chrono>  
#include <mutex>  
#include <condition_variable>  // 任務類型定義  
struct Task {Task() {}Task(int id, std::function<void()> work) : id(id), work(work) {}int id;std::function<void()> work;
};// 任務隊列類  
class TaskQueue 
{
public:// 向隊列中添加任務  void pushTask(Task task) {std::lock_guard<std::mutex> lock(mtx);tasks.push_back(task);condVar.notify_one(); // 通知等待的線程有新任務到來  }// 從隊列中取出任務并執行  bool popTask(Task& task) {std::unique_lock<std::mutex> lock(mtx);condVar.wait(lock, [this] { return !tasks.empty(); }); // 等待直到有任務到來  task = tasks.front();tasks.pop_front(); // 移除并返回隊列前端的任務  return true;}// 檢查隊列是否為空  bool isEmpty() {std::lock_guard<std::mutex> lock(mtx);return tasks.empty();}
private:std::list<Task> tasks;std::mutex mtx;std::condition_variable condVar;};// 模擬任務執行的函數  
void simulateWork(int taskId) {std::cout << "Executing task " << taskId << std::endl;std::this_thread::sleep_for(std::chrono::seconds(1)); // 模擬耗時任務  
}int main() 
{TaskQueue taskQueue;// 啟動生產者線程，向隊列中添加任務  std::thread producer([&taskQueue]() {for (int i = 0; i < 10; ++i) {taskQueue.pushTask(Task(i, std::bind(simulateWork, i)));std::this_thread::sleep_for(std::chrono::milliseconds(500)); // 模擬任務生成間隔  }});// 啟動消費者線程，從隊列中取出并執行任務  std::thread consumer([&taskQueue]() {Task task;while (taskQueue.popTask(task)) {task.work(); // 執行任務  }});// 等待生產者和消費者線程完成  producer.join();consumer.join();return 0;
}

上面代碼的輸出為：

Executing task 0
Executing task 1
Executing task 2
Executing task 3
Executing task 4
Executing task 5
Executing task 6
Executing task 7
Executing task 8
Executing task 9

上面代碼中定義了一個 Task 結構體來表示任務，它包含一個標識符和一個工作函數。TaskQueue 類提供了 pushTask 方法來向隊列中添加任務，以及 popTask 方法來從隊列中取出并執行任務。TaskQueue 還使用了一個互斥鎖和一個條件變量來確保線程安全，并允許消費者在任務可用時被喚醒。

simulateWork 函數模擬了任務的執行過程，它只是打印任務 ID 并休眠一秒鐘來模擬耗時任務。在 main 函數中，創建了一個生產者線程來生成任務，并將其添加到任務隊列中，同時還創建了一個消費者線程來從隊列中取出任務并執行。

2.2 std::list 應用于文本編輯器中的撤銷與重做操作

在文本編輯器的撤銷與重做操作中，使用 std::list 的雙向迭代特性可以使得在向前和向后遍歷編輯歷史時都非常高效。下面是一個示例，該示例演示了如何使用 std::list 來管理編輯歷史，并支持撤銷和重做操作，同時體現了雙向迭代在處理這種需要前后關聯的數據時的優勢。

#include <iostream>  
#include <list>  
#include <string>  // 文本編輯器類  
class TextEditor 
{
public:// 構造函數  TextEditor() : currentPos(history.end()) {}// 輸入文本  void inputText(const std::string& text) {// 添加新文本到歷史記錄  history.push_back(text);// 更新當前位置迭代器  currentPos = std::prev(history.end());}// 撤銷操作  void undo() {if (currentPos != history.begin()) {// 如果不是第一次編輯，則向前移動迭代器  --currentPos;}}// 重做操作  void redo() {if (std::next(currentPos) != history.end()) {// 如果還有后續的歷史記錄，則向后移動迭代器  ++currentPos;}}// 獲取當前文本  std::string getCurrentText() const {if (currentPos != history.end()) {return *currentPos;}return "";}// 顯示編輯歷史  void showHistory() const {for (const auto& text : history) {std::cout << text << std::endl;}}private:std::list<std::string> history; // 存儲編輯歷史的列表  std::list<std::string>::iterator currentPos; // 當前編輯位置的迭代器  
};int main() {TextEditor editor;// 用戶輸入一些文本  editor.inputText("Initial text.");editor.inputText("Edited text.");editor.inputText("Edited again.");// 顯示編輯歷史  editor.showHistory();// 執行撤銷操作  editor.undo();std::cout << "After undo: " << editor.getCurrentText() << std::endl;// 執行重做操作  editor.redo();std::cout << "After redo: " << editor.getCurrentText() << std::endl;// 再次顯示編輯歷史來驗證狀態  editor.showHistory();return 0;
}

上面代碼的輸出為：

Initial text.
Edited text.
Edited again.
After undo: Edited text.
After redo: Edited again.
Initial text.
Edited text.
Edited again.

在上面代碼中，TextEditor 類使用 std::list 來維護編輯歷史。每次調用 inputText 方法時，它都會清除當前位置之后的所有歷史記錄，并將新文本添加到歷史列表的末尾。撤銷操作通過向前移動迭代器并刪除當前元素來實現，而重做操作則通過向后移動迭代器來實現。由于 std::list 支持雙向迭代，因此這些操作都是常數時間復雜度的，非常高效。

3 std::list 的擴展與自定義

在大多數情況下，不需要對 std::list 做擴展與自定義，因為它已經提供了非常完整的功能集。然而，如果需要更高級的功能或定制行為，則可以考慮以下幾種方法：

（1）繼承自 std::list：
可以通過繼承 std::list 并添加自定義成員函數來擴展其功能。然而，這通常不是推薦的做法，因為繼承標準庫組件可能導致未定義的行為或意外的副作用。標準庫組件通常設計為不可繼承的，并且它們的內部實現可能會在不同版本的編譯器或標準庫中發生變化。

（2）使用適配器模式：
適配器模式允許將一個類的接口轉換為另一個類的接口，而不需要修改原始類。可以創建一個適配器類，它封裝了一個 std::list 實例，并提供了自定義的接口。這樣，可以在不修改 std::list 本身的情況下添加新功能。

（3）自定義迭代器：
std::list 允許使用自定義迭代器。開發人員可以創建自己的迭代器類，該類提供對 std::list 元素的訪問，并在迭代過程中添加自定義邏輯。然后，可以將這些自定義迭代器傳遞給 std::list 的成員函數，以在遍歷元素時應用自定義行為。

（4）使用代理類：
代理類是一個設計模式，它允許一個類代表另一個類的功能，并在調用功能時添加額外的邏輯。你可以創建一個代理類，它封裝了一個 std::list 實例，并提供與 std::list 相同的接口。在代理類的實現中，可以在調用 std::list 的方法之前或之后添加自定義邏輯：

（5）自定義分配器：
std::list 使用分配器來管理內存。可以通過提供一個自定義的分配器來定制 std::list 的內存分配行為。自定義分配器可以允許你控制內存的分配策略，例如使用內存池、共享內存或其他高級內存管理技術。

4 實現一個簡單的 std::list 容器

如下是一個一個簡化的 std::list 容器的實現，僅包含基本的構造函數、析構函數、插入和遍歷功能：

#include <iostream>  template <typename T>
class MyList 
{
public:struct Node {T data;Node* next;Node* prev;Node(const T& value) : data(value), next(nullptr), prev(nullptr) {}};MyList() : head(nullptr), tail(nullptr) {}~MyList() {clear();}void push_back(const T& value) {Node* newNode = new Node(value);if (head == nullptr) {head = newNode;tail = newNode;}else {tail->next = newNode;newNode->prev = tail;tail = newNode;}}void push_front(const T& value) {Node* newNode = new Node(value);if (head == nullptr) {head = newNode;tail = newNode;}else {newNode->next = head;head->prev = newNode;head = newNode;}}void clear() {Node* current = head;while (current != nullptr) {Node* next = current->next;delete current;current = next;}head = nullptr;tail = nullptr;}void display() const {Node* current = head;while (current != nullptr) {std::cout << current->data << " ";current = current->next;}std::cout << std::endl;}private:Node* head;Node* tail;
};int main() 
{MyList<int> myList;myList.push_back(10);myList.push_back(20);myList.push_front(5);myList.display();myList.clear();return 0;
}

上面代碼的輸出為：

5 10 20

這個簡化的 MyList 類包含了一個內部的Node結構，用于存儲數據以及指向下一個和上一個節點的指針。MyList 類提供了 push_back 和 push_front 方法用于在列表的末尾和開頭插入元素，clear 方法用于刪除所有元素，以及 display 方法用于遍歷并打印列表中的所有元素。