C++STL—常用算法

Author： admin
发布时间：May 26, 2022
1035views
299 words
Categories： publish

STL—常用算法

零、概述

算法主要是由头文件<algorithm>,<functhionla>,<numeric>组成。
<algorithm>是所有STL头文件最大的一个，范围涉及到比较，交换，查找，遍历操作，复制，修改等等
<numeric>体积很小，只包括几个在序列上面进行简单数学运算的模板函数
<functhionla>定义了一些模板类，用以声明函数对象

一、常用遍历算法

1.`for_each`-遍历容器

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void myPrint(const int & i)
{
    cout << i << endl;
}
class mprint {
public:
    void operator ()(const int & i)
    {
        cout << i << endl;
    }
};
int main()
{
    vector <int> mv;
    for (int i = 1; i<=3 ; i++)
    {
        mv.push_back(i);
    }
    //for_each(mv.begin(), mv.end(), myPrint);//自定义函数输出
    for_each(mv.begin(), mv.end(), mprint());//仿函数输出法
    system("pause");
}

2.`transform`-搬运到另一个容器中

transform(iterator beg1, iterator end1, iterator beg2,_func);

beg1 源容器开始迭代器
end1 源容器结束迭代器
beg2 目标容器开始迭代器
end2 目标容器结束迭代器
_func 函数或者函数对象

目标vector容器必须先分配好空间

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int myTrans(const int & i)
{
    cout << i << endl;
    return i;
}
class myTran
{
public:
    int operator()(const int & i)
    {
        return i+1;
    }

};
void myPrint(const int & i)
{
    cout << i << endl;
}
int main()
{
    vector <int> mv;
    for (int i = 1; i<=5 ; i++)
    {
        mv.push_back(i);
    }
    vector<int> mv2;
    mv2.resize(mv.size());//需要重新设置大小、否则会报错
    for_each(mv.begin(), mv.end(), myPrint);//仿函数法
    transform(mv.begin()+1, mv.end(), mv2.begin(), myTran());//仿函数法
    for_each(mv.begin(), mv.end(), myPrint);//仿函数法
    system("pause");
}

二、常用查找算法

find                    //查找元素
find_if                    //按条件查找元素
adjacent_find            //查找相邻重复元素
binary_search            //二分查找法
count                    //统计元素个数
count_if                //按条件统计元素个数

1.find-查找指定元素

查找指定元素，找到返回指定元素的迭代器，找不到返回结束迭代器

find(iterator beg, iterator end, value)

beg 开始迭代器
end 结束迭代器
value 查找的元素

内置数据类型

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void test()
{
    vector<int> mv;
    for(int i =0; i<=10;i++)
    {
        mv.push_back(i);
    }
    //查找容器中是否有5这个元素
    vector<int>::iterator it = find(mv.begin(), mv.end(), 5);
    if (it == mv.end())
    {
        cout<<"error"<<endl;
        return;
    }
    else
    {
        cout << *it << endl;
    }
}
int main()
{
    test();
    system("pause");
    return 0;
}

自定义数据类型

自定义数据类型必须重载自定义数据类型的==运算符

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
class Person
{
public:
    Person(int id, string name):m_id(id),m_name(name){};
    int m_id;
    string m_name;
    //重载==号让find知道如何对比person数据类型
    bool operator==(const Person &p)
    {
        return p.m_id == this->m_id;
    }
};
void test()
{
    vector<Person> mv;
    mv.push_back(Person(1,string("wangtaijie")));
    mv.push_back(Person(2,string("sadad")));
    mv.push_back(Person(3,string("ssdadasf")));
    mv.push_back(Person(4,string("sdadasfasdwq")));
    //查找容器中是否有5这个元素
    vector<Person>::iterator it = find(mv.begin(), mv.end(), *(mv.begin()+1));
    if (it == mv.end())
    {
        cout<<"error"<<endl;
        return;
    }
    else
    {
        cout << it->m_id<< it->m_name<< endl;
    }
}
int main()
{
    test();
    return 0;
}

2.find_if-按条件查找

find_if(iterator beg, iterator end, _pred);        //按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置

beg 开始迭代器
end 结束迭代器
_pred 函数或者谓词(返回bool类型的仿函数)

内置数据类型

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class myFind
{
public:
    bool operator()(int val)
    {
        return val>5;
    }
};
void test()
{
    vector<int> mv;
    for(int i =0; i<=10;i++)
    {
        mv.push_back(i);
    }
    //查找容器中是否有5这个元素
    vector<int>::iterator it = find_if(mv.begin(), mv.end(), myFind());
    if (it == mv.end())
    {
        cout<<"error"<<endl;
        return;
    }
    else
    {
        cout << *it << endl;
    }
}
int main()
{
    test();
    system("pause");
    return 0;
}

自定义数据类型

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
class Person
{
public:
    Person(int id, string name):m_id(id),m_name(name){};
    int m_id;
    string m_name;
};
class myCreat
{
public:
    bool operator()(const Person &p)
    {
        return p.m_id > 3;
    }
};
void test()
{
    vector<Person> mv;
    mv.push_back(Person(1,string("wangtaijie")));
    mv.push_back(Person(2,string("sadad")));
    mv.push_back(Person(3,string("ssdadasf")));
    mv.push_back(Person(4,string("sdadasfasdwq")));
    vector<Person>::iterator it = find_if(mv.begin(), mv.end(), myCreat());
    if (it == mv.end())
    {
        cout<<"error"<<endl;
        return;
    }
    else
    {
        cout << it->m_id<< it->m_name<< endl;
    }
}
int main()
{
    test();
    return 0;
}

