C++標(biāo)準(zhǔn)模板庫STL(Standard Template Library)全解析

更新時(shí)間：2026年01月12日 09:41:12 作者：白落提fy

C++標(biāo)準(zhǔn)模板庫（STL）是一套功能強(qiáng)大的模板類和函數(shù)集合,用于提供通用的、可復(fù)用的算法和數(shù)據(jù)結(jié)構(gòu),STL分為容器、迭代器、算法、函數(shù)對象、適配器和分配器等組件,廣泛應(yīng)用于C++編程中,本文介紹C++標(biāo)準(zhǔn)模板庫STL(Standard Template Library)詳解,感興趣的朋友一起看看吧

一.STL 概述

C++ 標(biāo)準(zhǔn)模板庫（Standard Template Library，STL）是一套功能強(qiáng)大的 C++ 模板類和函數(shù)的集合，它提供了一系列通用的、可復(fù)用的算法和數(shù)據(jù)結(jié)構(gòu)。
STL 的設(shè)計(jì)基于泛型編程，這意味著使用模板可以編寫出獨(dú)立于任何特定數(shù)據(jù)類型的代碼。
STL 分為多個(gè)組件，包括容器（Containers）、迭代器（Iterators）、算法（Algorithms）、函數(shù)對象（Function Objects）、適配器（Adapters）和分配器（Allocators）等。
使用 STL 的好處:
代碼復(fù)用：STL 提供了大量的通用數(shù)據(jù)結(jié)構(gòu)和算法，可以減少重復(fù)編寫代碼的工作。
性能優(yōu)化：STL 中的算法和數(shù)據(jù)結(jié)構(gòu)都經(jīng)過了優(yōu)化，以提供最佳的性能。
泛型編程：使用模板，STL 支持泛型編程，使得算法和數(shù)據(jù)結(jié)構(gòu)可以適用于任何數(shù)據(jù)類型。
易于維護(hù)：STL 的設(shè)計(jì)使得代碼更加模塊化，易于閱讀和維護(hù)。

二.STL 的六大組件

組件	功能描述
容器（Containers）	管理數(shù)據(jù)集合
算法（Algorithms）	操作容器中的元素
迭代器（Iterators）	連接容器和算法的橋梁
函數(shù)對象（Function Objects）	使算法更加靈活
適配器（Adapters）	修改或組合組件
分配器（Allocators）	內(nèi)存管理

1.容器（Containers）

容器是 STL 中最基本的組件之一，用于存儲(chǔ)和管理數(shù)據(jù)集合。所有容器都是模板類，可以存儲(chǔ)任意類型的數(shù)據(jù)。容器提供了各種數(shù)據(jù)結(jié)構(gòu)，包括向量（vector）、鏈表（list）、隊(duì)列（queue）、棧（stack）、集合（set）、映射（map）等。這些容器具有不同的特性和用途，可以根據(jù)實(shí)際需求選擇合適的容器。

1.1序列式容器（順序容器）

元素按線性順序排列，每個(gè)元素都有固定位置，位置取決于插入的時(shí)間和位置。允許雙向遍歷。

vector（動(dòng)態(tài)數(shù)組）：支持快速隨機(jī)訪問。將元素置于一個(gè)動(dòng)態(tài)數(shù)組中加以管理，可以隨機(jī)存取元素（用索引直接存?。?，數(shù)組尾部添加或移除元素非?？焖?，但是在中部或頭部安插元素比較費(fèi)時(shí)。

#include <vector>
// 創(chuàng)建和初始化
vector<int> vec1;                    // 空vector
vector<int> vec2(10, 5);             // 10個(gè)5
vector<int> vec3 = {1, 2, 3, 4, 5};  // 初始化列表
vector<int> vec4(vec3);              // 拷貝構(gòu)造
vector<int> vec5(vec3.begin(), vec3.begin() + 3);  // 范圍構(gòu)造
// 容量操作
cout << "大小: " << vec3.size() << endl;          // 5
cout << "容量: " << vec3.capacity() << endl;      // 5
cout << "是否為空: " << vec3.empty() << endl;     // 0(false)
vec3.reserve(20);                    // 預(yù)留容量，不改變大小
vec3.resize(8, 0);                   // 調(diào)整大小，新元素初始化為0
vec3.shrink_to_fit();                // 減少容量以匹配大小(C++11)
// 元素訪問
vec3[2] = 99;                        // 不檢查邊界
vec3.at(3) = 88;                     // 檢查邊界，越界拋異常
cout << "第一個(gè)元素: " << vec3.front() << endl;  // 1
cout << "最后一個(gè)元素: " << vec3.back() << endl;  // 0(新增的元素)
// 添加元素
vec3.push_back(6);                   // 尾部添加，O(1)平攤
vec3.insert(vec3.begin() + 2, 77);   // 指定位置插入，O(n)
vec3.emplace_back(7);                // 尾部就地構(gòu)造，避免復(fù)制(C++11)
// 刪除元素
vec3.pop_back();                     // 尾部刪除，O(1)
vec3.erase(vec3.begin() + 1);        // 刪除指定位置，O(n)
vec3.erase(vec3.begin() + 1, vec3.begin() + 3);  // 刪除范圍
vec3.clear();                        // 清空所有元素
// 交換
vector<int> other = {10, 20, 30};
vec3.swap(other);                    // 交換兩個(gè)vector的內(nèi)容
// 內(nèi)存管理技巧
vector<int>().swap(vec3);            // 清空并釋放所有內(nèi)存

deque（雙端隊(duì)列）：支持快速插入和刪除。是“double-ended queue”的縮寫，可以隨機(jī)存取元素（用索引直接存?。?，數(shù)組頭部和尾部添加或移除元素都非?？焖?，但是在中部安插元素比較費(fèi)時(shí)。

#include <deque>
deque<int> dq = {1, 2, 3, 4, 5};
// 兩端操作（高效）
dq.push_front(0);                    // 頭部插入，O(1)
dq.push_back(6);                     // 尾部插入，O(1)
dq.pop_front();                      // 頭部刪除，O(1)
dq.pop_back();                       // 尾部刪除，O(1)
// 隨機(jī)訪問（高效）
dq[2] = 99;                          // O(1)
// 中間操作（低效）
dq.insert(dq.begin() + 2, 88);       // O(n)
// 應(yīng)用場景：需要兩端快速操作的序列

list（雙向鏈表）：支持快速插入和刪除，但不支持隨機(jī)訪問。不提供隨機(jī)存?。ò错樞蜃叩叫璐嫒〉脑兀琌(n)），在任何位置上執(zhí)行插入或刪除動(dòng)作都非常迅速，內(nèi)部只需調(diào)整一下指針。

#include <list>
list<int> lst = {1, 2, 3, 4, 5};
// 插入和刪除（任何位置都高效）
auto it = lst.begin();
advance(it, 2);                      // it指向第3個(gè)元素
lst.insert(it, 99);                  // O(1)
lst.erase(it);                       // O(1)
// 鏈表特有操作
lst.sort();                          // 排序，O(n log n)
lst.unique();                        // 去重相鄰重復(fù)元素，O(n)
lst.reverse();                       // 反轉(zhuǎn)，O(n)
// 合并和拼接
list<int> lst2 = {6, 7, 8};
lst.merge(lst2);                     // 合并兩個(gè)有序鏈表
lst.splice(lst.begin(), lst2);       // 將lst2的所有元素移到lst開頭
// 訪問元素（不支持隨機(jī)訪問）
for (auto it = lst.begin(); it != lst.end(); ++it) {
    cout << *it << " ";
}
// 應(yīng)用場景：頻繁在任意位置插入刪除

forward_list（單向鏈表，C++11引入）：

#include <forward_list>
forward_list<int> flst = {1, 2, 3, 4, 5};
// 只能從頭部操作
flst.push_front(0);                  // O(1)
flst.pop_front();                    // O(1)
// 插入刪除使用after版本
auto it = flst.begin();
flst.insert_after(it, 99);           // 在it后插入
flst.erase_after(it);                // 刪除it后的元素
// 更節(jié)省內(nèi)存，但功能受限

array（固定數(shù)組，C++11引入）：

#include <array>
array<int, 5> arr = {1, 2, 3, 4, 5};
// 類似C數(shù)組，但有STL接口
arr.fill(0);                         // 填充所有元素為0
cout << "大小: " << arr.size() << endl;        // 5
cout << "是否為空: " << arr.empty() << endl;   // false
// 支持迭代器
for (auto it = arr.begin(); it != arr.end(); ++it) {
    cout << *it << " ";
}
// 編譯時(shí)確定大小，棧上分配

1.2關(guān)聯(lián)式容器（有序容器）

元素按鍵（Key）排序，通過鍵快速訪問元素。存儲(chǔ)鍵值對，每個(gè)元素都有一個(gè)鍵（key）和一個(gè)值（value），并且通過鍵來組織元素。元素位置取決于特定的排序準(zhǔn)則，和插入順序無關(guān)。

set（集合）：不允許重復(fù)元素。內(nèi)部的元素依據(jù)其值自動(dòng)排序，set 內(nèi)的相同數(shù)值的元素只能出現(xiàn)一次。內(nèi)部由二叉樹實(shí)現(xiàn)，便于查找。

#include <set>
set<int> s = {5, 3, 1, 4, 2};  // 自動(dòng)排序: 1,2,3,4,5
// 插入元素
auto result = s.insert(6);     // 返回pair<iterator, bool>
if (result.second) {
    cout << "插入成功" << endl;
}
// 查找元素
auto it = s.find(3);           // O(log n)
if (it != s.end()) {
    cout << "找到: " << *it << endl;
}
// 邊界查找
auto lb = s.lower_bound(3);    // 第一個(gè)>=3的迭代器
auto ub = s.upper_bound(3);    // 第一個(gè)>3的迭代器
// 范圍查找
auto range = s.equal_range(3); // pair<lower_bound, upper_bound>
for (auto it = range.first; it != range.second; ++it) {
    cout << *it << " ";
}
// 刪除元素
s.erase(3);                    // 刪除值為3的元素
s.erase(it);                   // 刪除迭代器指向的元素
s.erase(s.begin(), s.find(3)); // 刪除范圍
// 自定義比較函數(shù)
struct Compare {
    bool operator()(int a, int b) const {
        return a > b;           // 降序排列
    }
};
set<int, Compare> s2 = {1, 2, 3, 4, 5};  // 5,4,3,2,1

multiset（多重集合）：允許多個(gè)元素具有相同的鍵。內(nèi)部的元素依據(jù)其值自動(dòng)排序，multiset 內(nèi)可包含多個(gè)數(shù)值相同的元素，內(nèi)部由二叉樹實(shí)現(xiàn)，便于查找。

#include <set>
multiset<int> ms = {1, 2, 2, 3, 3, 3};
// 允許重復(fù)元素
ms.insert(2);                   // 現(xiàn)在有3個(gè)2
// 統(tǒng)計(jì)元素個(gè)數(shù)
int count = ms.count(2);        // 返回3
// 查找所有相同元素
auto range = ms.equal_range(2);
for (auto it = range.first; it != range.second; ++it) {
    cout << *it << " ";
}

map（映射）：每個(gè)鍵映射到一個(gè)值。map 的元素是成對的鍵值 / 實(shí)值，內(nèi)部的元素依據(jù)其值自動(dòng)排序，map 內(nèi)的相同數(shù)值的元素只能出現(xiàn)一次。

#include <map>
map<string, int> m = {
    {"Alice", 25},
    {"Bob", 30},
    {"Charlie", 35}
};
// 插入元素
auto result = m.insert({"David", 40});      // 返回pair<iterator, bool>
m["Eve"] = 45;                               // 如果不存在則插入，存在則修改
// 訪問元素
int age = m.at("Alice");                     // 如果不存在則拋出異常
int age2 = m["Bob"];                         // 如果不存在則創(chuàng)建默認(rèn)值
// 查找元素
auto it = m.find("Charlie");
if (it != m.end()) {
    cout << it->first << ": " << it->second << endl;
}
// 遍歷
for (const auto& [key, value] : m) {         // C++17結(jié)構(gòu)化綁定
    cout << key << ": " << value << endl;
}
for (const auto& pair : m) {                 // C++11方式
    cout << pair.first << ": " << pair.second << endl;
}
// 刪除元素
m.erase("Alice");
m.erase(it);
// 自定義比較函數(shù)
map<string, int, greater<string>> m2;        // 按鍵降序排列

multimap（多重映射）：存儲(chǔ)了鍵值對（pair），其中鍵是唯一的，但值可以重復(fù)，允許一個(gè)鍵映射到多個(gè)值。

#include <map>
multimap<string, int> mm = {
    {"Alice", 25},
    {"Alice", 26},
    {"Bob", 30}
};
// 允許重復(fù)鍵
mm.insert({"Alice", 27});
// 查找特定鍵的所有值
auto range = mm.equal_range("Alice");
for (auto it = range.first; it != range.second; ++it) {
    cout << it->first << ": " << it->second << endl;
}
// 應(yīng)用場景：一對多映射關(guān)系

1.3無序關(guān)聯(lián)式容器（哈希容器，C++11引入）

元素基于哈希表組織，不保證順序。支持快速的查找、插入和刪除。
-unordered_set（無序集合）：

#include <unordered_set>
unordered_set<int> us = {5, 3, 1, 4, 2};  // 順序不確定
// 基本操作
us.insert(6);
us.erase(3);
auto it = us.find(4);                     // 平均O(1)
// 哈希表特性
cout << "桶數(shù)量: " << us.bucket_count() << endl;
cout << "負(fù)載因子: " << us.load_factor() << endl;
cout << "最大負(fù)載因子: " << us.max_load_factor() << endl;
// 重新哈希
us.rehash(100);                           // 設(shè)置桶數(shù)量
us.reserve(100);                          // 預(yù)留空間
// 遍歷桶
for (size_t i = 0; i < us.bucket_count(); ++i) {
    cout << "桶" << i << "有" << us.bucket_size(i) << "個(gè)元素" << endl;
}
// 自定義哈希函數(shù)
struct Person {
    string name;
    int age;
};
struct PersonHash {
    size_t operator()(const Person& p) const {
        return hash<string>()(p.name) ^ (hash<int>()(p.age) << 1);
    }
};
struct PersonEqual {
    bool operator()(const Person& a, const Person& b) const {
        return a.name == b.name && a.age == b.age;
    }
};
unordered_set<Person, PersonHash, PersonEqual> people;

unordered_map（無序映射）：

#include <unordered_map>
unordered_map<string, int> um = {
    {"Alice", 25},
    {"Bob", 30},
    {"Charlie", 35}
};
// 操作類似map，但無序
um["David"] = 40;
um.insert({"Eve", 45});
// 性能相關(guān)
um.max_load_factor(0.7f);                 // 設(shè)置最大負(fù)載因子
um.rehash(50);                            // 重新哈希
// 遍歷
for (const auto& [key, value] : um) {
    cout << key << ": " << value << endl;
}
// 應(yīng)用場景：需要快速查找，不關(guān)心順序

1.4 容器適配器

基于其他容器實(shí)現(xiàn)特殊接口。

stack（棧）：后進(jìn)先出（LIFO）的數(shù)據(jù)結(jié)構(gòu)

#include <stack>
stack<int> stk;
// 基本操作
stk.push(10);
stk.push(20);
stk.push(30);
cout << "棧頂: " << stk.top() << endl;    // 30
stk.pop();                                 // 刪除30
cout << "大小: " << stk.size() << endl;   // 2
cout << "是否為空: " << stk.empty() << endl; // false
// 使用不同底層容器
stack<int, vector<int>> stk_vec;          // 使用vector作為底層
stack<int, list<int>> stk_list;           // 使用list作為底層
stack<int, deque<int>> stk_deque;         // 使用deque作為底層（默認(rèn)）
// 注意：stack沒有迭代器，只能訪問棧頂

queue（隊(duì)列）：先進(jìn)先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)

#include <queue>
queue<int> q;
// 基本操作
q.push(10);
q.push(20);
q.push(30);
cout << "隊(duì)首: " << q.front() << endl;    // 10
cout << "隊(duì)尾: " << q.back() << endl;     // 30
q.pop();                                   // 刪除10
cout << "大小: " << q.size() << endl;     // 2
// 使用不同底層容器
queue<int, list<int>> q_list;             // 使用list作為底層
queue<int, deque<int>> q_deque;           // 使用deque作為底層（默認(rèn)）
// 注意：queue沒有迭代器

priority_queue（優(yōu)先隊(duì)列）：元素按優(yōu)先級出隊(duì)，默認(rèn)最大元素優(yōu)先

#include <queue>
// 默認(rèn)最大堆（最大元素在頂部）
priority_queue<int> pq_max;
pq_max.push(30);
pq_max.push(10);
pq_max.push(20);
cout << "頂部: " << pq_max.top() << endl;  // 30
// 最小堆
priority_queue<int, vector<int>, greater<int>> pq_min;
pq_min.push(30);
pq_min.push(10);
pq_min.push(20);
cout << "頂部: " << pq_min.top() << endl;  // 10
// 自定義比較函數(shù)
struct Compare {
    bool operator()(int a, int b) {
        // 按絕對值比較，絕對值大的優(yōu)先級高
        return abs(a) < abs(b);
    }
};
priority_queue<int, vector<int>, Compare> pq_custom;
// 存儲(chǔ)復(fù)雜類型
struct Task {
    int priority;
    string description;
    bool operator<(const Task& other) const {
        return priority < other.priority;  // 最大堆
    }
};
priority_queue<Task> task_queue;
task_queue.push({3, "低優(yōu)先級任務(wù)"});
task_queue.push({1, "高優(yōu)先級任務(wù)"});
task_queue.push({2, "中優(yōu)先級任務(wù)"});
while (!task_queue.empty()) {
    Task task = task_queue.top();
    cout << task.priority << ": " << task.description << endl;
    task_queue.pop();
}

2.算法（Algorithms）

STL算法是STL中非常重要的一部分，它們提供了大量的標(biāo)準(zhǔn)算法，用于對容器中的元素進(jìn)行操作。這些算法覆蓋了常見的操作，如查找、排序、復(fù)制、修改等。STL算法通過迭代器與容器進(jìn)行交互，因此它們可以用于不同類型的容器，只需要指定要操作的范圍即可。
STL算法的特點(diǎn)
通過迭代器操作，與容器解耦
大多數(shù)算法在<algorithm>頭文件中
數(shù)值算法在 <numeric>頭文件中
STL算法大致可以分為以下幾類：

非修改序列算法：不會(huì)改變?nèi)萜髦械膬?nèi)容，例如查找、計(jì)數(shù)等。
修改序列算法：會(huì)改變?nèi)萜髦械膬?nèi)容，例如復(fù)制、替換、填充等。
排序和相關(guān)算法：包括排序、合并、二分查找等。
數(shù)值算法：例如累加、內(nèi)積等。

2.1. 非修改序列算法

查找算法

#include <algorithm>
#include <vector>
#include <iostream>
void find_examples() {
    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    // find: 查找指定值
    auto it1 = std::find(v.begin(), v.end(), 5);
    if (it1 != v.end()) {
        std::cout << "找到5: " << *it1 << std::endl;  // 5
    }
    // find_if: 按條件查找
    auto it2 = std::find_if(v.begin(), v.end(), [](int x) {
        return x > 7;
    });
    if (it2 != v.end()) {
        std::cout << "找到大于7的元素: " << *it2 << std::endl;  // 8
    }
    // find_if_not: 查找不滿足條件的元素
    auto it3 = std::find_if_not(v.begin(), v.end(), [](int x) {
        return x < 5;
    });
    if (it3 != v.end()) {
        std::cout << "找到不小于5的元素: " << *it3 << std::endl;  // 5
    }
    // find_end: 查找子序列最后出現(xiàn)的位置
    std::vector<int> sub = {3, 4, 5};
    auto it4 = std::find_end(v.begin(), v.end(), sub.begin(), sub.end());
    if (it4 != v.end()) {
        std::cout << "子序列最后出現(xiàn)在位置: " << std::distance(v.begin(), it4) << std::endl;
    }
    // search: 查找子序列首次出現(xiàn)的位置
    auto it5 = std::search(v.begin(), v.end(), sub.begin(), sub.end());
    if (it5 != v.end()) {
        std::cout << "子序列首次出現(xiàn)在位置: " << std::distance(v.begin(), it5) << std::endl;
    }
    // search_n: 查找連續(xù)n個(gè)相同元素
    std::vector<int> v2 = {1, 2, 2, 2, 3, 4, 2, 2};
    auto it6 = std::search_n(v2.begin(), v2.end(), 3, 2);
    if (it6 != v2.end()) {
        std::cout << "找到3個(gè)連續(xù)的2" << std::endl;
    }
    // adjacent_find: 查找相鄰重復(fù)元素
    std::vector<int> v3 = {1, 2, 3, 3, 4, 5, 5, 6};
    auto it7 = std::adjacent_find(v3.begin(), v3.end());
    if (it7 != v3.end()) {
        std::cout << "找到相鄰重復(fù)元素: " << *it7 << std::endl;  // 3
    }
    // 自定義比較函數(shù)的adjacent_find
    auto it8 = std::adjacent_find(v3.begin(), v3.end(), 
        [](int a, int b) { return abs(a - b) == 1; });
    if (it8 != v3.end()) {
        std::cout << "找到相鄰元素差為1: " << *it8 << "和" << *(it8 + 1) << std::endl;
    }
}

計(jì)數(shù)算法

void count_examples() {
    std::vector<int> v = {1, 2, 2, 3, 3, 3, 4, 4, 4, 4};
    // count: 統(tǒng)計(jì)等于某個(gè)值的元素個(gè)數(shù)
    int cnt1 = std::count(v.begin(), v.end(), 3);
    std::cout << "3的個(gè)數(shù): " << cnt1 << std::endl;  // 3
    // count_if: 統(tǒng)計(jì)滿足條件的元素個(gè)數(shù)
    int cnt2 = std::count_if(v.begin(), v.end(), [](int x) {
        return x > 2;
    });
    std::cout << "大于2的個(gè)數(shù): " << cnt2 << std::endl;  // 7
    // 統(tǒng)計(jì)字符串中字符個(gè)數(shù)
    std::string str = "Hello, World!";
    int cnt3 = std::count(str.begin(), str.end(), 'l');
    std::cout << "l的個(gè)數(shù): " << cnt3 << std::endl;  // 3
    // 統(tǒng)計(jì)元音字母個(gè)數(shù)
    std::string vowels = "aeiouAEIOU";
    int cnt4 = std::count_if(str.begin(), str.end(), [&vowels](char c) {
        return vowels.find(c) != std::string::npos;
    });
    std::cout << "元音字母個(gè)數(shù): " << cnt4 << std::endl;  // 3
}

比較算法

