【STL十八】算法——不修改序列的操作（for_each、count、find、equal、search）

• 前言：在前面我们讲解容器和函数对象时，都刻意的回避了算法，在此，我们单独分一篇文章，来讲解下stl提供的算法。

一、简介

STL算法部分主要是由三个头文件承担： algorithm、numeric、functional

• algorithm：意思是算法，只要想使用STL库中的算法函数就得包含该头文件。
• numeric：包含了一系列用于计算数值序列的算法，其具有一定的灵活性，也能够适用于部分非数值序列的计算
• functional：定义了一些模板，可以用来声明函数对象。

本文，我们讲解下algorithm提供的算法。

二、头文件

#include <algorithm>

三、分类

根据网站https://www.apiref.com/cpp-zh/cpp/header.html显示，头文件<algorithm>提供的算法如下图。

• 常用的分类
  • 不修改序列的操作
  • 修改序列的操作
  • 排序操作
  • 集合操作

四、不修改序列的操作

项目	Value
for_each()	在范围的每个元素上应用提供的函数。
count()	返回范围内值的出现次数。
count_if()	返回满足条件的范围的值的出现次数。
find()	查找元素的第一个匹配项。
find_if()	查找满足条件的元素的第一个匹配项。
equal()	测试两组元素是否相等。 两组的大小不必相等。
search()	用于在序列 A 中查找序列 B 第一次出现的位置。

1、for_each

for_each在容器中的使用

• 普通函数
• 仿函数（函数对象）
• lambda表达式

// C++98
template <class InputIterator, class Function>
Function for_each (InputIterator first, InputIterator last, Function fn);

参数 (Parameters)
first - 将迭代器输入到初始位置。
last - 最终位置的最终迭代器。
fn - 接受范围内元素作为参数的一元函数。


返回值
返回函数fn 。

• demo

// for_each example
#include <iostream> 
#include <algorithm>  
#include <vector>  

// 普通函数
void myfunction(int i) { 
	std::cout << ' ' << i;
}

// 函数对象
class FunctionObject {  
public:
	void operator() (int i) 
	{ 
		std::cout << ' ' << i; 
	}
} ;

// lamdba表达式
auto f = [](int i)
{
	std::cout << ' ' << i;
};

int main() {
	std::vector<int> myvector = {1,3,5};

	//给 for_each 传递一个函数
	std::cout << "myvector contains:";
	for_each(myvector.begin(), myvector.end(), myfunction);  
	std::cout << '\n';

	//给 for_each 传递一个函数对象
	std::cout << "myvector contains:";
	FunctionObject fo;
	for_each(myvector.begin(), myvector.end(), fo);  
	std::cout << '\n';

	// 给 for_each 传递一个lamdba
	std::cout << "myvector contains:";
	for_each(myvector.begin(), myvector.end(), f); 
	std::cout << '\n';

	return 0;
}

输出

myvector contains: 1 3 5
myvector contains: 1 3 5
myvector contains: 1 3 5

2、count、count_if

• count

//C++98
template <class InputIterator, class T>
typename iterator_traits<InputIterator>::difference_type
count (InputIterator first, InputIterator last, const T& val);

参数 (Parameters)
first - 将迭代器输入到搜索序列的初始位置。
last - 将迭代器输入到搜索序列的最终位置。
val - 要在范围内搜索的值。


返回值
返回第一个到最后一个范围内的元素数。

• count_if

// C++98
template <class InputIterator, class Predicate>
typename iterator_traits<InputIterator>::difference_type
count_if (InputIterator first, InputIterator last, UnaryPredicate pred);

参数 (Parameters)
first - 将迭代器输入到搜索序列的初始位置。
last - 将迭代器输入到搜索序列的最终位置。
pred - 一元谓词，它接受一个参数并返回bool。


返回值
返回pred返回true的范围内的元素数。

• demo

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

bool mygreater(int n) {
	return (n > 3);
}

int main(void) {
	vector<int> v = { 1, 3, 3, 3, 3 , 4, 5};

	// count
	int cnt;
	cnt = count(v.begin(), v.end(), 3);
	cout << "Number 3 occurs " << cnt << " times." << endl;

	// count_if
	int cnt2;
	cnt2 = count_if(v.begin(), v.end(), mygreater);
	cout << "There are " << cnt2 << " numbers are greater that 3." << endl;
	
	return 0;
}

输出

Number 3 occurs 4 times.
There are 2 numbers are greater that 3.

3、find、find_if

• 模板及参数请参考cout、count_if

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

bool unary_pre(int n) {
    return ((n % 2) == 0);
}

int main(void) {
    int val = 5;
    vector<int> v = { 1, 2, 3, 4, 5 };
    auto result = find(v.begin(), v.end(), val);
    if (result != end(v))
        cout << "Vector contains element " << val << endl;
    
    auto it = find_if(v.begin(), v.end(), unary_pre);
    if (it != end(v))
        cout << "First even number is " << *it << endl;

    return 0;
}

输出

Vector contains element 5
First even number is 2

4、euqal

