C++ 算法函数

2025 年 8 月 29 日 | 阅读 20 分钟

在 C++ 中，标准模板库 (STL) 在 `` 头文件中提供了强大的底层函数集合。这些函数有助于对数组、向量、列表和其他容器等序列执行广泛的操作。算法函数是通用的，并且操作于迭代器，这使得它们可以跨多种容器类型重用。

算法类型

算法主要有两种类型。它们如下：

非修改算法
修改算法

现在，我们将逐一讨论这些算法。

非修改算法

在 C++ 中，非修改算法在不改变其值的情况下对元素序列进行操作。它们的主要用途是对各种元素执行查询、比较和检查。当目的是检索信息而不是更改容器的内容时，这些算法效果很好。常见示例包括 `find()`，它查找给定值，以及 `count()`，它计算特定元素出现的次数。

这些函数效率高，可确保数据完整性，并且是分析或验证 STL 容器（如向量、列表和数组）中元素的关键工具。

修改算法

在 C++ 中，修改算法是指修改或重新排列范围中元素的算法。这些算法会更改原始数据，而不是创建新容器。有几种修改算法，例如 `sort()`、`reverse()`、`rotate()`、`partition()`、`remove()` 等。这些算法通常用于高效的就地数据转换。

C++ 算法的成员函数

以下是 map 的所有成员函数列表

标准非修改序列算法

下表显示了 C++ 算法中使用的几种标准非修改序列操作。

函数	描述
all_of	此函数用于测试范围内所有元素的条件。
any_of	此函数用于测试范围内某些或任何元素的条件
none_of	此函数用于检查是否没有元素满足条件。
for_each	该函数将操作应用于范围内的所有元素。
find	该函数在范围内查找值。
find_if	该函数在范围内查找元素。
find_if_not	该函数以与上面相反的方式在范围内查找元素。
find_end	此函数用于返回范围的最后一个元素。
find_first_of	该函数查找满足条件且出现在第一个的元素。
adjacent_find	该函数在范围内搜索查找相等且相邻的元素。
count	该函数返回范围内某个值的计数。
count_if	该函数返回满足条件的计数值。
mismatch	该函数返回序列中第一个不匹配的值。
equal	该函数用于检查两个范围是否所有元素都相等。
is_permutation	该函数检查范围是否是某个其他范围的排列。
search	该函数在范围内搜索子序列。
search_n	该函数在范围内搜索元素的出现次数。

C++ 非修改序列操作示例

让我们举例说明 C++ 中的非修改序列操作。

