STL Non-mutating Algorithms小结

2024-05-27 06:38

本文主要是介绍STL Non-mutating Algorithms小结,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

C++ STL中有许多非变易算法,这些算法不破坏操作数据,用来对序列数据进行逐个处理(for_each)、元素查找(find)、子序列搜索(find_first_of)、统计和匹配(countmismatch)等。非变易算法在实现各种大型复杂一点的算法的时候比较方便,而且比较稳定,这也是STL本身固有的特点。主要列出以下几种,参考了叶志军的那本《C++ STL开发技术导引》,同时也结合网站Cplusplus.com(http://www.cplusplus.com/),查看其实现的原理,以及在C++98C++11两个版本中的区别和变化,以便于做到全方位地学习,主要以C++11为主。例子大部分是书上的例子,这里摆出来主要是为了后期用了想不起来的时候可以回头看一下,呵呵。

逐个容器元素for_each

for_each函数对迭代器区间的每个元素进行循环操作,执行由单参数函数对象f所定义的操作。函数原型为:

UnaryFunction for_each(InputIteratorfirst,InputIterator last, UnaryFunction f)

C++ Reference

http://www.cplusplus.com/reference/algorithm/for_each/?kw=for_each

上可以看到起实现的源码如下:

// Applies function fn to each of the elements in the range [first,last).
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);
}


 

C++98C++11中,该函数的变化不大。

可以清楚地看到并没有修改任何数据,只是执行得函数fn会改动数据。

下面的示例程序将 list 链表容器的元素,调用 for_each 算法函数,通过 print 函数对象,将各个链表的元素乘以3后打印,并输出元素个数。

#include<iostream>
#include<list>
#include<algorithm>
using namespace std;
struct print{int count;print(){count=0;}void operator()(int x){cout<<3*x<<endl;count++;}
};
int main()
{list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);print p=for_each(l.begin(),l.end(),print());cout<<p.count<<endl;return 0;
}


查找容器元素find

该函数用于查找等于某值的元素。如果迭代器i所指的元素满足*i == value,则返回迭代器i。未找到满足条件的元素,返回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;
}


 

下面的示例程序查找容器list中,第一个值为6的元素,打印元素位置及其前一元素。

#include<iostream>
#include<algorithm>
#include<list>
using namespace std;
int main()
{list<int> l;l.push_back(1);l.push_back(5);l.push_back(6);l.push_back(19);list<int>::iterator i=find(l.begin(),l.end(),6);if(i!=l.end()){cout<<"找到元素6"<<endl;}cout<<"前一个元素为"<<*(--i)<<endl; return 0;
}


条件查找容器元素find_if

该函数是find的一个谓词判断版本,查找满足谓词判断函数的元素。

函数原型为:

template <class InputIterator, classUnaryPredicate>

  InputIterator find_if (InputIterator first, InputIterator last,UnaryPredicate pred);

实现原理:
// Returns an iterator to the first element in the range [first,last) for which pred returns true. If no such element is found, the function returns last.
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;
}


 

下面的实例程序将寻找容器vector中第一个能被5整除的元素。
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
bool divBy5(int x)
{return x%5?0:1;
}
int main()
{vector<int> v(10);for(int j=0;j<v.size();j++)v[j]=(j+1)*(j+3);vector<int>::iterator i;i=find_if(v.begin(),v.end(),divBy5);if(i!=v.end())cout<<"找到第一个能被5整除的元素:"<<*i<<endl<<"索引位置为:"<<i-v.begin()<<endl;return 0;
}


查找临近元素adjacent_find

adjacent_find顾名思义,寻找邻近的意思。该函数用于查找相等或满足条件的邻近元素对。它有两个使用原型,一个用于查找相等的两个连续元素,另一个使用二元谓词判断,查找满足条件的邻近元素对。

函数原型:

