C++学习笔记——STL常用算法

常用遍历算法：

for_each

功能：实现遍历容器

函数原型：

for_each(iterator beg, iterator end, _func);
// 遍历算法 遍历容器元素
// beg 开始迭代器
// end 结束迭代器
// _func 函数或者函数对象

例子：

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


//普通函数
void print01(int a){
    cout<<a<<" ";
}

//函数对象
class print02{
public:
    void operator()(int a){
        cout<<a<<" ";
    }
};

void test01(){
    vector<int> v;
    for(int i=0;i<20;i++){
        v.push_back(i);
    }

//    遍历
    for_each(v.begin(),v.end(),print01);
    cout<<endl;

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

int main() {
    test01();
    return 0;
}

transform

功能：搬运容器到另一个容器中

函数原型：

transform(iterator beg1, iterator end1, iterator beg2, _func);
//beg1 源容器开始迭代器
//end1 源容器结束迭代器
//beg2 目标容器开始迭代器
//_func 函数或者函数对象

例子：

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


//函数对象
class print01{
public:
    void operator()(int a){
        cout<<a<<" ";
    }
};

class Transform{
public:
    int operator()(int value){
        return value;
    }
};

void test01(){
    vector<int> v;
    for(int i=0;i<20;i++){
        v.push_back(i);
    }

//    目标容器
    vector<int> v_target;
//    目标容器需要提前开辟空间
    v_target.resize(v.size());

    transform(v.begin(),v.end(),v_target.begin(),Transform());

    for_each(v_target.begin(),v_target.end(),print01());
    cout<<endl;
}

int main() {
    test01();
    return 0;
}

常用查找算法：

find

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

函数原型：

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

例子：

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


class Student{
public:
    Student(string name,int age){
        this->m_name=name;
        this->m_age=age;
    }

//    查找自定义数据类型时需要重载==运算符
    bool operator==(const Student& student){
        if(this->m_name==student.m_name&&this->m_age==student.m_age){
            return true;
        }
        return false;
    }

public:
    string m_name;
    int m_age;
};

void test01(){
    Student student1("li",20);
    Student student2("wang",16);
    Student student3("liu",18);
    Student student4("tian",16);

    vector<Student> v;

    v.push_back(student1);
    v.push_back(student2);
    v.push_back(student3);
    v.push_back(student4);

//    查找指定元素
    vector<Student>::iterator  it=find(v.begin(),v.end(),student1);
    if(it!=v.end()){
        cout<<"找到学生"<<endl;
    }else{
        cout<<"未找到"<<endl;
    }
}

int main() {
    test01();
    return 0;
}

find_if

功能：按照条件查找第一个满足条件的元素

函数原型：

find_if(iterator beg, iterator end, _Pred); 
// 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置
// beg 开始迭代器
// end 结束迭代器
// _Pred 函数或者谓词（返回bool类型的仿函数）

例子：

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


class LessthanEight{
public:
    bool operator()(int value){
        return value<8;
    }
};

void test01(){
    vector<int> v;
    for(int i=0;i<20;i++){
        v.push_back(i);
    }

    vector<int>::iterator it=find_if(v.begin(),v.end(),LessthanEight());
    if(it!=v.end()){
        cout<<"找到了小于8的元素:"<<*it<<endl;
    }else{
        cout<<"未找到"<<endl;
    }
}

int main() {
    test01();
    return 0;
}

adjacent_find

功能：查找相邻重复元素

函数原型：

adjacent_find(iterator beg, iterator end); 
// 查找相邻重复元素,返回相邻元素的第一个位置的迭代器
// beg 开始迭代器
// end 结束迭代器

例子：

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


void test01(){
    vector<int> v;
    v.push_back(2);
    v.push_back(3);
    v.push_back(3);
    v.push_back(5);
    v.push_back(4);
    v.push_back(4);

    vector<int>::iterator it=adjacent_find(v.begin(),v.end());
    if(it!=v.end()){
        cout<<"找到相邻的重复元素为："<<*it<<endl;
    }else{
        cout<<"未找到"<<endl;
    }
}

int main() {
    test01();
    return 0;
}

binary_search

功能：使用二分查找，查找指定元素是否存在，必须在有序序列中使用

函数原型：

bool binary_search(iterator beg, iterator end, value);  
// 查找指定的元素，查到 返回true  否则false
// beg 开始迭代器
// end 结束迭代器
// value 查找的元素

例子：

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


void test01(){
    vector<int> v;
    for(int i=0;i<20;i++){
        v.push_back(i);
    }

//    二分查找
    bool ret=binary_search(v.begin(),v.end(),8);
    if(ret){
        cout<<"找到了"<<endl;
    }else{
        cout<<"未找到"<<endl;
    }
}

int main() {
    test01();
    return 0;
}

count

功能：统计元素个数，在统计自定义的数据类型时需要重载==运算符

函数原型：

count(iterator beg, iterator end, value);  
// 统计元素出现次数
// beg 开始迭代器
// end 结束迭代器
// value 统计的元素

例子：

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


void test01(){
    vector<int> v;
    for(int i=0;i<20;i++){
        v.push_back(i%2);
    }
    
    int num=count(v.begin(),v.end(),1);
    cout<<"1的个数为："<<num<<endl;
}

int main() {
    test01();
    return 0;
}

count_if

功能：按照条件统计元素个数

函数原型：

count_if(iterator beg, iterator end, _Pred);  
// 按条件统计元素出现次数
// beg 开始迭代器
// end 结束迭代器
// _Pred 谓词

例子：

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

class Less15{
public:
    bool operator()(int value){
        return value<15;
    }
};

void test01(){
    vector<int> v;
    for(int i=0;i<20;i++){
        v.push_back(i);
    }

    int num=count_if(v.begin(),v.end(),Less15());
    cout<<"小于15的个数为："<<num<<endl;
}

int main() {
    test01();
    return 0;
}

常用排序算法：

sort

功能：对容器内元素排序，默认从小到大

函数原型：

sort(iterator beg, iterator end, _Pred);
// 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置
//  beg    开始迭代器
//  end    结束迭代器
// _Pred  谓词

random_shuffle

功能：指定范围内元素随机调整次序，使用的时候要添加随机数种子

函数原型：

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

merge

功能：两个容器元素合并，并存储到另一个容器中

函数原型：

merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest); 
// 容器元素合并，并存储到另一容器中
// 注意: 两个容器必须是有序的
// beg1   容器1开始迭代器
// end1   容器1结束迭代器
// beg2   容器2开始迭代器
// end2   容器2结束迭代器
// dest    目标容器开始迭代器

