八、算法概述(遍历、查找、排序、替换)

算法主要由头文件<algorithm> <function> <numeric>组成

这里只是将这三个头文件里面的常用算法，不是算法结构

  • <algorithm>是所有STL头文件中最大的一个，其中常用的功能设计到比较、交换、查找、遍历、赋值、修改、反转、排序、合并等
  • <numeric>体积很小，只包括在几个序列容器上进行的简单运算的模板函数
  • <functional>定义了一些模板类，用以声明函数对象

STL算法分为：质变函数和非质变函数

所有的STL算法都作用在由迭代器(first,end)所标示出来的区间上.

质变算法，是指运算过程中会改变区间内的(迭代器所指)的元素内容。比如，拷贝(copy)、互换(swap)、替代(replace)、填写(fill)、删除(remove)、排序(sort)等算法都属于此类.

非质变算法，是指在运算过程中不会更改区间内(迭代器所指)的元素内容，比如查找(find)、计数(count)、遍历(for_each)、寻找极值等(max,min)，都属于此类。但是如果你在for_each遍历每个元素的时候试图应用一个会改变元素内容的仿函数，那么元素当然也会改变

1.常用遍历算法
#include <iostream>
#include <vector>
#include <algorithm>  //for_each
#include <functional>
#include <numeric>
using namespace std;


//for_each算法
class print{
public:
    print():count(0){}
    void operator()(int v){
        count++;
        cout<<" "<<v;
    }
    int count;
}

void test01(){
    vector<int> v;
    for(int i = 0 ; i < 10;i++){
        v.push_back(i);
    }
    
    print p1;
    //for_each(v.begin(),v.end(),print());
    print p2 = for_each(v.begin(),v.end(),p1);
    cout<<endl;
    cout<<"count:"<<p1.count<<endl;//0
    cout<<"count:"<<p2.count<<endl;//10
}

//transform算法
class myplus100{
public:
    int operator()(int v){
        return v + 100;
    }
};

class myminute{
public:
    int operator()(int v1,int v2){
         return v1 - v2;
    }
 
};

void test02(){
    vector<int> v1,v2;
    for(int i = 0 ; i < 10;i++){
        v1.push_back(i);
    }
    v2.resize(v1.size());
    
    //第一种情况，一个容器中的元素经过运算 把结果放进目标容器中 v2
    transform(v1.begin(),v1.end(),v2.begin(),myplus100());//把v1的所有值对位加100放到v2中

    print p1;
    for_each(v2.begin(),v2.end(),p1);
    cout<<endl;

    //-------------------------------------------------------------
    //第二种方式
    vector<int> v1,v2,v3;
    for(int i = 0;i<10;i++){
        v1.push_back(i);
        v2.push_back(i+1);
    }
    
    v3.resize(v1.size());
    transform(v1.begin(),v1.end(),v2.begin(),v3.begin(),myminute());

}

int main(){

   //test01();
   test02();
   
   return 0;
}
2.常用查找算法
iterator find(iterator beg,iterator end,value);
/*
  find 算法 查找元素
  @param beg 容器开始迭代器
  @param end 容器结束迭代器
  @param value 查找的元素
  @return 返回元素的位置
*/

iterator adjacent_find(iterator beg,iterator end,_callback);
/*
  adjacent_find 算法 查找相邻重复元素
  @param beg 容器开始迭代器
  @param end 容器结束迭代器
  @param _callback 回调函数或者谓词(返回Bool类型的函数对象)
  @return 返回相邻元素的第一个位置的迭代器
*/


bool binary_find(iterator beg,iterator end,TYPE & value);
/*
  binary_find 算法 二分查找法
  注意： 在无序序列中不可用
  @param beg 容器开始迭代器
  @param end 容器结束迭代器
  @param value 查找的元素
  @return bool 查找返回true 否则false
*/

iterator find_if(iterator beg,iterator end,_callback);
/*
  find_if 算法 条件查找
  @param beg 容器开始迭代器
  @param end 容器结束迭代器
  @param _callback 回调函数或者谓词(返回Bool类型的函数对象)
  @return iterator 返回迭代器
*/