template <class ForwardIterator>ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last);
template <class ForwardIterator, class BinaryPredicate>ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last,BinaryPredicate pred);
// Searches the range [first,last) for the first occurrence of two consecutive elements that match, and returns an iterator to the first of these two elements, or last if no such pair is found.
实现原理:
template <class ForwardIterator>ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last)
{if (first != last){ForwardIterator next=first; ++next;while (next != last) {if (*first == *next)     // or: if (pred(*first,*next)), for version (2)return first;++first; ++next;}}return last;
}


 

下面的例子用于寻找容器中相等的元素和奇偶性相同的元素。

#include<iostream>
#include<algorithm>
#include<list>
using namespace std;
bool parity_equal(int x,int y){return (x-y)%2==0 ? 1:0;
}
int main()
{list<int> l;l.push_back(3);l.push_back(6);l.push_back(9);l.push_back(11);l.push_back(20);l.push_back(20);list<int>::iterator i=adjacent_find(l.begin(),l.end());if(i!=l.end()){cout<<"发现两个邻接的元素相等:"<<*i<<" ";i++;cout<<*i<<endl;}i=adjacent_find(l.begin(),l.end(),parity_equal);if(i!=l.end()){cout<<"发现两个奇偶性相同的元素:"<<*i<<" ";i++;cout<<*i;}return 0;
}

find_first_of

该函数用于查找某个范围之内的元素。它有两个使用原型,一个是相等,另一个是二元谓词判断。元素找到则返回迭代器,否则返回末位置。该函数在C++98C++11在传入的参数上有稍微的变化,C++98中要求传入的第一个迭代区间必须是前向迭代器ForwardIterator,而C++11没这个要求,下面的函数原型是C++11的函数原型。

template <class InputIterator, class ForwardIterator>InputIterator find_first_of (InputIterator first1, InputIterator last1,ForwardIterator first2, ForwardIterator last2);
template <class InputIterator, class ForwardIterator, class BinaryPredicate>InputIterator find_first_of (InputIterator first1, InputIterator last1,ForwardIterator first2, ForwardIterator last2,BinaryPredicate pred);
//Returns an iterator to the first element in the range [first1,last1) that matches any of the elements in [first2,last2). If no such element is found, the function returns last1.
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;
}

下面的例子显示字符串1第一个出现在字符串2中的字符。

 

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{char* str1="abceefgh7ijklmn";char* str2="zyx3pr7yst";char* rs=find_first_of(str1,str1+strlen(str1),str2,str2+strlen(str2));cout<<"str1第一个出现在str2的字符为:"<<*rs<<endl;return 0;
}

count

该函数用于计算容器中某个给定值的出现次数。它有两个使用原型,区别在于计数是直接返回还是引用返回。

template <class InputIterator, class T>typename iterator_traits<InputIterator>::difference_type
count (InputIterator first, InputIterator last, const T& val);
Returns the number of elements in the range [first,last) that compare equal to val.
The function uses operator== to compare the individual elements to val.
template <class InputIterator, class T>typename iterator_traits<InputIterator>::difference_typecount (InputIterator first, InputIterator last, const T& val)
{typename iterator_traits<InputIterator>::difference_type ret = 0;while (first!=last) {if (*first == val) ++ret;++first;}return ret;
}

例子统计数字在数组中出现的次数(Cplusplus.com上的例子)
// count algorithm example
#include <iostream>     // std::cout
#include <algorithm>    // std::count
#include <vector>       // std::vectorint main () {// counting elements in array:int myints[] = {10,20,30,30,20,10,10,20};   // 8 elementsint mycount = std::count (myints, myints+8, 10);std::cout << "10 appears " << mycount << " times.\n";// counting elements in container:std::vector<int> myvector (myints, myints+8);mycount = std::count (myvector.begin(), myvector.end(), 20);std::cout << "20 appears " << mycount  << " times.\n";return 0;
}


count_if

该函数使用谓词判断函数,统计迭代器区间上满足条件的元素个数。它有两个使用原型,区别在与计数是直接返回还是引用返回。

 

template <class InputIterator, class UnaryPredicate>typename iterator_traits<InputIterator>::difference_typecount_if (InputIterator first, InputIterator last, UnaryPredicate pred);
Return number of elements in range satisfying condition
Returns the number of elements in the range [first,last) for which pred is true.
template <class InputIterator, class UnaryPredicate>typename iterator_traits<InputIterator>::difference_typecount_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;
}
统计奇数出现的次数
#include <iostream>     // std::cout
#include <algorithm>    // std::count_if
#include <vector>       // std::vectorbool 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 9int mycount = count_if (myvector.begin(), myvector.end(), IsOdd);std::cout << "myvector contains " << mycount  << " odd values.\n";return 0;
}


 

mismatch

该函数用于比较两个序列,找出首个不匹配元素的位置。它有两个使用原型,分别为不相等和不满足二元谓词条件。该函数还涉及到pair的使用。

template <class InputIterator1, class InputIterator2>pair<InputIterator1, InputIterator2>mismatch (InputIterator1 first1, InputIterator1 last1,InputIterator2 first2);
template <class InputIterator1, class InputIterator2, class BinaryPredicate>pair<InputIterator1, InputIterator2>mismatch (InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, BinaryPredicate pred);Compares the elements in the range [first1,last1) with those in the range beginning at first2, and returns the first element of both sequences that does not match.
The elements are compared using operator== (or pred, in version (2)).
The function returns a pair of iterators to the first element in each range that does not match.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);
}


 

例子是比较两个整型容器,并找出不匹配的数字。

 

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{vector<int> v1,v2;v1.push_back(1);v1.push_back(1);v1.push_back(2);v2.push_back(1);v2.push_back(1);v2.push_back(3);pair<vector<int>::iterator,vector<int>::iterator> rs=mismatch(v1.begin(),v1.end(),v2.begin());if(rs.first==v1.end()&&rs.second==v2.end()){cout<<"v1、v2完全相同";}else{cout<<"v1、v2不同"<<v1[rs.first-v1.begin()]<<" "<<v2[rs.second-v2.begin()]<<endl;}return 0;
}


equal

该函数逐一比较两个序列的元素是否相等,返回值为true/false,不返回迭代器值。它有两个使用原型,分别为元素相等和二元谓词判断条件。

template <class InputIterator1, class InputIterator2>bool equal (InputIterator1 first1, InputIterator1 last1,InputIterator2 first2);
template <class InputIterator1, class InputIterator2, class BinaryPredicate>bool equal (InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, BinaryPredicate pred);Compares the elements in the range [first1,last1) with those in the range beginning at first2, and returns true if all of the elements in both ranges match.
The elements are compared using operator== (or pred, in version (2)).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 2return false;++first1; ++first2;}return true;
}


 

下面的例子用于比较两容器中数字绝对值是否相等。
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
bool absEqual(int a,int b)
{return abs(a) == abs(b) ? 1 : 0;
}
int main()
{vector<int> v1(5);vector<int> v2(5);for(int i=0;i<v1.size();i++){v1[i]=i;v2[i]=-1*i;}if(equal(v1.begin(), v1.end(), v2.begin(), absEqual)) {cout << "v1 v2绝对值完全相等" << endl;} else {cout << "v1 v2绝对值不完全相等" << endl;}return 0;
}

search

该函数在一个序列中搜索与另一序列匹配的子序列。它有两个使用原型,分别为完全匹配和二元谓词判断。匹配成功则返回子序列的首个元素的迭代器值。

search函数与find_first_of函数形似,但不相同。search找的是一块相同的区域,要求这块区域与后面列表的元素及其顺序相同;find_first_of找的是一个元素,只要这个元素是后面一个列表的任意一个就行。

template <class ForwardIterator1, class ForwardIterator2>ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1,ForwardIterator2 first2, ForwardIterator2 last2);
template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1,ForwardIterator2 first2, ForwardIterator2 last2,BinaryPredicate pred);Searches the range [first1,last1) for the first occurrence of the sequence defined by [first2,last2), and returns an iterator to its first element, or last1 if no occurrences are found.
The elements in both ranges are compared sequentially using operator== (or pred, in version (2)): A subsequence of [first1,last1) is considered a match only when this is true for all the elements of [first2,last2).
This function returns the first of such occurrences. For an algorithm that returns the last instead, see find_end. 在C++11中,If [first2,last2) is an empty range, the function returns first1.而在C++98中,If [first2,last2) is an empty range, the result is unspecified.template<class ForwardIterator1, class ForwardIterator2>ForwardIterator1 search ( ForwardIterator1 first1, ForwardIterator1 last1,ForwardIterator2 first2, ForwardIterator2 last2)
{if (first2==last2) return first1;  // specified in C++11while (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;
}


 