void compare_examples() {
    std::vector<int> v1 = {1, 2, 3, 4, 5};
    std::vector<int> v2 = {1, 2, 3, 4, 5};
    std::vector<int> v3 = {1, 2, 3, 4, 6};
    // equal: 比較兩個(gè)序列是否相等
    bool eq1 = std::equal(v1.begin(), v1.end(), v2.begin());
    std::cout << "v1等于v2: " << eq1 << std::endl;  // true
    bool eq2 = std::equal(v1.begin(), v1.end(), v3.begin());
    std::cout << "v1等于v3: " << eq2 << std::endl;  // false
    // 自定義比較函數(shù)
    bool eq3 = std::equal(v1.begin(), v1.end(), v3.begin(), [](int a, int b) {
        return abs(a - b) <= 1;
    });
    std::cout << "v1與v3元素差不大于1: " << eq3 << std::endl;  // true
    // mismatch: 查找第一個(gè)不匹配的位置
    auto p = std::mismatch(v1.begin(), v1.end(), v3.begin());
    if (p.first != v1.end()) {
        std::cout << "第一個(gè)不匹配: " << *(p.first) << " vs " << *(p.second) << std::endl;  // 5 vs 6
    }
    // lexicographical_compare: 字典序比較
    std::string s1 = "apple";
    std::string s2 = "banana";
    bool lt = std::lexicographical_compare(s1.begin(), s1.end(), s2.begin(), s2.end());
    std::cout << s1 << " < " << s2 << ": " << lt << std::endl;  // true
    // is_permutation: 判斷是否為排列（C++11）
    std::vector<int> v4 = {1, 2, 3, 4, 5};
    std::vector<int> v5 = {5, 4, 3, 2, 1};
    bool perm = std::is_permutation(v4.begin(), v4.end(), v5.begin());
    std::cout << "v5是v4的排列: " << perm << std::endl;  // true
}

遍歷算法

#include <algorithm>
#include <vector>
#include <iostream>
#include <functional>
void foreach_examples() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    // for_each: 對每個(gè)元素執(zhí)行操作
    std::cout << "原始值: ";
    std::for_each(v.begin(), v.end(), [](int x) {
        std::cout << x << " ";
    });
    std::cout << std::endl;
    // 修改元素
    std::cout << "乘以2: ";
    std::for_each(v.begin(), v.end(), [](int& x) {
        x *= 2;
    });
    std::for_each(v.begin(), v.end(), [](int x) {
        std::cout << x << " ";
    });
    std::cout << std::endl;
    // 使用函數(shù)對象
    struct Printer {
        void operator()(int x) const {
            std::cout << x << " ";
        }
    };
    std::cout << "使用函數(shù)對象: ";
    std::for_each(v.begin(), v.end(), Printer());
    std::cout << std::endl;
    // for_each_n: 對前n個(gè)元素執(zhí)行操作（C++17）
    std::vector<int> v2 = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    std::cout << "前5個(gè)元素加10: ";
    std::for_each_n(v2.begin(), 5, [](int& x) { x += 10; });
    for (int x : v2) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    // 統(tǒng)計(jì)操作次數(shù)
    struct Counter {
        int count = 0;
        void operator()(int x) {
            if (x > 12) ++count;
        }
    };
    Counter c = std::for_each(v2.begin(), v2.end(), Counter());
    std::cout << "大于12的元素個(gè)數(shù): " << c.count << std::endl;
}

搜索算法

void search_examples() {
    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    // lower_bound: 第一個(gè)不小于給定值的迭代器
    auto lb = std::lower_bound(v.begin(), v.end(), 5);
    std::cout << "第一個(gè)不小于5的元素: " << *lb << std::endl;  // 5
    // upper_bound: 第一個(gè)大于給定值的迭代器
    auto ub = std::upper_bound(v.begin(), v.end(), 5);
    std::cout << "第一個(gè)大于5的元素: " << *ub << std::endl;  // 6
    // equal_range: 返回等于給定值的范圍
    auto range = std::equal_range(v.begin(), v.end(), 5);
    std::cout << "等于5的范圍: [" << std::distance(v.begin(), range.first) 
              << ", " << std::distance(v.begin(), range.second) << ")" << std::endl;
    // binary_search: 判斷是否存在（要求序列有序）
    bool found = std::binary_search(v.begin(), v.end(), 5);
    std::cout << "5是否存在: " << found << std::endl;  // true
}

2.2. 修改序列算法

復(fù)制算法

void copy_examples() {
    std::vector<int> src = {1, 2, 3, 4, 5};
    // copy: 復(fù)制元素
    std::vector<int> dst1(src.size());
    std::copy(src.begin(), src.end(), dst1.begin());
    std::cout << "copy結(jié)果: ";
    for (int x : dst1) std::cout << x << " ";
    std::cout << std::endl;
    // copy_if: 按條件復(fù)制
    std::vector<int> dst2;
    std::copy_if(src.begin(), src.end(), std::back_inserter(dst2),
                 [](int x) { return x % 2 == 0; });
    std::cout << "copy_if(偶數(shù)): ";
    for (int x : dst2) std::cout << x << " ";
    std::cout << std::endl;
    // copy_n: 復(fù)制前n個(gè)元素
    std::vector<int> dst3(3);
    std::copy_n(src.begin(), 3, dst3.begin());
    std::cout << "copy_n(前3個(gè)): ";
    for (int x : dst3) std::cout << x << " ";
    std::cout << std::endl;
    // copy_backward: 從后往前復(fù)制
    std::vector<int> dst4(5);
    std::copy_backward(src.begin(), src.end(), dst4.end());
    std::cout << "copy_backward結(jié)果: ";
    for (int x : dst4) std::cout << x << " ";
    std::cout << std::endl;
    // 復(fù)制到輸出流
    std::cout << "復(fù)制到輸出流: ";
    std::copy(src.begin(), src.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
    // 從輸入流復(fù)制
    std::istringstream iss("1 2 3 4 5");
    std::vector<int> dst5;
    std::copy(std::istream_iterator<int>(iss),
              std::istream_iterator<int>(),
              std::back_inserter(dst5));
    std::cout << "從輸入流復(fù)制: ";
    for (int x : dst5) std::cout << x << " ";
    std::cout << std::endl;
}

移動(dòng)算法

#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
void move_examples() {
    // move: 移動(dòng)元素（C++11）
    std::vector<std::string> src = {"apple", "banana", "cherry"};
    std::vector<std::string> dst(3);
    std::cout << "move前src: ";
    for (const auto& s : src) std::cout << "\"" << s << "\" ";
    std::cout << std::endl;
    std::move(src.begin(), src.end(), dst.begin());
    std::cout << "move后src: ";
    for (const auto& s : src) std::cout << "\"" << s << "\" ";  // 有效但未指定狀態(tài)
    std::cout << std::endl;
    std::cout << "move后dst: ";
    for (const auto& s : dst) std::cout << "\"" << s << "\" ";
    std::cout << std::endl;
    // move_backward: 從后往前移動(dòng)
    std::vector<std::string> src2 = {"dog", "cat", "bird"};
    std::vector<std::string> dst2(5);
    std::move_backward(src2.begin(), src2.end(), dst2.end());
    std::cout << "move_backward后dst2: ";
    for (const auto& s : dst2) {
        if (s.empty()) std::cout << "[空] ";
        else std::cout << "\"" << s << "\" ";
    }
    std::cout << std::endl;
    // 實(shí)際應(yīng)用：交換兩個(gè)vector
    std::vector<int> v1 = {1, 2, 3};
    std::vector<int> v2 = {4, 5, 6};
    std::cout << "交換前 v1: ";
    for (int x : v1) std::cout << x << " ";
    std::cout << "\n交換前 v2: ";
    for (int x : v2) std::cout << x << " ";
    std::cout << std::endl;
    // 使用move交換
    std::vector<int> temp = std::move(v1);
    v1 = std::move(v2);
    v2 = std::move(temp);
    std::cout << "交換后 v1: ";
    for (int x : v1) std::cout << x << " ";
    std::cout << "\n交換后 v2: ";
    for (int x : v2) std::cout << x << " ";
    std::cout << std::endl;
}

變換算法

void transform_examples() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    // transform: 對每個(gè)元素應(yīng)用函數(shù)
    std::vector<int> result(v.size());
    std::transform(v.begin(), v.end(), result.begin(),
                   [](int x) { return x * x; });
    std::cout << "平方變換: ";
    for (int x : result) std::cout << x << " ";
    std::cout << std::endl;
    // 兩個(gè)序列的transform
    std::vector<int> v1 = {1, 2, 3};
    std::vector<int> v2 = {4, 5, 6};
    std::vector<int> result2(v1.size());
    std::transform(v1.begin(), v1.end(), v2.begin(), result2.begin(),
                   [](int a, int b) { return a + b; });
    std::cout << "兩個(gè)序列相加: ";
    for (int x : result2) std::cout << x << " ";
    std::cout << std::endl;
    // 原地變換
    std::cout << "原地乘以2: ";
    std::transform(v.begin(), v.end(), v.begin(),
                   [](int x) { return x * 2; });
    for (int x : v) std::cout << x << " ";
    std::cout << std::endl;
    // 字符串變換
    std::string str = "Hello World";
    std::string upper_str;
    std::transform(str.begin(), str.end(), std::back_inserter(upper_str),
                   [](char c) { return std::toupper(c); });
    std::cout << "轉(zhuǎn)大寫: " << upper_str << std::endl;
    // 復(fù)雜變換：生成斐波那契數(shù)列
    std::vector<int> fib(10);
    fib[0] = 0;
    fib[1] = 1;
    std::transform(fib.begin(), fib.end() - 2,
                   fib.begin() + 1,
                   fib.begin() + 2,
                   std::plus<int>());
    std::cout << "斐波那契數(shù)列: ";
    for (int x : fib) std::cout << x << " ";
    std::cout << std::endl;
}

替換算法

void replace_examples() {
    std::vector<int> v = {1, 2, 3, 2, 5, 2, 7};
    // replace: 替換指定值
    std::replace(v.begin(), v.end(), 2, 99);
    std::cout << "替換2為99: ";
    for (int x : v) std::cout << x << " ";
    std::cout << std::endl;
    // replace_if: 按條件替換
    std::vector<int> v2 = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    std::replace_if(v2.begin(), v2.end(),
                    [](int x) { return x < 5; },
                    0);
    std::cout << "替換小于5的為0: ";
    for (int x : v2) std::cout << x << " ";
    std::cout << std::endl;
    // replace_copy: 替換并復(fù)制到新容器
    std::vector<int> src = {1, 2, 3, 2, 5};
    std::vector<int> dst(src.size());
    std::replace_copy(src.begin(), src.end(), dst.begin(), 2, 99);
    std::cout << "原始: ";
    for (int x : src) std::cout << x << " ";
    std::cout << "\n替換復(fù)制后: ";
    for (int x : dst) std::cout << x << " ";
    std::cout << std::endl;
    // replace_copy_if: 按條件替換并復(fù)制
    std::vector<int> dst2(src.size());
    std::replace_copy_if(src.begin(), src.end(), dst2.begin(),
                         [](int x) { return x % 2 == 0; },
                         -1);
    std::cout << "替換偶數(shù)為-1并復(fù)制: ";
    for (int x : dst2) std::cout << x << " ";
    std::cout << std::endl;
}

填充算法

void fill_examples() {
    // fill: 填充值
    std::vector<int> v(5);
    std::fill(v.begin(), v.end(), 42);
    std::cout << "填充42: ";
    for (int x : v) std::cout << x << " ";
    std::cout << std::endl;
    // fill_n: 填充前n個(gè)元素
    std::vector<int> v2(10);
    std::fill_n(v2.begin(), 3, 99);
    std::cout << "填充前3個(gè)為99: ";
    for (int x : v2) std::cout << x << " ";
    std::cout << std::endl;
    // generate: 用函數(shù)生成值
    std::vector<int> v3(5);
    int n = 1;
    std::generate(v3.begin(), v3.end(), [&n]() { return n++; });
    std::cout << "生成遞增序列: ";
    for (int x : v3) std::cout << x << " ";
    std::cout << std::endl;
    // generate_n: 生成前n個(gè)值
    std::vector<int> v4(5);
    std::generate_n(v4.begin(), 3, []() { return rand() % 100; });
    std::cout << "生成前3個(gè)隨機(jī)數(shù): ";
    for (int x : v4) std::cout << x << " ";
    std::cout << std::endl;
    // iota: 填充遞增序列（C++11）
    std::vector<int> v5(10);
    std::iota(v5.begin(), v5.end(), 100);
    std::cout << "iota從100開始: ";
    for (int x : v5) std::cout << x << " ";
    std::cout << std::endl;
}

刪除算法

void remove_examples() {
    // remove: 邏輯刪除指定值
    std::vector<int> v = {1, 2, 3, 2, 5, 2, 7};
    auto new_end = std::remove(v.begin(), v.end(), 2);
    std::cout << "邏輯刪除2后: ";
    for (auto it = v.begin(); it != new_end; ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    std::cout << "整個(gè)vector: ";
    for (int x : v) std::cout << x << " ";
    std::cout << std::endl;
    // 物理刪除
    v.erase(new_end, v.end());
    std::cout << "物理刪除后: ";
    for (int x : v) std::cout << x << " ";
    std::cout << std::endl;
    // remove_if: 按條件刪除
    v = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    new_end = std::remove_if(v.begin(), v.end(),
                             [](int x) { return x % 2 == 0; });
    v.erase(new_end, v.end());
    std::cout << "刪除偶數(shù)后: ";
    for (int x : v) std::cout << x << " ";
    std::cout << std::endl;
    // remove_copy: 刪除并復(fù)制到新容器
    std::vector<int> src = {1, 2, 3, 2, 5};
    std::vector<int> dst;
    std::remove_copy(src.begin(), src.end(), std::back_inserter(dst), 2);
    std::cout << "刪除2并復(fù)制: ";
    for (int x : dst) std::cout << x << " ";
    std::cout << std::endl;
    // unique: 刪除相鄰重復(fù)元素
    std::vector<int> v2 = {1, 1, 2, 2, 3, 3, 3, 4, 5, 5};
    new_end = std::unique(v2.begin(), v2.end());
    v2.erase(new_end, v2.end());
    std::cout << "去重后: ";
    for (int x : v2) std::cout << x << " ";
    std::cout << std::endl;
    // 自定義相等判斷的unique
    std::vector<int> v3 = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
    std::sort(v3.begin(), v3.end());
    new_end = std::unique(v3.begin(), v3.end(),
                          [](int a, int b) { return abs(a - b) <= 1; });
    v3.erase(new_end, v3.end());
    std::cout << "自定義去重(差<=1): ";
    for (int x : v3) std::cout << x << " ";
    std::cout << std::endl;
}

交換算法

void swap_examples() {
    // swap: 交換兩個(gè)元素
    int a = 10, b = 20;
    std::swap(a, b);
    std::cout << "a = " << a << ", b = " << b << std::endl;  // a=20, b=10
    // swap_ranges: 交換兩個(gè)范圍
    std::vector<int> v1 = {1, 2, 3, 4, 5};
    std::vector<int> v2 = {10, 20, 30, 40, 50};
    std::swap_ranges(v1.begin(), v1.begin() + 3, v2.begin());
    std::cout << "交換范圍后v1: ";
    for (int x : v1) std::cout << x << " ";
    std::cout << "\n交換范圍后v2: ";
    for (int x : v2) std::cout << x << " ";
    std::cout << std::endl;
    // iter_swap: 交換兩個(gè)迭代器指向的元素
    std::vector<int> v3 = {1, 2, 3, 4, 5};
    std::iter_swap(v3.begin(), v3.end() - 1);
    std::cout << "交換首尾后v3: ";
    for (int x : v3) std::cout << x << " ";
    std::cout << std::endl;
    // 交換整個(gè)容器
    std::vector<int> v4 = {1, 2, 3};
    std::vector<int> v5 = {4, 5, 6};
    std::swap(v4, v5);
    std::cout << "交換容器后v4: ";
    for (int x : v4) std::cout << x << " ";
    std::cout << "\n交換容器后v5: ";
    for (int x : v5) std::cout << x << " ";
    std::cout << std::endl;
}

2.3. 排序和相關(guān)算法

排序算法

void sort_examples() {
    std::vector<int> v = {5, 3, 1, 4, 2, 6, 8, 7, 9};
    // sort: 快速排序
    std::sort(v.begin(), v.end());
    std::cout << "升序排序: ";
    for (int x : v) std::cout << x << " ";
    std::cout << std::endl;
    // 降序排序
    std::sort(v.begin(), v.end(), std::greater<int>());
    std::cout << "降序排序: ";
    for (int x : v) std::cout << x << " ";
    std::cout << std::endl;
    // 自定義排序
    std::vector<std::string> words = {"apple", "banana", "cherry", "date"};
    std::sort(words.begin(), words.end(),
              [](const std::string& a, const std::string& b) {
                  return a.length() < b.length();
              });
    std::cout << "按長度排序: ";
    for (const auto& w : words) std::cout << w << " ";
    std::cout << std::endl;
    // stable_sort: 穩(wěn)定排序
    std::vector<std::pair<int, int>> pairs = {
        {1, 5}, {2, 3}, {1, 3}, {2, 1}, {1, 1}
    };
    std::stable_sort(pairs.begin(), pairs.end(),
                     [](const auto& a, const auto& b) {
                         return a.first < b.first;
                     });
    std::cout << "穩(wěn)定排序(按first): ";
    for (const auto& p : pairs) {
        std::cout << "(" << p.first << "," << p.second << ") ";
    }
    std::cout << std::endl;
    // partial_sort: 部分排序
    v = {5, 3, 1, 4, 2, 6, 8, 7, 9};
    std::partial_sort(v.begin(), v.begin() + 3, v.end());
    std::cout << "部分排序(前3個(gè)最小): ";
    for (int x : v) std::cout << x << " ";
    std::cout << std::endl;
    // nth_element: 使第n個(gè)元素處于正確位置
    v = {5, 3, 1, 4, 2, 6, 8, 7, 9};
    std::nth_element(v.begin(), v.begin() + 4, v.end());
    std::cout << "第5小元素是: " << v[4] << std::endl;
    std::cout << "nth_element后: ";
    for (int x : v) std::cout << x << " ";
    std::cout << std::endl;
    // is_sorted: 判斷是否有序
    v = {1, 2, 3, 4, 5};
    bool sorted = std::is_sorted(v.begin(), v.end());
    std::cout << "是否升序: " << sorted << std::endl;  // true
    // is_sorted_until: 查找無序位置
    v = {1, 2, 3, 5, 4, 6, 7};
    auto it = std::is_sorted_until(v.begin(), v.end());
    if (it != v.end()) {
        std::cout << "從位置 " << std::distance(v.begin(), it)
                  << " 開始無序" << std::endl;
    }
}

二分查找算法

void binary_search_examples() {
    // 必須是有序序列
    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    // binary_search: 判斷是否存在
    bool found = std::binary_search(v.begin(), v.end(), 5);
    std::cout << "5是否存在: " << found << std::endl;  // true
    found = std::binary_search(v.begin(), v.end(), 10);
    std::cout << "10是否存在: " << found << std::endl;  // false
    // lower_bound: 第一個(gè)不小于給定值的迭代器
    auto lb = std::lower_bound(v.begin(), v.end(), 5);
    std::cout << "第一個(gè)不小于5的元素: " << *lb << std::endl;  // 5
    lb = std::lower_bound(v.begin(), v.end(), 5.5);
    std::cout << "第一個(gè)不小于5.5的元素: " << *lb << std::endl;  // 6
    // upper_bound: 第一個(gè)大于給定值的迭代器
    auto ub = std::upper_bound(v.begin(), v.end(), 5);
    std::cout << "第一個(gè)大于5的元素: " << *ub << std::endl;  // 6
    // equal_range: 返回等于給定值的范圍
    auto range = std::equal_range(v.begin(), v.end(), 5);
    std::cout << "等于5的范圍大小: " 
              << std::distance(range.first, range.second) << std::endl;  // 1
    // 在自定義排序的序列中查找
    std::vector<int> v2 = {9, 8, 7, 6, 5, 4, 3, 2, 1};  // 降序
    found = std::binary_search(v2.begin(), v2.end(), 5, std::greater<int>());
    std::cout << "在降序序列中5是否存在: " << found << std::endl;  // true
    // 查找第一個(gè)大于等于3的元素（在降序序列中）
    lb = std::lower_bound(v2.begin(), v2.end(), 3, std::greater<int>());
    std::cout << "降序序列中第一個(gè)>=3的元素: " << *lb << std::endl;  // 3
    // 應(yīng)用：查找區(qū)間
    struct Interval {
        int start, end;
        bool operator<(const Interval& other) const {
            return start < other.start;
        }
    };
    std::vector<Interval> intervals = {
        {1, 3}, {2, 4}, {5, 7}, {6, 8}
    };
    // 查找起點(diǎn)大于等于3的區(qū)間
    Interval target = {3, 0};
    auto it = std::lower_bound(intervals.begin(), intervals.end(), target);
    if (it != intervals.end()) {
        std::cout << "第一個(gè)起點(diǎn)>=3的區(qū)間: [" 
                  << it->start << ", " << it->end << "]" << std::endl;
    }
}

合并算法

void merge_examples() {
    // merge: 合并兩個(gè)有序序列
    std::vector<int> v1 = {1, 3, 5, 7, 9};
    std::vector<int> v2 = {2, 4, 6, 8, 10};
    std::vector<int> result(v1.size() + v2.size());
    std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin());
    std::cout << "合并結(jié)果: ";
    for (int x : result) std::cout << x << " ";
    std::cout << std::endl;
    // 自定義比較函數(shù)的merge
    std::vector<int> v3 = {9, 7, 5, 3, 1};  // 降序
    std::vector<int> v4 = {10, 8, 6, 4, 2}; // 降序
    std::vector<int> result2(v3.size() + v4.size());
    std::merge(v3.begin(), v3.end(), v4.begin(), v4.end(),
               result2.begin(), std::greater<int>());
    std::cout << "降序合并: ";
    for (int x : result2) std::cout << x << " ";
    std::cout << std::endl;
    // inplace_merge: 原地合并
    std::vector<int> v5 = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
    std::inplace_merge(v5.begin(), v5.begin() + 5, v5.end());
    std::cout << "原地合并: ";
    for (int x : v5) std::cout << x << " ";
    std::cout << std::endl;
    // 應(yīng)用：多路歸并
    std::vector<std::vector<int>> vectors = {
        {1, 4, 7},
        {2, 5, 8},
        {3, 6, 9}
    };
    std::vector<int> merged;
    for (const auto& vec : vectors) {
        std::vector<int> temp(merged.size() + vec.size());
        std::merge(merged.begin(), merged.end(), vec.begin(), vec.end(),
                   temp.begin());
        merged.swap(temp);
    }
    std::cout << "多路歸并: ";
    for (int x : merged) std::cout << x << " ";
    std::cout << std::endl;
}

集合算法