3.adjacent_find-查找两个相邻重复元素

adjacent_find(iterator beg, iterator end);

beg 开始迭代器
end 结束迭代器
返回第一个元素出现的位置

4.binary_search-查找指定元素是否存在、有序序列的二分查找法

bool binary_search(iterator beg, iterator end, value);

注意:在无序序列中不可用
beg 开始迭代器
end 结束迭代器
value 查找的元素
找到返回true,否则返回false

5.count-统计元素出现次数

count(iterator beg, iterator end, value);

beg 开始迭代器
end 结束迭代器
value 查找的元素
自定义元素需要重载==运算符

自定义类型

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
class Person
{
public:
    Person(int id, string name):m_id(id),m_name(name){};
    int m_id;
    string m_name;
    bool operator==(const Person &p)
    {
        return p.m_id == this->m_id;
    }
};
void test()
{
    vector<Person> mv;
    mv.push_back(Person(1,string("wangtaijie")));
    mv.push_back(Person(2,string("sadad")));
    mv.push_back(Person(3,string("ssdadasf")));
    mv.push_back(Person(2,string("sdadasfasdwq")));
    int it = count(mv.begin(), mv.end(), *(mv.begin()+1));
    if (it == 0)
    {
        cout<<"未找到"<<endl;
        return;
    }
    else
    {
        cout <<"重复次数"<<it<< endl;
    }
}
int main()
{
    test();
    return 0;
}

重复次数2

6.count_if-按条件统计元素个数

count_if(iterator beg,iterator end, _pred);

beg 开始迭代器
end 结束迭代器
_pred 谓词

自定义数据类型

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
class Person
{
public:
    Person(int id, string name):m_id(id),m_name(name){};
    int m_id;
    string m_name;
};
bool check(const Person &p)
{
    return p.m_id>=2;
}
void test()
{
    vector<Person> mv;
    mv.push_back(Person(1,string("wangtaijie")));
    mv.push_back(Person(2,string("sadad")));
    mv.push_back(Person(3,string("ssdadasf")));
    mv.push_back(Person(2,string("sdadasfasdwq")));
    int it= count_if(mv.begin(), mv.end(), check);
    if (it ==  0)
    {
        cout<<"未找到"<<endl;
        return;
    }
    else
    {
        cout <<"结果"<<it<< endl;
    }
}
int main()
{
    test();
    return 0;
}

结果3

三、常用排序算法

sort            //对容器内元素进行排序
radom_shuffle    //洗牌，指定范围内的元素调整次序
merge            //容器元素合并，并储存到另一个容器中
reverse            //反转指定范围内的元素

1.sort-排序算法

sort(iterator beg, iterator end, _Pred);

beg 开始迭代器
end 结束迭代器
_Pred 谓词
默认采用升序，降序则使用greater<T>(),默认降序
使用自定义类型则需要自定义谓词(返回值为bool的函数)

2.radom_shuffle-随机打乱

radom_shuffle(iterator beg, iterator end);

可以指定随机数种子srand((unsigned int)time(NULL)),需要包含<ctime>、不然每次生成的顺序就相同

3.merge-容器合并

merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);//容器元素合并，并存到另一容器中

注意：两个容器必须是有序的
beg1 容器1开始迭代器
end1 容器1结束迭代器
beg2 容器2开始迭代器
end2 容器2结束迭代器
dest 目标容器开始迭代器,生成的容器也是有序的，而且重复的元素会前后排好
目标容器必须先分配好空间,否则程序会崩溃

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
void myPrintf(int & i)
{
    cout << i << " ";
}
void test()
{
    vector<int> mv;
    vector<int> mv2;
    for (int i = 0; i< 20 ; i++)
    {
        mv.push_back(i);
    }
    for (int i = 20; i< 23; i++)
    {
        mv2.push_back(i);
    }
    vector<int> target;
    target.resize(mv.size()+mv2.size());//目标容器必须先分配好空间,否则程序会崩溃
    merge(mv.begin(),mv.end(),mv2.begin(),mv2.end(),target.begin());
    for_each(target.begin(),target.end(),myPrintf);
    cout << endl;
}
int main()
{
    test();
    return 0;
}

4.reverse-顺序对调

reverse(iterator beg, iterator end);//将容器前后顺序对调，

beg 开始迭代器
end 结束迭代器

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
void myPrintf(int & i)
{
    cout << i << " ";
}
void test()
{
    vector<int> mv;
    mv.push_back(19);
    mv.push_back(12);
    mv.push_back(23);
    mv.push_back(423);
    mv.push_back(21);
    for_each(mv.begin(),mv.end(),myPrintf);
    cout << endl;
    reverse(mv.begin(),mv.end());
    for_each(mv.begin(),mv.end(),myPrintf);
    cout << endl;
}
int main()
{
    test();
    return 0;
}

19 12 23 423 21
21 423 23 12 19

四、常用拷贝和替换算法

