算法概述

算法主要是由头文件 组成

是所有STL头文件中最大的一个，其中常用的功能涉及到比较、交换、查找、遍历、复制、修改、反转、排序、合并等。

体积很小，只包括在几个序列容器上进行的简单运算的模板函数

定义了一些模板类，用以声明函数对象

仿函数、算法、适配器三者关系

算法常常会和仿函数和适配器一起使用，仿函数用来扩展算法的功能，用一个重载()运算符来修改算法最关键处的功能

适配器则用来适配算法和仿函数的。

例如find_if中第三个参数在内部调用的时候只会传递给仿函数1个参数值，但是我们需要使用的仿函数有两个参数，这时候就需要用适配器来适配仿函数。
关系.jpg

算法操作自定义数据成员

容器中的成员为自定义数据类型的时候，需要在类内部对算法的功能模板行为进行重载。
例如find算法中的模板行为为==，如果不使用find_if,就需要在类内部对==进行重载

常用的遍历算法

_callback for_each(iterator begin,iterator end,_callback)

@param begin 容器开始迭代器 
@param end 容器结束迭代器
@param _callback 回调函数或者仿函数
@return 返回仿函数的对象
transform(iterator beg1,iterator end1,iterator beg2,_callback) 

@param beg1 源容器开始迭代器 
@param end1 源容器结束迭代器
@param beg2 目标容器开始迭代器
@param _callback 回调函数或者仿函数
@return 返回目标容器的迭代器

note:将容器中的数据进行搬运到另一个容器中，但是需要给目标空间开辟空间(resize).

代码示例

/*************************************************************************
	> File Name: main.cpp
	> Author:  遍历算法练习
	> Mail: 
	> Created Time: 2020年01月01日 星期三 10时24分49秒
 ************************************************************************/

# include<iostream>
# include <algorithm>
# include <vector>
# include <functional>
using namespace std;
struct myPrint  //和class的区别是成员访问权限
{
    void operator()(int num)
    {
        cout<<num<<"  ";
    }
};
//for_each代码示例
void test01()
{
    vector<int> v;
    for(int i=0;i<10;i++)
    {
        v.push_back(i);
    }
    for_each(v.begin(),v.end(),myPrint());
    cout<<endl;

}

struct myPrint02  //和class的区别是成员访问权限
{
    int m_cout=0;
    void operator()(int num)
    {
        cout<<num<<"  ";
        m_cout++;
    }
};
void test02()
{
    vector<int> v;
    for(int i=0;i<10;i++)
    {
        v.push_back(i);
    }
    myPrint02 my=for_each(v.begin(),v.end(),myPrint02());
    cout<<endl;
    cout<<my.m_cout<<endl;

}
struct myPrint03:public binary_function<int,int,void> //和class的区别是成员访问权限
{
    void operator()(int num,int start)const 
    {
        cout<<num+start<<"  ";
    }
};
void test03()
{
    vector<int> v;
    for(int i=0;i<10;i++)
    {
        v.push_back(i);
    }
    for_each(v.begin(),v.end(),bind2nd(myPrint03(),100));
    cout<<endl;

}

/********TransForm*******************/
class TransForm04
{
    public:
        int operator()(int val)
    {
        return val+48;
    }
};
void test04()
{
    vector<int> v;
    for(int i=0;i<10;i++)
    {
        v.push_back(i);
    }
    vector<int>Target;
    Target.resize(v.size());
    transform(v.begin(),v.end(),Target.begin(),TransForm04());
    for_each(Target.begin(),Target.end(),[](int val){cout<< val <<" ";});
    
}
class TransForm05
{
    public:
        int operator()(int val,int start)
    {
        return val+start;
    }
};
void test05()  //两数相加
{
    vector<int>v1;
    vector<int>v2;
    for(int i=0;i<10;i++)
    {
        v1.push_back(i);
        v2.push_back(i);
    }
    vector<int>Target;
    Target.resize(v1.size());
    transform(v1.begin(),v1.end(),v2.begin(),Target.begin(),TransForm05());
    for_each(v1.begin(),v1.end(),[](int v){cout<<v<<" ";});
    cout<<endl;
    for_each(v2.begin(),v2.end(),[](int v){cout<<v<<" ";});
    cout<<endl;
    for_each(Target.begin(),Target.end(),[](int v){cout<<v<<" ";});
    cout<<endl;
    
}
int main()
{
    test05();

    return 0;
}

for_each:test01测试
for_each.jpg

transform:test05测试
transform.jpg

常用的查找算法

find查找元素

如果是自定义的数据类型，那么需要在类里面重载==.

iterator find(iterator beg,iterator end,T)

@param beg 容器开始迭代器
@param end 容器结束迭代器
@param value 查找的元素
@return 返回查找元素的位置
iterator find_if(iterator beg,iterator end,_callback)

