c++常见算法_c++算法

/*
1 @param beg1 源容器开始迭代器
4 @param end1 源容器结束迭代器
5 @param beg2 目标容器开始迭代器
6 @param _cakkback 回调函数或者函数对象
7 @return 返回目标容器迭代器
8 */
transform(iterator beg1, iterator end1, iterator beg2, _callbakc);

其中 回调函数 _callback 可以使用  普通函数 或者 函数对象 实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void printVectorInt(vector<int> &v)
{
    vector<int>::iterator it;
    for(it=v.begin(); it!=v.end(); it++)
    {
        cout<<*it<<" ";
    }
    cout<<endl;
}
 
 
//回调函数 使用 普通函数完成，也可以使用函数对象完成
//回调函数中对 数据 进行需要的处理
int myTransInt01(int val)
{
    return val;
}
 
void test01()
{
    vector<int> v1;
    v1.push_back(10);
    v1.push_back(70);
    v1.push_back(30);
    v1.push_back(50);
    v1.push_back(90);
 
 
    vector<int> v2;
    v2.resize(v1.size());
    transform(v1.begin(), v1.end(), v2.begin(), myTransInt01);
    printVectorInt(v2);
}
 
 
int main(int argc, char *argv[])
{
    test01();
    return 0;
}

 2、常见的查找算法

2.1、find 算法查找元素

 
/*
2 find算法 查找元素
3 @param beg 容器开始迭代器
4 @param end 容器结束迭代器
5 @param value 查找的元素
6 @return 返回查找元素的位置
7 */
find(iterator beg, iterator end, value)；

2.1.1、find 算法查找基本类型

 
void test02()
{
    vector<int> v1;
    v1.push_back(10);
    v1.push_back(70);
    v1.push_back(30);
    v1.push_back(50);
    v1.push_back(90);
 
    vector<int>::iterator ret;
    ret = find(v1.begin(), v1.end(), 30);
    if(ret != v1.end())
    {
        cout<<"查找的数据:"<<*ret<<endl;
    }
}
 
int main(int argc, char *argv[])
{
    test02();
    return 0;
}

2.1.2、find 算法查找自定义类型

find 查找自定义数据类型  需要重载==

 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
#include<string>
class Person
{
    friend void test03();
private:
    int num;
    string name;
public:
    Person(){}
    Person(int num, string name){
        this->num = num;
        this->name = name;
    }
    bool operator==(const Person &ob)
    {
        return ((this->num == ob.num) && (this->name == ob.name));
    }
};
 
void test03()
{
    vector<Person> v1;
    v1.push_back(Person(100,"lucy"));
    v1.push_back(Person(101,"bob"));
    v1.push_back(Person(102,"tom"));
 
    vector<Person>::iterator ret;
    //find 查找自定义数据类型  需要重载==
    ret = find(v1.begin(), v1.end(), Person(101,"bob"));
    if(ret != v1.end())
    {
        cout<<"查找的数据:"<<(*ret).num<<" "<<(*ret).name<<endl;
    }
}
 
int main(int argc, char *argv[])
{
    test03();
    return 0;
}

如果没有重载 相等（==）运算符，则编译会报错

 也即是 find 函数查找自定义类型数据的时候，是从开始迭代器到末尾迭代器中依次将容器中的元素从头到尾取出来，然后和当前需要查找的元素一一对比，但是由于是自定义类型的数据，所以必须要重 相等（==）运算符，否则编译会报错

bool operator==(const Person &ob)
    {
        return ((this->num == ob.num) && (this->name == ob.name));
    }

2.2、find_if 按照条件查找

/*
2 @param beg 容器开始迭代器
3 @param end 容器结束迭代器
4 @param callback 回调函数或者谓词(返回bool类型的函数对象)
5 @return bool 查找返回true 否则false
6 */
find_if(iterator beg, iterator end, _callback);

从容器中查找出大于 30 的元素

oid test04()
{
    vector<int> v1;
    v1.push_back(10);
    v1.push_back(70);
    v1.push_back(30);
    v1.push_back(50);
    v1.push_back(90);
 
    vector<int>::iterator ret;
    ret = find_if(v1.begin(), v1.end(),  bind2nd(greater<int>(),30)  );
    if(ret != v1.end())
    {
        cout<<"查找的数据:"<<*ret<<endl;
    }
}
 
