C++ 常用 <algorithm> 算法概覽

??C++ 標準庫中的 <algorithm> 頭文件提供了大量有用的算法，主要用于操作容器（如 vector, list, array 等）。這些算法通常通過迭代器來操作容器元素。

1. 非修改序列操作

std::all_of, std::any_of, std::none_of

#include <algorithm>
#include <vector>std::vector<int> v = {1, 2, 3, 4, 5};// 檢查所有元素是否滿足條件
bool all_even = std::all_of(v.begin(), v.end(), [](int i){ return i % 2 == 0; });// 檢查是否有任一元素滿足條件
bool any_even = std::any_of(v.begin(), v.end(), [](int i){ return i % 2 == 0; });// 檢查是否沒有元素滿足條件
bool none_even = std::none_of(v.begin(), v.end(), [](int i){ return i % 2 == 0; });

std::for_each

std::vector<int> v = {1, 2, 3, 4, 5};// 對每個元素執行操作
std::for_each(v.begin(), v.end(), [](int &n){ n *= 2; });

std::count, std::count_if

std::vector<int> v = {1, 2, 3, 4, 5};// 計算等于3的元素個數
int count_3 = std::count(v.begin(), v.end(), 3);// 計算滿足條件的元素個數
int count_even = std::count_if(v.begin(), v.end(), [](int i){ return i % 2 == 0; });

std::find, std::find_if, std::find_if_not

std::vector<int> v = {1, 2, 3, 4, 5};// 查找值為3的元素
auto it = std::find(v.begin(), v.end(), 3);// 查找第一個偶數
auto it_even = std::find_if(v.begin(), v.end(), [](int i){ return i % 2 == 0; });// 查找第一個非偶數
auto it_not_even = std::find_if_not(v.begin(), v.end(), [](int i){ return i % 2 == 0; });

2. 修改序列操作

std::copy, std::copy_if

std::vector<int> src = {1, 2, 3, 4, 5};
std::vector<int> dst(5);// 復制元素
std::copy(src.begin(), src.end(), dst.begin());// 條件復制
std::vector<int> dst_even;
std::copy_if(src.begin(), src.end(), std::back_inserter(dst_even), [](int i){ return i % 2 == 0; });

std::fill, std::fill_n

std::vector<int> v(5);// 填充所有元素為42
std::fill(v.begin(), v.end(), 42);// 填充前3個元素為10
std::fill_n(v.begin(), 3, 10);

std::transform

std::vector<int> v = {1, 2, 3, 4, 5};
std::vector<int> result(v.size());// 對每個元素應用函數
std::transform(v.begin(), v.end(), result.begin(), [](int i){ return i * 2; });

std::replace, std::replace_if

std::vector<int> v = {1, 2, 3, 4, 5};// 替換所有3為10
std::replace(v.begin(), v.end(), 3, 10);// 替換所有偶數為0
std::replace_if(v.begin(), v.end(), [](int i){ return i % 2 == 0; }, 0);

std::remove, std::remove_if

std::vector<int> v = {1, 2, 3, 4, 5, 6};// "移除"所有3（實際上是移動到最后，返回新的邏輯end）
auto new_end = std::remove(v.begin(), v.end(), 3);
v.erase(new_end, v.end()); // 真正刪除// "移除"所有偶數
new_end = std::remove_if(v.begin(), v.end(), [](int i){ return i % 2 == 0; });
v.erase(new_end, v.end());

3. 排序和相關操作

std::sort, std::stable_sort

std::vector<int> v = {5, 3, 1, 4, 2};// 默認升序排序
std::sort(v.begin(), v.end());// 自定義排序
std::sort(v.begin(), v.end(), [](int a, int b){ return a > b; }); // 降序// 穩定排序（保持相等元素的相對順序）
std::stable_sort(v.begin(), v.end());

std::partial_sort

std::vector<int> v = {5, 6, 1, 3, 2, 4};// 部分排序（前3個最小的元素）
std::partial_sort(v.begin(), v.begin() + 3, v.end());

std::nth_element

std::vector<int> v = {5, 6, 1, 3, 2, 4};// 使第n個元素處于正確位置
std::nth_element(v.begin(), v.begin() + 2, v.end());
// v[2]現在是排序后的正確元素，前面的都<=它，后面的都>=它

std::is_sorted, std::is_sorted_until

std::vector<int> v = {1, 2, 3, 4, 5};// 檢查是否已排序
bool sorted = std::is_sorted(v.begin(), v.end());// 查找第一個破壞排序的元素
auto it = std::is_sorted_until(v.begin(), v.end());

4. 二分搜索（必須在已排序的序列上使用）

std::lower_bound, std::upper_bound, std::equal_range

std::vector<int> v = {1, 2, 2, 3, 4, 5};// 查找第一個不小于3的元素
auto low = std::lower_bound(v.begin(), v.end(), 3);// 查找第一個大于3的元素
auto up = std::upper_bound(v.begin(), v.end(), 3);// 查找等于3的范圍
auto range = std::equal_range(v.begin(), v.end(), 3);

std::binary_search

std::vector<int> v = {1, 2, 3, 4, 5};// 檢查元素是否存在
bool found = std::binary_search(v.begin(), v.end(), 3);

5. 集合操作（必須在已排序的序列上使用）

std::merge

std::vector<int> v1 = {1, 3, 5};
std::vector<int> v2 = {2, 4, 6};
std::vector<int> dst(v1.size() + v2.size());// 合并兩個已排序的序列
std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), dst.begin());

std::includes, std::set_difference, std::set_intersection, std::set_union, std::set_symmetric_difference

std::vector<int> v1 = {1, 2, 3, 4, 5};
std::vector<int> v2 = {2, 4, 6};std::vector<int> result;// 檢查v1是否包含v2的所有元素
bool includes = std::includes(v1.begin(), v1.end(), v2.begin(), v2.end());// 差集(v1 - v2)
std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result));// 交集
result.clear();
std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(),std::back_inserter(result));// 并集
result.clear();
std::set_union(v1.begin(), v1.end(), v2.begin(), v2.end(),std::back_inserter(result));// 對稱差集（在v1或v2中但不同時在兩者中）
result.clear();
std::set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(),std::back_inserter(result));

6. 堆操作

std::make_heap, std::push_heap, std::pop_heap, std::sort_heap

std::vector<int> v = {3, 1, 4, 1, 5, 9};// 構建最大堆
std::make_heap(v.begin(), v.end());// 添加元素到堆
v.push_back(6);
std::push_heap(v.begin(), v.end());// 移除堆頂元素
std::pop_heap(v.begin(), v.end());
v.pop_back();// 堆排序
std::sort_heap(v.begin(), v.end());

7. 最小/最大值操作

std::min_element, std::max_element, std::minmax_element

std::vector<int> v = {3, 1, 4, 1, 5, 9};// 查找最小元素
auto min_it = std::min_element(v.begin(), v.end());// 查找最大元素
auto max_it = std::max_element(v.begin(), v.end());// 同時查找最小和最大元素
auto minmax = std::minmax_element(v.begin(), v.end());

std::clamp (C++17)

int value = 15;
// 將值限制在10-20范圍內
int clamped = std::clamp(value, 10, 20); // 返回15
clamped = std::clamp(5, 10, 20); // 返回10
clamped = std::clamp(25, 10, 20); // 返回20

8. 排列操作

std::next_permutation, std::prev_permutation

std::vector<int> v = {1, 2, 3};// 生成下一個排列
do {// 處理當前排列
} while (std::next_permutation(v.begin(), v.end()));// 生成前一個排列
std::prev_permutation(v.begin(), v.end());

9. 其他有用算法

std::accumulate (來自 <numeric>)

#include <numeric>
std::vector<int> v = {1, 2, 3, 4, 5};// 求和
int sum = std::accumulate(v.begin(), v.end(), 0);// 自定義操作（如乘積）
int product = std::accumulate(v.begin(), v.end(), 1, [](int a, int b){ return a * b; });

std::inner_product (來自 <numeric>)

std::vector<int> v1 = {1, 2, 3};
std::vector<int> v2 = {4, 5, 6};// 點積
int dot = std::inner_product(v1.begin(), v1.end(), v2.begin(), 0);

std::iota (來自 <numeric>)

std::vector<int> v(5);// 填充序列值
std::iota(v.begin(), v.end(), 10); // v = {10, 11, 12, 13, 14}

這些算法可以大大提高C++編程效率，避免了手動編寫循環的繁瑣工作，同時通常比手寫循環更高效。