美文网首页
八、算法概述(遍历、查找、排序、替换)

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

作者: 木鱼_cc | 来源:发表于2018-07-02 20:15 被阅读0次

    算法主要由头文件<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;
}

    相关文章

      网友评论

          本文标题：八、算法概述(遍历、查找、排序、替换)

          本文链接：https://www.haomeiwen.com/subject/kzdluftx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|八、算法概述(遍历、查找、排序、替换)|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！