int main(int argc, char *argv[])
{
    test04();
    return 0;
}

2.3、adjacent_find算法 查找相邻重复元素

 
void test05()
{
    vector<int> v1;
    v1.push_back(10);
    v1.push_back(20);
    v1.push_back(20);
    v1.push_back(30);
    v1.push_back(30);
    vector<int>::iterator ret;
 
    ret = adjacent_find(v1.begin(),v1.end());
    if(ret != v1.end())
    {
        cout<<"第一个相邻重复的元素:"<<*ret<<endl;
    }
}
 
int main(int argc, char *argv[])
{
    test05();
    return 0;
}

2.4、binary_search算法 二分查找法

binary_search 查找的结果和前面的查找算法的返回值不一样，前面的查找算法是迭代器，但是binary_search 查找的结果是 bool 类型

1 /*
2 注意: 在无序序列中不可用
3 @param beg 容器开始迭代器
4 @param end 容器结束迭代器
5 @param value 查找的元素
6 @return bool 查找返回true 否则false
7 */
bool binary_search(iterator beg, iterator end, value);

void test06()
{
    vector<int> v1;
    v1.push_back(10);
    v1.push_back(70);
    v1.push_back(30);
    v1.push_back(50);
    v1.push_back(90);
    sort(v1.begin(), v1.end());
 
    bool ret;
    ret = binary_search(v1.begin(), v1.end(),  30);
    if(ret)
    {
        cout<<"存在该数据"<<endl;
    }
}

2.5、count算法 统计元素出现次数

/*
2 @param beg 容器开始迭代器
3 @param end 容器结束迭代器
4 @param value
5 @return int返回元素个数
6 */
count(iterator beg, iterator end, value);

 
void test07()
{
    vector<int> v1;
    v1.push_back(10);
    v1.push_back(30);
    v1.push_back(70);
    v1.push_back(30);
    v1.push_back(90);
 
    cout<<count(v1.begin(), v1.end(), 30)<<endl;
}
 
int main(int argc, char *argv[])
{
    test07();
    return 0;
}

2.6、count_if算法 统计元素出现次数

/*
2 @count_if算法 统计元素出现次数
3 @param beg 容器开始迭代器
4 @param end 容器结束迭代器
5 @param callback 回调函数或者谓词(返回bool类型的函数对象)
6 @return int返回元素个数
7 */
count_if(iterator beg, iterator end, _callback);

 
void test08()
{
    vector<int> v1;
    v1.push_back(10);
    v1.push_back(30);
    v1.push_back(70);
    v1.push_back(30);
    v1.push_back(90);
 
    cout<<count_if(v1.begin(), v1.end(), bind2nd(greater<int>(), 10) )<<endl;
}
 
int main(int argc, char *argv[])
{
    test08();
    return 0;
}

3、常用的排序算法

3.1、merge算法 容器元素合并

/*
2 merge算法 容器元素合并，并存储到另一容器中
3 注意:两个容器必须是有序的
4 @param beg1 容器1开始迭代器
5 @param end1 容器1结束迭代器
6 @param beg2 容器2开始迭代器
7 @param end2 容器2结束迭代器
8 @param dest 目标容器开始迭代器
9 */
merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterat
or dest)

void test10()
{
    vector<int> v1;
    v1.push_back(10);
    v1.push_back(30);
    v1.push_back(50);
 
    vector<int> v2;
    v2.push_back(20);
    v2.push_back(40);
    v2.push_back(60);
    v2.push_back(70);
    v2.push_back(80);
 
    vector<int> v3;
    v3.resize(v1.size() + v2.size());
    merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
    printVectorInt(v3);
}
 
int main(int argc, char *argv[])
{
    test10();
    return 0;
}

3.2、sort算法 容器元素排序  

/*
2 sort算法 容器元素排序
3 @param beg 容器1开始迭代器
4 @param end 容器1结束迭代器
5 @param _callback 回调函数或者谓词(返回bool类型的函数对象)
6 */
sort(iterator beg, iterator end, _callback)

3.3、random_shuffle算法 对指定范围内的元素随机调整次序