copy                    //容器内指定范围的元素拷贝到另一个容器中
replace                    //将容器内指定的范围的旧元素改为新元素
replace_if                //容器内指定范围满足条件的元素替换为新元素
swap                    //互换两个容器的元素

1.copy-容器拷贝

copy(iterator beg, iterator end, iterator dest);

beg 开始迭代器
end 结束迭代器
dest 目标容器开始迭代器
目标容器必须先分配好空间,否则程序会崩溃

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
void myPrintf(int & i)
{
    cout << i << " ";
}
void test()
{
    vector<int> mv;
    for (int i = 0; i< 20 ; i++)
    {
        mv.push_back(i);
    }
    vector<int> tar;
    tar.resize(mv.size());
    for_each(mv.begin(),mv.end(),myPrintf);
    cout << endl;
    copy(mv.begin(),mv.end(),tar.begin());
    for_each(mv.begin(),mv.end(),myPrintf);
    cout << endl;
}
int main()
{
    test();
    return 0;
}

2.replace-指定范围替换

replace(iterator beg, iterator end, oldvalue, newvlaue);//将区间内的所有指定元素替换成新的元素

beg 开始迭代器
end 结束迭代器
oldvalue 旧元素
newvlaue 新元素
所有对应元素都会被替换
无返回值

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
void myPrintf(int & i)
{
    cout << i << " ";
}
void test()
{
    vector<int> mv;
    for (int i = 0; i< 12 ; i++)
    {
        mv.push_back(i);
    }
    for_each(mv.begin(),mv.end(),myPrintf);
    cout << endl;
    replace(mv.begin(),mv.end(),10, 2000);
    for_each(mv.begin(),mv.end(),myPrintf);
    cout << endl;
}
int main()
{
    test();
    return 0;
}

2 3 3
2 2000 2000

3.replace_if-条件替换

replace_if(iterator beg, iterator end, _Pred, newvlaue);//将区间内所有满足条件的元素替换成指定元素

beg 开始迭代器
end 结束迭代器
_pred 谓词
newvalue 新的元素

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
void myPrintf(int & i)
{
    cout << i << " ";
}
class myGreater
{
public:
    bool operator ()(int i)
    {
        return i>2;
    }
};
void test()
{
    vector<int> mv;
    mv.push_back(2);
    mv.push_back(3);
    mv.push_back(3);
    for_each(mv.begin(),mv.end(),myPrintf);
    cout << endl;
    replace_if(mv.begin(),mv.end(),myGreater(),2000);
    for_each(mv.begin(),mv.end(),myPrintf);
    cout << endl;
}
int main()
{
    test();
    return 0;
}

2 3 3
2 2000 2000

4.swap-互换两个容器内容

swap(container c1, contain c2);

两个容器类型必须相同
c1容器
c2容器

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
void myPrintf(int & i)
{
    cout << i << " ";
}
void test()
{
    vector<int> mv;
   for (int i = 0; i< 20 ; i++)
    {
        mv.push_back(i);
    }
    vector<int> mv2;
     for (int i = 232; i< 245 ; i++)
    {
        mv2.push_back(i);
    }
    for_each(mv.begin(),mv.end(),myPrintf);
    cout << endl;
    for_each(mv2.begin(),mv2.end(),myPrintf);
    cout << endl;
    swap(mv,mv2);
    for_each(mv.begin(),mv.end(),myPrintf);
    cout << endl;
    for_each(mv2.begin(),mv2.end(),myPrintf);
    cout << endl;
}
int main()
{
    test();
    return 0;
}

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
232 233 234 235 236 237 238 239 240 241 242 243 244
232 233 234 235 236 237 238 239 240 241 242 243 244
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

五、常用算术生成算法

算术生成算法属于小型算法，使用时包含头文件#include <numeric>

accumulate                    //计算容器元素累计和
fill                        //向容器中添加元素

1.accumulate-容器元素累加和

accumulate(iterator beg, iterator end, value);//计算容器元素累加总和

beg 开始迭代器
end 结束迭代器
value 起始值
返回值：结果

#include <iostream>
#include <vector>
#include <numeric>
#include <string>
using namespace std;
void test()
{
    vector<int> mv;
   for (int i = 0; i< 20 ; i++)
    {
        mv.push_back(i);
    }
    int result = accumulate(mv.begin(),mv.end(),0);
    cout<<result<<endl;
}
int main()
{
    test();
    return 0;
}

2.fill-填充指定元素

fill(iterator beg, iterator end, value);

beg 开始迭代器
end 结束迭代器
vlaue 填充值
必须先用resize预留好空间

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <string>
using namespace std;
void myPrintf(int & i)
{
    cout << i << " ";
}
void test()
{
    vector<int> mv;
    mv.resize(20);//预留空间、必须用resize
    fill(mv.begin(),mv.end(),5);
    for_each(mv.begin(),mv.end(),myPrintf);
    cout << endl;
}
int main()
{
    test();
    return 0;
}

六、常用集合算法

set_intersection            //求两个容器的交集
set_union                    //求两个容器的并集
set_difference                //求两个容器的差集

1.set_intersection-求两个容器的交集

set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