示例

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric> // for iota function
using namespace std;  //using standard namespace
int main() {  //main function
    vector<int> data = {2, 4, 6, 8, 10, 3, 4, 6, 8, 10};

    // all_of
    bool allEven = all_of(data.begin(), data.end(), [](int x){ return x % 2 == 0; });
    cout << "All elements are even? " << boolalpha << allEven << endl;

    // any_of
    bool anyOdd = any_of(data.begin(), data.end(), [](int x){ return x % 2 != 0; });
    cout << "Any element is odd? " << boolalpha << anyOdd << endl;

    // none_of
    bool noneNegative = none_of(data.begin(), data.end(), [](int x){ return x < 0; });
    cout << "No negative elements? " << boolalpha << noneNegative << endl;

    // for_each
    cout << "Elements: ";
    for_each(data.begin(), data.end(), [](int x){ cout << x << " "; });
    cout << endl;

    // find
    auto it1 = find(data.begin(), data.end(), 6);
    if (it1 != data.end())
        cout << "First occurrence of 6 found at index: " << distance(data.begin(), it1) << endl;

    // find_if
    auto it2 = find_if(data.begin(), data.end(), [](int x){ return x > 8; });
    if (it2 != data.end())
        cout << "First element > 8 is: " << *it2 << endl;

    // find_if_not
    auto it3 = find_if_not(data.begin(), data.end(), [](int x){ return x % 2 == 0; });
    if (it3 != data.end())
        cout << "First non-even element: " << *it3 << endl;

    // find_end
    vector<int> sub1 = {4, 6};
    auto it4 = find_end(data.begin(), data.end(), sub1.begin(), sub1.end());
    if (it4 != data.end())
        cout << "Last occurrence of {4, 6} starts at index: " << distance(data.begin(), it4) << endl;

    // find_first_of
    vector<int> targets = {3, 7, 9};
    auto it5 = find_first_of(data.begin(), data.end(), targets.begin(), targets.end());
    if (it5 != data.end())
        cout << "First matching element from {3,7,9} is: " << *it5 << endl;

    // adjacent_find
    vector<int> repeated = {1, 2, 3, 3, 4, 5};
    auto it6 = adjacent_find(repeated.begin(), repeated.end());
    if (it6 != repeated.end())
        cout << "First pair of adjacent equal elements: " << *it6 << " and " << *(it6 + 1) << endl;

    // count
    int count_4 = count(data.begin(), data.end(), 4);
    cout << "Count of 4s in data: " << count_4 << endl;

    // count_if
    int count_gt_5 = count_if(data.begin(), data.end(), [](int x){ return x > 5; });
    cout << "Count of elements > 5: " << count_gt_5 << endl;

    // mismatch
    vector<int> d1 = {1, 2, 3, 4, 5};
    vector<int> d2 = {1, 2, 0, 4, 5};
    auto [m1, m2] = mismatch(d1.begin(), d1.end(), d2.begin());
    cout << "First mismatch: " << *m1 << " vs " << *m2 << endl;

    // equal
    bool areEqual = equal(d1.begin(), d1.end(), d2.begin());
    cout << "Are d1 and d2 equal? " << boolalpha << areEqual << endl;

    // is_permutation
    vector<int> a = {1, 2, 3};
    vector<int> b = {3, 2, 1};
    bool isPerm = is_permutation(a.begin(), a.end(), b.begin());
    cout << "Is b a permutation of a? " << boolalpha << isPerm << endl;

    // search
    vector<int> needle = {6, 8};
    auto it7 = search(data.begin(), data.end(), needle.begin(), needle.end());
    if (it7 != data.end())
        cout << "Subsequence {6,8} found at index: " << distance(data.begin(), it7) << endl;

    // search_n
    auto it8 = search_n(data.begin(), data.end(), 2, 4);
    if (it8 != data.end())
        cout << "Two consecutive 4s found at index: " << distance(data.begin(), it8) << endl;

    return 0;
}

编译并运行

输出

All elements are even? false
Any element is odd? true
No negative elements? true
Elements: 2 4 6 8 10 3 4 6 8 10 
First occurrence of 6 found at index: 2
First element > 8 is: 10
First non-even element: 3
Last occurrence of {4, 6} starts at index: 6
First matching element from {3,7,9} is: 3
First pair of adjacent equal elements: 3 and 3
Count of 4s in data: 2
Count of elements > 5: 6
First mismatch: 3 vs 0
Are d1 and d2 equal? false
Is b a permutation of a? true
Subsequence {6,8} found at index: 2

修改序列操作

下表显示了 C++ 算法中使用的几种修改序列操作。

函数	描述
副本	该函数复制元素范围。
copy_n	该函数复制范围的 n 个元素
copy_if	如果满足某个条件，该函数将复制范围的元素。
copy_backward	该函数按倒序复制元素
move	该函数移动元素范围。
move_backward	该函数按倒序移动元素范围
swap	该函数交换两个对象的值。
swap_ranges	该函数交换两个范围的值。
iter_swap	该函数交换引用下的两个迭代器的值。
transform	该函数转换范围内的所有值。
replace	该函数将范围内的值替换为特定值。
replace_if	如果满足某个条件，该函数将替换范围的值。
replace_copy	该函数通过替换元素来复制值范围。
replace_copy_if	如果满足某个条件，该函数通过替换元素来复制值范围。
fill	该函数使用某个值填充范围内的值。
fill_n	该函数填充序列中的值。
generate	该函数用于生成范围的值。
generate_n	该函数用于生成序列的值。
remove	该函数从范围内删除值。
remove_if	如果满足某个条件，该函数将删除范围的值。
remove_copy	该函数通过删除它们来复制范围的值。
remove_copy_if	如果满足某个条件，该函数通过删除它们来复制范围的值。
unique	该函数识别范围内的唯一元素。
unique_copy	该函数复制范围内的唯一元素。
反转	该函数反转范围。
reverse_copy	该函数通过反转值来复制范围。
rotate	该函数将范围中的元素向左旋转。
rotate_copy	该函数复制向左旋转的范围中的元素。
random_shuffle	该函数随机打乱范围。
shuffle	该函数借助生成器随机打乱范围。

