【C++】C++11 STL算法(一)：非修改序列操作（Non-modifying sequence operations）

头文件：#include <algorithm>

一、all_of、any_of、none_of：

1、官方说明

检查谓词对于范围中的所有元素、任一元素或没有这样的元素 为真（功C能模板）。

2、谓词

汉语中谓词包括动词和形容词，详解参见https://baike.baidu.com/item/%E8%B0%93%E8%AF%8D。

3、STL算法对谓词的说明

参见：https://en.cppreference.com/w/cpp/named_req/Predicate，简单的来说，就是一个返回布尔值的函数。
这三类算法函数中，都有一个模板参数：UnaryPredicate p（一元谓词）：

使用 p 测试迭代器指向的对象，逻辑结构如下：if(pred(*first)) {...}

4、谓词的五种模式

函数、函数指针、lambda表达式、函数对象、库定义的函数对象.参见博客：https://blog.csdn.net/caroline_wendy/article/details/15378055

5、all_of （C++ 11）

原型：

template< class InputIt, class UnaryPredicate >
bool all_of( InputIt first, InputIt last, UnaryPredicate p );

说明：
在[first, last)范围内的元素全都满足条件p，则返回真true；

6、any_of （C++ 11）

原型：

template< class InputIt, class UnaryPredicate >
bool any_of( InputIt first, InputIt last, UnaryPredicate p );

说明：
在[first, last)范围内至少有一个元素满足条件p，则返回真true；

7、none_of（C++ 11）

原型：

template< class InputIt, class UnaryPredicate >
bool none_of( InputIt first, InputIt last, UnaryPredicate p );

说明：
在[first, last)范围内没有一个元素满足条件p，则返回真true；

8、官方demo：

#include <vector>
#include <numeric>
#include <algorithm>
#include <iterator>
#include <iostream>
#include <functional>int main()
{std::vector<int> v(10, 2);	// {2,2,2,2,2,2,2,2,2,2}std::partial_sum(v.cbegin(), v.cend(), v.begin());	// {2,4,6,8,10,12,14,16,18,20}std::cout << "Among the numbers: ";std::copy(v.cbegin(), v.cend(), std::ostream_iterator<int>(std::cout, " "));std::cout << '\n';if (std::all_of(v.cbegin(), v.cend(), [](int i){ return i % 2 == 0; })) {	// 谓词p是lambda表达式std::cout << "All numbers are even\n";}if (std::none_of(v.cbegin(), v.cend(), std::bind(std::modulus<int>(), std::placeholders::_1, 2))) {	// 谓词p是库函数对象std::cout << "None of them are odd\n";}struct DivisibleBy{const int d;DivisibleBy(int n) : d(n) {}bool operator()(int n) const { return n % d == 0; }};if (std::any_of(v.cbegin(), v.cend(), DivisibleBy(7))) {	// 谓词p是函数对象std::cout << "At least one number is divisible by 7\n";}
}

输出:

Among the numbers: 2 4 6 8 10 12 14 16 18 20 
All numbers are even
None of them are odd
At least one number is divisible by 7

二、for_each

1、原型：

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

2 说明：

将函数f应用到[first, last)范围内的所有元素。
如果f返回结果，则忽略该结果。与其余算法不同，for_each不允许复制序列中的元素，即使它们是可复制的。

3、官方demo：

#include <vector>
#include <algorithm>
#include <iostream>struct Sum
{Sum(): sum{0} { }void operator()(int n) { sum += n; }int sum;
};int main()
{std::vector<int> nums{3, 4, 2, 8, 15, 267};auto print = [](const int& n) { std::cout << " " << n; };std::cout << "before:";std::for_each(nums.begin(), nums.end(), print);std::cout << '\n';std::for_each(nums.begin(), nums.end(), [](int &n){ n++; });// calls Sum::operator() for each numberSum s = std::for_each(nums.begin(), nums.end(), Sum());std::cout << "after: ";std::for_each(nums.begin(), nums.end(), print);std::cout << '\n';std::cout << "sum: " << s.sum << '\n';
}

Output:

before: 3 4 2 8 15 267
after:  4 5 3 9 16 268
sum: 305

