STL算法

STL算法

STL算法由头文件, 和 组成的。

其中****：这是STL中最大的头文件，包括了各种常用算法，如：比较，交换，查找，遍历，复制，修改，排序等相关操作。

这个头文件相对较小，他主要包括了序列上进行数学运算法的模板函数。如：累积，内积，部分和，相邻差异等。

这个头文件定义了一些模板类，用于声明函数对象（也称为仿函数）。这些函数对象经常用于STL算法中，特别是那些需要自定义比较或操作的算法。如：比较，逻辑操作等。

常用遍历算法

for_each

for_each它允许将给定函数或可调用对象应用于范围中的每个函数。也就是说它会遍历集合中每一个元素，然后执行你需要的操作。

for_each的函数模板

template<class InputIt, class UnaryFunction>
unaryFuction for_each(InputIt first, InputIt last, UnaryFunction f);
1
2

InputIt: 元素范围开头和结尾的输入迭代器类型。

UnaryFunction: 一元函数的类型。

返回值是函数将可调用对象f应用到范围中的每个元素后返回。

我将介绍一下for_each的基本实现

template<typename Iterator, typename Func>
void My_for_each(Iterator begin, Iterator end, Func f){
    while(begin != end){
        f(*begin);
        ++begin;
    }
}
1
2
3
4
5
6
7

下面是用My_for_each调用函数的操作。

#include
#include

using namespace std;

template<typename Iterator, typename Func>
void My_for_each(Iterator begin, Iterator end, Func f){
    while(begin != end){
        f(*begin);
        ++begin;
    }
}

class PrintDouble{
public:
    void operator()(int i) const{
        cout<< i * 2<<" ";
    }
};