C++ 修改序列操作示例

让我们举例说明 C++ 中的修改序列操作。

示例

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>   // For iota
#include <random>    // For shuffle
using namespace std;   //using standard namespace

int main() {    //main function
    vector<int> original(10);
    iota(original.begin(), original.end(), 1);  // Fill with 1 to 10

    // copy
    vector<int> copied(10);
    copy(original.begin(), original.end(), copied.begin());
    cout << "Copied vector: ";
    for (int x : copied) cout << x << " ";
    cout << endl;

    // copy_if (copy only even numbers)
    vector<int> evens;
    copy_if(original.begin(), original.end(), back_inserter(evens), [](int x) { return x % 2 == 0; });
    cout << "Even elements (copy_if): ";
    for (int x : evens) cout << x << " ";
    cout << endl;

    // transform (multiply each element by 2)
    vector<int> doubled(10);
    transform(original.begin(), original.end(), doubled.begin(), [](int x) { return x * 2; });
    cout << "Transformed (doubled) vector: ";
    for (int x : doubled) cout << x << " ";
    cout << endl;

    // replace (replace 5 with 99)
    vector<int> replaced = original;
    replace(replaced.begin(), replaced.end(), 5, 99);
    cout << "Replaced 5 with 99: ";
    for (int x : replaced) cout << x << " ";
    cout << endl;

    // remove (remove value 3)
    vector<int> removed = original;
    auto new_end = remove(removed.begin(), removed.end(), 3);
    removed.erase(new_end, removed.end()); // Physically erase
    cout << "Removed 3 from vector: ";
    for (int x : removed) cout << x << " ";
    cout << endl;

    // unique (remove adjacent duplicates)
    vector<int> with_dupes = {1, 1, 2, 2, 2, 3, 3, 4};
    auto last_unique = unique(with_dupes.begin(), with_dupes.end());
    with_dupes.erase(last_unique, with_dupes.end());
    cout << "After unique(): ";
    for (int x : with_dupes) cout << x << " ";
    cout << endl;

    // reverse
    vector<int> reversed = original;
    reverse(reversed.begin(), reversed.end());
    cout << "Reversed vector: ";
    for (int x : reversed) cout << x << " ";
    cout << endl;

    // rotate (move first 3 elements to end)
    vector<int> rotated = original;
    rotate(rotated.begin(), rotated.begin() + 3, rotated.end());
    cout << "Rotated vector (left by 3): ";
    for (int x : rotated) cout << x << " ";
    cout << endl;

    // swap_ranges (swap original with doubled)
    vector<int> swapped1 = original, swapped2 = doubled;
    swap_ranges(swapped1.begin(), swapped1.end(), swapped2.begin());
    cout << "After swap_ranges(), swapped1: ";
    for (int x : swapped1) cout << x << " ";
    cout << "\nAfter swap_ranges(), swapped2: ";
    for (int x : swapped2) cout << x << " ";
    cout << endl;

    // shuffle (modern C++11 shuffle)
    vector<int> shuffled = original;
    random_device rd;
    mt19937 g(rd());
    shuffle(shuffled.begin(), shuffled.end(), g);
    cout << "Shuffled vector: ";
    for (int x : shuffled) cout << x << " ";
    cout << endl;

    return 0;
}

编译并运行

输出