int count(iterator beg,iterator end,TYPE & value)
/*
  count 算法 统计元素出现次数
  @param beg 容器开始迭代器
  @param end 容器结束迭代器
  @param value 要统计的值
  @return int 返回元素个数
*/

int count_if(iterator beg,iterator end,_callback);
/*
  count_if 算法 统计指定元素的个数
  @param beg 容器开始迭代器
  @param end 容器结束迭代器
  @param _callback 回调函数或者谓词(返回Bool类型的函数对象)
  @return bool 查找返回true 否则false
*/


//-----------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>  
#include <functional>
#include <numeric>
using namespace std;


//find算法
void test01(){
    vector<int> v;
    v.push_back(8);
    v.push_back(2);
    v.push_back(5);
    v.push_back(6);

    /*      
    template<class _InIt,
    class _Ty> inline
    _InIt find(_InIt _First, _InIt _Last, const _Ty& _Val)
    {   // find first matching _Val
    _DEBUG_RANGE(_First, _Last);
    return (_Rechecked(_First,
    _Find(_Unchecked(_First), _Unchecked(_Last), _Val)));
    }
    */

    vector<int>::itertaor pos = find(v.begin(),v.end(),5);
    if (pos == v.end())
    {
        cout<<"没有找到"<<endl;
    }
    else{
        cout<<"找到了:"<<*pos<<endl;
    }
}

//查找对象
class Student{
public:
    Student(int id,int age):id(id),age(age){}
    int id;
    int age;

    bool operator==(const Student &s){
       if (this->id = s.id && this->age == s.age)return true;
       else return false;
    }
};

void test02(){
    vector<Student> v;
    Student s1(1,2),s2(3,4),s3(5,6);

    v.push_back(s1);
    v.push_back(s2);
    v.push_back(s3);

    vector<Student>::iterator pos = find(v.begin(),v.end(),s1);
    if (pos == v.end())
    {
        cout<<"没有找到"<<endl;
    }
    else{
        cout<<"找到了:"<<pos->id<<" "<<pos->age<<endl;
    }
}

/*
找对象必然报错，因为在找的过程中
看原代码，两个对象的比较不是只是单纯地根据 == 号进行判断，编译器为了防止这种不严谨的写法，直接报错
所以 我们需要重载Student的 == 号运算符
*/


//find_if函数
class mycompare03{
public:
    bool operator()(int v){
        if (v > 6)
        {
            return true;
        }else{
            return false;
        }
    }
};

void test03(){
    vector<int> v;
    v.push_back(8);
    v.push_back(2);
    v.push_back(5);
    v.push_back(6);

    /*
    template<class _InIt,
    class _Pr> inline
    _InIt find_if(_InIt _First, _InIt _Last, _Pr _Pred)
    {   // find first satisfying _Pred
    _DEBUG_RANGE(_First, _Last);
    _DEBUG_POINTER(_Pred);
    return (_Rechecked(_First,
        _Find_if(_Unchecked(_First), _Unchecked(_Last), _Pred)));
    }

    template<class _InIt,
    class _Pr> inline
    _InIt _Find_if(_InIt _First, _InIt _Last, _Pr _Pred)
    {   // find first satisfying _Pred
    for (; _First != _Last; ++_First)
    if (_Pred(*_First))
    break;
    return (_First);
    }
    */

    vector<int>::iterator pos = find_if(v.begin(),v.end(),mycompare03());
    if (pos == v.end())
    {
        cout<<"没有找到"<<endl;
    }
    else
    {
        cout<<"找到了:"<<*pos<<endl;
    }


}

//adjacent_find 查找相邻重复元素 并返回第一个重复的元素出现的位置
void test04(){
    vector<int> v;
    v.push_back(8);
    v.push_back(2);
    v.push_back(2);
    v.push_back(5);
    v.push_back(6);

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

    vector<int>::iterator pos = adjacent_find(v.begin(),v.end());
    if (pos == v.end())
    {
        cout<<"没有找到"<<endl;
    }
    else
    {
        cout<<"找到了:"<<*pos<<endl;
    }

}

