常用查找算法

shienh 2020年02月10日 258次浏览
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>

using namespace std;

//对于自定义数据类型,需要重载==运算符
class Person{
  public:
    Person(string name,int age){
        this->age = age;
        this->name = name;
    }

    bool operator ==(const Person& p){
        return (this->name == p.name && this->age == p.age);
    }
public:
    string name;
    int age;

};

class ComparePerson:public binary_function<Person*,Person*,bool>{
public:
    bool operator()(Person* p1,Person* p2)const{
        if(p1->name == p2->name && p1->age == p2->age){
            return true;
        }
        return false;
    }
};

void test1(){
    vector<int> v;
    for(int i = 0; i < 10; i++){
        v.push_back(i);
    }
    vector<int>::iterator it =  find(v.begin(),v.end(),5);
    if(it!=v.end()){
        cout<<"value:"<<*it<<endl;
    }
    else{
        cout<<"no find value"<<endl;
    }
}

void test2(){
    vector<Person> p;
    Person p1("aaa",10);
    Person p2("bbb",20);
    Person p3("ccc",30);
    Person p4("ddd",40);
    Person p5("eee",50);
    p.push_back(p1);
    p.push_back(p2);
    p.push_back(p3);
    p.push_back(p4);
    p.push_back(p5);
    vector<Person>::iterator pIt = find(p.begin(),p.end(),p2);
    if(pIt!=p.end()){
        cout<<"name:"<<(*pIt).name<<endl;
    }
    else{
        cout<<"no find person"<<endl;
    }
}

void test3(){
    vector<Person*> p;
    Person p1("aaa",10);
    Person p2("bbb",20);
    Person p3("ccc",30);
    Person p4("ddd",40);
    Person p5("eee",50);
    p.push_back(&p1);
    p.push_back(&p2);
    p.push_back(&p3);
    p.push_back(&p4);
    p.push_back(&p5);
    vector<Person*>::iterator it = find_if(p.begin(),p.end(),bind2nd(ComparePerson(),&p2));
    if(it!=p.end()){
        cout<<"name:"<<(*it)->name<<endl;
    }
    else{
        cout<<"no find person"<<endl;
    }
}

void test4(){
    //查找相邻重复的元素,返回第一个元素的迭代器
    //adjacent_find
    vector<int> v;
    for(int i = 0; i < 10; i++){
        v.push_back(i);
    }
    v.push_back(9);

    vector<int>::iterator it = adjacent_find(v.begin(),v.end());
    if(it!=v.end()){
        cout<<*it<<endl;
    }
    else{
        cout<<"no find"<<endl;
    }
}

//binary_search 对有序容器进行查找,用的是二分查找算法
void test5(){
    vector<int> v;
    for(int i = 0; i < 10;i++){
        v.push_back(i);
    }
    bool ret = binary_search(v.begin(),v.end(),2);
    if(ret){
        cout<<"find"<<endl;
    }
    else{
        cout<<"no find"<<endl;
    }
}

//count统计
void test6(){
    vector<int> v;
    for(int i = 0; i < 10;i++){
        v.push_back(i);
    }
    int num = count(v.begin(),v.end(),3);
    cout<<"num:"<<num<<endl;
}

//统计大于7的个数
class compareTest7{
public:
    bool operator() (int val){
        return val > 7;
    }
};

//count_if
void test7(){
    vector<int> v;
    for(int i = 0; i < 10;i++){
        v.push_back(i);
    }
    int num = count_if(v.begin(),v.end(),compareTest7());
    cout<<"num:"<<num<<endl;
}



int main(int argc, char *argv[])
{
    test1();
    test2();
    test3();
    test4();
    test5();
    test6();
    test7();
    return 0;
}

运行结果:
image.png