Copied vector: 1 2 3 4 5 6 7 8 9 10 
Even elements (copy_if): 2 4 6 8 10 
Transformed (doubled) vector: 2 4 6 8 10 12 14 16 18 20 
Replaced 5 with 99: 1 2 3 4 99 6 7 8 9 10 
Removed 3 from vector: 1 2 4 5 6 7 8 9 10 
After unique(): 1 2 3 4 
Reversed vector: 10 9 8 7 6 5 4 3 2 1 
Rotated vector (left by 3): 4 5 6 7 8 9 10 1 2 3 
After swap_ranges(), swapped1: 2 4 6 8 10 12 14 16 18 20 
After swap_ranges(), swapped2: 1 2 3 4 5 6 7 8 9 10 
Shuffled vector: 6 9 1 7 4 3 5 8 2 10

分区

下表显示了 C++ 算法中使用的几种分区操作。

函数	描述
is_partitioned	该函数用于推断范围是否已分区。
partition	该函数用于分区范围。
stable_partition	该函数将范围分成两个稳定的部分。
partition_copy	该函数在分区后复制范围。
partition_point	该函数返回范围的分区点。

C++ 分区操作示例

让我们举例说明 C++ 中的分区操作。

示例

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;  //using standard namespace
bool isEven(int x) {
    return x % 2 == 0;
}
int main() {  //main function
    vector<int> data = {1, 2, 3, 4, 5, 6, 7, 8};
    
    // Check if already partitioned
    bool alreadyPartitioned = is_partitioned(data.begin(), data.end(), isEven);
    cout << "Is the data partitioned (evens first)? " << boolalpha << alreadyPartitioned << endl;
    
    // Apply partition (non-stable)
    partition(data.begin(), data.end(), isEven);
    cout << "After partition (evens first): ";
    for (int x : data) cout << x << " ";
    cout << endl;
    
    // Apply stable_partition
    vector<int> data2 = {1, 2, 3, 4, 5, 6, 7, 8};
    stable_partition(data2.begin(), data2.end(), isEven);
    cout << "After stable_partition (evens first, order preserved): ";
    for (int x : data2) cout << x << " ";
    cout << endl;
    
    // Use partition_copy
    vector<int> evens, odds;
    evens.resize(data.size());
    odds.resize(data.size());
    auto result = partition_copy(data.begin(), data.end(),
                                 evens.begin(), odds.begin(), isEven);
    evens.resize(distance(evens.begin(), result.first));
    odds.resize(distance(odds.begin(), result.second));
    cout << "Partitioned copy - evens: ";
    for (int x : evens) cout << x << " ";
    cout << "\nPartitioned copy - odds: ";
    for (int x : odds) cout << x << " ";
    cout << endl;
    
    // Use partition_point
    auto it = partition_point(data.begin(), data.end(), isEven);
    cout << "Partition point index: " << distance(data.begin(), it) << endl;
    
    return 0;
}

编译并运行

输出

Is the data partitioned (evens first)? false
After partition (evens first): 8 2 6 4 5 3 7 1 
After stable_partition (evens first, order preserved): 2 4 6 8 1 3 5 7 
Partitioned copy - evens: 8 2 6 4 
Partitioned copy - odds: 5 3 7 1 
Partition point index: 4

排序

下表显示了 C++ 算法中使用的几种排序操作。

函数	描述
排序	该函数对范围内的所有元素进行排序。
stable_sort	该函数对范围内的元素进行排序，同时保持相等元素的相对顺序。
partial_sort	该函数对范围的元素进行部分排序。
partial_sort_copy	该函数在对范围进行排序后复制其元素。
is_sorted	该函数检查范围是否已排序。
is_sorted_until	该函数检查范围在哪个元素之前是已排序的。
nth_element	该函数对范围内的元素进行排序。

C++ 排序操作示例

让我们举例说明 C++ 中的排序函数。

示例

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;  //using standard namespace
void printVector(const vector<int>& v, const string& msg) {
    cout << msg;
    for (int x : v) cout << x << " ";
    cout << endl;
}

