stl算法 find_end的用法

时间:2021-07-07 22:08:06

工作中对涉及到比较多数据的搜索排序等操作,为了省去数据操作编写过多相似的排序搜索代码,我计划将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;
}