当前位置: 首页 > news >正文

(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;
    }
}

 

相关文章:

  • STL算法
  • (4)STL算法之比较
  • linux中实现线程同步的6种方法
  • Linux TCP通信示例
  • QtTCP通信示例
  • (5)STL算法之复制
  • (6)STL算法之转换
  • (7)STL算法之交换赋值
  • 菱形继承问题
  • 改善程序与设计的N个做法
  • C++数据结构之顺序表
  • C++数据结构之单链表
  • (8)STL算法之替换
  • (9)STL算法之逆转旋转
  • NFS安装使用
  • “大数据应用场景”之隔壁老王(连载四)
  • Apache的基本使用
  • idea + plantuml 画流程图
  • IE报vuex requires a Promise polyfill in this browser问题解决
  • javascript 总结(常用工具类的封装)
  • Laravel Telescope:优雅的应用调试工具
  • Laravel 菜鸟晋级之路
  • Python代码面试必读 - Data Structures and Algorithms in Python
  • yii2中session跨域名的问题
  • 创建一个Struts2项目maven 方式
  • 基于Mobx的多页面小程序的全局共享状态管理实践
  • 利用jquery编写加法运算验证码
  • 前言-如何学习区块链
  • 人脸识别最新开发经验demo
  • 算法-图和图算法
  • 体验javascript之美-第五课 匿名函数自执行和闭包是一回事儿吗?
  • ionic入门之数据绑定显示-1
  • 如何用纯 CSS 创作一个货车 loader
  • ​【已解决】npm install​卡主不动的情况
  • ​低代码平台的核心价值与优势
  • !$boo在php中什么意思,php前戏
  • #多叉树深度遍历_结合深度学习的视频编码方法--帧内预测
  • #微信小程序(布局、渲染层基础知识)
  • $refs 、$nextTic、动态组件、name的使用
  • (python)数据结构---字典
  • (附源码)小程序儿童艺术培训机构教育管理小程序 毕业设计 201740
  • (三)uboot源码分析
  • (转)linux下的时间函数使用
  • (转)四层和七层负载均衡的区别
  • .Net Core 中间件验签
  • ::before和::after 常见的用法
  • @EventListener注解使用说明
  • @transactional 方法执行完再commit_当@Transactional遇到@CacheEvict,你的代码是不是有bug!...
  • [ Algorithm ] N次方算法 N Square 动态规划解决
  • [<MySQL优化总结>]
  • [100天算法】-二叉树剪枝(day 48)
  • [Angular 基础] - 自定义指令,深入学习 directive
  • [Angular] 笔记 18:Angular Router
  • [CSS]浮动
  • [docker] Docker的数据卷、数据卷容器,容器互联