reverse

功能：将容器内元素进行反转

函数原型：

reverse(iterator beg, iterator end); 
// 反转指定范围的元素
// beg 开始迭代器
// end 结束迭代器

例子：

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


void print_vector(const vector<int>& v){
    for(vector<int>::const_iterator it=v.begin();it!=v.end();it++){
        cout<<*it<<" ";
    }
    cout<<endl;
}

void test01(){
    vector<int> v;
    v.push_back(15);
    v.push_back(3);
    v.push_back(45);
    v.push_back(9);
    v.push_back(25);

//    sort默认从小到大
    sort(v.begin(),v.end());
    print_vector(v);

//    从大到小排序
    sort(v.begin(),v.end(),greater<int>());
    print_vector(v);
}

void test02(){
    srand((unsigned int)time(NULL));
    vector<int> v;
    for(int i=0;i<10;i++){
        v.push_back(i);
    }
    print_vector(v);

//    打乱顺序
    random_shuffle(v.begin(),v.end());
    print_vector(v);
}

void test03(){
    vector<int> v1;
    vector<int> v2;
    for(int i=0;i<10;i++){
        v1.push_back(i);
        v2.push_back(i+1);
    }

    vector<int> v_dst;
//    目标容器要提前开辟空间
    v_dst.resize(v1.size()+v2.size());
//    合并，两个有序序列
    merge(v1.begin(),v1.end(),v2.begin(),v2.end(),v_dst.begin());
    print_vector(v_dst);
}