void set_algorithm_examples() {
    // 要求序列有序
    std::vector<int> v1 = {1, 2, 3, 4, 5};
    std::vector<int> v2 = {3, 4, 5, 6, 7};
    std::vector<int> result;
    // set_union: 并集
    std::set_union(v1.begin(), v1.end(),
                   v2.begin(), v2.end(),
                   std::back_inserter(result));
    std::cout << "并集: ";
    for (int x : result) std::cout << x << " ";
    std::cout << std::endl;
    // set_intersection: 交集
    result.clear();
    std::set_intersection(v1.begin(), v1.end(),
                          v2.begin(), v2.end(),
                          std::back_inserter(result));
    std::cout << "交集: ";
    for (int x : result) std::cout << x << " ";
    std::cout << std::endl;
    // set_difference: 差集 (v1 - v2)
    result.clear();
    std::set_difference(v1.begin(), v1.end(),
                        v2.begin(), v2.end(),
                        std::back_inserter(result));
    std::cout << "差集(v1-v2): ";
    for (int x : result) std::cout << x << " ";
    std::cout << std::endl;
    // set_symmetric_difference: 對稱差集
    result.clear();
    std::set_symmetric_difference(v1.begin(), v1.end(),
                                  v2.begin(), v2.end(),
                                  std::back_inserter(result));
    std::cout << "對稱差集: ";
    for (int x : result) std::cout << x << " ";
    std::cout << std::endl;
    // includes: 判斷是否包含
    bool includes = std::includes(v1.begin(), v1.end(),
                                  v2.begin(), v2.begin() + 3);  // {3, 4, 5}
    std::cout << "v1是否包含{3,4,5}: " << includes << std::endl;  // true
    // 應(yīng)用：合并多個(gè)集合
    std::vector<std::vector<int>> sets = {
        {1, 2, 3},
        {2, 3, 4},
        {3, 4, 5}
    };
    std::vector<int> all_elements;
    for (const auto& s : sets) {
        std::vector<int> temp;
        std::set_union(all_elements.begin(), all_elements.end(),
                       s.begin(), s.end(),
                       std::back_inserter(temp));
        all_elements.swap(temp);
    }
    std::cout << "所有集合的元素: ";
    for (int x : all_elements) std::cout << x << " ";
    std::cout << std::endl;
}

堆算法

void heap_examples() {
    std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
    // make_heap: 建立最大堆
    std::make_heap(v.begin(), v.end());
    std::cout << "最大堆: ";
    for (int x : v) std::cout << x << " ";
    std::cout << std::endl;
    std::cout << "堆頂: " << v.front() << std::endl;  // 9
    // push_heap: 添加元素到堆
    v.push_back(8);
    std::push_heap(v.begin(), v.end());
    std::cout << "添加8后: ";
    for (int x : v) std::cout << x << " ";
    std::cout << std::endl;
    // pop_heap: 從堆中移除最大元素
    std::pop_heap(v.begin(), v.end());
    int max_val = v.back();
    v.pop_back();
    std::cout << "移除最大元素: " << max_val << std::endl;
    std::cout << "剩余堆: ";
    for (int x : v) std::cout << x << " ";
    std::cout << std::endl;
    // sort_heap: 堆排序
    std::sort_heap(v.begin(), v.end());
    std::cout << "堆排序后: ";
    for (int x : v) std::cout << x << " ";
    std::cout << std::endl;
    // is_heap: 判斷是否為堆
    std::vector<int> v2 = {9, 5, 4, 1, 3, 2};
    bool is_heap = std::is_heap(v2.begin(), v2.end());
    std::cout << "是否為堆: " << is_heap << std::endl;  // false
    std::make_heap(v2.begin(), v2.end());
    is_heap = std::is_heap(v2.begin(), v2.end());
    std::cout << "建立堆后是否為堆: " << is_heap << std::endl;  // true
    // is_heap_until: 查找破壞堆性質(zhì)的位置
    v2.push_back(10);
    auto it = std::is_heap_until(v2.begin(), v2.end());
    std::cout << "破壞堆性質(zhì)的位置: " << std::distance(v2.begin(), it)
              << " (元素: " << *it << ")" << std::endl;
    // 最小堆
    std::vector<int> v3 = {5, 3, 8, 1, 9};
    std::make_heap(v3.begin(), v3.end(), std::greater<int>());
    std::cout << "最小堆: ";
    for (int x : v3) std::cout << x << " ";
    std::cout << "\n最小堆堆頂: " << v3.front() << std::endl;  // 1
    // 應(yīng)用：優(yōu)先級隊(duì)列
    std::vector<int> tasks = {3, 1, 4, 1, 5, 9, 2, 6};
    std::make_heap(tasks.begin(), tasks.end(), std::greater<int>());  // 最小堆
    std::cout << "處理任務(wù)順序: ";
    while (!tasks.empty()) {
        std::pop_heap(tasks.begin(), tasks.end(), std::greater<int>());
        int task = tasks.back();
        tasks.pop_back();
        std::cout << task << " ";
    }
    std::cout << std::endl;
}

最值算法

void minmax_examples() {
    std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
    // min: 返回最小值
    int m1 = std::min(10, 20);
    std::cout << "min(10, 20) = " << m1 << std::endl;  // 10
    // max: 返回最大值
    int m2 = std::max(10, 20);
    std::cout << "max(10, 20) = " << m2 << std::endl;  // 20
    // minmax: 返回最小值和最大值（C++11）
    auto mm1 = std::minmax(10, 20);
    std::cout << "minmax(10, 20) = (" << mm1.first << ", " << mm1.second << ")" << std::endl;
    // min_element: 返回最小元素的迭代器
    auto min_it = std::min_element(v.begin(), v.end());
    std::cout << "最小元素: " << *min_it << " 位置: " 
              << std::distance(v.begin(), min_it) << std::endl;
    // max_element: 返回最大元素的迭代器
    auto max_it = std::max_element(v.begin(), v.end());
    std::cout << "最大元素: " << *max_it << " 位置: "
              << std::distance(v.begin(), max_it) << std::endl;
    // minmax_element: 返回最小和最大元素的迭代器（C++11）
    auto mm_it = std::minmax_element(v.begin(), v.end());
    std::cout << "最小元素: " << *(mm_it.first) 
              << " 最大元素: " << *(mm_it.second) << std::endl;
    // 自定義比較函數(shù)
    std::vector<std::string> words = {"apple", "banana", "cherry", "date"};
    auto longest = std::max_element(words.begin(), words.end(),
                                    [](const std::string& a, const std::string& b) {
                                        return a.length() < b.length();
                                    });
    std::cout << "最長的單詞: " << *longest << std::endl;
    // clamp: 限制值在范圍內(nèi)（C++17）
    int value = 150;
    int clamped = std::clamp(value, 0, 100);
    std::cout << "clamp(150, 0, 100) = " << clamped << std::endl;  // 100
    // 應(yīng)用：查找成績最優(yōu)和最差的學(xué)生
    struct Student {
        std::string name;
        int score;
    };
    std::vector<Student> students = {
        {"Alice", 85},
        {"Bob", 92},
        {"Charlie", 78},
        {"David", 95},
        {"Eve", 88}
    };
    auto best = std::max_element(students.begin(), students.end(),
                                 [](const Student& a, const Student& b) {
                                     return a.score < b.score;
                                 });
    auto worst = std::min_element(students.begin(), students.end(),
                                  [](const Student& a, const Student& b) {
                                      return a.score < b.score;
                                  });
    std::cout << "最高分: " << best->name << " (" << best->score << "分)" << std::endl;
    std::cout << "最低分: " << worst->name << " (" << worst->score << "分)" << std::endl;
}

排列算法

void permutation_examples() {
    std::vector<int> v = {1, 2, 3};
    std::cout << "所有排列:\n";
    do {
        for (int x : v) std::cout << x << " ";
        std::cout << std::endl;
    } while (std::next_permutation(v.begin(), v.end()));
    // 重新初始化為降序
    v = {3, 2, 1};
    std::cout << "\n降序排列的上一個(gè)排列:\n";
    std::prev_permutation(v.begin(), v.end());
    for (int x : v) std::cout << x << " ";  // 3 1 2
    std::cout << std::endl;
    // 判斷是否為排列
    std::vector<int> v1 = {1, 2, 3, 4, 5};
    std::vector<int> v2 = {5, 4, 3, 2, 1};
    bool is_perm = std::is_permutation(v1.begin(), v1.end(), v2.begin());
    std::cout << "v2是否是v1的排列: " << is_perm << std::endl;  // true
    // 生成所有排列的應(yīng)用：解決旅行商問題（暴力搜索）
    std::vector<std::string> cities = {"A", "B", "C", "D"};
    std::sort(cities.begin(), cities.end());  // 先排序
    std::cout << "\n所有旅行路線:\n";
    int count = 0;
    do {
        std::cout << ++count << ": ";
        for (const auto& city : cities) {
            std::cout << city << " ";
        }
        std::cout << std::endl;
    } while (std::next_permutation(cities.begin(), cities.end()));
}

2.4. 數(shù)值算法

#include <numeric>  // 數(shù)值算法頭文件
#include <iostream>
#include <vector>
#include <cmath>
void numeric_examples() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    // accumulate: 累加
    int sum = std::accumulate(v.begin(), v.end(), 0);
    std::cout << "累加: " << sum << std::endl;  // 15
    // 累乘
    int product = std::accumulate(v.begin(), v.end(), 1, std::multiplies<int>());
    std::cout << "累乘: " << product << std::endl;  // 120
    // 字符串連接
    std::vector<std::string> words = {"Hello", " ", "World", "!"};
    std::string sentence = std::accumulate(words.begin(), words.end(), std::string());
    std::cout << "字符串連接: " << sentence << std::endl;  // Hello World!
    // inner_product: 內(nèi)積（點(diǎn)積）
    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::cout << "內(nèi)積: " << dot << std::endl;  // 32 (1*4 + 2*5 + 3*6)
    // 自定義操作的內(nèi)積
    int sum_of_squares = std::inner_product(v1.begin(), v1.end(), v1.begin(), 0);
    std::cout << "平方和: " << sum_of_squares << std::endl;  // 14 (1*1 + 2*2 + 3*3)
    // partial_sum: 部分和
    std::vector<int> prefix_sum(v.size());
    std::partial_sum(v.begin(), v.end(), prefix_sum.begin());
    std::cout << "部分和: ";
    for (int x : prefix_sum) std::cout << x << " ";  // 1 3 6 10 15
    std::cout << std::endl;
    // 自定義操作的partial_sum
    std::vector<int> prefix_product(v.size());
    std::partial_sum(v.begin(), v.end(), prefix_product.begin(), std::multiplies<int>());
    std::cout << "部分積: ";
    for (int x : prefix_product) std::cout << x << " ";  // 1 2 6 24 120
    std::cout << std::endl;
    // adjacent_difference: 相鄰差
    std::vector<int> diff(v.size());
    std::adjacent_difference(v.begin(), v.end(), diff.begin());
    std::cout << "相鄰差: ";
    for (int x : diff) std::cout << x << " ";  // 1 1 1 1 1
    std::cout << std::endl;
    // 自定義操作的adjacent_difference
    std::vector<int> ratio(v.size());
    std::adjacent_difference(v.begin(), v.end(), ratio.begin(),
                             [](int a, int b) { return a - b; });
    std::cout << "相鄰差(自定義): ";
    for (int x : ratio) std::cout << x << " ";
    std::cout << std::endl;
    // iota: 填充遞增序列
    std::vector<int> seq(10);
    std::iota(seq.begin(), seq.end(), 100);
    std::cout << "iota從100開始: ";
    for (int x : seq) std::cout << x << " ";  // 100 101 102 ... 109
    std::cout << std::endl;
    // gcd和lcm（C++17）
    int a = 12, b = 18;
    int g = std::gcd(a, b);
    int l = std::lcm(a, b);
    std::cout << "gcd(12, 18) = " << g << std::endl;  // 6
    std::cout << "lcm(12, 18) = " << l << std::endl;  // 36
    // midpoint（C++20）
    int m = std::midpoint(10, 20);
    std::cout << "midpoint(10, 20) = " << m << std::endl;  // 15
    // 應(yīng)用：計(jì)算加權(quán)平均值
    std::vector<double> values = {85, 90, 78, 92, 88};
    std::vector<double> weights = {0.1, 0.2, 0.3, 0.2, 0.2};
    double weighted_sum = std::inner_product(values.begin(), values.end(),
                                             weights.begin(), 0.0);
    double total_weight = std::accumulate(weights.begin(), weights.end(), 0.0);
    double weighted_avg = weighted_sum / total_weight;
    std::cout << "加權(quán)平均值: " << weighted_avg << std::endl;
}