/*
2 random_shuffle算法 对指定范围内的元素随机调整次序
3 @param beg 容器开始迭代器
4 @param end 容器结束迭代器
5 */
random_shuffle(iterator beg, iterator end)

通过随机数种子调整元素顺序

#include<stdlib.h>
#include<time.h>
void test11()
{
    vector<int> v1;
    v1.push_back(10);
    v1.push_back(30);
    v1.push_back(50);
    v1.push_back(70);
    v1.push_back(90);
    printVectorInt(v1);
    //设置随机数种子
    srand(time(NULL));
    //洗牌
    random_shuffle(v1.begin(), v1.end());
    printVectorInt(v1);
}

3.4、reverse算法 反转指定范围的元素

不管容器中的元素有没有顺序，都可以反转

/*
2 reverse算法 反转指定范围的元素
3 @param beg 容器开始迭代器
4 @param end 容器结束迭代器
5 */
reverse(iterator beg, iterator end)

 
void test12()
{
    vector<int> v1;
    v1.push_back(10);
    v1.push_back(30);
    v1.push_back(50);
    v1.push_back(70);
    v1.push_back(90);
    printVectorInt(v1);
    //洗牌
    reverse(v1.begin(), v1.end());
    printVectorInt(v1);
}
 
int main(int argc, char *argv[])
{
    test12();
    return 0;
}

4、常见拷贝替换算法

4.1、copy算法

/*
2 copy算法 将容器内指定范围的元素拷贝到另一容器中
3 @param beg 容器开始迭代器
4 @param end 容器结束迭代器
5 @param dest 目标起始迭代器
6 */
copy(iterator beg, iterator end, iterator dest)

void test13()
{
    vector<int> v1;
    v1.push_back(10);
    v1.push_back(30);
    v1.push_back(50);
    v1.push_back(70);
    v1.push_back(90);
    vector<int> v2;
    v2.resize(v1.size());
 
    copy(v1.begin(), v1.end(), v2.begin());
    printVectorInt(v2);
}
 
int main(int argc, char *argv[])
{
    test13();
    return 0;
}

4.2、copy算法升级

#include<iterator>
void test14()
{
    vector<int> v1;
    v1.push_back(10);
    v1.push_back(30);
    v1.push_back(50);
    v1.push_back(70);
    v1.push_back(90);
     
    //第二个迭代器可以是控制台 ostream_iterator<int>(cout, " ") 
    copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " ") );
    cout<<endl;
}
 
int main(int argc, char *argv[])
{
    test14();
    return 0;
}

4.3、replace算法  

/*
2 replace算法 将容器内指定范围的旧元素修改为新元素
3 @param beg 容器开始迭代器
4 @param end 容器结束迭代器
5 @param oldvalue 旧元素
6 @param oldvalue 新元素
*/
replace(iterator beg, iterator end, oldvalue, newvalue)

void test15()
{
    vector<int> v1;
    v1.push_back(10);
    v1.push_back(30);
    v1.push_back(50);
    v1.push_back(70);
    v1.push_back(90);
 
    copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " ") );
    cout<<endl;
 
    replace(v1.begin(), v1.end(), 30, 3000);
 
    copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " ") );
    cout<<endl;
}
 
 
int main(int argc, char *argv[])
{
    test15();
  
}  

/*
2 replace_if算法 将容器内指定范围满足条件的元素替换为新元素
3 @param beg 容器开始迭代器
4 @param end 容器结束迭代器
5 @param callback函数回调或者谓词(返回Bool类型的函数对象)
6 @param oldvalue 新元素
7 */
replace_if(iterator beg, iterator end, _callback, newvalue)

void test16()
{
    vector<int> v1;
    v1.push_back(10);
    v1.push_back(30);
    v1.push_back(50);
    v1.push_back(70);
    v1.push_back(90);
 
    copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " ") );
    cout<<endl;
 
    replace_if(v1.begin(), v1.end(), bind2nd(greater<int>(),30), 3000);
 
    copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " ") );
    cout<<endl;
}

class GreaterThan30
{
public:
    bool operator()(int value)
    {
        return value>30;
    }
};
 