beg1 容器1开始迭代器
end1 容器1结束迭代器
beg2 容器2开始迭代器
end2 容器2结束迭代器
dest 目标容器开始迭代器,生成的容器也是有序的，而且重复的元素会前后排好
两个容器集合必须是有序序列
目标容器必须先分配好空间,否则程序会崩溃
返回值是交集在目标容器输出结束的位置

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
void myPrintf(int & i)
{
    cout << i << " ";
}
void test()
{
    vector<int> mv;
    vector<int> mv2;
    for (int i = 0; i< 20 ; i++)
    {
        mv.push_back(i);
    }
    for (int i = 10; i< 30; i++)
    {
        mv2.push_back(i);
    }
    vector<int> target;
     for_each(mv.begin(),mv.end(),myPrintf);
    cout << endl;
    for_each(mv2.begin(),mv2.end(),myPrintf);
    cout << endl;
    target.resize(min(mv.size(),mv2.size()));//目标容器必须先分配好空间,否则程序会崩溃
    vector<int>::iterator  itEnd = set_intersection(mv.begin(),mv.end(),mv2.begin(),mv2.end(),target.begin());//返回值是交集在目标容器输出结束的位置
    for_each(target.begin(),itEnd,myPrintf);//实际交集
    cout << endl;
    for_each(target.begin(),target.end(),myPrintf);
    cout << endl;
}
int main()
{
    test();
    return 0;
}

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
10 11 12 13 14 15 16 17 18 19
10 11 12 13 14 15 16 17 18 19 0 0 0 0 0 0 0 0 0 0

2.set_union-求并集

set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

beg1 容器1开始迭代器
end1 容器1结束迭代器
beg2 容器2开始迭代器
end2 容器2结束迭代器
dest 目标容器开始迭代器,生成的容器也是有序的，而且重复的元素会前后排好
两个容器集合必须是有序序列
目标容器必须先分配好空间,否则程序会崩溃
返回值是并集在目标容器输出结束的位置

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
void myPrintf(int & i)
{
    cout << i << " ";
}
void test()
{
    vector<int> mv;
    vector<int> mv2;
    for (int i = 0; i< 20 ; i++)
    {
        mv.push_back(i);
    }
    for (int i = 10; i< 30; i++)
    {
        mv2.push_back(i);
    }
    vector<int> target;
     for_each(mv.begin(),mv.end(),myPrintf);
    cout << endl;
    for_each(mv2.begin(),mv2.end(),myPrintf);
    cout << endl;
    target.resize(mv.size()+mv2.size());//目标容器必须先分配好空间,否则程序会崩溃
    vector<int>::iterator  itEnd = set_union(mv.begin(),mv.end(),mv2.begin(),mv2.end(),target.begin());//返回值是交集在目标容器输出结束的位置
    for_each(target.begin(),itEnd,myPrintf);
    cout << endl;
    for_each(target.begin(),target.end(),myPrintf);
    cout << endl;
}
int main()
{
    test();
    return 0;
}

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 0 0 0 0 0 0 0 0 0 0

3.set_difference-求差集

set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

beg1 容器1开始迭代器
end1 容器1结束迭代器
beg2 容器2开始迭代器
end2 容器2结束迭代器
dest 目标容器开始迭代器,生成的容器也是有序的，而且重复的元素会前后排好
两个容器集合必须是有序序列
目标容器必须先分配好空间,否则程序会崩溃
返回值是差集在目标容器输出结束的位置

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
void myPrintf(int & i)
{
    cout << i << " ";
}
void test()
{
    vector<int> mv;
    vector<int> mv2;
    for (int i = 0; i< 20 ; i++)
    {
        mv.push_back(i);
    }
    for (int i = 10; i< 30; i++)
    {
        mv2.push_back(i);
    }
    vector<int> target;
     for_each(mv.begin(),mv.end(),myPrintf);
    cout << endl;
    for_each(mv2.begin(),mv2.end(),myPrintf);
    cout << endl;
    target.resize(mv.size()+mv2.size());//目标容器必须先分配好空间,否则程序会崩溃
    vector<int>::iterator  itEnd = set_difference(mv.begin(),mv.end(),mv2.begin(),mv2.end(),target.begin());//返回值是交集在目标容器输出结束的位置
    for_each(target.begin(),itEnd,myPrintf);
    cout << endl;
    for_each(target.begin(),target.end(),myPrintf);
    cout << endl;
}
int main()
{
    test();
    return 0;
}

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

C++STL—常用算法

admin • 2022 年 05 月 26 日

STL—常用算法

零、概述

算法主要是由头文件<algorithm>,<functhionla>,<numeric>组成。
<algorithm>是所有STL头文件最大的一个，范围涉及到比较，交换，查找，遍历操作，复制，修改等等
<numeric>体积很小，只包括几个在序列上面进行简单数学运算的模板函数
<functhionla>定义了一些模板类，用以声明函数对象

一、常用遍历算法

1.`for_each`-遍历容器

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void myPrint(const int & i)
{
    cout << i << endl;
}
class mprint {
public:
    void operator ()(const int & i)
    {
        cout << i << endl;
    }
};
int main()
{
    vector <int> mv;
    for (int i = 1; i<=3 ; i++)
    {
        mv.push_back(i);
    }
    //for_each(mv.begin(), mv.end(), myPrint);//自定义函数输出
    for_each(mv.begin(), mv.end(), mprint());//仿函数输出法
    system("pause");
}

2.`transform`-搬运到另一个容器中

