Oreo's Blog

C++学习笔记（十二）

2022/1/20 C++

# 一、STL-函数对象

# 1.1函数对象的概念

  • 重载函数调用操作符的类，其对象常被称为函数对象
  • 函数对象使用重载()时，行类类似函数的调用所以也被称为仿函数

注意：函数对象本质上是一个类，并不是一个函数

# 1.2函数对象的使用

  • 函数对象在使用时，可以像普通函数那样被调用，可以有参数，也可以有返回值
  • 函数对象超出普通函数的概念，函数对象可以有自己的状态
  • 函数对象可以作为参数进行传递

# 二、谓词

# 2.1基本概念

  • 返回布尔类型的仿函数称为谓词
  • 如果operator()接受一个参数，称为一元谓词
  • 如果operator()接受两个参数，称为二元谓词

# 2.2一元谓词

#include "iostream"
#include "vector"
#include "algorithm"
using namespace std;

class GreaterFive {
public:
    bool operator()(int v) {
        return v > 5;
    }
};

int main() {
    vector<int> v;
    for (int i = 0; i < 10; i++) {
        v.push_back(i);
    }

    // 查找容器中是否存在大于5的数字
    // 使用find_if方法返回的是一个迭代器
    vector<int>::iterator it = find_if(v.begin(), v.end(), GreaterFive());
    if (it == v.end()) {
        cout << "Cant find" << endl;
    } else {
        cout << "Find it" << endl;
    }
}

# 2.3二元谓词

//
// Created by Jacob Lee on 2022/1/17.
//
#include "iostream"
using namespace std;
#include "algorithm"
#include "vector"

class PrintVector {
public:
    void operator()(vector<int> v) {
        for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
            cout << *it << " ";
        }
        cout << endl;
    }
};

// 二元谓词
class myCompare {
public:
    bool operator()(int v1, int v2) {
        return v1 > v2;
    }
};

int main() {
    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(40);
    v.push_back(30);
    v.push_back(0);

    PrintVector printVector;
    printVector(v);

    // 排序
    sort(v.begin(), v.end());
    printVector(v);

    // 使用函数对象改变算法策略
    sort(v.begin(), v.end(), myCompare());
    printVector(v);
}

# 三、STL-内建函数对象

# 3.1基本概念

STL哪见了一些函数对象，总共有三大类：算数仿函数、关系仿函数、逻辑仿函数

用法：

  • 这些仿函数产生的对象，用法和一般的函数完全一致
  • 使用内建函数对象，必须要引入头文件#include "funcional"

# 3.2算数仿函数

作用是实现四则运算，其中除去取反仿函数之外，其余的都是二元运算

  • template<class T> T plus<T>加法仿函数
  • template<class T> T minus<T>减法仿函数
  • template<class T> T multiplies<T>乘法仿函数
  • template<class T> T divides<T>除法仿函数
  • template<class T> T modulus<T>取模仿函数
  • template<class T> T negate<T>取反仿函数
#include "iostream"
#include "functional"
using namespace std;

int main() {
    // 一元内建函数
    negate<int> n;
    cout << n(50) << endl;

    // 二元内建函数
    plus<int> p;
    cout << p(1, 2) << endl;
}

# 3.3关系仿函数

  • template<class T> bool equal_to<T>等于
  • template<class T> bool not_equal_to<T>不等于
  • template<class T> bool greater<T>大于
  • template<class T> bool greater_equal<T>大于等于
  • template<class T> bool less<T>小于
  • template<class T> bool less_qual<T>小于等于

# 3.4逻辑仿函数

  • template<class T> bool logical_and<T>与
  • template<class T> bool logical_or<T>或
  • template<class T> bool logical_not<T>非

# 四、STL-常用算法

  • 算法主要是由头文件<algorithm> <functional> <numeric>组成
  • algorithm是所有STL头文件中最大的一个，范围涉及到比较、交换、查找、遍历、复制等等
  • numeric体积非常小，只包含了几个在序列上看进行的简单数学运算
  • functional定义了一些模板类，用于声明函数对象

# 4.1遍历算法

# 4.1.1for_each

实现遍历容器

函数原型：for_each(iterator beg, iterator end, func);

beg表示开始迭代器

end表示结束迭代器

func表示函数或者函数对象

#include "iostream"
#include "vector"
#include "algorithm"
using namespace std;

// 普通函数
void printVector01(int val) {
    cout << val << " ";
}

// 仿函数
class printVector02 {
public:
    void operator()(int val) {
        cout << val << " ";
    }
};

