(3)STL算法之搜索
3、搜寻算法
STL也提供了一系列搜寻算法。
(1)find()
在区间[first,last],查找值为val的元素,返回其位置
template <class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val);
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;
}
用法示例:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
int myints[] = { 10, 20, 30, 40 };
int* p; //指针是一个特殊的迭代器
p = find(myints, myints + 4, 30);
if (p != myints + 4)
cout << "Element found in myints: " << *p << '\n';
else
cout << "Element not found in myints\n";
vector<int> myvector(myints, myints + 4);
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;
}
(2)find_if()
查找第一个匹配自定义规则的元素
template <class InputIterator, class UnaryPredicate>
InputIterator find_if (InputIterator first, InputIterator last, UnaryPredicate pred);
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; //查找失败返回 last
}
用法示例:
#include <iostream>
#include <algorithm>
#include <vector>
bool IsOdd(int i)
{
return ((i % 2) == 1);
}
int main() {
vector<int> myvector;
myvector.push_back(10);
myvector.push_back(25);
myvector.push_back(40);
myvector.push_back(55);
auto it = find_if(myvector.begin(), myvector.end(), IsOdd);
cout << "第一个奇数:" << *it << '\n';
return 0;
}
(3)find_if_not()
C++11 ,与find_if()相反,find_if_not()查找第一个不匹配自定义规则的元素
template <class InputIterator, class UnaryPredicate>
InputIterator find_if_not (InputIterator first, InputIterator last, UnaryPredicate pred);
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;
}
用法示例:
#include <iostream>
#include <algorithm>
#include <array>
using namespace std;
int main() {
std::array<int, 5> foo = { 1,2,3,4,5 };
array<int, 5>::iterator it =
find_if_not(foo.begin(), foo.end(), [](int i) {return i % 2; }); // 遍历到元素2 的时候参数 3 为 0
cout << "The first even value is " << *it << '\n';
return 0;
}
(4)find_end()
返回区间[first1,last1]中,和区间[first2,last2]完全吻合的最后一个子区间内的第一个元素位置,第二个函数仅在pred为真时有意义,如果搜索失败返回 last1
// version1
template < class ForwardIterator1, class ForwardIterator2 >
ForwardIterator1 find_end (ForwardIterator1 first1, ForwardIterator1 last1,ForwardIterator2 first2, ForwardIterator2 last2);
template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 find_end (ForwardIterator1 first1, ForwardIterator1 last1,ForwardIterator2 first2, ForwardIterator2 last2)
{
if ( first2 == last2 )
return last1; // C++11
ForwardIterator1 ret = last1;
while (first1!=last1)
{
ForwardIterator1 it1 = first1;
ForwardIterator2 it2 = first2;
while (*it1==*it2) // or: while (pred(*it1,*it2)) version (2)
{
++it1; ++it2;
if (it2==last2)
{
ret=first1;
break;
}
if (it1==last1)
return ret;
}
++first1;
}
return ret;
}
// version2 返回区间[first1,last1]中,和区间[first2,last2]完全吻合的最后一个子区间内的第一个元素位置,pred为真时,才有意义,如果搜索失败返回 last1
template < class ForwardIterator1, class ForwardIterator2, class BinaryPredicate >
ForwardIterator1 find_end (ForwardIterator1 first1, ForwardIterator1 last1,ForwardIterator2 first2, ForwardIterator2 last2,BinaryPredicate pred);
用法示例:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool myfunction(int i, int j)
{
return (i == j);
}
int main() {
int myints[] = { 1,2,3,4,5,1,2,3,4,5 };
vector<int> haystack(myints, myints + 10);
int needle1[] = { 1,3,3 };
vector<int>::iterator it;
it = find_end(haystack.begin(), haystack.end(), needle1, needle1 + 3);
if (it != haystack.end())
cout << "needle1 last found at position " << (it - haystack.begin()) << '\n';
int needle2[] = { 3,4,5 };
it = find_end(haystack.begin(), haystack.end(), needle2, needle2 + 3, myfunction);
if (it != haystack.end())
cout << "needle2 last found at position " << (it - haystack.begin()) << '\n'; // 7
return 0;
}
(5)find_first_of()
返回 子串[first2,last2]中第一个元素(不要求子串完全吻合原串), 在区间[first1,last1]中第一次出现的位置,第二个函数仅在pred为真时执行,如果搜索失败返回 last1
// version 1 返回区间[first1,last1]中,和区间[first2,last2]完全吻合的第一个子区间内的第一个元素位置,如果搜索失败返回 last1
template <class InputIterator, class ForwardIterator>
InputIterator find_first_of (InputIterator first1, InputIterator last1,ForwardIterator first2, ForwardIterator last2);
version 2
template <class InputIterator, class ForwardIterator, class BinaryPredicate>
InputIterator find_first_of (InputIterator first1, InputIterator last1,ForwardIterator first2, ForwardIterator last2, BinaryPredicate pred);
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)) version 2
return first1;
}
++first1;
}
return last1;
}
用法示例:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool myfunction(int i, int j)
{
return (i == j);
}
int main() {
int myints[] = { 1,2,3,4,5,1,2,3,4,5 };
vector<int> haystack(myints, myints + 10);
int needle1[] = { 1,3 };
vector<int>::iterator it;
it = find_first_of(haystack.begin(), haystack.end(), needle1, needle1 + 2);
if (it != haystack.end())
cout << "needle1 first found at position " << (it - haystack.begin()) << '\n'; // 0
int needle2[] = { 3,5 };
it = find_first_of(haystack.begin(), haystack.end(), needle2, needle2 + 3, myfunction);
if (it != haystack.end())
cout << "needle2 first found at position " << (it - haystack.begin()) << '\n'; // 2
return 0;
}
下来介绍另外几种搜索算法......
(6) search() 与find_first_of()有点像, 但search()针对子区间,要求完全吻合,后者针对单个元素,不要求完全吻合。
搜寻第一个子区间。这两个函数都返回和区间[first2,last2]完全吻合的第一个子区间的第一个位置,第二个函数只在pred为真时才被执行。
//声明
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);
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
if (it2==last2)
return first1;
if (it1==last1)
return last1;
++it1;
++it2;
}
++first1;
}
return last1;
}
用法示例:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool myfunction(int i, int j)
{
return (i == j);
}
int main() {
int myints[] = { 1,2,3,4,5,1,2,3,4,5 };
vector<int> haystack(myints, myints + 10);
int needle1[] = { 1,3 }; //没有输出,search要求子串完全匹配,myints中没有子串 “1,3”
vector<int>::iterator it;
it = search(haystack.begin(), haystack.end(), needle1, needle1 + 3);
if (it != haystack.end())
cout << "needle1 first found at position " << (it - haystack.begin()) << '\n';
int needle2[] = { 3,4,5 };
it = search(haystack.begin(), haystack.end(), needle2, needle2 + 3, myfunction);
if (it != haystack.end())
cout << "needle2 first found at position " << (it - haystack.begin()) << '\n'; // 2
return 0;
}
(7)search_n()
搜索前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 );
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); // 将迭代器limit前进到 指定位置
while (first!=limit)
{
it = first; i=0;
while (*it==val) // or: while (pred(*it,val)) pred version
{
++it;
if (++i==count)
return first;
}
++first;
}
return last;
}
用法示例:
#include <functional>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
template <class T>
void FillValue(T& vect, int first, int last)
{
if (last >= first)
{
for (int i = first; i <= last; ++i)
vect.insert(vect.end(), i);
}
}
void print(int elem)
{
cout << elem << " ";
}
void main()
{
vector <int> myvector;
FillValue(myvector, -3, 12);
for_each(myvector.begin(), myvector.end(), print);
cout << endl;
vector <int>::iterator pos1;
pos1 = search_n(myvector.begin(), myvector.end(), 4, 3);
if (pos1 != myvector.end())
{
cout << "4个连续等于3的元素的起始位置:" << distance(myvector.begin(), pos1) + 1 << endl;
}
else
{
cout << "没有4个连续等于3的元素" << endl; // 没有找到就返回 右迭代器的位置,本例中就是 end
}
vector<int>::iterator pos2;
pos2 = search_n(myvector.begin(), myvector.end(), 4, 3, greater<int>());
if (pos2 != myvector.end())
{
cout << "4个连续大于3的元素的起始位置 :" << distance(myvector.begin(), pos2) + 1 << endl;
}
else
{
cout << "第一个大于3的元素位置 :" << distance(myvector.begin(), pos2) + 1 << endl;
}
}