C++?STL中常用算法怎么使用

# C++ STL中常用算法怎么使用

## 1. 概述

標準模板庫(STL)是C++中最重要的組成部分之一，它提供了豐富的容器、算法和迭代器。STL算法主要定義在`<algorithm>`頭文件中，這些算法可以對容器中的元素進行各種操作，如排序、查找、遍歷等。STL算法的優勢在于：

1. **高度通用性**：通過迭代器與各種容器配合工作
2. **高效實現**：底層經過充分優化
3. **減少代碼量**：避免重復編寫常見操作

## 2. 常用算法分類

### 2.1 非修改序列算法

不改變容器內容的算法：

```cpp
#include <algorithm>
#include <vector>

std::vector<int> v = {1, 2, 3, 4, 5};

// 查找算法
auto it = std::find(v.begin(), v.end(), 3);  // 查找值為3的元素

// 計數算法
int cnt = std::count(v.begin(), v.end(), 2);  // 統計值為2的元素個數

// 遍歷算法
std::for_each(v.begin(), v.end(), [](int x) {
    std::cout << x << " ";
});

2.2 修改序列算法

會改變容器內容的算法：

// 填充算法
std::fill(v.begin(), v.end(), 0);  // 將所有元素設為0

// 復制算法
std::vector<int> dest(v.size());
std::copy(v.begin(), v.end(), dest.begin());

// 移除算法
auto new_end = std::remove(v.begin(), v.end(), 3);  // 移除所有3
v.erase(new_end, v.end());  // 實際刪除元素

2.3 排序和相關算法

std::vector<int> nums = {5, 3, 1, 4, 2};

// 排序算法
std::sort(nums.begin(), nums.end());  // 默認升序

// 二分查找
bool found = std::binary_search(nums.begin(), nums.end(), 3);

// 合并兩個有序序列
std::vector<int> nums2 = {6, 7, 8};
std::vector<int> merged(nums.size() + nums2.size());
std::merge(nums.begin(), nums.end(), 
           nums2.begin(), nums2.end(),
           merged.begin());

2.4 數值算法

#include <numeric>

std::vector<int> v = {1, 2, 3, 4, 5};

// 累加
int sum = std::accumulate(v.begin(), v.end(), 0);

// 內積
std::vector<int> v2 = {2, 3, 4, 5, 6};
int product = std::inner_product(v.begin(), v.end(), v2.begin(), 0);

// 部分和
std::vector<int> partial(v.size());
std::partial_sum(v.begin(), v.end(), partial.begin());

3. 核心算法詳解

3.1 std::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;  // 降序排序
});

// 對結構體排序
struct Person {
    std::string name;
    int age;
};
std::vector<Person> people = {{"Alice", 25}, {"Bob", 20}};
std::sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
    return a.age < b.age;
});

3.2 std::find和std::find_if

std::vector<int> v = {1, 2, 3, 4, 5};

// 查找特定值
auto it = std::find(v.begin(), v.end(), 3);
if (it != v.end()) {
    std::cout << "Found: " << *it << std::endl;
}

// 使用謂詞查找
auto even = std::find_if(v.begin(), v.end(), [](int x) {
    return x % 2 == 0;
});
if (even != v.end()) {
    std::cout << "First even: " << *even << std::endl;
}

3.3 std::transform

std::vector<int> v = {1, 2, 3, 4, 5};
std::vector<int> squared(v.size());

// 對每個元素進行轉換
std::transform(v.begin(), v.end(), squared.begin(), [](int x) {
    return x * x;
});

// 兩個序列操作
std::vector<int> v2 = {2, 3, 4, 5, 6};
std::vector<int> result(v.size());
std::transform(v.begin(), v.end(), v2.begin(), result.begin(), 
    [](int a, int b) { return a + b; });

3.4 std::accumulate

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::vector<std::string> words = {"Hello", " ", "World"};
std::string sentence = std::accumulate(words.begin(), words.end(), 
    std::string());

4. 算法使用技巧

4.1 使用lambda表達式

std::vector<int> v = {1, 2, 3, 4, 5};

// 使用lambda作為謂詞
std::sort(v.begin(), v.end(), [](int a, int b) {
    return a > b;
});

// 捕獲外部變量
int threshold = 3;
auto count = std::count_if(v.begin(), v.end(), [threshold](int x) {
    return x > threshold;
});

4.2 算法組合使用

std::vector<int> v = {5, 3, 1, 4, 2, 3, 5};

// 先排序再去重
std::sort(v.begin(), v.end());
auto last = std::unique(v.begin(), v.end());
v.erase(last, v.end());

// 查找并處理
auto it = std::find(v.begin(), v.end(), 3);
if (it != v.end()) {
    *it = 30;  // 修改找到的元素
}

4.3 自定義比較函數

struct Point {
    int x, y;
};

std::vector<Point> points = {{1, 2}, {3, 1}, {2, 3}};

// 按x坐標排序
std::sort(points.begin(), points.end(), [](const Point& a, const Point& b) {
    return a.x < b.x;
});

// 多條件排序
std::sort(points.begin(), points.end(), [](const Point& a, const Point& b) {
    if (a.x != b.x) return a.x < b.x;
    return a.y < b.y;
});

5. 性能考慮

1. 算法復雜度：

   • std::sort: O(N log N)
   • std::find: O(N)
   • std::binary_search: O(log N)

2. 內存局部性：連續存儲容器(如vector)通常比鏈表(list)性能更好

3. 避免不必要的拷貝： “`cpp // 不佳的實現 std::vector copy = original; std::sort(copy.begin(), copy.end());

// 更好的實現(原地排序) std::sort(original.begin(), original.end());

## 6. 實際應用示例

### 6.1 統計文本詞頻

```cpp
std::vector<std::string> words = {"apple", "banana", "apple", "cherry"};
std::map<std::string, int> word_count;

std::for_each(words.begin(), words.end(), [&](const std::string& word) {
    word_count[word]++;
});

6.2 過濾容器元素

std::vector<int> numbers = {1, 2, 3, 4, 5, 6};
std::vector<int> evens;

std::copy_if(numbers.begin(), numbers.end(), 
             std::back_inserter(evens),
             [](int x) { return x % 2 == 0; });

6.3 并行算法(C++17)

#include <execution>

std::vector<int> v = {5, 3, 1, 4, 2};

// 并行排序
std::sort(std::execution::par, v.begin(), v.end());

// 并行遍歷
std::for_each(std::execution::par, v.begin(), v.end(), [](int& x) {
    x *= 2;
});

7. 總結

STL算法是C++編程中不可或缺的工具，掌握它們可以顯著提高開發效率和代碼質量。關鍵點包括：

1. 理解迭代器概念和算法適用范圍
2. 熟練使用lambda表達式自定義算法行為
3. 了解不同算法的復雜度特性
4. 合理組合算法完成復雜任務
5. 在C++17及以上版本中考慮使用并行算法

通過實踐這些算法，你將能夠編寫出更簡潔、高效和可維護的C++代碼。

8. 進一步學習資源

1. 《Effective STL》 by Scott Meyers
2. 《The C++ Standard Library》 by Nicolai Josuttis
3. C++官方文檔：https://en.cppreference.com/w/cpp/algorithm
4. C++ Core Guidelines：https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines

”`