首页 > 代码库 > STL (13) 非变动型算法
STL (13) 非变动型算法
STL (13) 非变动型算法
- algorithm是“算法”必须的头文件。
- Non-modifying sequence operations (非变动式算法):算法过后,容器内部数据不发生改变。
all_of
Test condition on all elements in range (function template )
any_of
Test if any element in range fulfills condition (function template )
none_of
Test if no elements fulfill condition (function template )
for_each
Apply function to range (function template )
find
Find value in range (function template )
find_if
Find element in range (function template )
find_if_not
Find element in range (negative condition) (function template )
find_end
Find last subsequence in range (function template )
find_first_of
Find element from set in range (function template )
adjacent_find
Find equal adjacent elements in range (function template )
count
Count appearances of value in range (function template )
count_if
Return number of elements in range satisfying condition (function template )
mismatch
Return first position where two ranges differ (function template )
equal
Test whether the elements in two ranges are equal (function template )
is_permutation
Test whether range is permutation of another (function template )
search
Search range for subsequence (function template )
search_n
Search range for elements (function template ) - all_of
Test condition on all elements in range (function template )
测试范围内所有元素的条件(函数模板)??? - 观察本质
- cplusplus页面上的范例
template<class InputIterator, class UnaryPredicate>
bool all_of (InputIterator first, InputIterator last, UnaryPredicate pred)
{
while (first!=last) {
if (!pred(*first)) return false;
++first;
}
return true;
}
---------------------------------------------------------
// all_of example
#include <iostream> // std::cout
#include <algorithm> // std::all_of
#include <array> // std::array
int main () {
std::array<int,8> foo = {3,5,7,11,13,17,19,23};
if ( std::all_of(foo.begin(), foo.end(), [](int i){return i%2;}) )
std::cout << "All the elements are odd numbers.\n";
return 0;
}???
------------------------------------------------------
Output:
All the elements are odd numbers.?
解释:
1. [](int i){return i%2;})??? 这里表示一个匿名函数,C++11专属
2. 些算法效率比较高:因为不是全部判断,只要其中有一个不符合,就返回false了。?
?? - vs2015中代码如下:
// TEMPLATE FUNCTION all_of
template<class _InIt,class _Pr> inline
bool _All_of_unchecked(_InIt _First, _InIt _Last, _Pr& _Pred)
{ // test if all elements satisfy _Pred
for (; _First != _Last; ++_First)
if (!_Pred(*_First))
return (false);
return (true);
}???? - all_of使用场景是很多的,它能帮我们判断容器内数据,是否符合我们的要求。
- any_of Test if any element in range fulfills condition (function template )
- 观察本质
- 与all_of成对出现,all_of是判断是否全部符合,any_of则是判断是否有一个符合。
- 示例:
template<class InputIterator, class UnaryPredicate>
bool any_of (InputIterator first, InputIterator last, UnaryPredicate pred)
{
while (first!=last) {
if (pred(*first)) return true;
++first;
}
return false;
}
----------------------------------------------------------
??// any_of example
#include <iostream> // std::cout
#include <algorithm> // std::any_of
#include <array> // std::array
int main () {
std::array<int,7> foo = {0,1,-1,3,-3,5,-5};
if ( std::any_of(foo.begin(), foo.end(), [](int i){return i<0;}) )
std::cout << "There are negative elements in the range.\n";
return 0;
}
--------------------------------------------------------------------
Output:
There are negative elements in the range.
解释:测试如果有一个元素满足条件
????
???? - none_of Test if no elements fulfill condition (function template ) 如果没有元素满足条件
- 观察本质
- 示例
template<class InputIterator, class UnaryPredicate>
bool none_of (InputIterator first, InputIterator last, UnaryPredicate pred)
{
while (first!=last) {
if (pred(*first)) return false;
++first;
}
return true;
}
---------------------------------------------------------
??
// none_of example
#include <iostream> // std::cout
#include <algorithm> // std::none_of
#include <array> // std::array
int main () {
std::array<int,8> foo = {1,2,4,8,16,32,64,128};
if ( std::none_of(foo.begin(), foo.end(), [](int i){return i<0;}) )
std::cout << "There are no negative elements in the range.\n";
return 0;
}
-------------------------------------------------------------
Output:
There are no negative elements in the range.?????
解释:测试如果没有元素满足条件
?
???? - for_each Apply function to range (function template ) 将函数应用到范围
- 观察本质
template<class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function fn)
{
while (first!=last) {
fn (*first);
++first;
}
return fn; // or, since C++11: return move(fn);
}
-------------------------------------------
??// for_each example
#include <iostream> // std::cout
#include <algorithm> // std::for_each
#include <vector> // std::vector
void myfunction (int i) { // function:
std::cout << ‘ ‘ << i;
}
struct myclass { // function object type:
void operator() (int i) {std::cout << ‘ ‘ << i;}
} myobject;
int main () {
std::vector<int> myvector;
myvector.push_back(10);
myvector.push_back(20);
myvector.push_back(30);
std::cout << "myvector contains:";
for_each (myvector.begin(), myvector.end(), myfunction);
std::cout << ‘\n‘;
// or:
std::cout << "myvector contains:";
for_each (myvector.begin(), myvector.end(), myobject);
std::cout << ‘\n‘;
return 0;
}
----------------------------------------------------------------------
Output:
myvector contains: 10 20 30
myvector contains: 10 20 30????
解释:??要注意C++98 与C++11返回值的不同。
C++11:Returns fn, as if calling std::move(fn).
C++98:Returns fn.???
??? - find Find value in range (function template ) 在范围内查找值
- 观察本质:找到了,直接返回找到的值,没找到,返回last。(有效空间的后面位置)
template<class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val)
{
while (first!=last) {
if (*first==val) return first;
++first;
}
return last; //返回有效区间+1的位置
}
-------------------------------------------------------------------------------
// find example
#include <iostream> // std::cout
#include <algorithm> // std::find
#include <vector> // std::vector
int main () {
// using std::find with array and pointer:
int myints[] = { 10, 20, 30, 40 };
int * p;
p = std::find (myints, myints+4, 30);
if (p != myints+4)
std::cout << "Element found in myints: " << *p << ‘\n‘;
else
std::cout << "Element not found in myints\n";
// using std::find with vector and iterator:
std::vector<int> myvector (myints,myints+4); //这里要注意,myints+4是有效区间+1的位置。
std::vector<int>::iterator it;
it = find (myvector.begin(), myvector.end(), 30);
if (it != myvector.end())
std::cout << "Element found in myvector: " << *it << ‘\n‘;
else
std::cout << "Element not found in myvector\n";
return 0;
}
---------------------------------------------------------------------------------
???????Output:
Element found in myints: 30
Element found in myvector: 30
解释:???查找值需要“operator==”支持
if (*first==val) return first; 核心代码:如果*first与val是相等的,返回first.?
------------------------vs2015代码----------------------------------
template<class _InIt,
class _Ty> inline
_InIt _Find_unchecked1(_InIt _First, _InIt _Last, const _Ty& _Val, false_type)
{ // find first matching _Val
for (; _First != _Last; ++_First)
if (*_First == _Val)
break;
return (_First);
}
???? - 注意点:
- 1 查找值需要“operator==”支持
- 2 查找值需要遍历容器数据,迭代器需要支持"operator++"
- 3 注意返回的位置,特别要注意数组和容器数据的不同,最后返回的位置last,在数组中是有效数据;而在前闭后开的容器中,last的位置是“有效数据+1”的无效数据。
- 示例
#include <iostream>
#include "Algorithm.h"
#include <array>
class Demo
{
int no_;
public:
bool operator==(int num)
{
return no_ == num;
}
};
int main ()
?{
Demo demoArray[10];
std::find(&demoArray[0], &demoArray[9], 20); //这里demoArray[9]是有效数据,demoArray[10]才是无效的数据
return 0;
}?? - find_if Find element in range (function template ) 在一个范围里面查找元素
- 观察本质
template<class InputIterator, class UnaryPredicate>
InputIterator find_if (InputIterator first, InputIterator last, UnaryPredicate pred)
{
while (first!=last) {
if (pred(*first)) return first; //返回第一个符合条件的元素。
++first;
}
return last;
}
----------------------------------------------------------------------------------------
// find_if example
#include <iostream> // std::cout
#include <algorithm> // std::find_if
#include <vector> // std::vector
bool IsOdd (int i) {
return ((i%2)==1);
}
int main () {
std::vector<int> myvector;
myvector.push_back(10);
myvector.push_back(25);
myvector.push_back(40);
myvector.push_back(55);
std::vector<int>::iterator it = std::find_if (myvector.begin(), myvector.end(), IsOdd);
std::cout << "The first odd value is " << *it << ‘\n‘;
return 0;
}
----------------------------------------------------------------------------------------------
Output:
The first odd value is 25
解释:返回第一个符合条件的元素。如果没有找到,则返回有效区间+1的无效数据位置。
?
???????
??? - find_if_not Find element in range (negative condition 否定条件) (function template )
- 观察本质
template<class InputIterator, class UnaryPredicate>
InputIterator find_if_not (InputIterator first, InputIterator last, UnaryPredicate pred)
{
while (first!=last) {
if (!pred(*first)) return first; //返回第一个不符合要求的元素
++first;
}
return last;
}
-----------------------------------------------------------------------------------------------
// find_if_not example
#include <iostream> // std::cout
#include <algorithm> // std::find_if_not
#include <array> // std::array
int main () {
std::array<int,5> foo = {1,2,3,4,5};
std::array<int,5>::iterator it =
std::find_if_not (foo.begin(), foo.end(), [](int i){return i%2;} );
std::cout << "The first even value is " << *it << ‘\n‘;
return 0;
}
---------------------------------------------------------------------------------------------------
???Output:
The first even value is 2
解释:在一个范围内查找不符合要求的元素,返回第一个不符合要求的元素。
???
??? - find_end Find last subsequence in range (function template )
- 观察本质
template<class ForwardIterator1, class ForwardIterator2> //只写了带4个参数的实现
ForwardIterator1 find_end (ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2)
{
if (first2==last2) return last1; // specified in C++11 判断第2区间是否有效
ForwardIterator1 ret = last1;
while (first1!=last1) //遍历第1区间
{
ForwardIterator1 it1 = first1;
ForwardIterator2 it2 = first2;
while (*it1==*it2) { // or: while (pred(*it1,*it2)) for version (2)
++it1; ++it2; //用临时it变量对比,第1区间每个元素,与第2区间的每个元素
if (it2==last2) { ret=first1; break; } //判断第2区间是否遍历完,完成了则重置要返回的值,跳出此内循环
if (it1==last1) return ret; //判断第1区间是否遍历完,完成了返回第1区间末尾加一位置
}
++first1;
}
return ret;
}
---------------------------------------------------------------------------------------
// find_end example
#include <iostream> // std::cout
#include <algorithm> // std::find_end
#include <vector> // std::vector
bool myfunction (int i, int j) {
return (i==j);
}
int main () {
int myints[] = {1,2,3,4,5,1,2,3,4,5};
std::vector<int> haystack (myints,myints+10);
?
int needle1[] = {1,2,3};?
// using default comparison:
std::vector<int>::iterator it;
it = std::find_end (haystack.begin(), haystack.end(), needle1, needle1+3);
if (it!=haystack.end())
std::cout << "needle1 last found at position " << (it-haystack.begin()) << ‘\n‘;
?
int needle2[] = {4,5,1};?
// using predicate comparison:
it = std::find_end (haystack.begin(), haystack.end(), needle2, needle2+3, myfunction);
if (it!=haystack.end())
std::cout << "needle2 last found at position " << (it-haystack.begin()) << ‘\n‘;
?
return 0;
}
------------------------------------------------------------------------------------------------
Output:
needle1 found at position 5
needle2 found at position 3
解释:
1 函数重载,一个4参数,一个5参数,后面多一个BinaryPredicate pred ?????(二元谓词)
2 算法功能:在第1区间查找,是否与第2区间完全匹配,匹配成功返回第1空间匹配最后的元素。简单来说:就是查找某一段数据。
3 ??注意点:数据如果不是在前闭后开的容器中(如:数组),都要注意最后的元素的设定。
----------------------------------------vs2015代码-----------------------------------------
// TEMPLATE FUNCTION find_end WITH PRED
template<class _FwdIt1, class _FwdIt2, class _Pr> inline
_FwdIt1 _Find_end_unchecked(_FwdIt1 _First1, _FwdIt1 _Last1,
_FwdIt2 _First2, _FwdIt2 _Last2, _Pr& _Pred)
{ // find last [_First2, _Last2) satisfying _Pred
_Iter_diff_t<_FwdIt1> _Count1 = _STD distance(_First1, _Last1); //区间距离1
_Iter_diff_t<_FwdIt2> _Count2 = _STD distance(_First2, _Last2); //区间距离2
_FwdIt1 _Ans = _Last1;
if (0 < _Count2)
{ // validate _Pred and test
_DEBUG_POINTER_IF(_Count2 <= _Count1, _Pred);
for (; _Count2 <= _Count1; ++_First1, (void)--_Count1)
{ // room for match, try it
_FwdIt1 _Mid1 = _First1;
for (_FwdIt2 _Mid2 = _First2; ; ++_Mid1)
if (!_Pred(*_Mid1, *_Mid2))
break;
else if (++_Mid2 == _Last2)
{ // potential answer, save it
_Ans = _First1;
break;
}
}
}
return (_Ans);
}??
??? - find_first_of Find element from set in range (function template ) 从设定范围内查找元素
- 观察本质
template<class InputIterator, class ForwardIterator>
InputIterator find_first_of ( InputIterator first1, InputIterator last1,
ForwardIterator first2, ForwardIterator last2)
{
while (first1!=last1) {
for (ForwardIterator it=first2; it!=last2; ++it) {
if (*it==*first1) // or: if (pred(*it,*first)) for version (2)
return first1;
}
++first1;
}
return last1;
}
--------------------------------------------------------------------------------------------
// find_first_of example
#include <iostream> // std::cout
#include <algorithm> // std::find_first_of
#include <vector> // std::vector
#include <cctype> // std::tolower
bool comp_case_insensitive (char c1, char c2) {
return (std::tolower(c1)==std::tolower(c2));
}
int main () {
int mychars[] = {‘a‘,‘b‘,‘c‘,‘A‘,‘B‘,‘C‘};
std::vector<char> haystack (mychars,mychars+6);
std::vector<char>::iterator it;
int needle[] = {‘A‘,‘B‘,‘C‘};
// using default comparison:
it = find_first_of (haystack.begin(), haystack.end(), needle, needle+3);
if (it!=haystack.end())
std::cout << "The first match is: " << *it << ‘\n‘;
// using predicate comparison:
it = find_first_of (haystack.begin(), haystack.end(),
needle, needle+3, comp_case_insensitive);
if (it!=haystack.end())
std::cout << "The first match is: " << *it << ‘\n‘;
return 0;
}
----------------------------------------------------------------------------------------
Output:
The first match is: A
The first match is: a
解释:
循环区间1,里面嵌套循环区间2,用临时it比较所有元素,相等(或其它条件)则直接返回区间1此时元素.
简单来说:就是查找任意一个相同(或者其它条件)元素,即刻返回。?
---------------------------------------------vs2015--------------------------------------
// TEMPLATE FUNCTION find_first_of WITH PRED
template<class _FwdIt1, class _FwdIt2, class _Pr> inline
_FwdIt1 _Find_first_of_unchecked(_FwdIt1 _First1, _FwdIt1 _Last1,
_FwdIt2 _First2, _FwdIt2 _Last2, _Pr& _Pred)
{ // look for one of [_First2, _Last2) satisfying _Pred with element
for (; _First1 != _Last1; ++_First1)
for (_FwdIt2 _Mid2 = _First2; _Mid2 != _Last2; ++_Mid2)
if (_Pred(*_First1, *_Mid2))
return (_First1);
return (_First1);
}??????
???
??? - adjacent_find Find equal adjacent elements in range (function template ) 在范围内查找相等的相邻元素
- 观察本质
template <class ForwardIterator>
ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last)
{
if (first != last)
{
ForwardIterator next=first; ++next; //跳过第1个元素
while (next != last) {
if (*first == *next) // or: if (pred(*first,*next)), for version (2) 比较第1个和第2个元素
return first; //如符合条件,直接返回first
++first; ++next; //不符合条件,则轮番向前
}
}
return last;
}
---------------------------------------------------------------------------------------
// adjacent_find example
#include <iostream> // std::cout
#include <algorithm> // std::adjacent_find
#include <vector> // std::vector
bool myfunction (int i, int j) {
return (i==j);
}
int main () {
int myints[] = {5,20,5,30,30,20,10,10,20};
std::vector<int> myvector (myints,myints+8);
std::vector<int>::iterator it;
// using default comparison:
it = std::adjacent_find (myvector.begin(), myvector.end());
if (it!=myvector.end())
std::cout << "the first pair of repeated elements are: " << *it << ‘\n‘;
//using predicate comparison:
it = std::adjacent_find (++it, myvector.end(), myfunction);
if (it!=myvector.end())
std::cout << "the second pair of repeated elements are: " << *it << ‘\n‘;
return 0;
}
-------------------------------------------------------------------------------------------
Output:
the first pair of repeated elements are: 30
the second pair of repeated elements are: 10
解释:
------------------------------------vs2015-----------------------------------------------
// TEMPLATE FUNCTION adjacent_find WITH PRED
template<class _FwdIt,
class _Pr> inline
_FwdIt _Adjacent_find_unchecked(_FwdIt _First, _FwdIt _Last, _Pr& _Pred)
{ // find first satisfying _Pred with successor
if (_First != _Last)
for (_FwdIt _Firstb; (void)(_Firstb = _First), ++_First != _Last; )
if (_Pred(*_Firstb, *_First))
return (_Firstb);
return (_Last);
}????????
???? - count Count appearances of value in range (function template ) 计数
- 观察本质
template <class InputIterator, class UnaryPredicate>
typename iterator_traits<InputIterator>::difference_type
count_if (InputIterator first, InputIterator last, UnaryPredicate pred)
{
typename iterator_traits<InputIterator>::difference_type ret = 0;
while (first!=last) {
if (pred(*first)) ++ret;
++first;
}
return ret;
}
-------------------------------------------------------------------------------------
// count_if example
#include <iostream> // std::cout
#include <algorithm> // std::count_if
#include <vector> // std::vector
bool IsOdd (int i) { return ((i%2)==1); }
int main () {
std::vector<int> myvector;
for (int i=1; i<10; i++) myvector.push_back(i); // myvector: 1 2 3 4 5 6 7 8 9
int mycount = count_if (myvector.begin(), myvector.end(), IsOdd);
std::cout << "myvector contains " << mycount << " odd values.\n";
return 0;
}
---------------------------------------------------------------------------------------------
Output:
myvector contains 5 odd values.
解释:计数算法
-------------------------------------------vs2015--------------------------------------------
// TEMPLATE FUNCTION count
template<class _InIt,
class _Ty> inline
_Iter_diff_t<_InIt>
_Count_unchecked(_InIt _First, _InIt _Last, const _Ty& _Val)
{ // count elements that match _Val
_Iter_diff_t<_InIt> _Count = 0;
for (; _First != _Last; ++_First)
if (*_First == _Val)
++_Count;
return (_Count);
}
?????????? - count_if Return number of elements in range satisfying condition (function template ) 按条件计数
- 观察本质
template <class InputIterator, class UnaryPredicate>
typename iterator_traits<InputIterator>::difference_type
count_if (InputIterator first, InputIterator last, UnaryPredicate pred)
{
typename iterator_traits<InputIterator>::difference_type ret = 0;
while (first!=last) {
if (pred(*first)) ++ret;
++first;
}
return ret;
}
------------------------------------------------------------------------------------
// count_if example
#include <iostream> // std::cout
#include <algorithm> // std::count_if
#include <vector> // std::vector
bool IsOdd (int i) { return ((i%2)==1); }
int main () {
std::vector<int> myvector;
for (int i=1; i<10; i++) myvector.push_back(i); // myvector: 1 2 3 4 5 6 7 8 9
int mycount = count_if (myvector.begin(), myvector.end(), IsOdd);
std::cout << "myvector contains " << mycount << " odd values.\n";
return 0;
}
-----------------------------------------------------------------------------------
Output:
myvector contains 5 odd values.
解释:按条件计数
-------------------------------------------------vs2015--------------------------
???????????? - mismatch Return first position where two ranges differ (function template ) 返回两个范围不同的第一位置
- 观察本质
template <class InputIterator1, class InputIterator2>
pair<InputIterator1, InputIterator2>
mismatch (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2 )
{
while ( (first1!=last1) && (*first1==*first2) ) // or: pred(*first1,*first2), for version 2
{ ++first1; ++first2; }
return std::make_pair(first1,first2);
}
----------------------------------------------------------------------------------------------
// mismatch algorithm example
#include <iostream> // std::cout
#include <algorithm> // std::mismatch
#include <vector> // std::vector
#include <utility> // std::pair
bool mypredicate (int i, int j) {
return (i==j);
}
int main () {
std::vector<int> myvector;
for (int i=1; i<6; i++) myvector.push_back (i*10); // myvector: 10 20 30 40 50
int myints[] = {10,20,80,320,1024}; // myints: 10 20 80 320 1024
std::pair<std::vector<int>::iterator,int*> mypair;
// using default comparison:
mypair = std::mismatch (myvector.begin(), myvector.end(), myints);
std::cout << "First mismatching elements: " << *mypair.first;
std::cout << " and " << *mypair.second << ‘\n‘;
++mypair.first; ++mypair.second;
// using predicate comparison:
mypair = std::mismatch (mypair.first, myvector.end(), mypair.second, mypredicate);
std::cout << "Second mismatching elements: " << *mypair.first;
std::cout << " and " << *mypair.second << ‘\n‘;
return 0;
}
-------------------------------------------------------------------------------------------------------------
Output:
First mismatching elements: 30 and 80
Second mismatching elements: 40 and 320
解释:
---------------------------------------vs2015--------------------------------------------------\
// TEMPLATE FUNCTION mismatch
template<class _InIt1,class _InIt2> inline
pair<_InIt1, _InIt2>
mismatch(_InIt1 _First1, _InIt1 _Last1,
_InIt2 _First2)
{ // return [_First1, _Last1)/[_First2, ...) mismatch
return (_STD mismatch(_First1, _Last1, _First2,
equal_to<>()));
}?????
-------------------------------------------------------------------------------------------------------、
// TEMPLATE FUNCTION mismatch WITH PRED
template<class _InIt1,class _InIt2, class _Pr> inline
pair<_InIt1, _InIt2>
_Mismatch_unchecked(_InIt1 _First1, _InIt1 _Last1,
_InIt2 _First2, _Pr& _Pred)
{ // return [_First1, _Last1)/[_First2, ...) mismatch using _Pred
for (; _First1 != _Last1 && _Pred(*_First1, *_First2); )
{ // point past match
++_First1;
++_First2;
}
return (pair<_InIt1, _InIt2>(_First1, _First2));
}????
?????? - equal Test whether the elements in two ranges are equal (function template )
- 观察本质
template <class InputIterator1, class InputIterator2>
bool equal ( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2 )
{
while (first1!=last1) {
if (!(*first1 == *first2)) // or: if (!pred(*first1,*first2)), for version 2
return false;
++first1; ++first2; //第2区间没有判断条件
}
return true;
}
--------------------------------------------------------------------------------------------
// equal algorithm example
#include <iostream> // std::cout
#include <algorithm> // std::equal
#include <vector> // std::vector
bool mypredicate (int i, int j) {
return (i==j);
}
int main () {
int myints[] = {20,40,60,80,100}; // myints: 20 40 60 80 100
std::vector<int>myvector (myints,myints+5); // myvector: 20 40 60 80 100
// using default comparison:
if ( std::equal (myvector.begin(), myvector.end(), myints) )
std::cout << "The contents of both sequences are equal.\n";
else
std::cout << "The contents of both sequences differ.\n";
myvector[3]=81; // myvector: 20 40 60 81 100
// using predicate comparison:
if ( std::equal (myvector.begin(), myvector.end(), myints, mypredicate) )
std::cout << "The contents of both sequences are equal.\n";
else
std::cout << "The contents of both sequences differ.\n";
return 0;
}
----------------------------------------------------------------------------------------
Output:
The contents of both sequences are equal.
The contents of both sequence differ.
解释:第2区间要保证比第1区间要长,不然会出问题。
-------------------------------------------------vs2015---------------------------------
// TEMPLATE FUNCTION equal WITH TWO RANGES, PRED
template<class _InIt1,class _InIt2,class _Pr> inline
bool _Equal_unchecked(_InIt1 _First1, _InIt1 _Last1,
_InIt2 _First2, _InIt2 _Last2, _Pr& _Pred,
input_iterator_tag, input_iterator_tag)
{ // compare [_First1, _Last1) to [_First2, _Last2)
// using _Pred, arbitrary iterators
_DEBUG_POINTER_IF(_First1 != _Last1 && _First2 != _Last2, _Pred);
for (; _First1 != _Last1 && _First2 != _Last2; ++_First1, (void)++_First2)
if (!_Pred(*_First1, *_First2))
return (false);
return (_First1 == _Last1 && _First2 == _Last2);
}??????
????? - is_permutation Test whether range is permutation of another (function template ) 测试范围是否是另一个排列
- 观察本质
template <class InputIterator1, class InputIterator2>
bool is_permutation (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2)
{
std::tie (first1,first2) = std::mismatch (first1,last1,first2);
if (first1==last1) return true;
InputIterator2 last2 = first2; std::advance (last2,std::distance(first1,last1));
for (InputIterator1 it1=first1; it1!=last1; ++it1) {
if (std::find(first1,it1,*it1)==it1) {
auto n = std::count (first2,last2,*it1);
if (n==0 || std::count (it1,last1,*it1)!=n) return false;
}
}
return true;
}
-----------------------------------------------------------------------------------------
// is_permutation example
#include <iostream> // std::cout
#include <algorithm> // std::is_permutation
#include <array> // std::array
int main () {
std::array<int,5> foo = {1,2,3,4,5};
std::array<int,5> bar = {3,1,4,5,2};
if ( std::is_permutation (foo.begin(), foo.end(), bar.begin()) )
std::cout << "foo and bar contain the same elements.\n";
return 0;
}
------------------------------------------------------------------------------------------------
Output:
foo and bar contain the same elements.
解释:是否是一组有序的排列
------------------------------------------vs2015-------------------------------------------
// TEMPLATE FUNCTION is_permutation WITH PRED
template<class _FwdIt1,
class _FwdIt2,
class _Pr> inline
bool _Is_permutation_unchecked(_FwdIt1 _First1, _FwdIt1 _Last1,
_FwdIt2 _First2, _Pr& _Pred)
{ // test if [_First1, _Last1) == permuted [_First2, ...), using _Pred
for (; _First1 != _Last1; ++_First1, (void)++_First2)
if (!_Pred(*_First1, *_First2))
{ // found first inequality, check match counts in suffix
_FwdIt2 _Last2 = _STD next(_First2,
_STD distance(_First1, _Last1));
return (_Check_match_counts(_First1, _Last1,
_First2, _Last2, _Pred));
}
return (true);
}?
?????????? - search Search range for subsequence (function template ) 搜索 标准的范围查找 对应 find_end
- 观察本质
template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 search ( ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2)
{
if (first2==last2) return first1; // specified in C++11
while (first1!=last1)
{
ForwardIterator1 it1 = first1;
ForwardIterator2 it2 = first2;
while (*it1==*it2) { // or: while (pred(*it1,*it2)) for version 2
++it1; ++it2;
if (it2==last2) return first1;
if (it1==last1) return last1;
}
++first1;
}
return last1;
}
---------------------------------------------------------------------------------
// search algorithm example
#include <iostream> // std::cout
#include <algorithm> // std::search
#include <vector> // std::vector
bool mypredicate (int i, int j) {
return (i==j);
}
int main () {
std::vector<int> haystack;
// set some values: haystack: 10 20 30 40 50 60 70 80 90
for (int i=1; i<10; i++) haystack.push_back(i*10);
// using default comparison:
int needle1[] = {40,50,60,70};
std::vector<int>::iterator it;
it = std::search (haystack.begin(), haystack.end(), needle1, needle1+4);
if (it!=haystack.end())
std::cout << "needle1 found at position " << (it-haystack.begin()) << ‘\n‘;
else
std::cout << "needle1 not found\n";
// using predicate comparison:
int needle2[] = {20,30,50};
it = std::search (haystack.begin(), haystack.end(), needle2, needle2+3, mypredicate);
if (it!=haystack.end())
std::cout << "needle2 found at position " << (it-haystack.begin()) << ‘\n‘;
else
std::cout << "needle2 not found\n";
return 0;
}
---------------------------------------------------------------------------------------------
Output:
needle1 found at position 3
needle2 not found
解释:
-------------------------------------vs2015------------------------------------------------
// TEMPLATE FUNCTION search WITH PRED
template<class _FwdIt1, class _FwdIt2, class _Pr> inline
_FwdIt1 _Search_unchecked(_FwdIt1 _First1, _FwdIt1 _Last1,
_FwdIt2 _First2, _FwdIt2 _Last2, _Pr& _Pred,
forward_iterator_tag, forward_iterator_tag)
{ // find first [_First2, _Last2) satisfying _Pred, arbitrary iterators
for (; ; ++_First1)
{ // loop until match or end of a sequence
_FwdIt1 _Mid1 = _First1;
for (_FwdIt2 _Mid2 = _First2; ; ++_Mid1, (void)++_Mid2)
if (_Mid2 == _Last2)
return (_First1);
else if (_Mid1 == _Last1)
return (_Last1);
else if (!_Pred(*_Mid1, *_Mid2))
break;
}
}????????? - search_n Search range for elements (function template )
- 观察本质
template<class ForwardIterator, class Size, class T>
ForwardIterator search_n (ForwardIterator first, ForwardIterator last,
Size count, const T& val)
{
ForwardIterator it, limit;
? Size i;
limit=first; std::advance(limit,std::distance(first,last)-count);
while (first!=limit)
{
it = first; i=0;
while (*it==val) // or: while (pred(*it,val)) for the pred version
{ ++it; if (++i==count) return first; }
++first;
}
return last;
}
-------------------------------------------------------------------------------------
// search_n example
#include <iostream> // std::cout
#include <algorithm> // std::search_n
#include <vector> // std::vector
bool mypredicate (int i, int j) {
return (i==j);
}
int main () {
int myints[]={10,20,30,30,20,10,10,20};
std::vector<int> myvector (myints,myints+8);
std::vector<int>::iterator it;
// using default comparison:
it = std::search_n (myvector.begin(), myvector.end(), 2, 30);
if (it!=myvector.end())
std::cout << "two 30s found at position " << (it-myvector.begin()) << ‘\n‘;
else
std::cout << "match not found\n";
// using predicate comparison:
it = std::search_n (myvector.begin(), myvector.end(), 2, 10, mypredicate);
if (it!=myvector.end())
std::cout << "two 10s found at position " << int(it-myvector.begin()) << ‘\n‘;
else
std::cout << "match not found\n";
return 0;
}
------------------------------------------------------------------------------------------
Output:
Two 30s found at position 2
Two 10s found at position 5
解释:##advance
template <class InputIterator, class Distance>
void advance (InputIterator& it, Distance n);
迭代器辅助函数。
使迭代器it偏移n,其中n为整数。?
-----------------------------advance-----------------------
?
#include <iostream> // std::cout
#include <iterator> // std::advance
#include <list> // std::list
int main () {
std::list<int> mylist;
for (int i=0; i<10; i++) mylist.push_back (i*10);
std::list<int>::iterator it = mylist.begin();
std::advance (it,5);
std::cout << "The sixth element in mylist is: " << *it << ‘\n‘;
std::advance (it,-1);
std::cout << "The fifth element in mylist is: " << *it << ‘\n‘;
return 0;
}?
-------------------------advnce Deom output---------------------
The sixth element in mylist is: 50
The fifth element in mylist is: 40??
?
?????
--------------------------------------vs2015-search_n--------------------------------------
?
// TEMPLATE FUNCTION search_n WITH PRED
template<class _FwdIt,class _Diff,class _Ty,class _Pr> inline
_FwdIt _Search_n_unchecked(_FwdIt _First, _FwdIt _Last,
_Diff _Count, const _Ty& _Val, _Pr& _Pred, forward_iterator_tag)
{ // find first _Count * _Val satisfying _Pred, forward iterators
if (_Count <= 0)
return (_First);
for (; _First != _Last; ++_First)
if (_Pred(*_First, _Val))
{ // found start of possible match, check it out
_FwdIt _Mid = _First;
for (_Diff _Count1 = _Count; ; )
if (--_Count1 == 0)
return (_First); // found rest of match, report it
else if (++_Mid == _Last)
return (_Last); // short match at end
else if (!_Pred(*_Mid, _Val))
{ // short match not at end
break;
}
_First = _Mid; // pick up just beyond failed match
}
return (_Last);
}???? - 非变动型算法分类:
- 算法 粗略分类0
- 1 不带后缀
- 基本上算法的主要功能,在语义上表示出来。
如:find count equal search - 2 带后缀
- xxx_of of带有“如果”的意义,此种带“of”后缀的算法,一定会带一个函数,来进行判断,返回一个bool值。all_of功能就是:判断容器里面全部数据是不是一个什么(of).如果是则返回true,否则返回faulse.
- xxx_if if带有“判断条件”的意义
- 算法 粗略分类1
- 搜索
search
search_n? - 查找
find
find_if
find_if_not
find_end
find_first_of???? - 是否相等(相同)
equal?
mismatch? - 是否同一组
is_permutation - 计数
count
count_if? - 小结:非变动型算法
1 all_of any_of none_of这3个主要功能:用来测试,测试在容器中有没有符合条件的数据。
2 ?for_each主要功能:巡访、遍历,具体是否改变,由程序员决定。
3 ?搜索查找系列:find find_if find_if_not find_end find_first_of search search_n ##“搜查七种武器”
find:值的查找 find_if 符合条件的查找 find_if_not 符合条件的查找取反 ?find_end 最后一个的、一整块符合条件的查找 find_first_of 查找符合条件的第一个元素 search 搜查最前一个的、一整块符合条件的 search_n 搜查一定偏移量的区间,查找符合特定条件的。
4 ?统计计数count count_if
5 比较 equal等。?
?
STL (13) 非变动型算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。