工作中对涉及到比较多数据的搜索排序等操作,为了省去数据操作编写过多相似的排序搜索代码,我计划将stl中的算法引入到工作中去,增加代码的精简程度。 下面就说下find_end的用法。
一、函数说明
find_end:
函数原型:
template <class FdwIt1,class FdwIt2>
FdwIt1 find_end(FdwIt1 first1,FdwIt1 last,FdwIt2 first2,FdwIt2 last2);
template <class FdwIt1,class FdwIt2,class Pred>
FdwIt1 find_end(FdwIt1 first1,FdwIt1 last,FdwIt2 first2,FdwIt2 last2, Pred pr);
功能:在由[first1,last1)标记的序列中查找“由iteratior对[first2,last2)标记
的第二个序列”的最后一次出现。例如,已知亭子符序列mississippi和第二
个序列ss,则find_end()返回一个FwdIt1指向第二个ss序列的第一个s。如果
在第一个序列中没有找到第二个序列,则返回last1.在第一个版本中,使用底
层的等于操作符。在第二个版本中,使用用户传递进来的二元操作符pr.
上面是我从别去参考拷贝过来的。此次应用的是第二个自带比较函数的算法,比如一个复杂的数据结构里面可能从不同的角度去查找,如一个学生的结构,可以从学号或是姓名等角度去查找。另写的比较算法有更强的适应性。
二、stl中的源代码
template<class _FwdIt1, class _FwdIt2,
class _Pr> inline
_FwdIt1 find_end(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2, _FwdIt2 _Last2, _Pr _Pred)
{ // find last [_First2, _Last2) satisfying _Pred
_ASSIGN_FROM_BASE(_First1,
_Find_end(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
_CHECKED_BASE(_First2), _CHECKED_BASE(_Last2), _Pred,
_Dist_type(_First1), _Dist_type(_First2)));
return _First1;
}
//去调用下面的函数进行查找
template<class _FwdIt1,
class _FwdIt2, class _Diff1, class _Diff2, class _Pr> inline
_FwdIt1 _Find_end(_FwdIt1 _First1, _FwdIt1 _Last1,
_FwdIt2 _First2, _FwdIt2 _Last2, _Pr _Pred, _Diff1 *, _Diff2 *)
{ // find last [_First2, _Last2) satisfying _Pred
_DEBUG_RANGE(_First1, _Last1);
_DEBUG_RANGE(_First2, _Last2);
_DEBUG_POINTER(_Pred);
_Diff1 _Count1 = 0;
_Distance(_First1, _Last1, _Count1);
_Diff2 _Count2 = 0;
_Distance(_First2, _Last2, _Count2);
_FwdIt1 _Ans = _Last1;
if (0 < _Count2)
for (; _Count2 <= _Count1; ++_First1, --_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);
}
//可以看出其实stl也是进行逐个变量进行比较的。好处是可以不管变量类型,和比较的算法。这就泛型的优点。
三、示例程序
#include "stdafx.h"
#include "tchar.h"
#include <vector>
#include <algorithm>
struct student
{
int num;
TCHAR name[32];
public :
student()
{
num = 0;
memset(name, 0, sizeof(TCHAR) * 32);
}
static void Empty(student *s)
{
s->num = 0;
memset(s->name, 0, sizeof(TCHAR) * 32);
}
};
typedef std::vector<student>vst;
typedef std::vector<student>::iterator vstitor;
bool stu_findnum(const student &t1, const student &t2)
{
return t1.num == t2.num;
}
bool stu_findname(const student &t1, const student &t2)
{
return _strcmpi(t1.name, t2.name) == 0;
}
void exam()
{
vst st, st2;
student stu;
int i;
vstitor itor;
for(i = 0; i< 10; i++)
{
student::Empty(&stu);
stu.num = 100 +i;
_stprintf(stu.name, "student %d", i);
st.push_back(stu);
}
student::Empty(&stu);
stu.num = 104;
st2.push_back(stu);
//查找学号为104的学生
itor = std::find_end(st.begin(), st.end(), st2.begin(), st2.end(),stu_findnum );
if(itor != st.end())
{
printf("student: name = %s num = %d/n", (*itor).name,
(*itor).num);
}
st2.clear();
student::Empty(&stu);
_tcscpy(stu.name , "student 1");
st2.push_back(stu);
//查找名为student 1学生
itor = std::find_end(st.begin(), st.end(), st2.begin(), st2.end(),stu_findname );
if(itor != st.end())
{
printf("student: name = %s num = %d/n ", (*itor).name,
(*itor).num);
}
}
int main(int argc, char* argv[])
{
exam();
return 0;
}