下面的例子指出二者的区别。

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void) {vector<int> v1, v2;v1.push_back(1);v1.push_back(4);v1.push_back(2);v1.push_back(3);v1.push_back(4);v2.push_back(2);v2.push_back(3);v2.push_back(4);vector<int>::iterator ivSearch, ivFind;ivSearch = search(v1.begin(), v1.end(), v2.begin(), v2.end());ivFind = find_first_of(v1.begin(), v1.end(), v2.begin(), v2.end());cout << "Position of search: " << ivSearch - v1.begin() << endl;//打印2cout << "Position of find_first_of: " << ivFind - v1.begin() << endl;//打印1return 0;
}

重复元素子序列搜索search_n

template <class ForwardIterator, class Size, class T>ForwardIterator search_n (ForwardIterator first, ForwardIterator last,Size count, const T& val);
template <class ForwardIterator, class Size, class T, class BinaryPredicate>ForwardIterator search_n ( ForwardIterator first, ForwardIterator last,Size count, const T& val, BinaryPredicate pred );Searches the range [first,last) for a sequence of count elements, each comparing equal to val (or for which pred returns true).
The function returns an iterator to the first of such elements, or last if no such sequence is found.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;
}
//向量内统计数字出现次数。
#include <algorithm>
#include <vector>
#include <iostream>
int main(){using namespace std;//初始化向量v={1, 8, 8, 8, 6, 6, 8}vector<int> v;v.push_back(1);v.push_back(8);v.push_back(8);v.push_back(8);v.push_back(6);v.push_back(6);v.push_back(8);//查找子序列{8, 8, 8}vector<int>::iterator iLocation;iLocation=search_n(v.begin(), v.end(), 3, 8);if(iLocation != v.end())cout << "在v中找到3个连续的元素8" << endl;else cout << "v中没有3个连续的元素8" << endl;//查找子序列{8, 8, 8, 8}iLocation=search_n(v.begin(), v.end(), 4, 8);if(iLocation != v.end())cout << "在v中找到4个连续的元素8" << endl;else cout << "v中没有4个连续的元素8" << endl;//查找子序列{6, 6}iLocation=search_n(v.begin(), v.end(), 2, 6);if(iLocation != v.end())cout << "在v中找到2个连续的元素6" << endl;else cout << "v中没有2个连续的元素6" << endl;return 0;
}


 

find_end

该函数用于在一个序列中搜索出最后一个与另一序列匹配的子序列。用search函数作用相似,方向相反。

template <class ForwardIterator1, class ForwardIterator2>ForwardIterator1 find_end (ForwardIterator1 first1, ForwardIterator1 last1,ForwardIterator2 first2, ForwardIterator2 last2);
template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>ForwardIterator1 find_end (ForwardIterator1 first1, ForwardIterator1 last1,ForwardIterator2 first2, ForwardIterator2 last2,BinaryPredicate pred);Searches the range [first1,last1) for the last occurrence of the sequence defined by [first2,last2), and returns an iterator to its first element, or last1 if no occurrences are found.
The elements in both ranges are compared sequentially using operator== (or pred, in version (2)): A subsequence of [first1,last1) is considered a match only when this is true for all the elements of [first2,last2).template<class ForwardIterator1, class ForwardIterator2>ForwardIterator1 find_end (ForwardIterator1 first1, ForwardIterator1 last1,ForwardIterator2 first2, ForwardIterator2 last2)
{if (first2==last2) return last1;  // specified in C++11ForwardIterator1 ret = last1;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) { ret=first1; break; }if (it1==last1) return ret;}++first1;}return ret;
}
在C++11中,If [first2,last2) is an empty range, the function returns last1.
在C++98中,If [first2,last2) is an empty range, the result is unspecified.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void) {vector<int> v, v2;//v={1,3,5,4,3,5,7}v.push_back(1);v.push_back(3);v.push_back(5);v.push_back(3);v.push_back(5);v.push_back(7);//v2={3,5}v2.push_back(3);v2.push_back(5);vector<int>::iterator iv = find_end(v.begin(), v.end(), v2.begin(), v2.end());if(iv != v.end()) {cout<< iv - v.begin() << endl;//3}return 0;
}


 

 