transform(iterator beg1, iterator end1, iterator beg2,_func);

beg1 源容器开始迭代器
end1 源容器结束迭代器
beg2 目标容器开始迭代器
end2 目标容器结束迭代器
_func 函数或者函数对象

目标vector容器必须先分配好空间

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int myTrans(const int & i)
{
    cout << i << endl;
    return i;
}
class myTran
{
public:
    int operator()(const int & i)
    {
        return i+1;
    }

};
void myPrint(const int & i)
{
    cout << i << endl;
}
int main()
{
    vector <int> mv;
    for (int i = 1; i<=5 ; i++)
    {
        mv.push_back(i);
    }
    vector<int> mv2;
    mv2.resize(mv.size());//需要重新设置大小、否则会报错
    for_each(mv.begin(), mv.end(), myPrint);//仿函数法
    transform(mv.begin()+1, mv.end(), mv2.begin(), myTran());//仿函数法
    for_each(mv.begin(), mv.end(), myPrint);//仿函数法
    system("pause");
}

二、常用查找算法

find                    //查找元素
find_if                    //按条件查找元素
adjacent_find            //查找相邻重复元素
binary_search            //二分查找法
count                    //统计元素个数
count_if                //按条件统计元素个数

1.find-查找指定元素

查找指定元素，找到返回指定元素的迭代器，找不到返回结束迭代器

find(iterator beg, iterator end, value)

beg 开始迭代器
end 结束迭代器
value 查找的元素

内置数据类型

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void test()
{
    vector<int> mv;
    for(int i =0; i<=10;i++)
    {
        mv.push_back(i);
    }
    //查找容器中是否有5这个元素
    vector<int>::iterator it = find(mv.begin(), mv.end(), 5);
    if (it == mv.end())
    {
        cout<<"error"<<endl;
        return;
    }
    else
    {
        cout << *it << endl;
    }
}
int main()
{
    test();
    system("pause");
    return 0;
}

自定义数据类型

自定义数据类型必须重载自定义数据类型的==运算符

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
class Person
{
public:
    Person(int id, string name):m_id(id),m_name(name){};
    int m_id;
    string m_name;
    //重载==号让find知道如何对比person数据类型
    bool operator==(const Person &p)
    {
        return p.m_id == this->m_id;
    }
};
void test()
{
    vector<Person> mv;
    mv.push_back(Person(1,string("wangtaijie")));
    mv.push_back(Person(2,string("sadad")));
    mv.push_back(Person(3,string("ssdadasf")));
    mv.push_back(Person(4,string("sdadasfasdwq")));
    //查找容器中是否有5这个元素
    vector<Person>::iterator it = find(mv.begin(), mv.end(), *(mv.begin()+1));
    if (it == mv.end())
    {
        cout<<"error"<<endl;
        return;
    }
    else
    {
        cout << it->m_id<< it->m_name<< endl;
    }
}
int main()
{
    test();
    return 0;
}

2.find_if-按条件查找

find_if(iterator beg, iterator end, _pred);        //按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置

beg 开始迭代器
end 结束迭代器
_pred 函数或者谓词(返回bool类型的仿函数)

内置数据类型

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class myFind
{
public:
    bool operator()(int val)
    {
        return val>5;
    }
};
void test()
{
    vector<int> mv;
    for(int i =0; i<=10;i++)
    {
        mv.push_back(i);
    }
    //查找容器中是否有5这个元素
    vector<int>::iterator it = find_if(mv.begin(), mv.end(), myFind());
    if (it == mv.end())
    {
        cout<<"error"<<endl;
        return;
    }
    else
    {
        cout << *it << endl;
    }
}
int main()
{
    test();
    system("pause");
    return 0;
}

自定义数据类型

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
class Person
{
public:
    Person(int id, string name):m_id(id),m_name(name){};
    int m_id;
    string m_name;
};
class myCreat
{
public:
    bool operator()(const Person &p)
    {
        return p.m_id > 3;
    }
};
void test()
{
    vector<Person> mv;
    mv.push_back(Person(1,string("wangtaijie")));
    mv.push_back(Person(2,string("sadad")));
    mv.push_back(Person(3,string("ssdadasf")));
    mv.push_back(Person(4,string("sdadasfasdwq")));
    vector<Person>::iterator it = find_if(mv.begin(), mv.end(), myCreat());
    if (it == mv.end())
    {
        cout<<"error"<<endl;
        return;
    }
    else
    {
        cout << it->m_id<< it->m_name<< endl;
    }
}
int main()
{
    test();
    return 0;
}

3.adjacent_find-查找两个相邻重复元素

adjacent_find(iterator beg, iterator end);

beg 开始迭代器
end 结束迭代器
返回第一个元素出现的位置

4.binary_search-查找指定元素是否存在、有序序列的二分查找法

bool binary_search(iterator beg, iterator end, value);

注意:在无序序列中不可用
beg 开始迭代器
end 结束迭代器
value 查找的元素
找到返回true,否则返回false

5.count-统计元素出现次数

count(iterator beg, iterator end, value);

beg 开始迭代器
end 结束迭代器
value 查找的元素
自定义元素需要重载==运算符