@param beg 容器开始迭代器
@param end 容器结束迭代器
@param _callback 回调函数或者一元谓词（返回bool类型的函数对象）
@return 返回查找元素的位置

count计算元素出现个数

int count(iterator beg,iterator end,value)

@param beg 容器开始迭代器
@param end 容器结束迭代器
@param value 查找的元素
@return 返回元素出现的次数

int count_if(iterator beg,iterator end,_callback)

按照条件计算元素出现的次数

@param beg 容器开始迭代器
@param end 容器结束迭代器
@param _callback 回调函数或者谓词
@return 返回元素出现的次数

adjacent_find找到相邻重复元素的第一个位置

iterator adjacent_find(iterator beg,iterator end)
iterator adjacent_find (iterator beg,iterator end,BinaryPredicate pred);

@param beg 容器开始迭代器
@param end 容器结束迭代器
@param BinaryPredicate 回调函数或者一元谓词（返回bool类型的函数对象）
@return 返回相邻重复元素的第一个位置的迭代器

binary_search 二分查找

bool binary_search(iterator beg,iterator end,value)
bool binary_search (iterator beg,iterator end,value, Compare comp);
二分查找法  只能用于**有序序列**!!!

需要用随机迭代器

该功能模板的行为等效于：operator<

@param beg 容器开始迭代器
@param end 容器结束迭代器
@param value 查找的元素
@param Compare bool(*)(T,T)的回调函数或者二元谓词
@return 返回true或者false

代码示例

/*************************************************************************
	> File Name: main.cpp
	> Author: 
	> Mail: 
	> Created Time: 2020年01月01日 星期三 11时28分40秒
 ************************************************************************/

# include <string>
# include <vector>
# include <algorithm>
# include<iostream>
using namespace std;
class Person
{
    public:
        Person(string name,int age)
    {
        m_name=name;
        m_age=age;
    }
        bool operator==(const Person &p)
    {
        if(m_name==p.m_name&&m_age==p.m_age)
            return true;
        else
            return false;
     
    }
    string getName()
    {return m_name;}
    int getAge()
    {
        return m_age;
    }
    private:
    string m_name;
    int m_age;
};
void test01()
{
    vector<Person> v;
    Person p1("aaala",10);
    Person p2("askldj",20);
    Person p3("aldkj",30);
    v.push_back(p1);
    v.push_back(p2);
    v.push_back(p3);
    if(find(v.begin(),v.end(),p2)!=v.end())
    {
        cout<<"找到了"<<endl;
    }
}
class MyCompare:public binary_function<Person *,Person *,bool>{
    public:
        bool operator()(Person *p1,Person *p2)const
    {
        if(p1->getName()==p2->getName()&&p1->getAge()==p2->getAge())
            return true;
        else
            return false;
    }
};

void test02()
{
    vector<Person *> v;
    Person p1("aaala",10);
    Person p2("askldj",20);
    Person p3("aldkj",30);
    v.push_back(&p1);
    v.push_back(&p2);
    v.push_back(&p3);
    Person *p=new Person("basd",20);
    if(find_if(v.begin(),v.end(),bind2nd(MyCompare(),p))!=v.begin())
    {
        cout<<"找到了"<<endl;
    }
}

void test03()
{
    vector<int> v;
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
    v.push_back(5);
    v.push_back(6);
    v.push_back(2);
    vector<int>::iterator pos=adjacent_find(v.begin(),v.end());
    if(pos!=v.end())
    {
        cout<<"找到了相邻重复元素"<<*pos<<endl;
    }

    
   
}

void test04()
{ 
    vector<int> v;
    for(int i=0;i<10;i++)
    {
        v.push_back(i);
    }
    if(binary_search(v.begin(),v.end(),4))
    {
        cout<<"找到4"<<endl;
    }else
        cout<<"找不到"<<endl;
      
}
void 

int main()
{
    test02();
    test03();
    test04();
    test05();
    return 0;
}

官网的二分查找例子


// binary_search example
# include <iostream>     // std::cout
# include <algorithm>    // std::binary_search, std::sort
# include <vector>       // std::vector

bool myfunction (int i,int j) { return (i<j); }

int main () {
  int myints[] = {1,2,3,4,5,4,3,2,1};
  std::vector<int> v(myints,myints+9);                         // 1 2 3 4 5 4 3 2 1

  // using default comparison:
  std::sort (v.begin(), v.end());

  std::cout << "looking for a 3... ";
  if (std::binary_search (v.begin(), v.end(), 3))
    std::cout << "found!\n"; else std::cout << "not found.\n";

  // using myfunction as comp:
  std::sort (v.begin(), v.end(), myfunction);

  std::cout << "looking for a 6... ";
  if (std::binary_search (v.begin(), v.end(), 6, myfunction))
    std::cout << "found!\n"; else std::cout << "not found.\n";

  return 0;
}

二分查找.jpg