int main(){
    vector<int> number = {1,2,3,4,5};
    My_for_each(number.begin(), number.end(),[](int n){
        cout<< n <<" ";
    });

    cout<<endl;
    
    My_for_each(number.begin(), number.end(), PrintDouble());

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

Note：

One interesting thing to note about for_each is that the function or callable can have side effects. Meaning , they can change the state of objects outside of their own scope.

Beside,the returned function object (f) can be used after the for_each call, especially if it maintains a state. For example, if you want to count occurrences of a certain condition, the callable object can keep a counter which will be available after the execution of for_each.

transform

transform与for_each的算法操作类似，它是对给定范围内的每个元素应用指定操作，并且将结果储存在另一个范围中。

transform的函数模板如下，

template<class InputIterator, class OutputIterator, class UnaryOperation>
OutputIterator transform(InputIterator first1, InputIterator last1, OutputIterator result, UnaryOperation op){
    while(first1 != last1){
        *result = op(*first1);
        ++result;
        ++first1;
    }
    return result;
}
1
2
3
4
5
6
7
8
9

其中result是一个迭代器，指向存储转换后的值的目标范围的开头。

下面是一个简单示例：

#include 
#include 
#include 

using namespace std;

int main() {
    vector<int> input = {1, 2, 3, 4, 5};
    vector<int> output(input.size());

    // Use std::transform to double each element in input and store in output
    transform(input.begin(), input.end(), output.begin(), [](int x) {
        return x * 2;
    });

    // Print the transformed values in output
    for (int val : output) {
        cout << val << " ";
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

常用查找算法

find

在给定的范围内查找指定的元素。如果找到，返回指定第一个匹配元素的迭代器；否则返回范围的末尾。

vector<int> v = {1, 2, 3, 4, 5};
auto it = find(v.begin(), v.end(), 3);
if (it != v.end()) {
    cout << "Found the value: " << *it << endl;
} else {
    cout << "Value not found." << endl;
}
1
2
3
4
5
6
7

find_if

在给定的范围内查找满足特定条件的第一个元素。

vector<int> v = {1, 2, 3, 4, 5};
auto it = find_if(v.begin(), v.end(), [](int x){ return x > 3; });
if (it != v.end()) {
    cout << "First value greater than 3: " << *it << endl;
} else {
    cout << "No values found greater than 3." << endl;
}
1
2
3
4
5
6
7

adjacent_find

在给定的范围内查找第一对相邻的匹配元素。

vector<int> v = {1, 2, 3, 3, 4};
auto it = adjacent_find(v.begin(), v.end());
if (it != v.end()) {
    cout << "Found adjacent value: " << *it << endl;
} else {
    cout << "No adjacent matching values found." << endl;
}
1
2
3
4
5
6
7

binary_search

在一个排序的范围内使用二分查找法检查一个元素是否存在。返回一个bool值，表示元素是否存在。

vector<int> v = {1, 2, 3, 4, 5};
if (binary_search(v.begin(), v.end(), 3)) {
    cout << "Value 3 exists." << endl;
} else {
    cout << "Value 3 does not exist." << endl;
}
1
2
3
4
5
6

count

在给定的范围内统计指定元素的出现次数

vector<int> v = {1, 2, 3, 4, 5, 3};
int num = count(v.begin(), v.end(), 3);
cout << "Number 3 appears " << num << " times." << endl;

1
2
3
4

count_if

在给定的范围内统计满足特定条件的元素的数量

int num = count_if(v.begin(), v.end(), [](int x){ return x > 3; });
cout << "Number of values greater than 3: " << num << endl;
1
2

常用排序算法

sort

对给定范围内的元素进行排序。

默认按升序排序。如果想要降序或者其他类型排序，可以提供自定义的比较函数

 vector<int> v = {4,5,8,55,7,2,1,9};
    sort(v.begin(), v.end());
    for_each(v.begin(), v.end(), [](int x){cout << x << " ";});
    cout << endl;
    // 降序
    sort(v.begin(), v.end(), [](int x, int y){return x > y;});
    for_each(v.begin(), v.end(), [](int x){cout << x << " ";});
1
2
3
4
5
6
7

random_shuffle

对给定范围的元素进行随机重新排列。（在c++17中这个函数已经被shuffle取代。）

#include 
#include 
#include 
#include 
using namespace std;

vector<int> v = {1, 2, 3, 4, 5};
srand(time(nullptr));  // 设置随机数种子
random_shuffle(v.begin(), v.end());
for (int i : v) {
    cout << i << " ";
} // 输出可能为: 3 5 1 4 2
1
2
3
4
5
6
7
8
9
10
11
12

merge

合并两个已排序的范围，并存储到另一个容器内。

#include 
#include 
using namespace std;

vector<int> a = {1, 3, 5};
vector<int> b = {2, 4, 6};
vector<int> result(a.size() + b.size());

merge(a.begin(), a.end(), b.begin(), b.end(), result.begin());
for (int i : result) {
    cout << i << " ";
} // 输出: 1 2 3 4 5 6
1
2
3
4
5
6
7
8
9
10
11
12

reverse

反转给定范围的元素。

vector<int> v = {1, 2, 3, 4, 5};
reverse(v.begin(), v.end());
for (int i : v) {
    cout << i << " ";
} // 输出: 5 4 3 2 1
1
2
3
4
5

常用拷贝和替换函数

copy

将一个容器内的指定范围的元素拷贝到另一个容器中。

vector<int> source = {1, 2, 3, 4, 5};
vector<int> destination(source.size());

copy(source.begin(), source.end(), destination.begin());
for (int i : destination) {
    cout << i << " ";
} // 输出: 1 2 3 4 5
1
2
3
4
5
6
7

replace

将容器内指定范围的旧元素替换为新元素。

vector<int> v = {1, 2, 3, 4, 3};
replace(v.begin(), v.end(), 3, 99);
for (int i : v) {
    cout << i << " ";
} // 输出: 1 2 99 4 99
1
2
3
4
5

replace_if

将容器内指定范围满足条件的元素替换为新元素。

vector<int> v = {1, 2, 3, 4, 5};
replace_if(v.begin(), v.end(), [](int n) { return n > 3; }, 99);
for (int i : v) {
    cout << i << " ";
} // 输出: 1 2 3 99 99
1
2
3
4
5

swap

交换两个容器（或两个元素）的内容。

vector<int> a = {1, 2, 3};
vector<int> b = {4, 5, 6};

swap(a, b);
for (int i : a) {
    cout << i << " ";
} // 输出: 4 5 6

for (int i : b) {
    cout << i << " ";
} // 输出: 1 2 3
1
2
3
4
5
6
7
8
9
10
11

常用算法生成算法

accumulate

计算给定范围内元素的累计总和

函数原型：accumulate(iterator beg, iterator end, value);

其中value是起始值

#include 
#include 
using namespace std;

vector<int> v = {1, 2, 3, 4, 5};
int sum = accumulate(v.begin(), v.end(), 0);
cout << sum; // 输出: 15
1
2
3
4
5
6
7

备注: accumulate也可以用来进行其他二元操作，例如累乘，但这需要提供一个自定义的二元函数。

fill

为容器内指定范围的所有元素设置一个新的值。

#include 
#include 
using namespace std;

vector<int> v(5);  // 创建一个大小为5的vector，所有元素默认初始化为0
fill(v.begin(), v.end(), 42);
for (int i : v) {
    cout << i << " ";
} // 输出: 42 42 42 42 42
1
2
3
4
5
6
7
8
9

备注: 虽然fill被定义在中，但是与accumulate一样，它也可以被看作是一个算术生成算法。

常用集合算法

set_intersection

求两个已排序的范围的交集。

函数原形：

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
                                InputIterator2 first2, InputIterator2 last2,
                                OutputIterator result);
1
2
3
4

result是目标容器的开始迭代器

#include 
#include 
using namespace std;

vector<int> a = {1, 2, 3, 4, 5};
vector<int> b = {4, 5, 6, 7, 8};
vector<int> intersection;

set_intersection(a.begin(), a.end(), b.begin(), b.end(), back_inserter(intersection));

for (int i : intersection) {
    cout << i << " ";
} // 输出: 4 5
1
2
3
4
5
6
7
8
9
10
11
12
13

注意: 输入范围必须是已排序的。输出不会自动删除重复元素。

set_union

求两个已排序的范围的并集。

vector<int> a = {1, 2, 3, 4};
vector<int> b = {3, 4, 5, 6};
vector<int> union_result;

set_union(a.begin(), a.end(), b.begin(), b.end(), back_inserter(union_result));

for (int i : union_result) {
    cout << i << " ";
} // 输出: 1 2 3 4 5 6
1
2
3
4
5
6
7
8
9

set_difference

求两个已排序的范围的差集（即第一个范围中存在但第二个范围中不存在的元素）。

vector<int> a = {1, 2, 3, 4, 5};
vector<int> b = {4, 5, 6, 7, 8};
vector<int> difference;

set_difference(a.begin(), a.end(), b.begin(), b.end(), back_inserter(difference));

for (int i : difference) {
    cout << i << " ";
} // 输出: 1 2 3
1
2
3
4
5
6
7
8
9