自定义类型

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
class Person
{
public:
    Person(int id, string name):m_id(id),m_name(name){};
    int m_id;
    string m_name;
    bool operator==(const Person &p)
    {
        return p.m_id == this->m_id;
    }
};
void test()
{
    vector<Person> mv;
    mv.push_back(Person(1,string("wangtaijie")));
    mv.push_back(Person(2,string("sadad")));
    mv.push_back(Person(3,string("ssdadasf")));
    mv.push_back(Person(2,string("sdadasfasdwq")));
    int it = count(mv.begin(), mv.end(), *(mv.begin()+1));
    if (it == 0)
    {
        cout<<"未找到"<<endl;
        return;
    }
    else
    {
        cout <<"重复次数"<<it<< endl;
    }
}
int main()
{
    test();
    return 0;
}

重复次数2

6.count_if-按条件统计元素个数

count_if(iterator beg,iterator end, _pred);

beg 开始迭代器
end 结束迭代器
_pred 谓词

自定义数据类型

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
class Person
{
public:
    Person(int id, string name):m_id(id),m_name(name){};
    int m_id;
    string m_name;
};
bool check(const Person &p)
{
    return p.m_id>=2;
}
void test()
{
    vector<Person> mv;
    mv.push_back(Person(1,string("wangtaijie")));
    mv.push_back(Person(2,string("sadad")));
    mv.push_back(Person(3,string("ssdadasf")));
    mv.push_back(Person(2,string("sdadasfasdwq")));
    int it= count_if(mv.begin(), mv.end(), check);
    if (it ==  0)
    {
        cout<<"未找到"<<endl;
        return;
    }
    else
    {
        cout <<"结果"<<it<< endl;
    }
}
int main()
{
    test();
    return 0;
}

结果3

三、常用排序算法

sort            //对容器内元素进行排序
radom_shuffle    //洗牌，指定范围内的元素调整次序
merge            //容器元素合并，并储存到另一个容器中
reverse            //反转指定范围内的元素

1.sort-排序算法

sort(iterator beg, iterator end, _Pred);

beg 开始迭代器
end 结束迭代器
_Pred 谓词
默认采用升序，降序则使用greater<T>(),默认降序
使用自定义类型则需要自定义谓词(返回值为bool的函数)

2.radom_shuffle-随机打乱

radom_shuffle(iterator beg, iterator end);

可以指定随机数种子srand((unsigned int)time(NULL)),需要包含<ctime>、不然每次生成的顺序就相同

3.merge-容器合并

merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);//容器元素合并，并存到另一容器中

注意：两个容器必须是有序的
beg1 容器1开始迭代器
end1 容器1结束迭代器
beg2 容器2开始迭代器
end2 容器2结束迭代器
dest 目标容器开始迭代器,生成的容器也是有序的，而且重复的元素会前后排好
目标容器必须先分配好空间,否则程序会崩溃

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
void myPrintf(int & i)
{
    cout << i << " ";
}
void test()
{
    vector<int> mv;
    vector<int> mv2;
    for (int i = 0; i< 20 ; i++)
    {
        mv.push_back(i);
    }
    for (int i = 20; i< 23; i++)
    {
        mv2.push_back(i);
    }
    vector<int> target;
    target.resize(mv.size()+mv2.size());//目标容器必须先分配好空间,否则程序会崩溃
    merge(mv.begin(),mv.end(),mv2.begin(),mv2.end(),target.begin());
    for_each(target.begin(),target.end(),myPrintf);
    cout << endl;
}
int main()
{
    test();
    return 0;
}

4.reverse-顺序对调

reverse(iterator beg, iterator end);//将容器前后顺序对调，

beg 开始迭代器
end 结束迭代器

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
void myPrintf(int & i)
{
    cout << i << " ";
}
void test()
{
    vector<int> mv;
    mv.push_back(19);
    mv.push_back(12);
    mv.push_back(23);
    mv.push_back(423);
    mv.push_back(21);
    for_each(mv.begin(),mv.end(),myPrintf);
    cout << endl;
    reverse(mv.begin(),mv.end());
    for_each(mv.begin(),mv.end(),myPrintf);
    cout << endl;
}
int main()
{
    test();
    return 0;
}

19 12 23 423 21
21 423 23 12 19

四、常用拷贝和替换算法

copy                    //容器内指定范围的元素拷贝到另一个容器中
replace                    //将容器内指定的范围的旧元素改为新元素
replace_if                //容器内指定范围满足条件的元素替换为新元素
swap                    //互换两个容器的元素

1.copy-容器拷贝

copy(iterator beg, iterator end, iterator dest);

beg 开始迭代器
end 结束迭代器
dest 目标容器开始迭代器
目标容器必须先分配好空间,否则程序会崩溃

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
void myPrintf(int & i)
{
    cout << i << " ";
}
void test()
{
    vector<int> mv;
    for (int i = 0; i< 20 ; i++)
    {
        mv.push_back(i);
    }
    vector<int> tar;
    tar.resize(mv.size());
    for_each(mv.begin(),mv.end(),myPrintf);
    cout << endl;
    copy(mv.begin(),mv.end(),tar.begin());
    for_each(mv.begin(),mv.end(),myPrintf);
    cout << endl;
}
int main()
{
    test();
    return 0;
}

2.replace-指定范围替换

replace(iterator beg, iterator end, oldvalue, newvlaue);//将区间内的所有指定元素替换成新的元素

