C++进阶STL-常用的查找算法

太过爱你忘了你带给我的痛 2022-05-08 10:54 209阅读 0赞

\#include <algorithm>

## find ##

#include "stdafx.h"
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    
    class Person
    { 
    public:
    	Person(int age, int id) :m_age(age), m_id(id)
    	{ 
    
    	}
    	bool operator==(const Person& p)const  //使用find算法的时候在查找自定义对象需要 重载 == 操作符
    	{ 
    		return m_age == p.m_age&&m_id == p.m_id;
    	}
    
    	int m_age;
    	int m_id;
    };
    
    
    int main()
    { 
    	vector<Person> v1;
    	Person p1(1, 1), p2(2, 2), p3(3, 3), p4(4, 4);
    	v1.push_back(p1);
    	v1.push_back(p2);
    	v1.push_back(p3);
    	v1.push_back(p4);
    
    	vector<Person>::iterator it = find(v1.begin(),v1.end(), p2);
    	if (it == v1.end())
    	{ 
    		cout << "not found" << endl;
    	}
    	else
    	{ 
    		cout << "found" << endl;
    	}
    
        return 0;
    }

--------------------

## find\_if（会根据我们的条件（函数），返回第一个满足条件的元素的迭代器） ##

#include "stdafx.h"
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    
    class Person
    { 
    public:
    	Person(int age, int id) :m_age(age), m_id(id)
    	{ 
    
    	}
    
    	int m_age;
    	int m_id;
    };
    
    struct Compare
    { 
    	bool operator()(const Person&p1)
    	{ 
    		return p1.m_age >4;
    	};
    };
    
    
    int main()
    { 
    	vector<Person> v1;
    	Person p1(1, 1), p2(2, 2), p3(3, 3), p4(4, 4),p5(5,5);
    
    	v1.push_back(p1);
    	v1.push_back(p2);
    	v1.push_back(p3);
    	v1.push_back(p4);
    	v1.push_back(p4);
    	v1.push_back(p5);
    
    	vector<Person>::iterator it =find_if(v1.begin(),v1.end(),Compare());
    	if (it == v1.end())
    	{ 
    		cout << "not found" << endl;
    	}
    	else
    	{ 
    		cout << "found:" <<(*it).m_age<< endl;
    	}
    	
        return 0;
    }

结果：5

--------------------

## binary\_search：二分法查找（必须有序排列的 ） ##

*  进行对象查找，自定义compare函数，如果是正常类型就不用提供compare，conpare可以是普通函数，也可以是函数对象（仿函数）

#include "stdafx.h"
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    
    class Person
    { 
    public:
    	Person(int age, int id) :m_age(age), m_id(id)
    	{ 
    	}
    	int m_age;
    	int m_id;
    };
    
    struct Compare
    { 
    	bool operator()(const Person&p1, const Person& p2)
    	{ 
    		return p1.m_age < p2.m_age;
    	};
    };
    
    int main()
    { 
    	vector<Person> v1;
    	Person p1(1, 1), p2(2, 2), p3(3, 3), p4(4, 4),p5(5,5);
    
    	v1.push_back(p1);
    	v1.push_back(p2);
    	v1.push_back(p3);
    	v1.push_back(p4);
    
    	bool tmp=binary_search(v1.begin(),v1.end(), p5, Compare());
    	if (tmp == false)
    	{ 
    		cout << "not found" << endl;
    	}
    	else
    	{ 
    		cout << "found" << endl;
    	}
    
        return 0;
    }

结果：not found

--------------------

## adjacent\_find：查找相邻重复的元素 ##

*  如果进行自定义类型查找，要么重载 == 操作符，要么需要给adjacent\_find提供函数对象（仿函数）或者普通函数

#include "stdafx.h"
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    
    class Person
    { 
    public:
    	Person(int age, int id) :m_age(age), m_id(id)
    	{ 
    
    	}
    	bool operator==(const Person& p)const
    	{ 
    		return m_age == p.m_age&&m_id == p.m_id;
    	}
    
    	int m_age;
    	int m_id;
    };
    
    //struct Compare
    //{ 
    // bool operator()(const Person&p1, const Person& p2)
    // { 
    // return p1.m_age == p2.m_age && p1.m_id==p2.m_id;
    // };
    //};
    
    
    
    int main()
    { 
    	vector<Person> v1;
    	Person p1(1, 1), p2(2, 2), p3(3, 3), p4(4, 4),p5(5,5);
    
    	v1.push_back(p1);
    	v1.push_back(p2);
    	v1.push_back(p3);
    	v1.push_back(p4);
    	v1.push_back(p4);
    	v1.push_back(p5);
    
    
    	vector<Person>::iterator it =adjacent_find(v1.begin(),v1.end());
    	if (it == v1.end())
    	{ 
    		cout << "not found" << endl;
    	}
    	else
    	{ 
    		cout << "found:" <<(*it).m_age<< endl;
    	}
    
        return 0;
    }

结果：4

--------------------

## count：计算符合条件（可以自定义）的个数 ##

#include "stdafx.h"
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    
    class Person
    { 
    public:
    	Person(int age, int id) :m_age(age), m_id(id)
    	{ 
    
    	}
    	bool operator == (const Person& p2) const
    	{ 
    		return m_age == p2.m_age && m_id == p2.m_id;
    	}
    	int m_age;
    	int m_id;
    };
    
    struct Compare
    { 
    	bool operator()(const Person&p1)
    	{ 
    		return p1.m_age ==4;
    	};
    };
    
    
    int main()
    { 
    	vector<Person> v1;
    	Person p1(1, 1), p2(2, 2), p3(3, 3), p4(4, 4),p5(5,5);
    
    	v1.push_back(p4);
    	v1.push_back(p5);
    	v1.push_back(p1);
    	v1.push_back(p2);
    	v1.push_back(p3);
    	v1.push_back(p4);
    	v1.push_back(p4);
    	v1.push_back(p5);
    
    
    	int num =count(v1.begin(),v1.end(),p4);
    
    	cout << num << endl;
    
        return 0;
    }

结果：3

--------------------

## count\_if：返回满足条件（可自定义）的元素个数 ##

#include "stdafx.h"
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    
    class Person
    { 
    public:
    	Person(int age, int id) :m_age(age), m_id(id)
    	{ 
    
    	}
    	bool operator == (const Person& p2) const
    	{ 
    		return m_age == p2.m_age && m_id == p2.m_id;
    	}
    	int m_age;
    	int m_id;
    };
    
    struct Compare
    { 
    	bool operator()(const Person&p1)
    	{ 
    		return p1.m_age >3;
    	};
    };
    
    
    int main()
    { 
    	vector<Person> v1;
    	Person p1(1, 1), p2(2, 2), p3(3, 3), p4(4, 4),p5(5,5);
    
    
    	v1.push_back(p4);
    	v1.push_back(p5);
    	v1.push_back(p1);
    	v1.push_back(p2);
    	v1.push_back(p3);
    	v1.push_back(p4);
    	v1.push_back(p4);
    	v1.push_back(p5);
    
    
    	int num =count_if(v1.begin(),v1.end(),Compare());
    
    	cout << num << endl;
    
        return 0;
    }

结果：5