int main() {
    vector<int> v;
    for (int i = 0; i < 10; i++) {
        v.push_back(i);
    }

    // 普通函数调用
    for_each(v.begin(), v.end(), printVector01);
    cout << endl;

    // 仿函数调用
    for_each(v.begin(), v.end(), printVector02());
    cout << endl;
}

# 4.1.2transform

主要的用途是：将一个容器搬运到另一个容器中

函数原型：transfor(iterator beg1, iterator end1, iterator beg2, func);

beg1源容器开始迭代器

end1源容器结束迭代器

beg2目标容器开始迭代器

func函数或者函数对象

#include "iostream"
#include "vector"
#include "algorithm"
using namespace std;

// 普通函数
void printVector01(int val) {
    cout << val << " ";
}

// transform处理函数
class Transform {
public:
    int operator()(int val) {
        return val + 1;
    }
};

int main() {
    vector<int> v;
    for (int i = 0; i < 10; i++) {
        v.push_back(i);
    }

    // 设定目标容器
    vector<int> vtarget;
    // 开辟空间
    vtarget.resize(v.size());
    transform(v.begin(), v.end(), vtarget.begin(), Transform());
    for_each(vtarget.begin(), vtarget.end(), printVector01);
}

注意！在进行目标搬运时一定要注意开辟新空间

# 4.2查找算法

# 4.2.1find

作用：查找元素，返回指定元素的迭代器，找不到就返回迭代器end()

  • fund(iterator beg, iterator end, value);
#include "iostream"
#include "vector"
#include "algorithm"
#include "string"
using namespace std;

class Person {
public:
    string m_Name;
    int m_Age;
    Person(string name, int age) {
        this->m_Name = name;
        this->m_Age = age;
    }
    bool operator==(const Person & p) {
        if (this->m_Name == p.m_Name && this->m_Age == p.m_Age) {
            return true;
        } else {
            return false;
        }
    }
};

int main() {
    // 内置类型
    vector<int> v;
    for (int i = 0; i < 10; i++) {
        v.push_back(i);
    }

    // 自定义类型
    vector<Person> p;
    Person p1("a", 10);
    p.push_back(p1);
    Person p2("b", 20);
    p.push_back(p2);
    Person p3("c", 30);
    p.push_back(p3);
    Person p4("d", 40);
    p.push_back(p4);

    // 使用find查找
    vector<int>::iterator it01 = find(v.begin(), v.end(), 5);
    cout << *it01 << endl;

    // 如果使用自定义类型一定要注意重载底层的==号
    vector<Person>::iterator it02 = find(p.begin(), p.end(), p2);
    cout << it02->m_Name << ": " << it02->m_Age << endl;
}

# 4.2.2find_if

作用：按条件查找元素

  • find_if(iterator beg, iterator end, end, pred)

pred表示函数或者谓词（返回bool类型的仿函数）

//
// Created by Jacob Lee on 2022/1/19.
//
#include "iostream"
#include "vector"
#include "algorithm"
#include "string"
using namespace std;

class Person {
public:
    string m_Name;
    int m_Age;
    Person(string name, int age) {
        this->m_Name = name;
        this->m_Age = age;
    }
    bool operator==(const Person & p) {
        if (this->m_Name == p.m_Name && this->m_Age == p.m_Age) {
            return true;
        } else {
            return false;
        }
    }
};

class GreaterFive {
public:
    bool operator()(int val) {
        return val > 5;
    }
};

class GreaterTwenty {
public:
    bool operator()(Person & p) {
        return p.m_Age > 20;
    }
};


int main() {
    // 内置类型
    vector<int> v;
    for (int i = 0; i < 10; i++) {
        v.push_back(i);
    }

    // 自定义类型
    vector<Person> p;
    Person p1("a", 10);
    p.push_back(p1);
    Person p2("b", 20);
    p.push_back(p2);
    Person p3("c", 30);
    p.push_back(p3);
    Person p4("d", 40);
    p.push_back(p4);

    vector<int>::iterator it01 = find_if(v.begin(), v.end(), GreaterFive());
    cout << *it01 << endl;

    vector<Person>::iterator it02 = find_if(p.begin(), p.end(), GreaterTwenty());
    cout << it02->m_Name << ": "<< it02->m_Age << endl;
}

# 4.2.3adjacent_find

作用：查找相邻的重复元素

  • adjacent_find(iterator beg, iterator end);
#include "iostream"
#include "vector"
#include "algorithm"
#include "string"
using namespace std;