//binary_search 二分查找法   需要容器内元素有序
void test05(){

    vector<int> v;
    v.push_back(8);
    v.push_back(2);
    v.push_back(2);
    v.push_back(5);
    v.push_back(6);

    greater<int> mygreater;
    sort(v.begin(),v.end(),mygreater);
    //sort(v.begin(),v.end());
    /*
    template<class _FwdIt,
    class _Ty> inline
    bool binary_search(_FwdIt _First, _FwdIt _Last, const _Ty& _Val)
    {   // test if _Val equivalent to some element, using operator<
    return (_STD binary_search(_First, _Last, _Val, less<>()));
    }
    */
    bool flag = binary_search(v.begin(),v.end(),5,mygreater);
//bool flag = binary_search(v.begin(),v.end(),5);
//默认是从小到大二分查找，如果你排序过程中变成了从大到小，这里就必须申明
    if (flag)
    {
        cout<<"找到了！"<<endl;
    }
    else
    {
        cout<<"没有查找到"<<endl;
    }
}

//count  count_if
class mycompare06{
public:
    bool operator()(int v){
        return v > 2;
    }
}
void test06(){
    vector<int> v;
    v.push_back(8);
    v.push_back(2);
    v.push_back(2);
    v.push_back(5);
    v.push_back(6);

    //count 算法
    int n = count(v.begin(),v.end(),2);
    cout<<"n:"<<n<<endl;

    //count_if
    /*
        template<class _InIt,
        class _Pr> inline
        typename iterator_traits<_InIt>::difference_type
        count_if(_InIt _First, _InIt _Last, _Pr _Pred)
        {   // count elements satisfying _Pred
        _DEBUG_RANGE(_First, _Last);
        _DEBUG_POINTER(_Pred);
        return (_Count_if(_Unchecked(_First), _Unchecked(_Last), _Pred));
        }
    
    */
    n = count_if(v.begin(),v.end(),mycompare06());
    cout<<"n:"<<n<<endl;
}

int main(){

  //test01();
  //test02();
  //test03();
  //test04();
  //test05();
  test06();
   
   return 0;
}
3.常用排序算法
merge(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator dest);
/*
  merge 算法 容器元素合并，并存储到另一容器中
  两个容器内元素必须有序！
  而且必须都从大到小 或 一起从小到大！不然就报错了
  @param beg1 容器1开始迭代器
  @param end1 容器1结束迭代器
  @param beg2 容器2开始迭代器
  @param end2 容器2结束迭代器
  @param dest 目标容器开始迭代器
  @
*/

sort(iterator beg,iterator end,_callback);
/*
  sort 算法 容器元素排序
  注意：两个容器必须是有序的
  list容器不支持随机访问，所以不能用sort
  @param beg 容器开始迭代器
  @param end 容器结束迭代器
  @param _callback 回调函数或者谓词（返回bool类型的函数对象)
  @
*/

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

//-----------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>  
#include <functional>
#include <numeric>
using namespace std;

//merge算法
void print(int v){
   cout<<v<<" ";
}

void test01(){
    vector<int> v1,v2,v3;

    v1.push_back(6);
    v1.push_back(2);
    v1.push_back(8);
    v1.push_back(4);

    v2.push_back(1);
    v2.push_back(2);
    v2.push_back(6);
    v2.push_back(4);

    /*
        
        template<class _InIt1,
        class _InIt2,
        class _OutIt> inline
        _OutIt merge(_InIt1 _First1, _InIt1 _Last1,
        _InIt2 _First2, _InIt2 _Last2,
        _OutIt _Dest)
        {   // copy merging ranges, both using operator<
        return (_STD merge(_First1, _Last1, _First2, _Last2, _Dest,
        less<>()));
        }
    */
    sort(v1.begin(),v1.end(),greater<int>());//参数三可不写 默认less 从小到大
    sort(v2.begin(),v2.end(),greater<int>());

    v3.resize(v1.size() + v2.size());//v1 v2不排序 必然报错
    merge(v1.begin(),v1.end(),v2.begin(),v2.end(),v3.begin(),greater<int>());//参数6可不写 默认less 从小到大

    for_each(v3.begin(),v3.end(),print);
    cout<<endl;

}

