STL算法（查找）

作者: 第八区 | 来源:发表于2017-09-01 18:20 被阅读13次

常用的 STL 查找算法
STL算法（查找）
STL算法之常用查找
C++ STL是什么
音视频开发之旅（23) 算法系列 - 冒泡排序
c++ STL algorithm(转载)
标准模板库STL
极客班STL与泛型编程（第三周笔记）
【Geekband】Week 8 Notes.md
[C++] 习题 2.18 倒序查找字串

简介

adjacent_find
binary_search
cout/cout_if
find/find_if/equal_range

adjacent_find

在一个集合中寻找两个相邻的元素。如果相等，就返回这两个相等元素第一个元素的迭代器，不等的话，就返回v.end().
函数原型：

template<class _FwdIt,
    class _Pr> inline
    _FwdIt adjacent_find(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
    {   // find first satisfying _Pred with successor
    _DEBUG_RANGE(_First, _Last);
    _DEBUG_POINTER_IF(_First != _Last && _STD next(_First) != _Last, _Pred);
    return (_Rechecked(_First,
        _Adjacent_find_unchecked(_Unchecked(_First), _Unchecked(_Last), _Pred)));
    }

        // TEMPLATE FUNCTION adjacent_find
template<class _FwdIt> inline
    _FwdIt adjacent_find(_FwdIt _First, _FwdIt _Last)
    {   // find first matching successor
    return (_STD adjacent_find(_First, _Last, equal_to<>()));
    }

示例

#include "stdafx.h"
#include "iostream"
#include "string"
#include "algorithm"
#include "vector"
#include "list"
using namespace std;
class Student{
private:
    int number;
    string name;
public:
    Student(int number, string name) {
        cout << "构造 " << number << " " << name.c_str() << endl;
        this->number = number;
        this->name = name;
    }
    Student(const Student & stu) {
        //cout << "copy构造" <<stu.getNumber()<<" "<<stu.getName().c_str()<< endl;
        this->number = stu.getNumber();
        this->name = stu.getName();
    }
    ~Student() {
        //cout<<"析构 " << this->number << " " << this->name.c_str() << endl;
    }

    void print() {
        cout << "print 》》 " << this->number << " " << this->name.c_str() << endl;
    }

    int getNumber() const{
        return this->number;
    }
    string getName()const {
        return this->name;
    }
};

struct StuFunc
{
    bool operator()(const Student & stu1, const Student & stu2) const {
        return stu1.getNumber() == stu2.getNumber();
    }
};

void printStuV(vector<Student> v) {
    cout << "开始遍历============" << endl;
    for (vector<Student>::iterator it = v.begin(); it != v.end(); it++) {
        it->print();
    }
    cout << "结束遍历============" << endl;
}
int main()
{
    vector<Student> v;
    v.push_back(Student(1, "one"));
    Student stu2(2, "two");
    v.push_back(stu2);
    v.push_back(stu2);
    v.push_back(Student(3, "three"));
    v.push_back(Student(4, "four"));
    v.push_back(Student(5, "five"));
    printStuV(v);
    vector<Student>::iterator res=adjacent_find(v.begin(), v.end(), StuFunc());
    if (res != v.end()) {
        cout << "adjacent_find result:"<<endl;
        res++->print();
        res++->print();
        res->print();
    }
    else {
        cout << "adjacent_find nothing!" << endl;
    }
    return 0;
}

结果：

adjacent_find.png

binary_search

二分查找
集合必须是有序的

示例

#include "stdafx.h"
#include "iostream"
#include "string"
#include "algorithm"
#include "vector"
#include "list"
using namespace std;
class Student{
private:
    int number;
    string name;
public:
    Student(int number, string name) {
        cout << "构造 " << number << " " << name.c_str() << endl;
        this->number = number;
        this->name = name;
    }
    Student(const Student & stu) {
        //cout << "copy构造" <<stu.getNumber()<<" "<<stu.getName().c_str()<< endl;
        this->number = stu.getNumber();
        this->name = stu.getName();
    }
    ~Student() {
        //cout<<"析构 " << this->number << " " << this->name.c_str() << endl;
    }

    void print()const {
        cout << "print 》》 " << this->number << " " << this->name.c_str() << endl;
    }

    int getNumber() const{
        return this->number;
    }
    string getName()const {
        return this->name;
    }
};

struct StuFunc
{
    bool operator()(const Student & stu1, const Student & stu2) const {
        cout << "StuFunc》》"<<endl;
        stu1.print();
        stu2.print();
        return stu1.getNumber() <stu2.getNumber();
    }
};

void printStuV(vector<Student> v) {
    cout << "开始遍历============" << endl;
    for (vector<Student>::iterator it = v.begin(); it != v.end(); it++) {
        it->print();
    }
    cout << "结束遍历============" << endl;
}
int main()
{
    vector<Student> v;
    v.push_back(Student(1, "one"));
    Student stu2(2, "two");
    v.push_back(stu2);
    v.push_back(stu2);
    v.push_back(Student(3, "three"));
    v.push_back(Student(4, "four"));
    v.push_back(Student(5, "five"));
    printStuV(v);
    bool res=binary_search(v.begin(), v.end(),Student(7,"keyword"), StuFunc());
    cout << "binary_search 7: " << res << endl << endl;;
    res = binary_search(v.begin(), v.end(), Student(2, "keyword"), StuFunc());
    cout << "binary_search 2: " << res << endl;
    return 0;
}

结果：

binary_search.png

count/count_if

前两个参数是iterator(迭代器)，表示查找半闭合区间的前后两个位置。

count_if 第三个参数是具体元素
count_if 更加灵活，用来查找自定义类型数据或复杂的查询条件
- 带参数的仿函数
- 通过函数适配器使用系统预定义的仿函数。
```
 bind2nd( greater<int>(), 1)
```

示例

这里的Student沿用前面的定义。

struct StuCount {
private:
    int num ;
public:
    StuCount(const int num) {
        this->num = num;
    }
    bool operator()(const Student & stu) {
        return stu.getNumber() == num;
    }
};

int main()
{
    vector<Student> v;
    v.push_back(Student(1, "one"));
    Student stu2(2, "two");
    v.push_back(stu2);
    v.push_back(stu2);
    v.push_back(Student(3, "three"));
    v.push_back(Student(4, "four"));
    v.push_back(Student(5, "five"));
    printStuV(v);
    int sum=count_if(v.begin(), v.end(), StuCount(2));
    cout << "vStu count_if 2: " << sum << endl;
    vector<int> vNum;
    vNum.push_back(1);
    vNum.push_back(1);
    vNum.push_back(1);
    vNum.push_back(2);
    cout << "vNum count 1: " << count(vNum.begin(),vNum.end(),1) << endl;
    cout << "vNum count_if 1: " << count_if(vNum.begin(), vNum.end(),bind2nd( greater<int>(), 1)) << endl;
    return 0;
}

结果：

count.png

find/find_if/equal_range

find 利用底层元素的等于操作符，对指定范围内的元素与输入值进行比较。当匹配时，结束搜索，返回该元素的迭代器。
equal_range: 返回一对iterator，第一个表示lower_bound,第二个表示upper_bound。
find_if: 使用输入的函数代替等于操作符执行find。返回被找到的元素的迭代器。

struct StuCount {
private:
    int num ;
public:
    StuCount(const int num) {
        this->num = num;
    }
    bool operator()(const Student & stu) {
        return stu.getNumber() == num;
    }
};

int main()
{
    vector<Student> v;
    v.push_back(Student(1, "one"));
    Student stu2(2, "two");
    v.push_back(stu2);
    v.push_back(stu2);
    v.push_back(Student(3, "three"));
    v.push_back(Student(4, "four"));
    v.push_back(Student(5, "five"));
    printStuV(v);
    vector<Student>::iterator itStuRes=find_if(v.begin(), v.end(), StuCount(2));
    if (itStuRes != v.end()) {
        itStuRes->print();
    }
    vector<int> vNum;
    vNum.push_back(1);
    vNum.push_back(1);
    vNum.push_back(1);
    vNum.push_back(2);
    vector<int>::iterator itNumRes=find(vNum.begin(), vNum.end(), 2);
    cout <<"num find " << *itNumRes << endl;

    pair<vector<int>::iterator,vector<int>::iterator> pRes=equal_range(vNum.begin(), vNum.end(), 1);
    cout << "equal_range left:" << *pRes.first << " right:" << *pRes.second << endl;
    return 0;
}

结果：

find.png

常用的 STL 查找算法
常用的 STL 查找算法《effective STL》中有句忠告，尽量用算法替代手写循环；查找少不了循环遍历，在...
STL算法（查找）
简介 adjacent_findbinary_searchcout/cout_iffind/find_if/equ...
STL算法之常用查找
find API 实例 find_if API 实例 adjacent_find API 实例 binary_se...
C++ STL是什么
STL 组件主要包括容器，迭代器、算法和仿函数。STL 基本结构和 STL 组件对应。 STL 主要由迭代器、算法...
音视频开发之旅（23) 算法系列 - 冒泡排序
目录主流排序算法 stl中sort的实现冒泡算法优化点资料收获 Stl中算法组件是Function te...
c++ STL algorithm(转载)
STL中的所有算法(70个) STL算法部分主要由头文件 ,,组成。要使...
标准模板库STL
一、STL简介 STL实现了计算机科学领域里常用的基本数据结构和基本算法； STL主要包含了容器、算法、迭代器。 ...
极客班STL与泛型编程（第三周笔记）
算法头文件（STL算法部分主要由头文件,,组成。要使用STL中的算法函数必须包含头文件，对于数值算法须包含，中...
【Geekband】Week 8 Notes.md
1. STL常见非变异算法 2. STL常见变异算法 2.1 Copy - 对数据的各类拷贝 2.2 Swap -...
[C++] 习题 2.18 倒序查找字串
设计一个算法，在串 str 中查找字串 substr 最后一次出现的位置（不能使用 STL）为了完成那个不能使用...