int main() {
    // 内置类型
    vector<int> v;
    v.push_back(0);
    v.push_back(1);
    v.push_back(1);
    v.push_back(3);
    v.push_back(4);

    vector<int>::iterator it = adjacent_find(v.begin(), v.end());
    cout << *it << endl;
}

# 4.2.4binary_search

作用：二分查找，查找指定元素是否存在

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

查找指定元素，查到返回true，否则返回false

能够使用binary_search一定要是一个有序序列

//
// Created by Jacob Lee on 2022/1/19.
//
#include "iostream"
#include "vector"
#include "algorithm"
#include "string"
using namespace std;

int main() {
    // 内置类型
    vector<int> v;
    for (int i = 0; i < 10; i++) {
        v.push_back(i);
    }

    if (binary_search(v.begin(), v.end(), 5)) {
        cout << "OK" << endl;
    } else {
        cout << "NO" << endl;
    }
}

# 4.2.5count

作用：统计元素个数

  • count(iterator beg, iterator end, value);

value表示统计的元素

//
// Created by Jacob Lee on 2022/1/19.
//
#include "iostream"
#include "vector"
#include "algorithm"
#include "string"
using namespace std;

class Person {
public:
    string m_Name;
    int m_Age;
    Person(string name, int age) {
        this->m_Name = name;
        this->m_Age = age;
    }
    bool operator==(const Person & p) {
        if (this->m_Age == p.m_Age) {
            return true;
        } else {
            return false;
        }
    }
};

int main() {
    // 内置类型
    vector<int> v;
    for (int i = 0; i < 10; i++) {
        v.push_back(i);
        v.push_back(i);
    }

    // 自定义类型
    vector<Person> p;
    Person p1("a", 10);
    p.push_back(p1);
    Person p2("b", 10);
    p.push_back(p2);
    Person p3("c", 10);
    p.push_back(p3);
    Person p4("d", 40);
    p.push_back(p4);

    int num_count = count(v.begin(), v.end(), 2);
    cout << num_count << endl;

    Person target("t", 10);
    int person_count = count(p.begin(), p.end(), target);
    cout << person_count << endl;
}

# 4.2.6count_if

作用：按条件统计元素个数

  • count_if(iterator beg, iterator end, pred);

pred表示筛选的谓词

//
// Created by Jacob Lee on 2022/1/19.
//
#include "iostream"
#include "vector"
#include "algorithm"
#include "string"
using namespace std;

class Person {
public:
    string m_Name;
    int m_Age;
    Person(string name, int age) {
        this->m_Name = name;
        this->m_Age = age;
    }
    bool operator==(const Person & p) {
        if (this->m_Age == p.m_Age) {
            return true;
        } else {
            return false;
        }
    }
};

class GreaterTwo {
public:
    bool operator()(int val) {
        return val > 2;
    }
};

class GreaterTwenty {
public:
    bool operator()(const Person & p) {
        return p.m_Age > 20;
    }
};

int main() {
    // 内置类型
    vector<int> v;
    for (int i = 0; i < 10; i++) {
        v.push_back(i);
    }

    // 自定义类型
    vector<Person> p;
    Person p1("a", 10);
    p.push_back(p1);
    Person p2("b", 20);
    p.push_back(p2);
    Person p3("c", 30);
    p.push_back(p3);
    Person p4("d", 40);
    p.push_back(p4);

    int num_count = count_if(v.begin(), v.end(), GreaterTwo());
    cout << num_count << endl;

    int person_count = count_if(p.begin(), p.end(), GreaterTwenty());
    cout << person_count << endl;
}

# 4.3排序算法

# 4.3.1sort

对容器内的元素进行排序

  • sirt(iterator beg, iterator end, pred)

pred可填可不填，如果不填则使用默认规则：从小到大，如果要填则需要使用一个谓词

#include "iostream"
#include "vector"
#include "algorithm"
#include "string"
using namespace std;

class mySort {
public:
    bool operator()(int a, int b) {
        return a > b;
    }
};

void printVector(int val) {
    cout << val << " ";
}

int main() {
    // 内置类型
    vector<int> v;
    for (int i = 0; i < 10; i++) {
        v.push_back(i);
    }

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

    sort(v.begin(), v.end(), mySort());
    for_each(v.begin(), v.end(), printVector);
    cout << endl;
}

# 4.3.2random_shuffle

将指定范围内中所有的元素进行随意调整次序

  • random_shuffle(iterator beg, iterator end)
#include "iostream"
#include "vector"
#include "algorithm"
#include "ctime"
using namespace std;

void printVector(int val) {
    cout << val << " ";
}