//sort 算法
void test02(){
    vector<int> v;

    v.push_back(6);
    v.push_back(2);
    v.push_back(8);
    v.push_back(4);
    sort(v.begin(),v.end(),greater<int>());//从大到小排序 默认从小到大
}

//random_shuffle 洗牌 将容器中的元素 顺序打乱
void test03(){
    vector<int> v;
    for (int i = 0; i < 10; ++i)
    {
        v.push_back(i);
    }
    for_each(v.begin(),v.end(),print);
    cout<<endl;

    random_shuffle(v.begin(),v.end());

    for_each(v.begin(),v.end(),print);
    cout<<endl;
}

//reverse 反转容器中的元素
void test04(){
    vector<int> v;
    for (int i = 0; i < 10; ++i)
    {
        v.push_back(i);
    }
    for_each(v.begin(),v.end(),print);
    cout<<endl;

    reverse(v.begin(),v.end());

    for_each(v.begin(),v.end(),print);
    cout<<endl;
}

int main(){

  //test01();
  //test02();
  //test03();
   test04();
   return 0;
}
4.常用的拷贝和替换算法
copy(iterator beg,iterator end,iterator dest);
/*
  copy 算法 将容器内指定范围的元素拷贝到另一个容器中
  @param beg 容器开始迭代器
  @param end 容器结束迭代器
  @param dest 目标容器开始迭代器
  @
*/

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

replace_if(iterator beg,iterator end,_callback,TYPE & newvalue);
/*
  replace_if 算法 将容器内指定范围满足条件的元素修改为新元素
  @param beg 容器开始迭代器
  @param end 容器结束迭代器
  @param _callback 函数回调或者谓词(返回Bool类型的函数对象)
  @param newvalue 新元素
  @
*/

swap(container c1,container c2);
/*
  swap 算法 互换两个容器的元素
  @param c1 容器1
  @param c2 容器2
  @
*/

//-----------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>  
#include <functional>
#include <numeric>
using namespace std;

//copy算法
void print(int v){
   cout<<v<<" ";
}
void test01(){
    vector<int> v1,v2;
    for (int i = 0; i < 10; ++i)
    {
        v1.push_back(i);
    }

    v2.reszie(v1.size());

    copy(v1.begin(),v1.end(),v2.begin());

    for_each(v2.begin(),v2.end(),print);
}

//replace  replace_if算法
class mycompare02{
public:
    bool operator()(int v){
            return v>5;
    }
}
void test02(){
    vector<int> v;
    for (int i = 0; i < 10; ++i)
    {
        v.push_back(i);
    }

    replace(v.begin(),v.end(),6,100);
    for_each(v.begin(),v.end(),print);
    cout<<endl;

    //replace_if
    replace_if(v.begin(),v.end(),mycompare02(),50);
    for_each(v.begin(),v.end(),print);
    cout<<endl;

    //swap
    vector<int> v2;
    for (int i = 0; i < 10; ++i)
    {
        v2.push_back(i);
    }

    for_each(v1.begin(),v1.end(),print);
    cout<<endl;

    for_each(v2.begin(),v2.end(),print);
    cout<<endl;

    cout<<"-----------------------------"<<endl;
    swap(v1,v2);

    for_each(v1.begin(),v1.end(),print);
    cout<<endl;

    for_each(v2.begin(),v2.end(),print);
    cout<<endl;
}

int main(){

  //test01();
  test02();
   return 0;
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 216,324评论 6赞 498
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 92,356评论 3赞 392
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 162,328评论 0赞 353
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,147评论 1赞 292
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,160评论 6赞 388
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,115评论 1赞 296
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,025评论 3赞 417
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,867评论 0赞 274
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,307评论 1赞 310
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,528评论 2赞 332
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,688评论 1赞 348
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,409评论 5赞 343
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 41,001评论 3赞 325
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,657评论 0赞 22
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,811评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,685评论 2赞 368
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,573评论 2赞 353