int main() {  //main function
    vector<int> data = {7, 2, 9, 4, 3, 8, 1, 6, 5};
    
    // 1. sort
    vector<int> sorted = data;
    sort(sorted.begin(), sorted.end());
    printVector(sorted, "Sorted vector: ");
    
    // 2. stable_sort
    vector<pair<int, char>> stableData = {{3, 'a'}, {1, 'b'}, {3, 'c'}, {2, 'd'}};
    stable_sort(stableData.begin(), stableData.end());
    cout << "Stable sorted vector of pairs: ";
    for (auto& p : stableData) cout << "(" << p.first << "," << p.second << ") ";
    cout << endl;
    
    // 3. partial_sort (smallest 5 elements)
    vector<int> partial = data;
    partial_sort(partial.begin(), partial.begin() + 5, partial.end());
    printVector(partial, "Partially sorted (first 5 smallest): ");
    
    // 4. partial_sort_copy
    vector<int> dest(5);
    partial_sort_copy(data.begin(), data.end(), dest.begin(), dest.end());
    printVector(dest, "Partial sort copy (5 smallest): ");
    
    // 5. is_sorted
    bool sortedStatus = is_sorted(sorted.begin(), sorted.end());
    cout << "Is the sorted vector actually sorted? " << boolalpha << sortedStatus << endl;
    
    // 6. is_sorted_until
    vector<int> partlySorted = {1, 2, 3, 7, 5, 6};
    auto until = is_sorted_until(partlySorted.begin(), partlySorted.end());
    cout << "is_sorted_until found unsorted at position: "
         << distance(partlySorted.begin(), until) << endl;
         
    // 7. nth_element (place the 5th smallest element in correct position)
    vector<int> nth = data;
    nth_element(nth.begin(), nth.begin() + 4, nth.end());  // 5th smallest
    printVector(nth, "After nth_element (5th smallest in correct place): ");
    cout << "5th smallest element is: " << nth[4] << endl;
    
    return 0;
}

编译并运行

输出

Sorted vector: 1 2 3 4 5 6 7 8 9 
Stable sorted vector of pairs: (1,b) (2,d) (3,a) (3,c) 
Partially sorted (first 5 smallest): 1 2 3 4 5 9 8 7 6 
Partial sort copy (5 smallest): 1 2 3 4 5 
Is the sorted vector actually sorted? true
is_sorted_until found unsorted at position: 4
After nth_element (5th smallest in correct place): 3 2 1 4 5 7 6 9 8 
5th smallest element is: 5

二分搜索

下表显示了 C++ 算法中使用的几种二分查找操作。

函数	描述
lower_bound	返回范围的下界元素。
upper_bound	返回范围的上界元素。
equal_range	该函数返回相等元素的子范围。
binary_search	该函数测试范围内的值是否存在于排序序列中。

C++ 二分查找操作示例

让我们举例说明 C++ 中的二分查找操作。

示例

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;   //using standard namespace

int main() {   //main function
    vector<int> data = {1, 3, 3, 3, 5, 7, 9, 11};
    // Must be sorted before using binary search algorithms
    cout << "Sorted data: ";
    for (int x : data) cout << x << " ";
    cout << endl;
    int value = 3;
    
    // 1. binary_search
    bool found = binary_search(data.begin(), data.end(), value);
    cout << "Is value " << value << " present? " << boolalpha << found << endl;
    
    // 2. lower_bound
    auto lower = lower_bound(data.begin(), data.end(), value);
    cout << "Lower bound of " << value << " is at index: " << distance(data.begin(), lower)
         << ", value: " << *lower << endl;
    
    // 3. upper_bound
    auto upper = upper_bound(data.begin(), data.end(), value);
    cout << "Upper bound of " << value << " is at index: " << distance(data.begin(), upper)
         << ", value: " << *upper << endl;
    
    // 4. equal_range
    auto range = equal_range(data.begin(), data.end(), value);
    cout << "Equal range of " << value << " is from index "
         << distance(data.begin(), range.first) << " to "
         << distance(data.begin(), range.second) << endl;
    cout << "Elements in equal range: ";
    for (auto it = range.first; it != range.second; ++it)
        cout << *it << " ";
    cout << endl;
    
    return 0;
}

编译并运行

输出

Sorted data: 1 3 3 3 5 7 9 11 
Is value 3 present? true
Lower bound of 3 is at index: 1, value: 3
Upper bound of 3 is at index: 4, value: 5
Equal range of 3 is from index 1 to 4
Elements in equal range: 3 3 3

合并

下表显示了 C++ 算法中使用的几种合并操作。

合并

函数	描述
merge	该函数合并两个已排序的范围。
inplace_merge	该函数合并两个相邻的已排序范围。
includes	该函数搜索已排序范围是否包含另一个范围。
set_union	该函数返回两个已排序范围的并集。
set_intersection	该函数返回两个已排序范围的交集。
set_difference	该函数返回两个已排序范围的差集。
set_symmetric_difference	该函数返回两个已排序范围的对称差集。

C++ 合并操作示例

让我们举例说明 C++ 中的合并操作。

示例

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;  //using standard namespace
void printVector(const vector<int>& v, const string& msg) {
    cout << msg;
    for (int x : v) cout << x << " ";
    cout << endl;
}

int main() {  //main function
    vector<int> A = {1, 3, 5, 7};
    vector<int> B = {2, 3, 6, 8};
    
    // 1. merge
    vector<int> merged(A.size() + B.size());
    merge(A.begin(), A.end(), B.begin(), B.end(), merged.begin());
    printVector(merged, "Merged A and B: ");
    
    // 2. inplace_merge
    vector<int> C = {1, 3, 5, 7, 2, 4, 6};
    inplace_merge(C.begin(), C.begin() + 4, C.end());
    printVector(C, "After inplace_merge: ");
    
    // 3. includes
    vector<int> superset = {1, 2, 3, 4, 5};
    vector<int> subset = {2, 4};
    bool result = includes(superset.begin(), superset.end(), subset.begin(), subset.end());
    cout << "Does superset include subset? " << boolalpha << result << endl;
    
    // 4. set_union
    vector<int> unionResult(A.size() + B.size());
    auto it1 = set_union(A.begin(), A.end(), B.begin(), B.end(), unionResult.begin());
    unionResult.resize(it1 - unionResult.begin());
    printVector(unionResult, "Set union: ");
    
    // 5. set_intersection
    vector<int> intersectionResult(min(A.size(), B.size()));
    auto it2 = set_intersection(A.begin(), A.end(), B.begin(), B.end(), intersectionResult.begin());
    intersectionResult.resize(it2 - intersectionResult.begin());
    printVector(intersectionResult, "Set intersection: ");
    
    // 6. set_difference (A - B)
    vector<int> differenceResult(A.size());
    auto it3 = set_difference(A.begin(), A.end(), B.begin(), B.end(), differenceResult.begin());
    differenceResult.resize(it3 - differenceResult.begin());
    printVector(differenceResult, "Set difference (A - B): ");
    
    // 7. set_symmetric_difference
    vector<int> symmetricDiffResult(A.size() + B.size());
    auto it4 = set_symmetric_difference(A.begin(), A.end(), B.begin(), B.end(), symmetricDiffResult.begin());
    symmetricDiffResult.resize(it4 - symmetricDiffResult.begin());
    printVector(symmetricDiffResult, "Set symmetric difference: ");
    
    return 0;
}

编译并运行

输出

Merged A and B: 1 2 3 3 5 6 7 8 
After inplace_merge: 1 2 3 4 5 6 7 
Does superset include subset? true
Set union: 1 2 3 5 6 7 8 
Set intersection: 3 
Set difference (A - B): 1 5 7 
Set symmetric difference: 1 2 5 6 7 8

堆

下表显示了 C++ 算法中使用的几种堆操作。

函数	描述
push_heap	该函数将新元素推入堆。
pop_heap	该函数从堆中弹出新元素。
make_heap	该函数用于创建堆。
sort_heap	该函数对堆进行排序。
is_heap	该函数检查范围是否为堆。
is_heap_until	该函数检查范围在哪个位置是堆。

C++ 堆操作示例

让我们举例说明 C++ 中的堆操作。

示例

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;  //using standard namespace

void printVector(const vector<int>& v, const string& msg) {
    cout << msg;
    for (int x : v) cout << x << " ";
    cout << endl;
}

int main() {   //main function
    vector<int> heap = {10, 20, 30, 5, 15};
    
    // 1. make_heap
    make_heap(heap.begin(), heap.end());
    printVector(heap, "Heap after make_heap: ");  // Heapify the vector
    
    // 2. push_heap (insert new element into heap)
    heap.push_back(25);           // Add new element at the end
    push_heap(heap.begin(), heap.end());
    printVector(heap, "Heap after push_heap(25): ");
    
    // 3. pop_heap (remove root of heap)
    pop_heap(heap.begin(), heap.end()); // Moves the largest to the end
    cout << "Popped element: " << heap.back() << endl;
    heap.pop_back(); // Actually remove the last element
    printVector(heap, "Heap after pop_heap: ");
    
    // 4. is_heap
    bool result = is_heap(heap.begin(), heap.end());
    cout << "Is the vector a heap? " << boolalpha << result << endl;
    
    // 5. is_heap_until
    vector<int> testHeap = {30, 20, 25, 10, 15, 5, 40}; // not a valid heap
    auto it = is_heap_until(testHeap.begin(), testHeap.end());
    cout << "is_heap_until fails at index: " << distance(testHeap.begin(), it) << endl;
    
    // 6. sort_heap (converts heap into sorted array)
    sort_heap(heap.begin(), heap.end());
    printVector(heap, "Heap after sort_heap (sorted array): ");
    
    return 0;
}

编译并运行

输出

Heap after make_heap: 30 20 10 5 15 
Heap after push_heap(25): 30 20 25 5 15 10 
Popped element: 30
Heap after pop_heap: 25 20 10 5 15 
Is the vector a heap? true
is_heap_until fails at index: 6
Heap after sort_heap (sorted array): 5 10 15 20 25

最小值/最大值

下表显示了 C++ 算法中使用的几种最小值/最大值操作。

函数	描述
min	返回范围中的最小元素。
max	返回范围中的最大元素。
minmax	返回范围中的最小和最大元素。
min_element	返回范围中的最小元素。
max_element	返回范围中的最大元素。
minmax_element	返回范围中的最小和最大元素。

C++ 最小值/最大值操作示例

让我们举例说明 C++ 中的最小值/最大值操作。

示例

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility> // for std::pair
using namespace std; //using standard namespace

int main() {   //main function
    vector<int> nums = {12, 45, 23, 67, 34, 89, 11, 9};
    
    // 1. min (between two values)
    int a = 10, b = 20;
    cout << "min(10, 20): " << min(a, b) << endl;
    
    // 2. max (between two values)
    cout << "max(10, 20): " << max(a, b) << endl;
    
    // 3. minmax (between two values)
    auto minmaxVal = minmax(a, b);
    cout << "minmax(10, 20): (" << minmaxVal.first << ", " << minmaxVal.second << ")" << endl;
    
    // 4. min_element (smallest element in the vector)
    auto minIt = min_element(nums.begin(), nums.end());
    cout << "Minimum element in vector: " << *minIt << " at index " << distance(nums.begin(), minIt) << endl;
    
    // 5. max_element (largest element in the vector)
    auto maxIt = max_element(nums.begin(), nums.end());
    cout << "Maximum element in vector: " << *maxIt << " at index " << distance(nums.begin(), maxIt) << endl;
    
    // 6. minmax_element (returns both min and max from range)
    auto minmaxIt = minmax_element(nums.begin(), nums.end());
    cout << "Minmax in vector: min = " << *minmaxIt.first << ", max = " << *minmaxIt.second << endl;
    
    return 0;
}

编译并运行

输出

min(10, 20): 10
max(10, 20): 20
minmax(10, 20): (10, 20)
Minimum element in vector: 9 at index 7
Maximum element in vector: 89 at index 5
Minmax in vector: min = 9, max = 89

其他函数

下表显示了 C++ 算法中有用的几种其他操作。

函数	描述
lexicographical_comapre	该函数执行字典序小于比较。
next_permutation	该函数用于将范围转换为下一个排列。
prev_permutation	该函数用于将范围转换为上一个排列。