void test04(){
    vector<int> v;
    for(int i=0;i<10;i++){
        v.push_back(i);
    }
    cout<<"反转前："<<endl;
    print_vector(v);

    cout<<"反转后："<<endl;
    reverse(v.begin(),v.end());
    print_vector(v);
}
int main() {
    test01();
    test02();
    test03();
    test04();
    return 0;
}

常用拷贝和替换算法：

copy

功能：容器内指定范围的元素拷贝到另一个容器中

函数原型：

copy(iterator beg, iterator end, iterator dest); 
// 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置
// beg  开始迭代器
// end  结束迭代器
// dest 目标起始迭代器

replace

功能：将容器内指定范围的旧元素替换为新元素

函数原型：

replace(iterator beg, iterator end, oldvalue, newvalue);  
// 将区间内旧元素 替换成 新元素
// beg 开始迭代器
// end 结束迭代器
// oldvalue 旧元素
// newvalue 新元素

replace_if

功能：将容器内指定范围满足条件的元素，替换为新元素

函数原型：

replace_if(iterator beg, iterator end, _pred, newvalue); 
// 按条件替换元素，满足条件的替换成指定元素
// beg 开始迭代器
// end 结束迭代器
// _pred 谓词
// newvalue 替换的新元素

swap

功能：互换两个容器的元素

函数原型：

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

例子：

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


void print_vector(const vector<int>& v){
    for(vector<int>::const_iterator it=v.begin();it!=v.end();it++){
        cout<<*it<<" ";
    }
    cout<<endl;
}

void test01(){
    vector<int> v1;
    for(int i=0;i<10;i++){
        v1.push_back(i);
    }
    vector<int> v2;
    v2.resize(v1.size());
    copy(v1.begin(),v1.end(),v2.begin());
    print_vector(v2);
}

void test02(){
    vector<int> v;
    v.push_back(5);
    v.push_back(2);
    v.push_back(6);
    v.push_back(5);
    v.push_back(4);

    cout<<"替换前："<<endl;
    print_vector(v);

    cout<<"替换后："<<endl;
    replace(v.begin(),v.end(),5,10);
    print_vector(v);
}

class Less20{
public:
    bool operator()(int value){
        return value<10;
    }
};

void test03(){
    vector<int> v;
    for(int i=0;i<20;i++){
        v.push_back(i);
    }

    cout<<"替换前："<<endl;
    print_vector(v);

    cout<<"替换后："<<endl;
    replace_if(v.begin(),v.end(),Less20(),10);
    print_vector(v);
}

void test04(){
    vector<int> v1;
    vector<int> v2;
    for(int i=0;i<10;i++){
        v1.push_back(i);
        v2.push_back(i+2);
    }

    cout<<"交换前："<<endl;
    print_vector(v1);
    print_vector(v2);

    cout<<"交换后："<<endl;
    swap(v1,v2);
    print_vector(v1);
    print_vector(v2);
}

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

常用算术生成算法：

使用时需要包含头文件#include<numeric>

accumulate

功能：计算区间内容器元素累计之和

函数原型：

accumulate(iterator beg, iterator end, value);  
// 计算容器元素累计总和
// beg 开始迭代器
// end 结束迭代器
// value 起始值

fill

功能：向容器中填充指定的元素

函数原型：

fill(iterator beg, iterator end, value);  
// 向容器中填充元素
// beg 开始迭代器
// end 结束迭代器
// value 填充的值

例子:

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

class MyPrint{
public:
    void operator()(int value){
        cout<<value<<" ";
    }
};

void test01(){
    vector<int> v1;
    for(int i=0;i<1000;i++){
        v1.push_back(i);
    }

//    求和
    int sum=accumulate(v1.begin(),v1.end(),0);
    cout<<"sum= "<<sum<<endl;

    vector<int> v2;
    v2.resize(20);
//    填充
    fill(v2.begin(),v2.end(),10);
    for_each(v2.begin(),v2.end(),MyPrint());
}

int main() {
    test01();
    return 0;
}

常用集合算法：

set_intersection

功能：求两个集合的交集

函数原型：

set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);  
// 求两个集合的交集
// **注意:两个集合必须是有序序列**
// beg1 容器1开始迭代器
// end1 容器1结束迭代器
// beg2 容器2开始迭代器
// end2 容器2结束迭代器
// dest 目标容器开始迭代器

set_union

功能：求两个集合的并集

函数原型：

set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);  
// 求两个集合的并集
// **注意:两个集合必须是有序序列**
// beg1 容器1开始迭代器
// end1 容器1结束迭代器
// beg2 容器2开始迭代器
// end2 容器2结束迭代器
// dest 目标容器开始迭代器

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 <algorithm>
#include <vector>
using namespace std;


class MyPrint{
public:
    void operator()(int value){
        cout<<value<<" ";
    }
};

//交集
void test01(){
    vector<int> v1;
    vector<int> v2;
    for(int i=0;i<10;i++){
        v1.push_back(i);
        v2.push_back(i+2);
    }

    cout<<"v1:"<<endl;
    for_each(v1.begin(),v1.end(),MyPrint());
    cout<<endl;
    cout<<"v2:"<<endl;
    for_each(v2.begin(),v2.end(),MyPrint());
    cout<<endl;

    vector<int> v_dst;
//    取两个里面较小的值给目标容器开辟空间
    v_dst.resize(min(v1.size(),v2.size()));
//    返回目标容器的最后一个元素的迭代器地址
    vector<int>::iterator it=set_intersection(v1.begin(),v1.end(),v2.begin(),v2.end(),v_dst.begin());
    cout<<"v1和v2的交集:"<<endl;
    for_each(v_dst.begin(),it,MyPrint());
    cout<<endl;
}

//并集
void test02(){
    vector<int> v1;
    vector<int> v2;
    for(int i=0;i<10;i++){
        v1.push_back(i);
        v2.push_back(i+2);
    }

    cout<<"v1:"<<endl;
    for_each(v1.begin(),v1.end(),MyPrint());
    cout<<endl;
    cout<<"v2:"<<endl;
    for_each(v2.begin(),v2.end(),MyPrint());
    cout<<endl;

    vector<int> v_dst;
//    取两个的和给目标容器开辟空间
    v_dst.resize(v1.size()+v2.size());
//    返回目标容器的最后一个元素的迭代器地址
    vector<int>::iterator it=set_union(v1.begin(),v1.end(),v2.begin(),v2.end(),v_dst.begin());
    cout<<"v1和v2的并集:"<<endl;
    for_each(v_dst.begin(),it,MyPrint());
    cout<<endl;
}

//差集
void test03(){
    vector<int> v1;
    vector<int> v2;
    for(int i=0;i<10;i++){
        v1.push_back(i);
        v2.push_back(i+2);
    }

    cout<<"v1:"<<endl;
    for_each(v1.begin(),v1.end(),MyPrint());
    cout<<endl;
    cout<<"v2:"<<endl;
    for_each(v2.begin(),v2.end(),MyPrint());
    cout<<endl;

    vector<int> v_dst;
//    取两个的较大值给目标容器开辟空间
    v_dst.resize(max(v1.size(),v2.size()));
//    返回目标容器的最后一个元素的迭代器地址
    vector<int>::iterator it1=set_difference(v1.begin(),v1.end(),v2.begin(),v2.end(),v_dst.begin());
    cout<<"v1和v2的差集:"<<endl;
    for_each(v_dst.begin(),it1,MyPrint());
    cout<<endl;

    vector<int>::iterator it2=set_difference(v2.begin(),v2.end(),v1.begin(),v1.end(),v_dst.begin());
    cout<<"v2和v1的差集:"<<endl;
    for_each(v_dst.begin(),it2,MyPrint());
    cout<<endl;
}

int main() {
    test01();
    test02();
    test03();
    return 0;
}