void test16()
{
    vector<int> v1;
    v1.push_back(10);
    v1.push_back(30);
    v1.push_back(50);
    v1.push_back(70);
    v1.push_back(90);
 
    copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " ") );
    cout<<endl;
 
    replace_if(v1.begin(), v1.end(), GreaterThan30() , 3000);
 
    copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " ") );
    cout<<endl;
}
 
int main(int argc, char *argv[])
{
    test16();
    return 0;
}

/*
3 @param c1容器1
4 @param c2容器2
5 */
swap(container c1, container c2)

/*
3 @param beg 容器开始迭代器
4 @param end 容器结束迭代器
5 @param value累加值 （注意：求和完后 + value）
6 */
accumulate(iterator beg, iterator end, value)

/*
3 @param beg 容器开始迭代器
4 @param end 容器结束迭代器
5 @param value t填充元素
6 */
fill(iterator beg, iterator end, value)

void test17()
{
   vector<int> v1;
   v1.resize(5);
 
   fill(v1.begin(), v1.end(), 10);
 
   copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " ") );
   cout<<endl;
}
 
int main(){
    test17();
}

/*
4 @param beg1 容器1开始迭代器
5 @param end1 容器1结束迭代器
6 @param beg2 容器2开始迭代器
7 @param end2 容器2结束迭代器
8 @param dest 目标容器开始迭代器
9 @return 目标容器的最后一个元素的迭代器地址
10 */
set_intersection(iterator beg1, iterator end1, iterator beg2, iterator e
nd2,iterator dest)

void test18()
{
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(3);
    v1.push_back(5);
    v1.push_back(7);
    v1.push_back(9);
 
    vector<int> v2;
    v2.push_back(7);
    v2.push_back(9);
    v2.push_back(11);
    v2.push_back(13);
    v2.push_back(15);
 
    vector<int> v3;    //存放交集
    v3.resize( min(v1.size(),v2.size()));
 
    vector<int>::iterator ret;
    ret = set_intersection(v1.begin(), v1.end(), v2.begin(),v2.end(), v3.begin());
    copy(v3.begin(), ret, ostream_iterator<int>(cout, " ") );
    cout<<endl;
}
 
int main(){
    test18();
    return 0;
}

 /*
4 @param beg1 容器1开始迭代器
5 @param end1 容器1结束迭代器
6 @param beg2 容器2开始迭代器
7 @param end2 容器2结束迭代器
8 @param dest 目标容器开始迭代器
9 @return 目标容器的最后一个元素的迭代器地址
10 */
set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, it
erator dest)

void test18()
{
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(3);
    v1.push_back(5);
    v1.push_back(7);
    v1.push_back(9);
 
    vector<int> v2;
    v2.push_back(7);
    v2.push_back(9);
    v2.push_back(11);
    v2.push_back(13);
    v2.push_back(15);
 
    vector<int> v3;    //存放并集
    v3.resize(v1.size()+v2.size());
 
    vector<int>::iterator ret;
    ret = set_union(v1.begin(), v1.end(), v2.begin(),v2.end(), v3.begin());
    copy(v3.begin(), ret, ostream_iterator<int>(cout, " ") );
    cout<<endl;
}
 
int main(){
    test18();
    return 0;
}

 /*
4 @param beg1 容器1开始迭代器
5 @param end1 容器1结束迭代器
6 @param beg2 容器2开始迭代器
7 @param end2 容器2结束迭代器
8 @param dest 目标容器开始迭代器
9 @return 目标容器的最后一个元素的迭代器地址
10 */
set_difference(iterator beg1, iterator end1, iterator beg2, iterator end
2, iterator dest)

void test18()
{
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(3);
    v1.push_back(5);
    v1.push_back(7);
    v1.push_back(9);
 
    vector<int> v2;
    v2.push_back(7);
    v2.push_back(9);
    v2.push_back(11);
    v2.push_back(13);
    v2.push_back(15);
 
    vector<int> v3;    //存放差集
    v3.resize(v1.size());  //A - B ,则最大为 v1的容器大小
 
    vector<int>::iterator ret;
    ret = set_difference(v1.begin(), v1.end(), v2.begin(),v2.end(), v3.begin());
    copy(v3.begin(), ret, ostream_iterator<int>(cout, " ") );
    cout<<endl;
}
 
int main(){
    test18();
    return 0;
}