这篇关于STL Non-mutating Algorithms小结的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1006723

相关文章

Spring Boot读取配置文件的五种方式小结

《SpringBoot读取配置文件的五种方式小结》SpringBoot提供了灵活多样的方式来读取配置文件,这篇文章为大家介绍了5种常见的读取方式,文中的示例代码简洁易懂,大家可以根据自己的需要进... 目录1. 配置文件位置与加载顺序2. 读取配置文件的方式汇总方式一:使用 @Value 注解读取配置方式二

Python中的getopt模块用法小结

《Python中的getopt模块用法小结》getopt.getopt()函数是Python中用于解析命令行参数的标准库函数,该函数可以从命令行中提取选项和参数,并对它们进行处理,本文详细介绍了Pyt... 目录getopt模块介绍getopt.getopt函数的介绍getopt模块的常用用法getopt模

C 语言中enum枚举的定义和使用小结

《C语言中enum枚举的定义和使用小结》在C语言里,enum(枚举)是一种用户自定义的数据类型,它能够让你创建一组具名的整数常量,下面我会从定义、使用、特性等方面详细介绍enum,感兴趣的朋友一起看... 目录1、引言2、基本定义3、定义枚举变量4、自定义枚举常量的值5、枚举与switch语句结合使用6、枚

Java中的Lambda表达式及其应用小结

《Java中的Lambda表达式及其应用小结》Java中的Lambda表达式是一项极具创新性的特性,它使得Java代码更加简洁和高效,尤其是在集合操作和并行处理方面,:本文主要介绍Java中的La... 目录前言1. 什么是Lambda表达式?2. Lambda表达式的基本语法例子1:最简单的Lambda表

Java中Scanner的用法示例小结

《Java中Scanner的用法示例小结》有时候我们在编写代码的时候可能会使用输入和输出,那Java也有自己的输入和输出,今天我们来探究一下,对JavaScanner用法相关知识感兴趣的朋友一起看看吧... 目录前言一 输出二 输入Scanner的使用多组输入三 综合练习:猜数字游戏猜数字前言有时候我们在

SQL BETWEEN 的常见用法小结

《SQLBETWEEN的常见用法小结》BETWEEN操作符是SQL中非常有用的工具,它允许你快速选取某个范围内的值,本文给大家介绍SQLBETWEEN的常见用法,感兴趣的朋友一起看看吧... 在SQL中,BETWEEN是一个操作符,用于选取介于两个值之间的数据。它包含这两个边界值。BETWEEN操作符常用

go 指针接收者和值接收者的区别小结

《go指针接收者和值接收者的区别小结》在Go语言中,值接收者和指针接收者是方法定义中的两种接收者类型,本文主要介绍了go指针接收者和值接收者的区别小结,文中通过示例代码介绍的非常详细,需要的朋友们下... 目录go 指针接收者和值接收者的区别易错点辨析go 指针接收者和值接收者的区别指针接收者和值接收者的

python uv包管理小结

《pythonuv包管理小结》uv是一个高性能的Python包管理工具,它不仅能够高效地处理包管理和依赖解析,还提供了对Python版本管理的支持,本文主要介绍了pythonuv包管理小结,具有一... 目录安装 uv使用 uv 管理 python 版本安装指定版本的 Python查看已安装的 Python

C#中DrawCurve的用法小结

《C#中DrawCurve的用法小结》本文主要介绍了C#中DrawCurve的用法小结,通常用于绘制一条平滑的曲线通过一系列给定的点,具有一定的参考价值,感兴趣的可以了解一下... 目录1. 如何使用 DrawCurve 方法(不带弯曲程度)2. 如何使用 DrawCurve 方法(带弯曲程度)3.使用Dr

MySQL 分区与分库分表策略应用小结

《MySQL分区与分库分表策略应用小结》在大数据量、复杂查询和高并发的应用场景下,单一数据库往往难以满足性能和扩展性的要求,本文将详细介绍这两种策略的基本概念、实现方法及优缺点,并通过实际案例展示如... 目录mysql 分区与分库分表策略1. 数据库水平拆分的背景2. MySQL 分区策略2.1 分区概念