C++ 算法

在 C++ 中，标准模板库 (STL) 提供了一组丰富的算法，可用于执行诸如排序、搜索和操作容器（如数组、向量等）的元素等操作。

可以使用 <algorithm> 头文件访问这些算法。

#include <algorithm>

常用算法

C++ 中的 <algorithm> 库提供了许多有用的函数。以下是一些最常用的函数。

注意：我们将使用向量来理解所有这些函数的工作原理。但是，这些函数也适用于其他 STL 容器。

示例 1：将向量按升序排序

要将向量按升序排序，我们可以使用 sort() 函数。其语法是

sort( first, last);

这里，

• first - 指定排序范围开始处的迭代器（包含）
• last - 指定排序范围结束处的迭代器（不包含）

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

int main() {

    vector<int> vec = {4, 2, 3, 1, 5};

    //sort the elements of the vector
    sort(vec.begin(), vec.end());

    for(int num : vec) {
        cout << num << " ";
    }

    return 0;
}

输出

1 2 3 4 5 

在这里，我们使用 vec.begin() 指定了向量的开始排序范围，并使用 vec.end() 指定了向量的结束排序范围。

这将按升序对我们的向量进行排序。

示例 2：复制向量元素

我们使用 copy() 函数将给定范围的元素从一个向量复制到另一个向量。其语法是

copy(first, last, result);

这里，

• first - 指定要复制的范围开始处的迭代器（包含）
• last - 指定要复制的范围结束处的迭代器（不包含）
• result - 指定目标向量中元素将被复制到的位置的迭代器

例如，

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

int main() {

    vector<int> source = {1, 2, 3, 4, 5};

    // create destination vector of size 5
    vector<int> destination(5);
    
    // copy the contents of source to destination
    copy(source.begin(), source.end(), destination.begin());

    // print elements of destination vector
    for(int num : destination) {
        cout << num << " ";
    }

    return 0;
}

输出

1 2 3 4 5 

在这里，我们创建了包含五个元素的 source 和一个大小为 5 的空向量 destination。

然后，我们使用 copy() 函数将 source 的内容复制到 destination。

示例 3：移动向量元素

我们可以使用 move() 函数将元素从一个向量移动到另一个向量。其语法是

move(first, last, result);

例如，

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

int main() {

    vector<string> source = {"apple", "banana", "cherry"};
    vector<string> destination(3);

    cout << "Before move:" << endl;
    cout << "source: ";

    for(const string& str : source) {
        cout << str << " ";
    }
    cout << endl;

    cout << "destination: ";
    for(const string& str : destination) {
        cout << str << " ";
    }
    cout << endl;

    // perform the move operation
    move(source.begin(), source.end(), destination.begin());

    cout << "After move:" << endl;
    cout << "source: ";
    for(const string& str : source) {
        cout << str << " ";
    }
    cout << endl;

    cout << "destination: ";
    for(const string& str : destination) {
        cout << str << " ";
    }
    cout << endl;

    return 0;
}

输出

Before move:
source: apple banana cherry 
destination:    
After move:
source:    
destination: apple banana cherry 

示例 4：交换两个向量的内容

我们可以使用 swap() 函数交换两个 STL 向量的内容。其语法是

swap(x, y);

在这里，x 和 y 是需要交换其内容的容器。

例如，

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

int main() {

    vector<int> vec1 = {1, 2, 3};
    vector<int> vec2 = {4, 5, 6};

    // print vec1 and vec2 before swap
    cout << "Before swap:" << endl;
    cout << "vec1: ";
    for(int num : vec1) {
        cout << num << " ";
    }
    cout << endl;

    cout << "vec2: ";
    for(int num : vec2) {
        cout << num << " ";
    }
    cout << endl;

    // swap vec1 and vec2
    swap(vec1, vec2);

    // print vec1 and vec2 after swap
    cout << "After swap:" << endl;
    cout << "vec1: ";
    for(int num : vec1) {
        cout << num << " ";
    }
    cout << endl;

    cout << "vec2: ";
    for(int num : vec2) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

输出

Before swap:
vec1: 1 2 3 
vec2: 4 5 6 
After swap:
vec1: 4 5 6 
vec2: 1 2 3 

示例 5：合并两个向量

我们可以使用 merge() 函数合并两个 STL 容器。其语法是

merge(first1, last1, first2,  last2, result);

这里，

• first1, last1 - 指定第一个输入范围的迭代器。
• first2, last2 - 指定第二个输入范围的迭代器。
• result - 指定目标范围开始处的迭代器。

例如，

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

int main() {

    vector<int> vec1 = {1, 3, 5};
    vector<int> vec2 = {2, 4, 6};
    vector<int> result(6);

    // vec1 and vec2 before merge
    cout << "Before merge:" << endl;
    cout << "vec1: ";
    for(int num : vec1) {
        cout << num << " ";
    }
    cout << endl;

    cout << "vec2: ";
    for(int num : vec2) {
        cout << num << " ";
    }
    cout << endl;

    // perform merge operation
    merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin());

    // output result after merge
    cout << "After merge:" << endl;
    cout << "result: ";
    for(int num : result) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

输出

Before merge:
vec1: 1 3 5 
vec2: 2 4 6 
After merge:
result: 1 2 3 4 5 6 

请注意，合并后的向量将按排序顺序返回。

示例 6：替换向量元素

我们可以使用 replace() 函数将 STL 容器中某个元素的所有出现项替换为另一个元素。其语法是

replace(first, last, old_value, new_value);

这里，

• first, last - 指定要转换的范围的迭代器。
• old_value - 要替换的值。
• new_value - 替换值。

例如，

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

int main() {

    vector<int> vec = {4, 2, 3, 2, 5};

    // display the vector before replacement
    cout << "Before: ";
    for(int num : vec) {
        cout << num << " ";
    }
    cout << endl;

    // replace 2 with 99
    replace(vec.begin(), vec.end(), 2, 99);

    // display the vector after replacement
    cout << "After: ";
    for(int num : vec) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

输出

Before: 4 2 3 2 5 
After: 4 99 3 99 5 

在这里，我们将所有出现的 2 替换为 99。

示例 7：从给定范围内删除值

我们可以使用 remove() 函数从给定范围内删除某个值的第一次出现。其语法是

remove(first, last, val);

这里，

• first, last - 指定要转换的范围的迭代器
• val - 要删除的值

例如，

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

int main() {

    vector<int> vec = {4, 2, 3, 2, 5};

    // print the vector before deletion
    cout << "Before deletion: ";
    for(int num : vec) {
        cout << num << " ";
    }
    cout << endl;

    // remove the first occurrence of 2
    remove(vec.begin(), vec.end(), 2);

    // print the vector after deletion
    cout << "After deletion: ";
    for(int num : vec) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

输出

Before deletion: 4 2 3 2 5 
After deletion: 4 3 5 2 5