Skip to content

STL算法

算法中包含很多对容器进行处理的算法,使用迭代器来标识要处理的数据或数据段、以及结果的存放位置,有的函数还作为对象参数传递给另一个函数,实现数据的处理。这些算法可以操作在多种容器类型上,所以称为“泛型”,泛型算法不是针对容器编写,而只是单独依赖迭代器和迭代器操作实现。而且算法库中的算法都是普通函数(自由函数)。

头文件

算法主要是由头文件<algorithm><functional><numeric>组成。

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

分类

  • 非修改式序列操作:不改变容器的内容,如find()、for_each()等。
  • 修改式序列操作:可以修改容器中的内容,如transform()、random_shuffle()、copy等。
  • 排序和相关操作:包括各种排序函数等,如sort()等。
  • 通用数字运算:计算两个容器的内部乘积等。

函数/断言/谓词

  • 函数:普通函数。
  • 断言:返回bool类型的函数称为断言/谓词。
  • 函数对象:重载了函数调用运算符的类的对象称为函数对象。

  • 一元函数:接受一个参数的函数,返回一个值。
  • 一元断言/一元谓词:接受一个参数的函数,返回值为bool类型的函数,用于判断一个条件是否成立。
  • 二元函数:接受两个参数的函数,返回一个值。
  • 二元断言/二元谓词:接受两个参数的函数,返回值为bool类型的函数,用于判断一个条件是否成立。
cpp
//一元断言/一元谓词
bool func(int value){
   return value > 5;
}

// 一元函数
void func(int value) {
    cout << value << " ";
}

函数绑定器

https://zh.cppreference.com/w/cpp/utility/functional

类模板声明

cpp
#include <functional>
template <class F, class T>
std::binder1st<F> bind1st(const F &f, const T &x);

template <class F, class T>
std::binder2nd<F> bind2nd(const F &f, const T &x);

模板形式中,两个函数绑定器的第一个参数就是一个函数,第二个参数就是一个数字,如果F是一个二元函数(普通二元函数或者二元谓词),我们可以绑定F的第一个参数(bind1st)或者第二个参数(bind2nd),达到我们想要的效果(使用二元谓词的效果)

cpp
void test() {
    vector<int> number{1, 3, 5, 4, 9, 7, 6, 2, 10};
    copy(number.begin(), number.end(), ostream_iterator<int>(cout, " "));
    std::greater<int> gt;
    auto it = remove_if(number.begin(), number.end(), std::bind2nd(gt, 5));
    number.erase(it, number.end());
    copy(number.begin(), number.end(), ostream_iterator<int>(cout, " "));
}

C++11中的bind(非常重要)

cpp
#include <functional>

template <class F, class... Args>
/*unspecified*/ bind(F &&f, Args &&...args); // 返回类型没有确定

template <class R, class F, class... Args>
/*unspecified*/ bind(F &&f, Args &&...args); // 返回类型没有确定

bind函数的使用相比于bind1st以及bind2nd更加的具有通用性,因为后者只能绑定一个参数,而bind可以绑定任意个参数。

绑定函数类型

bind可以绑定到普通函数、成员函数。

cpp
int add(int x, int y) {
    cout << "int add(int, int)" << endl;
    return x + y;
}
class Example {
public:
    int add(int x, int y) // 成员函数形式
    {
        cout << "int Example::add(int, int)" << endl;
        return x + y;
    }
};
void test() {
    auto f = bind(add, 1, 2);
    cout << "f() = " << f() << endl; // 类似C语言中函数指针的用法
    Example example;
    // 非静态的成员函数的第一个隐含参数是this指针
    auto f2 = bind(&Example::add, &example, 10, 20);
    cout << "f() = " << f() << endl;
}

函数指针的特点

  • 函数指针的类型是由函数的返回值类型和参数类型共同决定的。
  • 函数指针的类型是一个指针类型,指向一个函数。
  • 函数指针的类型是一个函数类型,这个函数类型的返回值类型和参数类型和函数的返回值类型和参数类型相同。
cpp
typedef int (*pFunc)(); // 函数指针

int func1() {
    return 5;
}

int func2() {
    return 10;
}

void test2() {
    pFunc f = func1;                 // 对于f注册回调函数,C语言是可以实现多态的(通过函数指针实现多态)
    cout << "f() = " << f() << endl; // 执行回调函数
    f = func2;
    cout << "f() = " << f() << endl;
}

函数对象

函数对象是可以以函数方式与()结合使用的任意对象,包括:(functor-仿函数)

  1. 函数名;
  2. 指向函数的指针;
  3. 重载了()操作符的类对象(即定义了函数operator()()的类)。

