常用查找算法

简介

find //查找
find_if //按条件查找
adjacent_find //查找相邻重复元素
count //统计一个元素出现的个数
binary_search //二分查找法
count_if //按条件统计元素的个数

find

find 查找指定元素，找到的话返回指定元素的迭代器，找不到返回结束元素的迭代器
find(iterator begin,iterator end,value);
value 表示要茶查找的元素

查找内置数据类型

//查找内置数据类型
void test01()
{
    vector<int>v;
    for (int i = 0; i < 10; i++)
    {
        v.push_back(i + 1);
    }
    //查找元素5
    vector<int>::iterator pos = find(v.begin(), v.end(), 5);
    if (pos == v.end())
    {
        cout << "未找到！" << endl;
    }
    else
    {
        cout << "找到元素:" << *pos << endl;
    }
}

查找自定义数据类型

class Person
{
public:
    Person(string name, int age)
    {
        this->age = age;
        this->name = name;
    }
    //重载==号
    bool operator==(const Person& p)
    {
        if (this->age == p.age && this->name == p.name)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    string name;
    int age;
};

//查找自定义数据类型
void test02()
{
    vector<Person> vp;
    vp.push_back(Person("aaa", 20));
    vp.push_back(Person("bbb", 10));
    vp.push_back(Person("ccc", 36));
    vp.push_back(Person("ddd", 29));
    vp.push_back(Person("eee", 15));

    vector<Person>::iterator pos = find(vp.begin(), vp.end(), Person("ddd", 29));
    if (pos == vp.end())
    {
        cout << "未找到！" << endl;
    }
    else
    {
        cout << "找到了, 姓名：" << pos->name << " 年龄：" << pos->age << endl;
    }
}

find用来查找自定义数据类型的时候需要重载“==”运算符，否则find底层无法对自定义数据类型进行比较。

find_if

find_if(iterator begin,iterator end, _Pred);
_Perd代表谓词或者函数
按条件查找元素，查找到的话返回指定位置的迭代器，找不到的话返回结束迭代器

内置数据类型

class GreaterThanFive
{
public:
    bool operator()(int val)
    {
        return val > 5;
    }
};

//查找内置数据类型
void test01()
{
    vector<int>v;
    for (int i = 0; i < 10; i++)
    {
        v.push_back(i + 1);
    }
    //查找元素比5大的元素
    vector<int>::iterator pos = find_if(v.begin(), v.end(), GreaterThanFive());
    if (pos == v.end())
    {
        cout << "未找到！" << endl;
    }
    else
    {
        cout << "大于5的数字为:" << *pos << endl;
    }
}

自定义数据类型

class Person
{
public:
    Person(string name, int age)
    {
        this->age = age;
        this->name = name;
    }
    
    string name;
    int age;
};

class Compare
{
public:
    bool operator()(const Person &p)
    {
        return p.age > 20;
    }
};

//查找自定义数据类型
void test02()
{
    vector<Person> vp;
    vp.push_back(Person("aaa", 20));
    vp.push_back(Person("bbb", 10));
    vp.push_back(Person("ccc", 36));
    vp.push_back(Person("ddd", 29));
    vp.push_back(Person("eee", 15));

    vector<Person>::iterator pos = find_if(vp.begin(), vp.end(), Compare());
    if (pos == vp.end())  //姓名ccc 年龄36 
    {
        cout << "未找到！" << endl;
    }
    else
    {
        cout << "找到了, 姓名：" << pos->name << " 年龄：" << pos->age << endl;
    }
}

adjacent_find

adjacent_find(iterator begin,iterator end)
返回相邻重复的元素的第一个位置的迭代器，若没有找到则返回结束迭代器

void test01()
{
    vector<int>v;
    v.push_back(0);
    v.push_back(1);
    v.push_back(0);
    v.push_back(2);
    v.push_back(0);
    v.push_back(3);
    v.push_back(3);

    //查找相邻重复元素
    vector<int>::iterator pos = adjacent_find(v.begin(), v.end());
    if (pos == v.end())
    {
        cout << "未找到！" << endl;
    }
    else
    {
        cout << "相邻重复元素为:" << *pos << endl;
    }
}

binary_search

bool binary_serach(iterator begin(),iterator end(),value)
查找指定的元素找到返回true查不到返回false
只能在有序列里面使用，不能在无序序列里面使用

void test01()
{
    vector<int>v;
    for (int i = 0; i < 10; i++)
    {
        v.push_back(i + 1);
    }

    bool ret = binary_search(v.begin(), v.end(), 4);
    if (ret == true)
    {
        cout << "未找到！" << endl;
    }
    else
    {
        cout << "找到了" << endl;
    }
}

binary_search只能查找某一个元素是否存在，不能返回元素的迭代器。只能在有序序列中使用，如果序列无序，则查找
结果未必准确。

count

count(iterator begin(), iterator end(), value);
统计元素value出现的个数，返回一个整型数字

内置数据类型

//查找内置数据类型
void test01()
{
    vector<int>v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(10);
    v.push_back(20);
    v.push_back(10);
    v.push_back(10);
    v.push_back(10);

    int ret = count(v.begin(), v.end(), 10);
    cout << "元素10共有" << ret << "个";
}

自定义数据类型

class Person
{
public:
    Person(string name, int age)
    {
        this->age = age;
        this->name = name;
    }
    //重载==号
    bool operator==(const Person& p)
    {
        if (this->age == p.age)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    string name;
    int age;
};

//查找自定义数据类型
void test02()
{
    vector<Person> vp;
    vp.push_back(Person("aaa", 20));
    vp.push_back(Person("bbb", 20));
    vp.push_back(Person("ccc", 36));
    vp.push_back(Person("ddd", 29));
    vp.push_back(Person("eee", 20));

    int ret = count(vp.begin(), vp.end(), Person("fff", 20));

    cout << "与fff同岁的有" << ret << "个" << endl;  //3个
}

对于自定义数据类型，需要重载==。由于我们的只要求年龄相同，所以重载的函数体只写了this->age == p.age，如果要求年龄也相等，则需要加上条件this->name == p.name。

count_if

count_if(iterator begin,iterator end,_Pred);
_Pred 谓词
按条件统计

内置数据类型

class GreaterThan20
{
public:
    bool operator()(int val)
    {
        return val > 20;
    }
};

//查找内置数据类型
void test01()
{
    vector<int>v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    v.push_back(40);
    v.push_back(50);
    v.push_back(10);

    int ret = count_if(v.begin(), v.end(), GreaterThan20());
    cout << "大于20的元素共有" << ret << "个";  //4个
}

自定义数据类型

class Person
{
public:
    Person(string name, int age)
    {
        this->age = age;
        this->name = name;
    }
    string name;
    int age;
};

class Compare
{
public:
    bool operator()(const Person &p)
    {
        return p.age > 20;
    }
};


//查找自定义数据类型
void test02()
{
    vector<Person> vp;
    vp.push_back(Person("aaa", 20));
    vp.push_back(Person("bbb", 20));
    vp.push_back(Person("ccc", 36));
    vp.push_back(Person("ddd", 29));
    vp.push_back(Person("eee", 20));

    int ret = count_if(vp.begin(), vp.end(), Compare());

    cout << "年龄大于20的人有" << ret << "个" << endl;  //2个
}