三、count count_if

1、原型：

template< class InputIt, class T >
typename iterator_traits<InputIt>::difference_typecount( InputIt first, InputIt last, const T &value );template< class InputIt, class UnaryPredicate >
typename iterator_traits<InputIt>::difference_typecount_if( InputIt first, InputIt last, UnaryPredicate p );

2、说明：

返回满足特定条件的元素数量

3、官方demo

#include <algorithm>
#include <iostream>
#include <vector>int main()
{std::vector<int> v{ 1, 2, 3, 4, 4, 3, 7, 8, 9, 10 };// 返回匹配目标值target的数量int target1 = 3;int target2 = 5;int num_items1 = std::count(v.begin(), v.end(), target1);int num_items2 = std::count(v.begin(), v.end(), target2);std::cout << "number: " << target1 << " count: " << num_items1 << '\n';std::cout << "number: " << target2 << " count: " << num_items2 << '\n';// 可被3整除的数量int num_items3 = std::count_if(v.begin(), v.end(), [](int i){return i % 3 == 0;});std::cout << "number divisible by three: " << num_items3 << '\n';
}

Output:

number: 3 count: 2
number: 5 count: 0
number divisible by three: 3

四、mismatch

1、原型：

template< class InputIt1, class InputIt2 >
std::pair<InputIt1,InputIt2>mismatch( InputIt1 first1, InputIt1 last1, InputIt2 first2 );

2、说明：

找到两个范围不同的第一个位置

3、官方demo

#include <iostream>
#include <string>
#include <algorithm>std::string mirror_ends(const std::string& in)
{return std::string(in.begin(),std::mismatch(in.begin(), in.end(), in.rbegin()).first);
}int main()
{std::cout << mirror_ends("abXYZba") << '\n'<< mirror_ends("abca") << '\n'<< mirror_ends("aba") << '\n';
}

Output:

ab
a
aba

五、find、find_if、find_if_not

1、原型：

template< class InputIt, class T >
InputIt find( InputIt first, InputIt last, const T& value );template< class InputIt, class UnaryPredicate >
InputIt find_if( InputIt first, InputIt last, UnaryPredicate p );template< class InputIt, class UnaryPredicate >
InputIt find_if_not( InputIt first, InputIt last, UnaryPredicate q );

2、说明：

找到满足特定条件的第一个元素
UnaryPredicate p：参见all_of、any_of、none_of关于谓词的解释

3、官方demo

#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>int main()
{int n1 = 3;int n2 = 5;std::vector<int> v{0, 1, 2, 3, 4};auto result1 = std::find(std::begin(v), std::end(v), n1);auto result2 = std::find(std::begin(v), std::end(v), n2);if (result1 != std::end(v)) {std::cout << "v contains: " << n1 << '\n';} else {std::cout << "v does not contain: " << n1 << '\n';}if (result2 != std::end(v)) {std::cout << "v contains: " << n2 << '\n';} else {std::cout << "v does not contain: " << n2 << '\n';}
}

Output:

v contains: 3
v does not contain: 5

六、find_end

1、原型：

template< class ForwardIt1, class ForwardIt2 >
ForwardIt1 find_end( ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last );template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
ForwardIt1 find_end( ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p );

2、说明：

查找某个范围内，最后一个和序列2匹配的位置（返回该位置的迭代器）

3、官方demo

#include <algorithm>
#include <iostream>
#include <vector>int main()
{std::vector<int> v{1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4};std::vector<int>::iterator result;std::vector<int> t1{1, 2, 3};result = std::find_end(v.begin(), v.end(), t1.begin(), t1.end());if (result == v.end()) {std::cout << "sequence not found\n";} else {std::cout << "last occurrence is at: "<< std::distance(v.begin(), result) << "\n";	// std::distance 计算迭代器之间的距离}std::vector<int> t2{4, 5, 6};result = std::find_end(v.begin(), v.end(), t2.begin(), t2.end());if (result == v.end()) {std::cout << "sequence not found\n";} else {std::cout << "last occurrence is at: " << std::distance(v.begin(), result) << "\n";}
}

Output:

last occurrence is at: 8
sequence not found

七、find_first_of

1、原型：

template< class InputIt, class ForwardIt >
InputIt find_first_of( InputIt first, InputIt last, ForwardIt s_first, ForwardIt s_last );

2、说明：

搜索序列1中可以匹配序列2中任一元素的位置（迭代器）

3、官方demo

#include <algorithm>
#include <iostream>
#include <vector>int main()
{std::vector<int> v{0, 2, 3, 25, 5};std::vector<int> t{3, 19, 10, 2};auto result = std::find_first_of(v.begin(), v.end(), t.begin(), t.end());if (result == v.end()) {std::cout << "no elements of v were equal to 3, 19, 10 or 2\n";} else {std::cout << "found a match at "<< std::distance(v.begin(), result) << "\n";}}

Output:

found a match at 1

八、adjacent_find

1、原型：

template< class ForwardIt >
ForwardIt adjacent_find( ForwardIt first, ForwardIt last );template< class ForwardIt, class BinaryPredicate>
ForwardIt adjacent_find( ForwardIt first, ForwardIt last, BinaryPredicate p );

2、说明：

在[first, last)范围内搜索两个连续相同的元素。

3、官方demo

#include <algorithm>
#include <iostream>
#include <vector>
#include <functional>int main()
{std::vector<int> v1{0, 1, 2, 3, 40, 40, 41, 41, 5};auto i1 = std::adjacent_find(v1.begin(), v1.end());if (i1 == v1.end()) {std::cout << "no matching adjacent elements\n";} else {std::cout << "the first adjacent pair of equal elements at: "<< std::distance(v1.begin(), i1) << '\n';}auto i2 = std::adjacent_find(v1.begin(), v1.end(), std::greater<int>());if (i2 == v1.end()) {std::cout << "The entire vector is sorted in ascending order\n";} else {std::cout << "The last element in the non-decreasing subsequence is at: "<< std::distance(v1.begin(), i2) << '\n';}
}

Output:

The first adjacent pair of equal elements at: 4	
The last element in the non-decreasing subsequence is at: 7

九、search

1、原型：

template< class ForwardIt1, class ForwardIt2 >
ForwardIt1 search( ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last );template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
ForwardIt1 search( ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p );

2、说明：

在序列1中搜索匹配序列2的位置（迭代器）

3、官方demo

#include <string>
#include <algorithm>
#include <iostream>
#include <vector>
#include <functional>template <typename Container>
bool in_quote(const Container& cont, const std::string& s)
{return std::search(cont.begin(), cont.end(), s.begin(), s.end()) != cont.end();
}int main()
{std::string str = "why waste time learning, when ignorance is instantaneous?";// str.find() can be used as wellstd::cout << std::boolalpha << in_quote(str, "learning") << '\n'<< in_quote(str, "lemming")  << '\n';std::vector<char> vec(str.begin(), str.end());std::cout << std::boolalpha << in_quote(vec, "learning") << '\n'<< in_quote(vec, "lemming")  << '\n';
}

Output:

true
false
true
false

十、search_n

1、原型：

template< class ForwardIt, class Size, class T >
ForwardIt search_n( ForwardIt first, ForwardIt last, Size count, const T& value );template< class ForwardIt, class Size, class T, class BinaryPredicate >
ForwardIt search_n( ForwardIt first, ForwardIt last, Size count, const T& value, BinaryPredicate p );

2、说明：

在给定范围内搜索多个连续元素的位置（迭代器）

3、官方demo

#include <iostream>
#include <algorithm>
#include <iterator>template <class Container, class Size, class T>
bool consecutive_values(const Container& c, Size count, const T& v)
{return std::search_n(std::begin(c),std::end(c),count,v) != std::end(c);
}int main()
{const char sequence[] = "1001010100010101001010101";std::cout << std::boolalpha;std::cout << "Has 4 consecutive zeros: "<< consecutive_values(sequence,4,'0') << '\n';std::cout << "Has 3 consecutive zeros: "<< consecutive_values(sequence,3,'0') << '\n';
}

Output:

Has 4 consecutive zeros: false
Has 3 consecutive zeros: true