STL 演算法
C++ 標準模板庫 (STL) 提供了一組豐富的通用演算法，這些演算法作用於元素範圍。這些演算法旨在高效且透過迭代器與各種容器類型配合使用。它們提供了強大的排序、搜尋、轉換和資料操作功能，通常比手動實作提供更優化的解決方案。本模組將這些演算法與常見的 JavaScript 陣列方法進行比較。
演算法庫概述
STL 演算法通常位於 <algorithm> 標頭中。它們是通用的，這表示它們可以與不同的資料類型和容器類型配合使用，只要提供的迭代器符合演算法的要求即可。演算法與容器的分離是 STL 的一個關鍵設計原則，促進了可重用性和靈活性。
排序演算法
排序演算法以特定順序排列元素。
std::sort
- 預設情況下，以升序排序範圍內的元素。
- 通常使用內省排序 (快速排序、堆積排序和插入排序的混合) 實現平均 O(N log N) 的複雜度。
正在加载...
std::stable_sort
- 在排序元素的同時，保留等效元素的相對順序。
- 通常使用合併排序或類似演算法，複雜度為 O(N log N)。
std::partial_sort
- 僅排序範圍的一部分，特別是前
n個元素。
搜尋演算法
搜尋演算法在範圍內尋找元素。
std::find
- 在範圍內搜尋值的第一次出現。
- 返回指向第一個匹配元素的迭代器，如果未找到則返回
last。 - 線性搜尋，O(N) 複雜度。
正在加载...
std::binary_search
- 檢查已排序範圍中是否存在元素。
- 如果找到則返回
true，否則返回false。 - 二分搜尋，O(log N) 複雜度。
std::lower_bound / std::upper_bound
lower_bound：返回指向已排序範圍中第一個不小於 (即大於或等於) 給定值的元素的迭代器。upper_bound：返回指向已排序範圍中第一個大於給定值的元素的迭代器。
修改演算法
修改演算法會更改範圍內的元素。
std::copy
- 將元素從一個範圍複製到另一個範圍。
正在加载...
std::transform
- 對範圍中的每個元素應用函式，並將結果儲存在另一個範圍中。
正在加载...
std::replace
- 將範圍中特定值的所有出現替換為另一個值。
數值演算法
數值演算法位於 <numeric> 標頭中。
std::accumulate
- 計算範圍中元素的總和，或累加應用二元運算。
正在加载...
std::inner_product
- 計算兩個範圍的內積 (對應元素乘積的總和)。
與 JavaScript 陣列方法的比較
JavaScript 的 Array.prototype 提供了許多內建方法，這些方法提供了與 STL 演算法類似的功能。但是，存在關鍵差異：
| 特性 | JavaScript 陣列方法 | C++ STL 演算法 |
|---|---|---|
| 通用性 | 透過動態類型實現 | 透過模板和迭代器實現 |
| 類型安全 | 運行時類型檢查 | 編譯時類型檢查 |
| 性能 | 通常內部優化，但動態類型/GC 帶來開銷 | 高度優化，直接記憶體存取，編譯時優化 |
| 靈活性 | 僅限於陣列 (和類似陣列的物件) | 適用於任何提供迭代器的容器 |
| 錯誤處理 | 拋出運行時錯誤 | 類型不匹配的編譯時錯誤，無效迭代器的運行時錯誤 |
演算法性能分析
STL 演算法通常經過高度優化，並提供強大的性能保證。它們的複雜度通常以其操作範圍中的元素數量 (N) 表示。
- O(N) (線性)：
std::find、std::copy、std::transform、std::accumulate。 - O(N log N) (對數線性)：
std::sort、std::stable_sort。 - O(log N) (對數)：
std::binary_search(在已排序範圍上)。
了解這些複雜度有助於為給定任務選擇最合適的演算法，尤其是在性能關鍵的應用程式中。
練習題：
- 解釋
std::sort和std::stable_sort之間的區別。何時會優先選擇其中一個？ - C++ 中的
std::transform與 JavaScript 的Array.prototype.map()如何比較？提供一個簡單的範例，其中使用std::transform將向量中的每個元素加倍。 - 討論使用 STL 演算法相對於在 C++ 中手動實作類似功能的優點。
專案構想：
- 創建一個 C++ 程式，從檔案中讀取數字列表，對其進行排序，移除重複項，然後計算其總和和平均值。使用適當的 STL 容器和演算法 (
std::vector、std::sort、std::unique、std::accumulate)。將其性能與手動實作的排序和求和版本進行比較。