beg 开始迭代器
end 结束迭代器
oldvalue 旧元素
newvlaue 新元素
所有对应元素都会被替换
无返回值

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
void myPrintf(int & i)
{
    cout << i << " ";
}
void test()
{
    vector<int> mv;
    for (int i = 0; i< 12 ; i++)
    {
        mv.push_back(i);
    }
    for_each(mv.begin(),mv.end(),myPrintf);
    cout << endl;
    replace(mv.begin(),mv.end(),10, 2000);
    for_each(mv.begin(),mv.end(),myPrintf);
    cout << endl;
}
int main()
{
    test();
    return 0;
}

2 3 3
2 2000 2000

3.replace_if-条件替换

replace_if(iterator beg, iterator end, _Pred, newvlaue);//将区间内所有满足条件的元素替换成指定元素

beg 开始迭代器
end 结束迭代器
_pred 谓词
newvalue 新的元素

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
void myPrintf(int & i)
{
    cout << i << " ";
}
class myGreater
{
public:
    bool operator ()(int i)
    {
        return i>2;
    }
};
void test()
{
    vector<int> mv;
    mv.push_back(2);
    mv.push_back(3);
    mv.push_back(3);
    for_each(mv.begin(),mv.end(),myPrintf);
    cout << endl;
    replace_if(mv.begin(),mv.end(),myGreater(),2000);
    for_each(mv.begin(),mv.end(),myPrintf);
    cout << endl;
}
int main()
{
    test();
    return 0;
}

2 3 3
2 2000 2000

4.swap-互换两个容器内容

swap(container c1, contain c2);

两个容器类型必须相同
c1容器
c2容器

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
void myPrintf(int & i)
{
    cout << i << " ";
}
void test()
{
    vector<int> mv;
   for (int i = 0; i< 20 ; i++)
    {
        mv.push_back(i);
    }
    vector<int> mv2;
     for (int i = 232; i< 245 ; i++)
    {
        mv2.push_back(i);
    }
    for_each(mv.begin(),mv.end(),myPrintf);
    cout << endl;
    for_each(mv2.begin(),mv2.end(),myPrintf);
    cout << endl;
    swap(mv,mv2);
    for_each(mv.begin(),mv.end(),myPrintf);
    cout << endl;
    for_each(mv2.begin(),mv2.end(),myPrintf);
    cout << endl;
}
int main()
{
    test();
    return 0;
}

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
232 233 234 235 236 237 238 239 240 241 242 243 244
232 233 234 235 236 237 238 239 240 241 242 243 244
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

五、常用算术生成算法

算术生成算法属于小型算法，使用时包含头文件#include <numeric>

accumulate                    //计算容器元素累计和
fill                        //向容器中添加元素

1.accumulate-容器元素累加和

accumulate(iterator beg, iterator end, value);//计算容器元素累加总和

beg 开始迭代器
end 结束迭代器
value 起始值
返回值：结果

#include <iostream>
#include <vector>
#include <numeric>
#include <string>
using namespace std;
void test()
{
    vector<int> mv;
   for (int i = 0; i< 20 ; i++)
    {
        mv.push_back(i);
    }
    int result = accumulate(mv.begin(),mv.end(),0);
    cout<<result<<endl;
}
int main()
{
    test();
    return 0;
}

2.fill-填充指定元素

fill(iterator beg, iterator end, value);

beg 开始迭代器
end 结束迭代器
vlaue 填充值
必须先用resize预留好空间

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <string>
using namespace std;
void myPrintf(int & i)
{
    cout << i << " ";
}
void test()
{
    vector<int> mv;
    mv.resize(20);//预留空间、必须用resize
    fill(mv.begin(),mv.end(),5);
    for_each(mv.begin(),mv.end(),myPrintf);
    cout << endl;
}
int main()
{
    test();
    return 0;
}

六、常用集合算法

set_intersection            //求两个容器的交集
set_union                    //求两个容器的并集
set_difference                //求两个容器的差集

1.set_intersection-求两个容器的交集

set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

beg1 容器1开始迭代器
end1 容器1结束迭代器
beg2 容器2开始迭代器
end2 容器2结束迭代器
dest 目标容器开始迭代器,生成的容器也是有序的，而且重复的元素会前后排好
两个容器集合必须是有序序列
目标容器必须先分配好空间,否则程序会崩溃
返回值是交集在目标容器输出结束的位置

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
void myPrintf(int & i)
{
    cout << i << " ";
}
void test()
{
    vector<int> mv;
    vector<int> mv2;
    for (int i = 0; i< 20 ; i++)
    {
        mv.push_back(i);
    }
    for (int i = 10; i< 30; i++)
    {
        mv2.push_back(i);
    }
    vector<int> target;
     for_each(mv.begin(),mv.end(),myPrintf);
    cout << endl;
    for_each(mv2.begin(),mv2.end(),myPrintf);
    cout << endl;
    target.resize(min(mv.size(),mv2.size()));//目标容器必须先分配好空间,否则程序会崩溃
    vector<int>::iterator  itEnd = set_intersection(mv.begin(),mv.end(),mv2.begin(),mv2.end(),target.begin());//返回值是交集在目标容器输出结束的位置
    for_each(target.begin(),itEnd,myPrintf);//实际交集
    cout << endl;
    for_each(target.begin(),target.end(),myPrintf);
    cout << endl;
}
int main()
{
    test();
    return 0;
}

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
10 11 12 13 14 15 16 17 18 19
10 11 12 13 14 15 16 17 18 19 0 0 0 0 0 0 0 0 0 0

2.set_union-求并集

set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

beg1 容器1开始迭代器
end1 容器1结束迭代器
beg2 容器2开始迭代器
end2 容器2结束迭代器
dest 目标容器开始迭代器,生成的容器也是有序的，而且重复的元素会前后排好
两个容器集合必须是有序序列
目标容器必须先分配好空间,否则程序会崩溃
返回值是并集在目标容器输出结束的位置

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
void myPrintf(int & i)
{
    cout << i << " ";
}
void test()
{
    vector<int> mv;
    vector<int> mv2;
    for (int i = 0; i< 20 ; i++)
    {
        mv.push_back(i);
    }
    for (int i = 10; i< 30; i++)
    {
        mv2.push_back(i);
    }
    vector<int> target;
     for_each(mv.begin(),mv.end(),myPrintf);
    cout << endl;
    for_each(mv2.begin(),mv2.end(),myPrintf);
    cout << endl;
    target.resize(mv.size()+mv2.size());//目标容器必须先分配好空间,否则程序会崩溃
    vector<int>::iterator  itEnd = set_union(mv.begin(),mv.end(),mv2.begin(),mv2.end(),target.begin());//返回值是交集在目标容器输出结束的位置
    for_each(target.begin(),itEnd,myPrintf);
    cout << endl;
    for_each(target.begin(),target.end(),myPrintf);
    cout << endl;
}
int main()
{
    test();
    return 0;
}

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 0 0 0 0 0 0 0 0 0 0

3.set_difference-求差集

set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

beg1 容器1开始迭代器
end1 容器1结束迭代器
beg2 容器2开始迭代器
end2 容器2结束迭代器
dest 目标容器开始迭代器,生成的容器也是有序的，而且重复的元素会前后排好
两个容器集合必须是有序序列
目标容器必须先分配好空间,否则程序会崩溃
返回值是差集在目标容器输出结束的位置

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
void myPrintf(int & i)
{
    cout << i << " ";
}
void test()
{
    vector<int> mv;
    vector<int> mv2;
    for (int i = 0; i< 20 ; i++)
    {
        mv.push_back(i);
    }
    for (int i = 10; i< 30; i++)
    {
        mv2.push_back(i);
    }
    vector<int> target;
     for_each(mv.begin(),mv.end(),myPrintf);
    cout << endl;
    for_each(mv2.begin(),mv2.end(),myPrintf);
    cout << endl;
    target.resize(mv.size()+mv2.size());//目标容器必须先分配好空间,否则程序会崩溃
    vector<int>::iterator  itEnd = set_difference(mv.begin(),mv.end(),mv2.begin(),mv2.end(),target.begin());//返回值是交集在目标容器输出结束的位置
    for_each(target.begin(),itEnd,myPrintf);
    cout << endl;
    for_each(target.begin(),target.end(),myPrintf);
    cout << endl;
}
int main()
{
    test();
    return 0;
}

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

STL—常用算法

零、概述

一、常用遍历算法

1.for_each-遍历容器

2.transform-搬运到另一个容器中

二、常用查找算法

1.find-查找指定元素

内置数据类型

自定义数据类型

2.find_if-按条件查找

内置数据类型

自定义数据类型

3.adjacent_find-查找两个相邻重复元素

4.binary_search-查找指定元素是否存在、有序序列的二分查找法

5.count-统计元素出现次数

自定义类型

6.count_if-按条件统计元素个数

自定义数据类型

三、常用排序算法

1.sort-排序算法

2.radom_shuffle-随机打乱

3.merge-容器合并

四、常用拷贝和替换算法

1.copy-容器拷贝

2.replace-指定范围替换

3.replace_if-条件替换

五、常用算术生成算法

1.accumulate-容器元素累加和

2.fill-填充指定元素

六、常用集合算法

1.set_intersection-求两个容器的交集

2.set_union-求并集

3.set_difference-求差集

C++STL—常用算法

STL—常用算法

零、概述

一、常用遍历算法

1.for_each-遍历容器

2.transform-搬运到另一个容器中

二、常用查找算法

1.find-查找指定元素

内置数据类型

自定义数据类型

2.find_if-按条件查找

内置数据类型

自定义数据类型

3.adjacent_find-查找两个相邻重复元素

4.binary_search-查找指定元素是否存在、有序序列的二分查找法

5.count-统计元素出现次数

自定义类型

6.count_if-按条件统计元素个数

自定义数据类型

三、常用排序算法

1.sort-排序算法

2.radom_shuffle-随机打乱

3.merge-容器合并

四、常用拷贝和替换算法

1.copy-容器拷贝

2.replace-指定范围替换

3.replace_if-条件替换

五、常用算术生成算法

1.accumulate-容器元素累加和

2.fill-填充指定元素

六、常用集合算法

1.set_intersection-求两个容器的交集

2.set_union-求并集

3.set_difference-求差集

1.`for_each`-遍历容器

2.`transform`-搬运到另一个容器中

1.`for_each`-遍历容器

2.`transform`-搬运到另一个容器中