3.迭代器（Iterators）

迭代器用于遍歷容器中的元素，它是一種類似指針的對象，允許以統(tǒng)一的方式訪問容器中的元素，而不用了解容器的內(nèi)部實(shí)現(xiàn)細(xì)節(jié)。
迭代器的作用
1.連接容器和算法
2.提供統(tǒng)一的訪問接口
3.支持泛型編程

3.1. 迭代器類別

五種迭代器類別

// 迭代器分類（按功能從弱到強(qiáng)）

輸入迭代器 (Input Iterator) - 只讀，只能向前移動(dòng)
輸出迭代器 (Output Iterator) - 只寫，只能向前移動(dòng)
前向迭代器 (Forward Iterator) - 可讀寫，只能向前移動(dòng)
雙向迭代器 (Bidirectional Iterator) - 可讀寫，可向前向后移動(dòng)
隨機(jī)訪問迭代器 (Random Access Iterator) - 可讀寫，支持隨機(jī)訪問

各類迭代器的能力矩陣

操作	輸入	輸出	前向	雙向	隨機(jī)訪問
讀 (*it)	?		?	?	?
寫 (*it = value)		?	?	?	?
遞增 (++)	?	?	?	?	?
遞減 (–)				?	?
比較 (==, !=)	?		?	?	?
一次遍歷	?	?
多次遍歷			?	?	?
加/減整數(shù) (it + n)					?
下標(biāo)訪問 (it[n])					?
比較大小 (<, >)					?
距離 (it1 - it2)					?

3.2. 迭代器使用

獲取迭代器
每個(gè)容器都提供了獲取迭代器的成員函數(shù)：
begin()、end()：返回指向第一個(gè)元素和尾后位置的迭代器
cbegin()、cend()：返回const迭代器（C++11引入）
rbegin()、rend()：返回反向迭代器
crbegin()、crend()：返回const反向迭代器（C++11引入）
迭代器操作示例

#include <iostream>
#include <vector>
#include <list>
void basic_operations() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    // 獲取迭代器
    auto begin_it = v.begin();    // 指向第一個(gè)元素
    auto end_it = v.end();        // 指向最后一個(gè)元素的下一個(gè)位置
    // 解引用
    int first = *begin_it;        // 獲取第一個(gè)元素的值
    *begin_it = 10;               // 修改第一個(gè)元素的值
    // 遞增
    auto it = begin_it;
    ++it;                         // 移動(dòng)到下一個(gè)元素
    it++;                         // 移動(dòng)到下一個(gè)元素
    // 比較
    if (it != end_it) {
        std::cout << "迭代器有效" << std::endl;
    }
    // 迭代器遍歷
    for (auto it = v.begin(); it != v.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
}

不同容器的迭代器特性

void iterator_properties() {
    // vector - 隨機(jī)訪問迭代器
    std::vector<int> vec = {1, 2, 3, 4, 5};
    auto vec_it = vec.begin();
    vec_it += 3;                  // 支持隨機(jī)訪問
    int value = vec_it[2];        // 支持下標(biāo)訪問
    if (vec_it > vec.begin()) {   // 支持比較
        // ...
    }
    // list - 雙向迭代器
    std::list<int> lst = {1, 2, 3, 4, 5};
    auto lst_it = lst.begin();
    ++lst_it;                     // 支持向前移動(dòng)
    --lst_it;                     // 支持向后移動(dòng)
    // lst_it += 2;               // 錯(cuò)誤：不支持隨機(jī)訪問
    // int val = lst_it[2];       // 錯(cuò)誤：不支持下標(biāo)訪問
    // set - 雙向迭代器（const迭代器）
    std::set<int> s = {1, 2, 3, 4, 5};
    auto set_it = s.begin();
    // *set_it = 10;              // 錯(cuò)誤：set迭代器是const的
    int read_value = *set_it;     // 只能讀取
    // map - 雙向迭代器
    std::map<std::string, int> m = {{"a", 1}, {"b", 2}};
    auto map_it = m.begin();
    map_it->first;                // 訪問鍵（只讀）
    map_it->second = 3;           // 可以修改值
}

3.3. 迭代器適配器

迭代器適配器是特殊的迭代器，它們修改或增強(qiáng)現(xiàn)有迭代器的行為。常見的迭代器適配器有：

反向迭代器（Reverse Iterators）：允許反向遍歷容器。

std::vector<int> v = {1, 2, 3, 4, 5};
for (auto rit = v.rbegin(); rit != v.rend(); ++rit) {
    std::cout << *rit << " ";  // 輸出: 5 4 3 2 1
}

插入迭代器（Insert Iterators）：用于將元素插入容器，而不是覆蓋現(xiàn)有元素。

#include <iterator>
#include <vector>
#include <list>
#include <iostream>
int main() {
    std::vector<int> v = {1, 2, 3};
    std::list<int> lst;
    // 使用back_inserter（尾部插入）
    std::copy(v.begin(), v.end(), std::back_inserter(lst));
    // lst: 1 2 3
    // 使用front_inserter（頭部插入）
    std::list<int> lst2;
    std::copy(v.begin(), v.end(), std::front_inserter(lst2));
    // lst2: 3 2 1（注意順序）
    // 使用inserter（指定位置插入）
    std::vector<int> v2 = {4, 5, 6};
    std::copy(v2.begin(), v2.end(), std::inserter(lst, lst.begin()));
    // lst: 4 5 6 1 2 3
    return 0;
}

流迭代器（Stream Iterators）：用于從流中讀取或?qū)懭霐?shù)據(jù)。

#include <iterator>
#include <vector>
#include <iostream>
#include <sstream>
int main() {
    // 從標(biāo)準(zhǔn)輸入讀取整數(shù)
    std::cout << "請輸入一些整數(shù)，以Ctrl+D結(jié)束: ";
    std::istream_iterator<int> input_begin(std::cin);
    std::istream_iterator<int> input_end;
    std::vector<int> numbers(input_begin, input_end);
    // 輸出到標(biāo)準(zhǔn)輸出
    std::cout << "你輸入的數(shù)字是: ";
    std::ostream_iterator<int> output(std::cout, " ");
    std::copy(numbers.begin(), numbers.end(), output);
    std::cout << std::endl;
    // 從字符串流讀取
    std::stringstream ss("1 2 3 4 5");
    std::istream_iterator<int> ss_begin(ss);
    std::istream_iterator<int> ss_end;
    std::vector<int> nums(ss_begin, ss_end);
    return 0;
}

移動(dòng)迭代器（Move Iterators，C++11引入）：將迭代器的解引用操作轉(zhuǎn)換為移動(dòng)操作。

#include <iterator>
#include <vector>
#include <string>
#include <iostream>
int main() {
    std::vector<std::string> src = {"apple", "banana", "cherry"};
    std::vector<std::string> dst;
    // 使用移動(dòng)迭代器將元素從src移動(dòng)到dst
    dst.assign(std::make_move_iterator(src.begin()),
               std::make_move_iterator(src.end()));
    std::cout << "src: ";
    for (const auto& s : src) {
        std::cout << "\"" << s << "\" ";  // 注意：移動(dòng)后src中的字符串處于有效但未指定狀態(tài)
    }
    std::cout << std::endl;
    std::cout << "dst: ";
    for (const auto& s : dst) {
        std::cout << "\"" << s << "\" ";
    }
    std::cout << std::endl;
    return 0;
}

3.4. 迭代器特性

迭代器特性（iterator_traits）是一種模板結(jié)構(gòu)，用于獲取迭代器的相關(guān)類型信息。它對于編寫通用算法非常重要，因?yàn)樗惴ㄐ枰赖魉冈氐念愋偷刃畔ⅰ?/p>

迭代器特性定義了以下類型：

value_type：迭代器指向的元素的類型
difference_type：兩個(gè)迭代器之間距離的類型（通常為ptrdiff_t）
pointer：指向元素的指針類型
reference：元素的引用類型
iterator_category：迭代器的類別（五種之一）

4.函數(shù)對象（Function Objects）

STL中的函數(shù)對象（Function Objects）也稱為仿函數(shù)（Functors）。它們是行為類似函數(shù)的對象，通過重載函數(shù)調(diào)用運(yùn)算符（operator()）來實(shí)現(xiàn)。函數(shù)對象可以像函數(shù)一樣被調(diào)用，同時(shí)可以擁有狀態(tài)（即數(shù)據(jù)成員），因此比普通函數(shù)更加靈活。
函數(shù)對象的優(yōu)點(diǎn)：
1.可以擁有狀態(tài)：因?yàn)楹瘮?shù)對象是類實(shí)例，可以擁有成員變量，從而記錄狀態(tài)。
2.可以作為模板參數(shù)傳遞：函數(shù)對象的類型可以作為模板參數(shù)，從而在編譯時(shí)進(jìn)行優(yōu)化。
3.可以被內(nèi)聯(lián)：函數(shù)對象的operator()可以被編譯器內(nèi)聯(lián)，提高性能。

4.1.STL中預(yù)定義的函數(shù)對象

STL在<functional>頭文件中定義了一些常用的函數(shù)對象，分為以下幾類：

算術(shù)函數(shù)對象:

#include <functional>
#include <iostream>
void arithmetic_functors() {
    // plus: 加法
    std::plus<int> add;
    std::cout << "10 + 5 = " << add(10, 5) << std::endl;  // 15
    // minus: 減法
    std::minus<int> sub;
    std::cout << "10 - 5 = " << sub(10, 5) << std::endl;  // 5
    // multiplies: 乘法
    std::multiplies<int> mul;
    std::cout << "10 * 5 = " << mul(10, 5) << std::endl;  // 50
    // divides: 除法
    std::divides<int> div;
    std::cout << "10 / 5 = " << div(10, 5) << std::endl;  // 2
    // modulus: 取模
    std::modulus<int> mod;
    std::cout << "10 % 3 = " << mod(10, 3) << std::endl;  // 1
    // negate: 取負(fù)
    std::negate<int> neg;
    std::cout << "-10 = " << neg(10) << std::endl;  // -10
}

比較函數(shù)對象:

void comparison_functors() {
    // equal_to: 等于
    std::equal_to<int> eq;
    std::cout << "10 == 10: " << eq(10, 10) << std::endl;  // true
    std::cout << "10 == 5: " << eq(10, 5) << std::endl;    // false
    // not_equal_to: 不等于
    std::not_equal_to<int> neq;
    std::cout << "10 != 5: " << neq(10, 5) << std::endl;   // true
    // greater: 大于
    std::greater<int> gt;
    std::cout << "10 > 5: " << gt(10, 5) << std::endl;     // true
    // less: 小于
    std::less<int> lt;
    std::cout << "10 < 5: " << lt(10, 5) << std::endl;     // false
    // greater_equal: 大于等于
    std::greater_equal<int> ge;
    std::cout << "10 >= 10: " << ge(10, 10) << std::endl;  // true
    // less_equal: 小于等于
    std::less_equal<int> le;
    std::cout << "5 <= 10: " << le(5, 10) << std::endl;    // true
    // 在算法中使用比較函數(shù)對象
    std::vector<int> v = {5, 3, 1, 4, 2};
    // 降序排序
    std::sort(v.begin(), v.end(), std::greater<int>());
    std::cout << "降序排序: ";
    for (int x : v) std::cout << x << " ";  // 5 4 3 2 1
    std::cout << std::endl;
    // 升序排序（默認(rèn)）
    std::sort(v.begin(), v.end(), std::less<int>());
    std::cout << "升序排序: ";
    for (int x : v) std::cout << x << " ";  // 1 2 3 4 5
    std::cout << std::endl;
}