以上就是对函数对象做了一个扩充,具体的使用形式已经用过,此处不再赘述。

  • 函数对象的类型是由函数的返回值类型和参数类型共同决定的。
  • 函数对象的类型是一个类类型,这个类类型重载了函数调用运算符。
  • 函数对象的类型是一个函数类型,这个函数类型的返回值类型和参数类型和函数的返回值类型和参数类型相同。

函数对象和函数指针的区别

  • 函数对象是一个类类型,这个类类型重载了函数调用运算符。
  • 函数指针是一个指针类型,指向一个函数。
  • 函数对象的类型是一个类类型,这个类类型重载了函数调用运算符。

占位符

如果使用bind绑定函数的时候,并不是一定要将所有的参数全部以具体的值进行传递,可以使用占位符占据绑定的参数。例如:

cpp
void test() {
    // 占位符
    using namespace std::placeholders;
    auto f3 = bind(add, 3, _1); // 函数参数的绑定并不固定,并不一定要全部给出
    cout << "f3(10) = " << f3(10) << endl;
}

那么占位符整体代表什么含义、占位符中的数字代表什么含义呢?可以使用下面例子进行推导:

cpp
void func(int x1, int x2, int x3, const int &x4, int x5) {
    cout << "x1 = " << x1 << endl
         << "x2 = " << x2 << endl
         << "x3 = " << x3 << endl
         << "x4 = " << x4 << endl
         << "x5 = " << x5 << endl;
}

void test3() {
    using namespace std::placeholders; // 占位符作用域
    int number = 100;
    auto f = bind(func, 2, _3, _2, std::cref(number), number);
    number = 300;
    f(20, 30, 400, 50000, 5678); // 对于没有作用的实参是无效的参数
}
  • 占位符整体代表的是形参的位置。也就是func函数中的x2被占位符_3 替代,x3被占位符_2 替代。
  • 占位符中的数字代表的是实参的位置,比如:x2是实际传递的第三个值400,因为占位符中的数字是3,x3是实际传递的第二个值30,因为占位符中的数字是2。
  • bind默认采用的是值传递,而不是引用传递,即使func的第四个参数使用的是引用
  • 可以使用std::ref或者std::cref这两个引用包装器,传递引用。
  • 占位符的作用域是std::placeholders,也就是说占位符的作用域是std::placeholders命名空间。

bind的返回类型

cpp
int add(int x, int y) {
    return x + y;
}
auto f = bind(add, 100, _1);
cout << "f(200) = " << f(200) << endl;

以上述代码为例,bind绑定的函数是add,该函数的返回类型是int,并且有两个参数,所以我们就说add函数也是有类型的,可以通过函数的返回类型与函数的参数列表共同决定,也即是函数也有类型,可以使用int(int, int)表示add的函数类型(或者称为函数的标签)。使用bind将add的第一个参数固定为了100,相当于给add传递了一个参数,那么add的函数参数就只剩下一个int,所以bind的返回结果应该是int(int),正因为如此,在后面接受的时候f需要传递一个参数200。那么能不能直接将auto改为int(int)吗?尝试之后步行。

函数的容器function

cpp
#include <functional>

template <class>
class function;

template <class R, class... Args>
class function<R(Args...)> // R就是返回类型,Args是参数

可以看到function的模板参数,R(Args...),这个写法中的R不正好是函数的返回类型,Args正好是函数的参数列表,所以我们就可以用function接受bind的返回类型。

cpp
function<int(int)> f = bind(add, 100, _1);
cout << "f(200) = " << f(200) << endl;

这样以后就可以明确的写出bind的返回类型的问题了。

bind绑定到数据成员

cpp
class Example {
public:
    int add(int x, int y) // 成员函数形式
    {
        cout << "int Example::add(int, int)" << endl;
        return x + y;
    }
    int data = 100; // C++11中初始化数据成员的新方式
};

将公有的数据成员data看成是返回类型是int,参数是无参的函数,然后函数名字就是data。

cpp
Example ex;
function<int()> f = bind(&Example::data, &ex);
cout << "f() = " << f() << endl; // 打印的结果就是100

bind绑定成员函数的传参

cpp
Example ex;
function<int()> f = bind(&Example::add, &ex, 1, 2);
cout << "f() = " << f() << endl;

function<int()> f2 = bind(&Example::add, ex, 1, 2);
cout << "f2() = " << f2() << endl;

上述既可以传递对象地址也可以传递对象,区别是:对象地址的传递就是一个指针的传递,不会出现拷贝操作,但是使用对象传递,会存在拷贝对象操作,对象如果占用内存较大,会浪费空间;第二就是,使用对象地址,如果在使用的时候,对象已经销毁了,就有空指针的问题,但是拷贝一份对象,那原对象销毁了,这里采用的是拷贝操作,就不会有影响。

基于对象的写法

std::bind与std::function的结合使用,是一种非常非常非常强大的用法,因为bind具备改变函数形态的功能,只要函数的返回类型相同,任何参数类型的函数都可以被bind绑定之后,变成函数类型完全一致的函数类型,然后都可以被function进行接收。例如:再来看看std::function与std::bind结合使用体现出多态性的例子,也就是注册回调函数与执行回调函数。

cpp
class Figure {
public:
    using DisplayCallback = function<void()>;
    using AreaCallback = function<double()>;
    DisplayCallback _displayCallback;
    AreaCallback _areaCallback;
    // 注册回调函数
    void setDisplayCallback(DisplayCallback &&cb) // 思考:此处的cb到底是左值还是
        右值? {
        _displayCallback = std::move(cb);
    }

    void setAreaCallback(AreaCallback &&cb) {
        _areaCallback = std::move(cb);
    }
    // 执行回调函数
    void handleDispalyCallback() const {
        if (_displayCallback) {
            _displayCallback();
        }
    }
    double handleAreaCallback() const {
        if (_areaCallback) {
            return _areaCallback();
        } else {
            return 0;
        }
    }
};

// 执行回调函数
void test(const Figure &fig) // 这里使用const对象,所以处理函数必须定义为const版本
{
    fig.handleDispalyCallback();
    cout << "'s area is : " << fig.handleAreaCallback() << endl;
}

class Rectangle {
public:
    Rectangle(double length, double width)
        : _length(length), _width(width) {
    }
    void display(int ix) const // 相比之前,这里display函数可以传参
    {
        cout << "Rectangle ";
    }
    double area() const {
        return _length * _width;
    }

private:
    double _length;
    double _width;
};

class Circle {
public:
    Circle(double radis)
        : _radis(radis) {
    }
    void show() const {
        cout << "Circle ";
    }
    double getArea() const {
        return _radis * _radis * 3.1415;
    }

private:
    double _radis;
};

class Traingle {
public:
    Traingle(double a, double b, double c)
        : _a(a), _b(b), _c(c) {
    }
    void print() const {
        cout << "Traingle ";
    }
    // 海伦公式
    double calcArea() const {
        double tmp = (_a + _b + _c) / 2;
        return sqrt(tmp * (tmp - _a) * (tmp - _b) * (tmp - _c));
    }

private:
    double _a;
    double _b;
    double _c;
};

void test() {
    Rectangle rectangle(10, 20);
    Circle circle(10);
    Traingle traingle(3, 4, 5);
    Figure figure;
    figure.setDisplayCallback(bind(&Rectangle::display, &rectangle, 10));
    figure.setAreaCallback(bind(&Rectangle::area, &rectangle));
    test(figure);
    figure.setDisplayCallback(bind(&Circle::show, &circle));
    figure.setAreaCallback(bind(&Circle::getArea, &circle));
    test(figure);
    figure.setDisplayCallback(bind(&Traingle::print, &traingle));
    figure.setAreaCallback(bind(&Traingle::calcArea, &traingle));
    test(figure);
}

成员函数绑定器

cpp
#include <functional>

template <class M, class T>
/*unspecified*/ mem_fn(M T::*pm);

template <class M, class T>
/*unspecified*/ mem_fn(M T::*pm) noexcept;

因为成员函数与算法库中的算法不能直接很好的适配,所以二者结合使用的时候,需要使用成员函数适配器进行适配。例如:

cpp
class Number {
public:
    Number(size_t data = 0)
        : _data(data) {
    }
    void print() const {
        cout << _data << " ";
    }
    // 判断是不是偶数
    bool isEven() const {
        return (0 == _data % 2);
    }
    // 判断是不是质数
    bool isPrime() const {
        if (1 == _data) {
            return false;
        }
        // 质数/素数
        for (size_t idx = 2; idx <= _data / 2; ++idx) {
            if (0 == _data % idx) {
                return false;
            }
        }
        return true;
    }

private:
    size_t _data;
};

void test() {
    vector<Number> numbers;
    for (size_t idx = 1; idx != 10; ++idx) {
        numbers.push_back(Number(idx));
    }
    // for_each与成员函数print并不能很好的适配,需要使用mem_fn进行适配
    for_each(numbers.begin(), numbers.end(), mem_fn(&Number::print));
    // 删除所有的偶数
    numbers.erase(remove_if(numbers.begin(), numbers.end(),
                            mem_fn(&Number::isEven)),
                  numbers.end());
    for_each(numbers.begin(), numbers.end(), mem_fn(&Number::print));
    // 删除所有的质数
    numbers.erase(remove_if(numbers.begin(), numbers.end(),
                            mem_fn(&Number::isPrime)),
                  numbers.end());
    for_each(numbers.begin(), numbers.end(), mem_fn(&Number::print));
}

思考题:上述的men_fn的功能就是让成员函数与算法进行适配,那么大家可以想象一下,此处的mem_fn能否用之前所学的知识点进行替换呢?

遍历算法

cpp
/*
    遍历算法 遍历容器元素
    @param beg 开始迭代器
    @param end 结束迭代器
    @param _callback  函数回调或者函数对象
    @return 函数对象
*/
for_each(iterator beg, iterator end, _callback);


/*
    transform算法 将指定容器区间元素搬运到另一容器中
    注意 : transform 不会给目标容器分配内存,所以需要我们提前分配好内存
    @param beg1 源容器开始迭代器
    @param end1 源容器结束迭代器
    @param beg2 目标容器开始迭代器
    @param _cakkback 回调函数或者函数对象
    @return 返回目标容器迭代器
*/
transform(iterator beg1, iterator end1, iterator beg2, _callbakc)

for_each是非修改式算法,transform是修改式算法。

for_each使用示例
cpp
/*

template<class _InIt,class _Fn1> inline
void for_each(_InIt _First, _InIt _Last, _Fn1 _Func)
{
    for (; _First != _Last; ++_First)
        _Func(*_First);
}

*/

//普通函数
void print01(int val){
    cout << val << " ";
}
//函数对象
struct print001{
    void operator()(int val){
        cout << val << " ";
    }
};

//for_each算法基本用法
void test01(){
    
    vector<int> v;
    for (int i = 0; i < 10;i++){
        v.push_back(i);
    }

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

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

}

struct print02{
    print02(){
        mCount = 0;
    }
    void operator()(int val){
        cout << val << " ";
        mCount++;
    }
    int mCount;
};

//for_each返回值
void test02(){

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

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

struct print03 : public binary_function<int, int, void>{
    void operator()(int val,int bindParam) const{
        cout << val + bindParam << " ";
    }
};

//for_each绑定参数输出
void test03(){
    
    vector<int> v;
    for (int i = 0; i < 10; i++){
        v.push_back(i);
    }

    for_each(v.begin(), v.end(), bind2nd(print03(),100));
}
transform使用示例
cpp
//transform 将一个容器中的值搬运到另一个容器中
/*
    template<class _InIt, class _OutIt, class _Fn1> inline 
    _OutIt _Transform(_InIt _First, _InIt _Last,_OutIt _Dest, _Fn1 _Func)
    {   

        for (; _First != _Last; ++_First, ++_Dest)
            *_Dest = _Func(*_First);
        return (_Dest);
    }

    template<class _InIt1,class _InIt2,class _OutIt,class _Fn2> inline
    _OutIt _Transform(_InIt1 _First1, _InIt1 _Last1,_InIt2 _First2, _OutIt _Dest, _Fn2 _Func)
    {   
        for (; _First1 != _Last1; ++_First1, ++_First2, ++_Dest)
            *_Dest = _Func(*_First1, *_First2);
        return (_Dest);
    }
*/

struct transformTest01{
    int operator()(int val){
        return val + 100;
    }
};
struct print01{
    void operator()(int val){
        cout << val << " ";
    }
};
void test01(){

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

    //目标容器
    vector<int> vTarget;
    //给vTarget开辟空间
    vTarget.resize(vSource.size());
    //将vSource中的元素搬运到vTarget
    vector<int>::iterator it = transform(vSource.begin(), vSource.end(), vTarget.begin(), transformTest01());
    //打印
    for_each(vTarget.begin(), vTarget.end(), print01()); cout << endl;
    
}

//将容器1和容器2中的元素相加放入到第三个容器中
struct transformTest02{
    int operator()(int v1,int v2){
        return v1 + v2;
    }
};
void test02(){

    vector<int> vSource1;
    vector<int> vSource2;
    for (int i = 0; i < 10; i++){
        vSource1.push_back(i + 1);  
    }

    //目标容器
    vector<int> vTarget;
    //给vTarget开辟空间
    vTarget.resize(vSource1.size());
    transform(vSource1.begin(), vSource1.end(), vSource2.begin(),vTarget.begin(), transformTest02());
    //打印
    for_each(vTarget.begin(), vTarget.end(), print01()); cout << endl;
}

查找算法

cpp
/*
    find算法 查找元素
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    @param value 查找的元素
    @return 返回查找元素的位置
*/
find(iterator beg, iterator end, value)
/*
    find_if算法 条件查找
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    @param  callback 回调函数或者谓词(返回bool类型的函数对象)
    @return bool 查找返回true 否则false
*/
find_if(iterator beg, iterator end, _callback);

/*
    adjacent_find算法 查找相邻重复元素
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    @param  _callback 回调函数或者谓词(返回bool类型的函数对象)
    @return 返回相邻元素的第一个位置的迭代器
*/
adjacent_find(iterator beg, iterator end, _callback);
/*
    binary_search算法 二分查找法
    注意: 在无序序列中不可用
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    @param value 查找的元素
    @return bool 查找返回true 否则false
*/
bool binary_search(iterator beg, iterator end, value);
/*
    count算法 统计元素出现次数
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    @param  value回调函数或者谓词(返回bool类型的函数对象)
    @return int返回元素个数
*/
count(iterator beg, iterator end, value);
/*
count_if算法 统计元素出现次数
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    @param  callback 回调函数或者谓词(返回bool类型的函数对象)
    @return int返回元素个数
*/
count_if(iterator beg, iterator end, _callback);

排序算法

cpp
/*
    merge算法 容器元素合并,并存储到另一容器中
    注意:两个容器必须是有序的
    @param beg1 容器1开始迭代器
    @param end1 容器1结束迭代器
    @param beg2 容器2开始迭代器
    @param end2 容器2结束迭代器
    @param dest  目标容器开始迭代器
*/
merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)
/*
    sort算法 容器元素排序
    @param beg 容器1开始迭代器
    @param end 容器1结束迭代器
    @param _callback 回调函数或者谓词(返回bool类型的函数对象)
*/
sort(iterator beg, iterator end, _callback)
/*
    random_shuffle算法 对指定范围内的元素随机调整次序
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
*/
random_shuffle(iterator beg, iterator end)
/*
    reverse算法 反转指定范围的元素
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
*/
reverse(iterator beg, iterator end)

拷贝和替换算法

cpp
/*
    copy算法 将容器内指定范围的元素拷贝到另一容器中
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    @param dest 目标起始迭代器
*/
copy(iterator beg, iterator end, iterator dest)
/*
    replace算法 将容器内指定范围的旧元素修改为新元素
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    @param oldvalue 旧元素
    @param oldvalue 新元素
*/
replace(iterator beg, iterator end, oldvalue, newvalue)
/*
    replace_if算法 将容器内指定范围满足条件的元素替换为新元素
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    @param callback函数回调或者谓词(返回Bool类型的函数对象)
    @param oldvalue 新元素
*/
replace_if(iterator beg, iterator end, _callback, newvalue)
/*
    swap算法 互换两个容器的元素
    @param c1容器1
    @param c2容器2
*/
swap(container c1, container c2)

算数生成算法

cpp
/*
    accumulate算法 计算容器元素累计总和
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    @param value累加值
*/
accumulate(iterator beg, iterator end, value)
/*
    fill算法 向容器中添加元素
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    @param value t填充元素
*/
fill(iterator beg, iterator end, value)

集合算法

cpp
/*
    set_intersection算法 求两个set集合的交集
    注意:两个集合必须是有序序列
    @param beg1 容器1开始迭代器
    @param end1 容器1结束迭代器
    @param beg2 容器2开始迭代器
    @param end2 容器2结束迭代器
    @param dest  目标容器开始迭代器
    @return 目标容器的最后一个元素的迭代器地址
*/
set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)
/*
    set_union算法 求两个set集合的并集
    注意:两个集合必须是有序序列
    @param beg1 容器1开始迭代器
    @param end1 容器1结束迭代器
    @param beg2 容器2开始迭代器
    @param end2 容器2结束迭代器
    @param dest  目标容器开始迭代器
    @return 目标容器的最后一个元素的迭代器地址
*/
set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)
/*
    set_difference算法 求两个set集合的差集
    注意:两个集合必须是有序序列
    @param beg1 容器1开始迭代器
    @param end1 容器1结束迭代器
    @param beg2 容器2开始迭代器
    @param end2 容器2结束迭代器
    @param dest  目标容器开始迭代器
    @return 目标容器的最后一个元素的迭代器地址
*/
set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)

参考资料