int main() {
    srand((unsigned int) time(NULL));
    // 内置类型
    vector<int> v;
    for (int i = 0; i < 10; i++) {
        v.push_back(i);
    }

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

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

# 4.3.3merge

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

  • merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)

dest表示目标 容器的开始迭代器

//
// Created by Jacob Lee on 2022/1/19.
//
#include "iostream"
#include "vector"
#include "algorithm"
#include "ctime"
using namespace std;

void printVector(int val) {
    cout << val << " ";
}

int main() {
    vector<int> v1;
    for (int i = 0; i < 10; i++) {
        v1.push_back(i);
    }

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

    vector<int> v3;
    v3.resize(v1.size() + v2.size());
    merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());

    for_each(v3.begin(), v3.end(), printVector);
}

# 4.3.4reverse

将容器中的元素进行反转

  • reverse(iterator beg, iterator end);
#include "iostream"
#include "vector"
#include "algorithm"
#include "ctime"
using namespace std;

void printVector(int val) {
    cout << val << " ";
}

int main() {
    vector<int> v;
    for (int i = 0; i < 10; i++) {
        v.push_back(i);
    }

    reverse(v.begin(), v.end());
    for_each(v.begin(), v.end(), printVector);
}

# 4.4拷贝和替换算法

# 4.4.1copy

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

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

dest表示目标容器的起始迭代器

#include "iostream"
#include "vector"
#include "algorithm"
#include "ctime"
using namespace std;

void printVector(int val) {
    cout << val << " ";
}

int main() {
    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());

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

# 4.4.1replace

将容器内指定范围的旧元素修改为新元素

  • replace(iterator beg, iterator end, oldvalue, newvalue)

oldvalue表示目标旧元素，newvalue表示要修改的新元素

注意！是将范围内所有的旧元素都进行修改

# 4.4.1replace_if

将区间内满足条件的元素替换为指定元素

  • replace_if(iterator beg, iterator end, pred, newvalue);

pred表示判断条件的谓词

# 4.4.1swap

对两个容器进行互换

  • swap(container c1, container c2);

c1和c2分别表示两个需要互换的容器

# 4.5算数算法

注意：在进行算数算法时需要包含头文件：#include "numeric"

# 4.5.1accumulate

计算区间内容器元素的累计总和

  • accumulate(iterator beg, iterator end, value);

value表示起始值，在累计总和的基础上加的值

#include "iostream"
#include "vector"
#include "numeric"
using namespace std;

int main() {
    vector<int> v;
    for (int i = 0; i <= 100; i++) {
        v.push_back(i);
    }

    int sum = accumulate(v.begin(), v.end(),0);
    cout << sum << endl;
}

# 4.5.2fill

向容器中填充指定的元素

  • fill(iterator beg, iterator end, value)

value表示需要填充的值

#include "iostream"
#include "vector"
#include "numeric"
using namespace std;

int main() {
    vector<int> v;
    v.resize(10);
    fill(v.begin(), v.end(), 100);
}

# 4.6集合算法

这里使用的所有集合必须是有序序列

# 4.6.1set_intersection

求两个容器的交集

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

该算法返回一个迭代器，该迭代器指向交集的位置（尾部）

# 4.6.2set_union

求两个容器的并集

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

# 4.6.3set_difference

求两个容器的差集

  • set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)
#include "iostream"
#include "vector"
#include "algorithm"
using namespace std;

void printVector(int val) {
    cout << val << " ";
}

int main() {
    vector<int> v1;
    for (int i = 0; i <= 10; i++) {
        v1.push_back(i);
    }

    vector<int> v2;
    for (int i = 5; i <= 15; i++) {
        v2.push_back(i);
    }

    // 求交集
    vector<int> intersection_target;
    intersection_target.resize(min(v1.size(), v2.size()));
    vector<int>::iterator intersection_it = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), intersection_target.begin());
    for_each(intersection_target.begin(), intersection_it, printVector);
    cout << endl;

    // 求并集
    vector<int> union_target;
    intersection_target.resize(v1.size() + v2.size());
    vector<int>::iterator union_it = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), intersection_target.begin());
    for_each(intersection_target.begin(), union_it, printVector);
    cout << endl;

    // 求差集
    vector<int> difference_target;
    intersection_target.resize(max(v1.size(), v2.size()));
    vector<int>::iterator difference_it01 = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), intersection_target.begin());
    for_each(intersection_target.begin(), difference_it01, printVector);
    cout << endl;
    vector<int>::iterator difference_it02 = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), intersection_target.begin());
    for_each(intersection_target.begin(), difference_it02, printVector);
    cout << endl;
}