邏輯函數(shù)對象:

void logical_functors() {
    // logical_and: 邏輯與
    std::logical_and<bool> land;
    std::cout << "true && false: " << land(true, false) << std::endl;  // false
    std::cout << "true && true: " << land(true, true) << std::endl;    // true
    // logical_or: 邏輯或
    std::logical_or<bool> lor;
    std::cout << "true || false: " << lor(true, false) << std::endl;  // true
    std::cout << "false || false: " << lor(false, false) << std::endl; // false
    // logical_not: 邏輯非
    std::logical_not<bool> lnot;
    std::cout << "!true: " << lnot(true) << std::endl;   // false
    std::cout << "!false: " << lnot(false) << std::endl; // true
    // 在算法中使用邏輯函數(shù)對象
    std::vector<bool> flags = {true, false, true, false, true};
    // 檢查是否所有元素都為true
    bool all_true = std::all_of(flags.begin(), flags.end(), 
                                [](bool b) { return b; });
    std::cout << "所有元素都為true: " << all_true << std::endl;  // false
    // 檢查是否有任意元素為true
    bool any_true = std::any_of(flags.begin(), flags.end(), 
                                [](bool b) { return b; });
    std::cout << "有任意元素為true: " << any_true << std::endl;  // true
}

位運(yùn)算函數(shù)對象（C++11引入）:

void bitwise_functors() {
    // bit_and: 位與
    std::bit_and<int> band;
    int result = band(0b1010, 0b1100);  // 0b1000 -> 8
    std::cout << "0b1010 & 0b1100 = " << result << std::endl;  // 8
    // bit_or: 位或
    std::bit_or<int> bor;
    result = bor(0b1010, 0b1100);       // 0b1110 -> 14
    std::cout << "0b1010 | 0b1100 = " << result << std::endl;  // 14
    // bit_xor: 位異或
    std::bit_xor<int> bxor;
    result = bxor(0b1010, 0b1100);      // 0b0110 -> 6
    std::cout << "0b1010 ^ 0b1100 = " << result << std::endl;  // 6
    // 在算法中使用位運(yùn)算函數(shù)對象
    std::vector<int> v1 = {1, 2, 3, 4, 5};
    std::vector<int> v2 = {5, 4, 3, 2, 1};
    std::vector<int> result_vec(5);
    // 對兩個(gè)vector進(jìn)行位與操作
    std::transform(v1.begin(), v1.end(), v2.begin(), result_vec.begin(),
                   std::bit_and<int>());
    std::cout << "位與結(jié)果: ";
    for (int x : result_vec) std::cout << x << " ";  // 1&5=1, 2&4=0, 3&3=3, 4&2=0, 5&1=1
    std::cout << std::endl;
}

4.2. 自定義函數(shù)對象

我們可以通過定義一個(gè)類并重載operator()來創(chuàng)建自定義函數(shù)對象。

基本函數(shù)對象:

class BasicFunctor {
public:
    // 無狀態(tài)函數(shù)對象
    int operator()(int a, int b) const {
        return a + b;
    }
};
void basic_custom_functor() {
    BasicFunctor adder;
    std::cout << "5 + 3 = " << adder(5, 3) << std::endl;
    // 臨時(shí)對象調(diào)用
    std::cout << "10 + 20 = " << BasicFunctor()(10, 20) << std::endl;
}

有狀態(tài)函數(shù)對象:

class StatefulFunctor {
private:
    int count;
    int increment;
public:
    StatefulFunctor(int inc = 1) : count(0), increment(inc) {}
    int operator()() {
        count += increment;
        return count;
    }
    int getCount() const { return count; }
    void reset() { count = 0; }
};
void stateful_functor_example() {
    StatefulFunctor counter1;           // 默認(rèn)每次增加1
    StatefulFunctor counter2(5);        // 每次增加5
    std::cout << "counter1: ";
    for (int i = 0; i < 5; ++i) {
        std::cout << counter1() << " ";  // 1 2 3 4 5
    }
    std::cout << std::endl;
    std::cout << "counter2: ";
    for (int i = 0; i < 5; ++i) {
        std::cout << counter2() << " ";  // 5 10 15 20 25
    }
    std::cout << std::endl;
    // 在算法中使用有狀態(tài)函數(shù)對象
    std::vector<int> numbers(10);
    StatefulFunctor generator(2);
    std::generate(numbers.begin(), numbers.end(), generator);
    std::cout << "生成的序列: ";
    for (int n : numbers) {
        std::cout << n << " ";  // 2 4 6 8 10 12 14 16 18 20
    }
    std::cout << std::endl;
}

4.3. 函數(shù)適配器

函數(shù)適配器是用來適配函數(shù)對象，使其與其他函數(shù)對象或值組合，形成新的函數(shù)對象。C++11之后，函數(shù)適配器的使用減少，因?yàn)閘ambda表達(dá)式更靈活。但了解一些傳統(tǒng)的適配器仍有必要：

bind（C++11引入）- 參數(shù)綁定：可以綁定函數(shù)對象的參數(shù)，并可以重新排列參數(shù)順序

#include <functional>
#include <iostream>
void bind_examples() {
    using namespace std::placeholders;  // 使用占位符 _1, _2, _3...
    // 普通函數(shù)
    int multiply(int a, int b) {
        return a * b;
    }
    // 綁定第一個(gè)參數(shù)
    auto multiply_by_5 = std::bind(multiply, 5, _1);
    std::cout << "5 * 10 = " << multiply_by_5(10) << std::endl;  // 50
    // 綁定第二個(gè)參數(shù)
    auto multiply_by_3 = std::bind(multiply, _1, 3);
    std::cout << "10 * 3 = " << multiply_by_3(10) << std::endl;  // 30
    // 交換參數(shù)順序
    auto multiply_reverse = std::bind(multiply, _2, _1);
    std::cout << "交換參數(shù): " << multiply_reverse(5, 10) << std::endl;  // 50
    // 綁定成員函數(shù)
    class Calculator {
    public:
        int add(int a, int b) const {
            return a + b;
        }
    };
    Calculator calc;
    auto add_10 = std::bind(&Calculator::add, &calc, _1, 10);
    std::cout << "add(5, 10) = " << add_10(5) << std::endl;  // 15
    // 綁定數(shù)據(jù)成員
    struct Point {
        int x, y;
    };
    Point p = {10, 20};
    auto get_x = std::bind(&Point::x, _1);
    std::cout << "p.x = " << get_x(p) << std::endl;  // 10
    // 組合綁定
    auto complex = std::bind(multiply, 
                            std::bind(std::plus<int>(), _1, 5),  // (x + 5)
                            _2);                                 // * y
    std::cout << "(5 + 5) * 2 = " << complex(5, 2) << std::endl;  // 20
}

function（C++11引入）- 函數(shù)包裝器：

#include <functional>
#include <iostream>
void function_examples() {
    // 包裝普通函數(shù)
    int add(int a, int b) { return a + b; }
    std::function<int(int, int)> func1 = add;
    std::cout << "add(10, 20) = " << func1(10, 20) << std::endl;  // 30
    // 包裝函數(shù)對象
    struct Multiply {
        int operator()(int a, int b) const {
            return a * b;
        }
    };
    Multiply mult;
    std::function<int(int, int)> func2 = mult;
    std::cout << "mult(10, 20) = " << func2(10, 20) << std::endl;  // 200
    // 包裝lambda表達(dá)式
    std::function<int(int, int)> func3 = [](int a, int b) {
        return a - b;
    };
    std::cout << "subtract(20, 10) = " << func3(20, 10) << std::endl;  // 10
    // 包裝成員函數(shù)
    class Math {
    public:
        int square(int x) const {
            return x * x;
        }
        static int cube(int x) {
            return x * x * x;
        }
    };
    Math math;
    std::function<int(const Math&, int)> func4 = &Math::square;
    std::cout << "math.square(5) = " << func4(math, 5) << std::endl;  // 25
    std::function<int(int)> func5 = Math::cube;
    std::cout << "Math::cube(3) = " << func5(3) << std::endl;  // 27
    // 作為回調(diào)函數(shù)
    class Button {
        std::function<void()> onClick;
    public:
        void setOnClick(std::function<void()> callback) {
            onClick = callback;
        }
        void click() {
            if (onClick) onClick();
        }
    };
    Button button;
    button.setOnClick([]() {
        std::cout << "按鈕被點(diǎn)擊了！" << std::endl;
    });
    button.click();
    // 判斷是否為空
    std::function<void()> empty_func;
    if (!empty_func) {
        std::cout << "函數(shù)對象為空" << std::endl;
    }
}

mem_fn（C++11引入）- 成員函數(shù)適配器

#include <functional>
#include <vector>
#include <algorithm>
void mem_fn_examples() {
    class Person {
    public:
        std::string name;
        int age;
        Person(std::string n, int a) : name(std::move(n)), age(a) {}
        bool isAdult() const {
            return age >= 18;
        }
        void birthday() {
            ++age;
        }
        std::string getName() const {
            return name;
        }
    };
    std::vector<Person> people = {
        {"Alice", 25},
        {"Bob", 17},
        {"Charlie", 30},
        {"David", 16},
        {"Eve", 20}
    };
    // 使用mem_fn調(diào)用成員函數(shù)
    // 統(tǒng)計(jì)成年人數(shù)量
    int adult_count = std::count_if(people.begin(), people.end(),
                                    std::mem_fn(&Person::isAdult));
    std::cout << "成年人數(shù)量: " << adult_count << std::endl;  // 3
    // 獲取所有人的名字
    std::vector<std::string> names;
    std::transform(people.begin(), people.end(), std::back_inserter(names),
                   std::mem_fn(&Person::getName));
    std::cout << "名字: ";
    for (const auto& name : names) {
        std::cout << name << " ";
    }
    std::cout << std::endl;
    // 給所有人過生日
    std::for_each(people.begin(), people.end(),
                  std::mem_fn(&Person::birthday));
    std::cout << "過生日后的年齡: ";
    for (const auto& p : people) {
        std::cout << p.name << ":" << p.age << " ";
    }
    std::cout << std::endl;
    // 訪問數(shù)據(jù)成員
    std::vector<int> ages;
    std::transform(people.begin(), people.end(), std::back_inserter(ages),
                   std::mem_fn(&Person::age));
    std::cout << "年齡: ";
    for (int age : ages) {
        std::cout << age << " ";
    }
    std::cout << std::endl;
}

函數(shù)對象與lambda表達(dá)式：從C++11開始，lambda表達(dá)式提供了另一種創(chuàng)建函數(shù)對象的方式，通常更簡潔。

#include <iostream>
#include <vector>
#include <algorithm>
int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    // 使用lambda表達(dá)式作為函數(shù)對象
    std::sort(v.begin(), v.end(), [](int a, int b) {
        return a > b; // 降序排序
    });
    for (int x : v) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    // lambda表達(dá)式可以捕獲變量，類似于有狀態(tài)的函數(shù)對象
    int factor = 3;
    std::transform(v.begin(), v.end(), v.begin(), [factor](int x) {
        return x * factor;
    });
    for (int x : v) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    return 0;
}

5.適配器（Adapters）

STL適配器是一種設(shè)計(jì)模式，它用于修改或調(diào)整其他組件的接口，使其適應(yīng)不同的需求。STL中的適配器主要分為三類：容器適配器、迭代器適配器和函數(shù)適配器。

適配器分類：
容器適配器：基于其他容器實(shí)現(xiàn)的特殊數(shù)據(jù)結(jié)構(gòu)
迭代器適配器：改變迭代器的行為
函數(shù)適配器：修改函數(shù)對象的行為
適配器特點(diǎn)：
不提供新功能，而是改變現(xiàn)有組件的接口
實(shí)現(xiàn)組件復(fù)用
提高代碼的靈活性和可重用性