• 3 个输入迭代器参数，前两个参数是第一个序列的开始和结束迭代器，第三个参数是第二个序列的开始迭代器。
• 如果第二个序列中包含的元素少于第一个序列，结果是未定义的。 第2个长度要大于第1个的。
• 4 个参数：第一个序列的开始和结束迭代器，第二个序列的开始和结束迭代器，如果两个序列的长度不同，那么结果总是为 false。本节会演示这两个版本，但推荐使用接受 4 个参数的版本，因为它不会产生未定义的行为。
• demo

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void) {
    vector<int> v1 = { 1, 2, 3, 4, 5 };
    vector<int> v2 = { 2, 3, 4, 5, 6};

    bool result;
    result = equal(v1.begin(), v1.end(), v2.begin());
    if (result == false)
        cout << "Vector range is not equal." << endl;

    result = equal(v1.begin()+1, v1.end(), v2.begin());
    if (result == true)
        cout << "Vector range is equal." << endl;

    result = equal(v1.begin() + 1, v1.end(), v2.begin(),v2.end());
    if (result == false)
        cout << "Vector range is not equal." << endl;

    result = equal(v1.begin() + 1, v1.end(), v2.begin(), v2.end()-1);
    if (result == true)
        cout << "Vector range is equal." << endl;
    return 0;
}

输出

Vector range is not equal.
Vector range is equal.
Vector range is not equal.
Vector range is equal.

• 第1条语句中，两个序列的第一个元素直接就不匹配，所以结果为 false。
• 第 2条语句的输出为 true，因为 v1 的第二个元素到最后一个元素都从 v2 的第一个元素开始匹配。第二个序列的元素个数比第一个序列的元素个数多 1，但 第一个序列的元素个数决定了比较多少个对应的元素。
• 第3条语句的输出为 false，因为序列是不同的。这条语句不同于前面的 equal() 调用，因为指定了第二个序列的结束迭代器。
• 第4 条语句会从 v1 的第二个元素开始，与 v2 从第一个元素开始比较相同个数的元素，所以输出为 true。

5、search

• find_end() 函数用于在序列 A 中查找序列 B 最后一次出现的位置。那么，如果想知道序列 B 在序列 A 中第一次出现的位置，该如何实现呢？可以借助 search() 函数。

• search() 函数其功能恰好和 find_end() 函数相反，用于在序列 A 中查找序列 B 第一次出现的位置

#include <iostream> 
#include <vector> 
#include <algorithm> 
using namespace std;
int main()
{
    int i, j;

    // Declaring the sequence to be searched into 
    vector<int> v1 = { 1, 2, 3, 4, 5, 6, 7 };

    // Declaring the subsequence to be searched for 
    vector<int> v2 = { 3, 4, 5 };

    // Declaring an iterator for storing the returning pointer 
    vector<int>::iterator i1;

    // Using std::search and storing the result in 
    // iterator i1 
    i1 = std::search(v1.begin(), v1.end(), v2.begin(), v2.end());

    // checking if iterator i1 contains end pointer of v1 or not 
    if (i1 != v1.end()) {
        cout << "vector2 is present at index " << (i1 - v1.begin()) << endl;
    }
    else {
        cout << "vector2 is not present in vector1" << endl;
    }


    // Declaring the subsequence to be searched for 
    vector<int> v3 = { 3, 4, 6 };
    vector<int>::iterator i2;
    i2 = std::search(v1.begin(), v1.end(), v3.begin(), v3.end());
    if (i2 != v1.end()) {
        cout << "vector3 is present at index " << (i2 - v1.begin()) << endl;
    }
    else {
        cout << "vector3 is not present in vector1" << endl;
    }

    return 0;
}

输出

vector2 is present at index 2
vector3 is not present in vector1

• 也可以使用函数对象;(二元谓词)

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

// Defining the BinaryPredicate function 
bool pred(int i, int j)
{
    cout << i << ";" << j<< endl;
    if (i > j) {
        return 1;
        
    }
    else {
        return 0;
    }
}

int main()
{
    int i, j;

    // Declaring the sequence to be searched into 
    vector<int> v1 = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

    // Declaring the subsequence to be compared to based 
    // on predicate 
    vector<int> v2 = { 2, 3, 6 };

    // Declaring an iterator for storing the returning pointer 
    vector<int>::iterator i1;

    // Using std::search and storing the result in 
    // iterator i1 based on predicate pred 
    i1 = std::search(v1.begin(), v1.end(), v2.begin(), v2.end(), pred);

    cout << *i1 <<endl;

    // checking if iterator i1 contains end pointer of v1 or not 
    if (i1 != v1.end()) {
        cout << "vector1 elements are greater than vector2 starting "
            << "from position " << (i1 - v1.begin());
    }
    else {
        cout << "vector1 elements are not greater than vector2 "
            << "elements consecutively.";
    }

    return 0;
}

输出

1;2
2;2
3;2
4;3
5;6
4;2
5;3
6;6
5;2
6;3
7;6
5
vector1 elements are greater than vector2 starting from position 4

说明

• vector，v1中的{5，6，7}，第一次出现比v2中的{ 2, 3, 6 }大

参考
1、C++ STL 容器库 中文文档
2、STL教程：C++ STL快速入门
3、https://www.apiref.com/cpp-zh/cpp/header.html
4、https://en.cppreference.com/w/cpp/header
5、WIKI教程_C ++标准库_C++ Library - <algorithm>