C++ 算法函数的关键特性

C++ 算法函数有几个关键特性。一些主要特性如下：

通用且基于模板：C++ 算法函数是基于模板的，这允许它们在不重写的情况下与各种数据类型和容器类型（如 vector、list 和 array）一起工作。
修改和非修改类别：算法分为非修改（如 find、count 和 for_each）和修改（如 copy、replace 和 transform），取决于它们是否更改输入数据。
支持自定义条件：许多特定函数（例如 find_if、count_if）用于定义谓词函数或 lambda 表达式，以增加自定义逻辑。
高效且优化：STL 算法针对性能进行了优化，通常提供保证的时间复杂度（例如，sort 使用混合排序算法，复杂度为 O(n log n)）。
不调整容器大小：算法容器不管理大小或内存。

结论

总之，C++ 算法函数是通过标准模板库 (STL) 中的头文件提供的高效且富有表现力的编程的必备工具集。它们抽象了低级迭代逻辑，并为搜索、排序、修改、比较和转换数据等任务提供了干净、定制化的操作。

C++ 算法常见问题解答

1) C++ 中 `` 头文件的目的是什么？

在 C++ 中，`` 头文件提供了一系列预定义的函数，用于排序、搜索、计数和修改等操作。这些函数通过可重用逻辑替换手动编码，从而简化了代码。它们使用迭代器与容器广泛协作。它提高了 C++ 编程的可读性、效率和抽象性。

2) C++ 算法函数是否适用于所有类型的容器？

是的，算法函数操作于迭代器，而不是直接操作容器，因此它们可以与任何支持迭代器的 STL 容器一起使用，例如向量、列表，甚至是原始数组。这使得任务非常灵活。唯一的限制是某些算法需要特定的迭代器类型（例如，sort 需要随机访问迭代器）。

3) `std::sort()` 和 `std::stable_sort()` 之间有什么区别？

在 C++ 中，`std::sort()` 函数快速地对元素进行排序和重新排列，但不保留相等元素的原始顺序。另一方面，`std::stable_sort()` 在其原始相对位置上保持相等元素，这使得在有意义时顺序非常合适。虽然 `sort` 更高效，但 `stable_sort` 可确保在多级排序场景下的稳定性。

4) 算法函数如何通过谓词或 lambda 支持自定义逻辑？

许多算法接受一个自定义参数，称为谓词，它可以是函数指针、函数对象或 lambda 表达式。这允许函数在操作（如过滤、排序和搜索）期间应用用户定义的参数。Lambda 表达式被广泛用于编写简洁的内联逻辑。它使得 C++ 中的编程风格更具表现力和函数式。

5) 算法函数是否比手动循环更有效，为什么？

是的，算法函数通常比手动编写的循环更通用且更可靠。它们是 STL 的一部分，并受益于多年的测试和性能调优。它们使代码更易于理解，并且不易出错。开发人员不是专注于如何迭代，而是专注于要实现什么，从而使代码更具声明性。

下一主题C++ 面试题及答案

C++ 算法函数

算法类型

非修改算法

修改算法

C++ 算法的成员函数

标准非修改序列算法

C++ 非修改序列操作示例

示例

修改序列操作

C++ 修改序列操作示例

示例

分区

C++ 分区操作示例

示例

排序

C++ 排序操作示例

示例

二分搜索

C++ 二分查找操作示例

示例

合并

合并

C++ 合并操作示例

示例

堆

C++ 堆操作示例

示例

最小值/最大值

C++ 最小值/最大值操作示例

示例

其他函数

C++ 算法函数的关键特性

结论

C++ 算法常见问题解答

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 算法函数

算法类型

非修改算法

修改算法

C++ 算法的成员函数

标准非修改序列算法

C++ 非修改序列操作示例

示例

修改序列操作

C++ 修改序列操作示例

示例

分区

C++ 分区操作示例

示例

排序

C++ 排序操作示例

示例

二分搜索

C++ 二分查找操作示例

示例

合并

合并