6.分配器（Allocators）

STL中的分配器（Allocators）是用于內(nèi)存管理的組件，它封裝了內(nèi)存分配和釋放的細(xì)節(jié)，使得STL容器能夠獨(dú)立于具體的內(nèi)存管理方式。分配器是一個(gè)模板類，它定義了如何為容器分配和釋放內(nèi)存，以及如何構(gòu)造和銷毀對象。
分配器的作用
1.分離內(nèi)存分配與對象構(gòu)造
2.分離對象析構(gòu)與內(nèi)存釋放
3.提供一種可定制內(nèi)存管理策略的機(jī)制

6.1.標(biāo)準(zhǔn)分配器

C++標(biāo)準(zhǔn)庫提供了一個(gè)默認(rèn)的分配器std::allocator，它使用::operator new和::operator delete來分配和釋放內(nèi)存。

標(biāo)準(zhǔn)分配器（std::allocator）的基本使用

#include <memory>  // allocator 頭文件
#include <iostream>
void basic_allocator_usage() {
    // 創(chuàng)建int類型的分配器
    std::allocator<int> alloc;
    // 分配可以存儲(chǔ)5個(gè)int的內(nèi)存（不構(gòu)造對象）
    int* p = alloc.allocate(5);
    // 在已分配的內(nèi)存上構(gòu)造對象
    for (int i = 0; i < 5; ++i) {
        alloc.construct(p + i, i * 10);  // 在p[i]處構(gòu)造int，值為i*10
    }
    // 使用構(gòu)造的對象
    for (int i = 0; i < 5; ++i) {
        std::cout << p[i] << " ";  // 輸出: 0 10 20 30 40
    }
    std::cout << std::endl;
    // 銷毀對象（但不釋放內(nèi)存）
    for (int i = 0; i < 5; ++i) {
        alloc.destroy(p + i);
    }
    // 釋放內(nèi)存
    alloc.deallocate(p, 5);
}

分配器的方法

void allocator_methods() {
    std::allocator<std::string> alloc;
    // 1. allocate: 分配原始內(nèi)存
    std::string* ptr = alloc.allocate(3);  // 分配3個(gè)string的內(nèi)存
    // 2. construct: 構(gòu)造對象（C++17前，C++17后已棄用）
    alloc.construct(ptr, "Hello");         // 構(gòu)造第一個(gè)string
    alloc.construct(ptr + 1, "World");     // 構(gòu)造第二個(gè)string
    alloc.construct(ptr + 2, "!");         // 構(gòu)造第三個(gè)string
    // 3. destroy: 銷毀對象（C++17前，C++17后已棄用）
    alloc.destroy(ptr);
    alloc.destroy(ptr + 1);
    alloc.destroy(ptr + 2);
    // 4. deallocate: 釋放內(nèi)存
    alloc.deallocate(ptr, 3);
    // 5. max_size: 最大可分配數(shù)量（已棄用）
    // std::size_t max = alloc.max_size();
    // C++17推薦使用allocator_traits
}

使用allocator_traits（C++11）

#include <memory>
void allocator_traits_example() {
    using Alloc = std::allocator<int>;
    using Traits = std::allocator_traits<Alloc>;
    Alloc alloc;
    // 通過traits分配內(nèi)存
    int* p = Traits::allocate(alloc, 5);
    // 通過traits構(gòu)造對象
    for (int i = 0; i < 5; ++i) {
        Traits::construct(alloc, p + i, i * 10);
    }
    for (int i = 0; i < 5; ++i) {
        std::cout << p[i] << " ";  // 0 10 20 30 40
    }
    std::cout << std::endl;
    // 通過traits銷毀對象
    for (int i = 0; i < 5; ++i) {
        Traits::destroy(alloc, p + i);
    }
    // 通過traits釋放內(nèi)存
    Traits::deallocate(alloc, p, 5);
    // 獲取最大可分配大小
    auto max_size = Traits::max_size(alloc);
    std::cout << "max_size: " << max_size << std::endl;
}

6.2.分配器特性（Allocator Traits）

C++11引入了 allocator_traits，提供了一種統(tǒng)一的方式來訪問分配器的屬性，即使分配器沒有提供某些成員，allocator_traits 也會(huì)提供默認(rèn)實(shí)現(xiàn)。

allocator_traits 的主要功能

#include <memory>
#include <iostream>
void allocator_traits_features() {
    using Alloc = std::allocator<int>;
    using Traits = std::allocator_traits<Alloc>;
    Alloc alloc;
    // 1. 類型定義
    using value_type = Traits::value_type;           // int
    using pointer = Traits::pointer;                 // int*
    using const_pointer = Traits::const_pointer;     // const int*
    using void_pointer = Traits::void_pointer;       // void*
    using const_void_pointer = Traits::const_void_pointer;  // const void*
    using difference_type = Traits::difference_type; // ptrdiff_t
    using size_type = Traits::size_type;             // size_t
    // 2. 傳播特性（用于控制分配器的復(fù)制行為）
    using propagate_on_container_copy_assignment = 
        Traits::propagate_on_container_copy_assignment;  // false_type
    using propagate_on_container_move_assignment = 
        Traits::propagate_on_container_move_assignment;  // false_type
    using propagate_on_container_swap = 
        Traits::propagate_on_container_swap;              // false_type
    // 3. 分配器是否總是相等
    using is_always_equal = Traits::is_always_equal;      // true_type
    std::cout << "propagate_on_container_copy_assignment: " 
              << propagate_on_container_copy_assignment::value << std::endl;
    std::cout << "propagate_on_container_move_assignment: " 
              << propagate_on_container_move_assignment::value << std::endl;
    std::cout << "is_always_equal: " 
              << is_always_equal::value << std::endl;
}

6.3.分配器與容器

容器如何與分配器交互

void container_allocator_interaction() {
    // 1. 容器構(gòu)造時(shí)接收分配器
    std::allocator<int> alloc;
    std::vector<int, std::allocator<int>> v1(alloc);
    // 2. 獲取容器的分配器
    auto alloc_copy = v1.get_allocator();
    // 3. 分配器感知的容器操作
    std::vector<int> v2 = {1, 2, 3, 4, 5};
    std::vector<int> v3(v2.get_allocator());  // 使用相同的分配器
    // 4. 使用分配器分配內(nèi)存
    auto& alloc_ref = v3.get_allocator();
    int* p = alloc_ref.allocate(10);
    // ... 使用內(nèi)存 ...
    alloc_ref.deallocate(p, 10);
    // 5. 使用自定義分配器的容器
    SimpleAllocator<double> custom_alloc;
    std::vector<double, SimpleAllocator<double>> v4(custom_alloc);
    for (int i = 0; i < 10; ++i) {
        v4.push_back(i * 3.14);
    }
}

分配器對容器行為的影響

template<typename T>
class DebugAllocator {
public:
    using value_type = T;
    T* allocate(std::size_t n) {
        std::cout << "分配 " << n << " 個(gè) " << typeid(T).name() << std::endl;
        return static_cast<T*>(::operator new(n * sizeof(T)));
    }
    void deallocate(T* p, std::size_t n) {
        std::cout << "釋放 " << n << " 個(gè) " << typeid(T).name() << std::endl;
        ::operator delete(p);
    }
    template<typename U>
    struct rebind {
        using other = DebugAllocator<U>;
    };
};
template<typename T, typename U>
bool operator==(const DebugAllocator<T>&, const DebugAllocator<U>&) {
    return true;
}
template<typename T, typename U>
bool operator!=(const DebugAllocator<T>&, const DebugAllocator<U>&) {
    return false;
}
void allocator_effect_on_container() {
    // 使用調(diào)試分配器的vector
    std::cout << "=== vector with debug allocator ===" << std::endl;
    std::vector<int, DebugAllocator<int>> v;
    // 觀察vector如何分配內(nèi)存
    for (int i = 0; i < 10; ++i) {
        v.push_back(i);
        std::cout << "size: " << v.size() 
                  << ", capacity: " << v.capacity() << std::endl;
    }
    // 使用調(diào)試分配器的map
    std::cout << "\n=== map with debug allocator ===" << std::endl;
    std::map<std::string, int, std::less<std::string>, 
             DebugAllocator<std::pair<const std::string, int>>> m;
    m["apple"] = 3;
    m["banana"] = 5;
    m["cherry"] = 2;
    m["date"] = 7;
}

6.4.自定義分配器

簡單自定義分配器實(shí)現(xiàn)

#include <cstdlib>  // malloc, free
#include <iostream>
#include <memory>
#include <new>
template<typename T>
class SimpleAllocator {
public:
    // 類型定義（必須）
    using value_type = T;
    using pointer = T*;
    using const_pointer = const T*;
    using reference = T&;
    using const_reference = const T&;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    // 支持分配其他類型的rebind模板（必須）
    template<typename U>
    struct rebind {
        using other = SimpleAllocator<U>;
    };
    // 構(gòu)造函數(shù)
    SimpleAllocator() noexcept = default;
    template<typename U>
    SimpleAllocator(const SimpleAllocator<U>&) noexcept {}
    // 分配內(nèi)存
    pointer allocate(size_type n, const void* hint = 0) {
        if (n > max_size()) {
            throw std::bad_alloc();
        }
        // 使用malloc分配內(nèi)存
        if (auto p = static_cast<pointer>(std::malloc(n * sizeof(T)))) {
            std::cout << "分配 " << n << " 個(gè) " << typeid(T).name() 
                      << " (" << n * sizeof(T) << " 字節(jié))" << std::endl;
            return p;
        }
        throw std::bad_alloc();
    }
    // 釋放內(nèi)存
    void deallocate(pointer p, size_type n) noexcept {
        std::cout << "釋放 " << n << " 個(gè) " << typeid(T).name() 
                  << " (" << n * sizeof(T) << " 字節(jié))" << std::endl;
        std::free(p);
    }
    // 最大可分配數(shù)量
    size_type max_size() const noexcept {
        return std::size_t(-1) / sizeof(T);
    }
    // 構(gòu)造對象
    template<typename U, typename... Args>
    void construct(U* p, Args&&... args) {
        ::new(static_cast<void*>(p)) U(std::forward<Args>(args)...);
    }
    // 銷毀對象
    template<typename U>
    void destroy(U* p) {
        p->~U();
    }
    // 獲取地址
    pointer address(reference x) const noexcept { return &x; }
    const_pointer address(const_reference x) const noexcept { return &x; }
};
// 比較操作符（必須）
template<typename T, typename U>
bool operator==(const SimpleAllocator<T>&, const SimpleAllocator<U>&) noexcept {
    return true;
}
template<typename T, typename U>
bool operator!=(const SimpleAllocator<T>&, const SimpleAllocator<U>&) noexcept {
    return false;
}
void custom_allocator_example() {
    // 使用自定義分配器的vector
    std::vector<int, SimpleAllocator<int>> v;
    for (int i = 0; i < 5; ++i) {
        v.push_back(i * 10);
    }
    std::cout << "vector元素: ";
    for (int x : v) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    // 使用自定義分配器的map
    std::map<std::string, int, std::less<std::string>, 
             SimpleAllocator<std::pair<const std::string, int>>> m;
    m["apple"] = 3;
    m["banana"] = 5;
    m["cherry"] = 2;
    for (const auto& p : m) {
        std::cout << p.first << ": " << p.second << std::endl;
    }
}

到此這篇關(guān)于C++標(biāo)準(zhǔn)模板庫STL(Standard Template Library)詳解的文章就介紹到這了,更多相關(guān)C++標(biāo)準(zhǔn)模板庫STL內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: