常用的STL查找算法
|
《effective STL》中有句忠告，尽量用算法替代手写循环；查找少不了循环遍历，在这里总结下常用的STL查找算法； 查找有三种，即点线面： 针对每个类别的查找，默认的比较函数是相等，为了满足更丰富的需求，算法也都提供了自定义比较函数的版本； 单个元素查找 find() 比较条件为相等的查找 find()从给定区间中查找单个元素,定义： 复制代码 代码如下: template <class InputIterator,class T> InputIterator find (InputIterator first,InputIterator last,const T& val); 示例，从myvector中查找30： 复制代码 代码如下: int myints[] = { 10,20,30,40 }; std::vector<int> myvector (myints,myints+4); 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 myvectorn"; find_if() 自定义比较函数 std::find_if():从给定区间中找出满足比较函数的第一个元素； 复制代码 代码如下: bool cmpFunction (int i) { return ((i%30)==0); } it = std::find_if (myvector.begin(),cmpFunction); std::cout << "first:" << *it <<std::endl; count() 统计元素出现次数 std::count()：统计区间中某个元素出现的次数； search_n() 查询单个元素重复出现的位置 search_n(): find用来查询单个元素，search_n则用来查找区间中重复出现n次的元素； 示例：查询myvector中30连续出现2次的位置： 复制代码 代码如下: int myints[]={10,10,20}; std::vector<int> myvector (myints,myints+8); it = std::search_n (myvector.begin(),2,30); search_n() 支持自定义比较函数； adjacent_find() 查询区间中重复元素出现的位置 adjacent_find() 查询区间中重复元素出现的位置，该算法支持自定义比较函数； lower_bound() 有序区间中查询元素边界 lower_bound()用来在一个排序的区间中查找第一个不小于给定元素的值： 复制代码 代码如下: int myints[] = {10,20}; std::vector<int> v(myints,myints+8); // 10 20 30 30 20 10 10 20 std::sort (v.begin(),v.end()); // 10 10 10 20 20 20 30 30 std::vector<int>::iterator low,up; low=std::lower_bound (v.begin(),v.end(),20); std::cout << "lower_bound at position " << (low- v.begin()) << 'n'; 类似算法有upper_bound(),查找有序区间中第一个大于给定元素的值； binary_search() 有序区间的二分查找 binary_search() 用来在一个有序区间中使用二分法查找元素是否在这个区间中，注，这个算法的返回值为bool， 复制代码 代码如下: template <class ForwardIterator,class T> bool binary_search (ForwardIterator first,ForwardIterator last,const T& val) { first = std::lower_bound(first,last,val); return (first!=last && !(val<*first)); } 示例：从有序区间v中找3是否存在： 复制代码 代码如下: int myints[] = {1,3,4,5,1}; std::vector<int> v(myints,myints+9); // 1 2 3 4 5 4 3 2 1 std::sort (v.begin(),v.end()); if (std::binary_search (v.begin(),3)) std::cout << "found!n"; else std::cout << "not found.n"; min_element() 查找最小元素 min_element() 在给定区间中查找出最小值; 复制代码 代码如下: int myints[] = {3,7,6,9}; std::cout << "The smallest element is " << *std::min_element(myints,myints+7) << 'n'; 类似算法有：max_element() 查找最大值； 区间查找 search() search() 查找子区间首次出现的位置 find()用来查找单个元素，search()则用来查找一个子区间； 复制代码 代码如下: int needle1[] = {20,30}; it = std::search (myvector.begin(),needle1,needle1+2); if (it!=myvector.end()) std::cout << "needle1 found at position " << (it-myvector.begin()) << 'n'; search支持自定义比较函数； 复制代码 代码如下: bool cmpFunction (int i,int j) { return (i-j==1); } int myints[] = {1,1,5}; std::vector<int> haystack (myints,myints+10); int needle2[] = {1,3}; // using predicate comparison: it = std::search (haystack.begin(),haystack.end(),needle2,needle2+3,cmpFunction); find_end() 查找子区间最后一次出现的位置 search() 用来查找子区间第一次出现的位置，而find_end()用来查找子区间最后一次出现的位置： equal() 判断两个区间是否相等 equal（）用来判断两个区间是否相等，该算法支持自定义比较函数； mismatch() 查询两个区间首次出现不同的位置； mismatch() 查询两个区间首先出现不同的位置，这个算法也支持自定义比较函数； 集合查找 find_first_of 查找集合中的任意一个元素 find_first_of()用来查找给定集合中的任意一个元素: 复制代码 代码如下: int mychars[] = {'a','b','c','A','B','C'}; std::vector<char> haystack (mychars,mychars+6); int needle[] = {'C','A'}; // using default comparison: it = find_first_of (haystack.begin(),needle,needle+3); find_first_of支持自定义比较函数； 以上所述就是本文的全部内容了，希望大家能够喜欢。 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |