算法库

分类

非修改式的算法：count,find,for_each

修改式的算法：copy,replace,remove,remove_if

排序操作；sort

二分查找：lower_bound,upper_bound

集合操作：set_intersection

堆相关的操作：make_heap,push_heap

取最值：max,min

数值操作：accmulate（累加）

未初始化的内存操作：uninialized_copy

for_each算法

一元函数：函数的参数是一个

二元函数：函数的参数是两个

一元谓词/断言：函数的参数是一个，并且函数的返回类型是bool

二元谓词/断言：函数的参数是两个，并且函数的返回类型是bool

void func(value){
    cout << value << " ";
}

vector<int> vec = {1,2,3,4};
for_each(vec.begin(),vec.end(),func);

可以把函数实现放在括号里

1
2
3

for_each(vec.begin(),vec.end(),[](int &value)->void{
    cout << value <<" ";
});

lambda表达式—》匿名表达式由三部分组成

[]()->void{}
//() 表示函数体
//->void 表示返回类型 可以省略 省略就是自动推导
//[]表示捕获列表 用来捕获啥？
//{}函数体
int a = 10;
//能否在函数体力访问a呢 ，这个a定义出来，在作用域内都是可以访问得
[]()->void{
    cout << a << endl//error a不能访问
};
//想要用这个a 用[]捕获一下
[a](int value)->void{
    cout << a << endl;//可以用了
};
//这只是定义 要调用在后面加一个（）
[a](int value)->void{
    cout << a << endl;
    cout << value << endl;
}(200);

//可以修改value吗
[a](int value)->void{
    value++;//successful
    cout << a << endl;
    cout << value << endl;
}(200);
//可以修改a吗
[a](int value)->void{
    a++;//error a具有只读属性
    value++;//successful
    cout << a << endl;
    cout << value << endl;
}(200);
//如果要修改a怎么做？ 可以捕获得时候用&的形式
//函数中修改完，a本身也会被修改，因为用的引用的形式
[&a](int value)->void{
    a++;//successful  
    value++;//successful
    cout << a << endl;//11
    cout << value << endl;
}(200);
cout << a << endl;//11
//修改a的方法二  在参数列表后面加一个mutable表示去掉默认的const属性，是可修改的函数,a是值传递，是一个副本，这里修改的是副本，所以函数结束后，a本身的值不会变
[a](int value)mutable->void{
    a++;//successful
    value++;//successful
    cout << a << endl;
    cout << value << endl;//11
}(200);
cout << a << endl;//10

lambda表达式调用

//方式一  直接加一个（）
[a](int value)->void{
    cout << a << endl;
    cout << value << endl;
}(200);
//方式二 可以见这个函数赋值给一个变量
auto f = [a](int value)->void{
    cout << a << endl;
    cout << value << endl;
};//这是函数定义与f初始化
f(100);//这里是函数调用

捕获列表

void test(){
    int num = 10;
    int age = 60;
    string name("wd");
    
    auto f =[num,&age](int value){
        cout << value << endl;
        cout << num << endl;
        age += 10;
        cout << age << endl;
    };
    
    f(22);
    //需求 想要把Num age都+=10，对于名字只想打印
    auto f2 =[&num,&age，name](int value){
        num += 10;
        age += 10;
        cout << value << endl;
        cout << num << endl;
        cout << age << endl;
        cout << name << endl;
    };
    
    f2(200);
    //有别的写法实现这个需求吗，如果[]里面的参数非常多呢？
    //这表示name做值传递，其他的都做引用传递
    auto f3 =[&，name](int value){
        num += 10;
        age += 10;
        cout << value << endl;
        cout << num << endl;
        cout << age << endl;
        cout << name << endl;
    };
    
    f3(200);
    //如果少数想用引用传递，大多数用值传递呢
     auto f4 =[=&age](int value){
        num += 10;//error 其他的所有变量都作为值传递了
        age += 10;
        cout << value << endl;
        cout << num << endl;
        cout << age << endl;
        cout << name << endl;
    };
    
    f4(200);
    
}

全局变量

int Gnum = 110;
void test(){
    int num = 10;
    int age = 60;
    auto f3 =[&num,age](int value){
        num += 10;
        age += 10;
        cout << value << endl;
        cout << num << endl;
        cout << age << endl;
        cout << name << endl;
        cout << Gnum << endl;//发现可以直接使用
    };
}

捕获列表捕获的是局部变量，对于全局变量无序捕获可以直接使用

类数据成员

class Ex{
    void test{
        auto x = []{return _num};//error
        auto x2 = [this]{return _num};//并且可以修改
        auto x3 = [this]{return _num++l};
    }
    int _num;
}

lambda的本质

class Example{
    void operator()(int value) const{
        
    }
    //捕获列表相当于数据成员
    int &num;//这是引用传递
    int age;//这是值传递
};

lambda的返回值的接收

#include <functional>

function<void(int)> f =[num,&age](int value){
        cout << value << endl;
        cout << num << endl;
        age += 10;
        cout << age << endl;
    };

function<void(const string &,int)> f2 = [](const string &name,int value){
		cout << "name=" << name << endl;
    	cout << "value=" <<value << endl;
};

//调用
f2("ads",100);

remove_if

#include <algorithm>

bool void func(int value){
    return value > 3;
}

void tese(){
    vector<int> vec = {1,2,3,4,5};
    for_each(vec.begin(),vec.end(),[](int &value){ cout << value <<" ";});
    auto it = remove_if(vec.begin(),vec.end(),func);
    //remove_if不能将真正满足条件的元素删除，但是会返回待删除元素的首迭代器，然后配合容器的erase操作，才能将真正的元素全部删除
    //std::move 将左值转为右值
    //作用，删除所有大于5的元素
    vec.erase(it,vec.end());
    
     for_each(vec.begin(),vec.end(),[](int &value){ cout << value <<" ";});
    //在遍历一次， 发现大于3的元素被删掉了
}

remove_if的通用性更强，这也是为什么底层遍历找到符合条件的元素直接删除，而是把不符合条件的元素往前移，然后返回的迭代器指向的就是所有不符合条件的元素的那部分的迭代器，配合erase就可以删除

并且也是可以用lambda表达式的

auto it = remove_if(vec.begin(),vec.end(),[](int value)->bool{ return value > 5;});
//如果func是一个二元断言呢，那么表明他会有两个参数
//如果有一个语法手段，可以绑定二元断言的第一个参数，也就将二元断言的第一个参数进行固定，例如在这里就是returnValue  Func(Args1,Agrs2) 在这里Args1=3，Args2是[vec.begin(),vec.end()] 也就是表明func函数中Args1 < Args2 也就是return 5 < Args2 就表明Func可以是std::less 


//如果有一个语法可以绑定二元断言的第二个参数即Args2 = 5 Args1是[vec.begin(),vec.end()] 也就是表明func函数中Args1 > Args2就表明Func是std::greater

bind1st和bind2nd

bind1st可以绑定二元函数对象，将二元函数对象的第一个参数固定为x，bind2nd可以绑定二元函数对象，将二元函数对象的第二个参数固定为x

bind1st(less,3);
//就相当于
bool operator()(lhs = 5, rhs){
    return 3 < rhs;
}

bind2nd(greater,3);
//就相当于
bool operator()(lhs,rhs=5){
    return rhs < 3;
}

//所以上面的remove_if还可以写为
auto it = remove_if(vec.begin(),vec.end(),bind1st(less<int>(),3));

//同理也可以写为
auto it = remove_if(vec.begin(),vec.end(),bind2nd(greater<int>(),3));

==bind(重要)==

如何绑定参数的

int add(int x, int y){
    return x + y;
}

void test(){
    auto f = bind(add,1,2);//绑定两个参数 ，返回值用f接收
    cout << "f()" << f() << endl;//光写一个f不行，f实际上也是一个函数，所以加括号表示调用
}

int mutiply(int x, int y, int z){
    return x*y*z;
}
void test(){
    auto f2 = bind(mutiply,1,2,3);
    cout <<"f2()" << f2()<< endl;//也可以绑定三元函数
}

bind进行绑定的时候，绑定的是函数的地址

1	bind(&mutiply,1,2,3);//也是可以的

因为函数名就是函数地址，所以写函数名其实也是传的也是函数的入口地址，而且bind参数绑定的都是右值

引用折叠

& && = &;//如果模板推导出来的是左值引用，那么加上bind参数本来就有了&& 就变成三个&了，这个就是左值引用
&& && = &&;//同理如果推导出来是右值引用， 那么最终也是右值引用
& & = &;
&& & = &;//总结 只要跟左值引用结合 结果一定是左值引用，如果右值引用跟右值引用结合才是右值引用
//例子
template <class F>
void func(F && f){}//F可能推导出来&或者&&
template <class F>
void func(F & f){}//F可能推导出来&或者&&

bind绑定成员函数

class Example{
public:
	int add(int x, int y){
        return x+y;
    }    
};
int test(){
    auto f3 = bind(&Example::add,100,200);
    cout <<"f3()" << f3()<< endl;//error 
    //因为类的成员函数前面还有一个this指针
    //所以还需要传一个对象进去
    Example ex;
    auto f4 = bind(&Example::add,&ex,100,200);
    cout <<"f4()" << f4()<< endl;
}

如果绑定静态成员函数呢

class Example{
public:
	static int add(int x, int y){
        return x+y;
    }    
}
int test(){
    auto f4 = bind(&Example::add,100,200);//不需要绑定this了，因为静态成员函数没有this指针
    cout <<"f4()" << f4()<< endl;
}

bind可以绑定一部分参数，另一部分参数不绑定吗

1 2	auto f4 = bind(add,100);//不绑定y 在调用的时候再绑定但是error ,不绑定的这个至少要用个占位符占一下位置 cout << "f4(300)" << f4(300) << endl;

1
2
3

using namespace std::placeholders;
auto f4 = bind(add,100,_1);// _1表示占位符
cout <<"f4(300)" << f4(300) << endl;

==占位符==

1
2
3

using namespace std::placeholders;
auto f4 = bind(add,100,_2);// _2表示占位符
cout <<"f4(300)" << f4(300,50,60) << endl;//发现用的是第二个参数

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 test(){
    int number = 500;
    using namespace std::placeholders;
    //占位符整体代表的是函数形参的位置，
    //占位符中的数字代表的参数里表中实参的位置
    //占位符的数字一定要小于等于参数列表中的个数
    //不同占位符的数字可以是一样的
    bind(func,100,_3,_1,number,number);
    number = 3000;//发现这里更改没有更在func里面的值，说明bind默认采用的是值传递
    //如果想使用引用传递，可以使用引用的包装器std::cref/std::ref
    //std::cref = const reference
    //ref = reference
    f(1,20,300,400,5000);//多余的参数直接扔掉，没有任何用处，
    //打印 100 ，300，1，500，500
        
}

引用的包装器

1	bind(func3,100,_3,_1,std::cref(number),number);

bind函数的返回值是什么类型？

auto f2 = bind(mutiply,1,2,3);//返回类型 int(int int int)如何判断见下面注释
//bind绑定了三个 所以函数类型变成了 int返回类型无参的函数类型
function<int()> f2 = bind(mutiply,1,2,3);
function<int(int)> f4 = bind(add,100,_1);
//bind绑定了一个参数 还有一个参数 所以要写
function<int()> f5 = bind(add,1,2);
//这里f2可以直接替代f5,写成
f2 = bind(add,1,2);

因为function可以存放函数类型，将其称为函数的容器

bind绑定数据成员(了解)

class Example{
public:
	static int add(int x, int y){
        return x+y;
    }    
	int data = 100;//将data看成是返回类型是int 参数是Example*的函数，然后通过bind绑定参数改变函数形态，最终用function接受
}
void test(){
    Examble ex;
    function<int()> f = bind(&Examble::data,&ex);
    cout << "f5()=" << f5() << endl;
}

由于形式与函数指针很类似两者之间有什么区别？

int func(){
    return 10;
}

int func2(){
    return 20;
}

void test(){
    //函数指针
    typedef int(*pFunc)();//c++98给函数指针取别名
    //上面这个写法可以改写为
    using pFunc = int(*)();//c++11中给函数指针取别名
    
    pFunc f1 = func();//注册回调函数
    //auto f4 = bind(&Example::add,100,200);很相似，所以就可以猜一下 是不是auto这个类型是pFunc类型
    //函数的类型（函数的标签）：函数的返回类型与函数的参数列表（函数的参数的个数，参数的类型，参数的顺序）
    //可以推断出 例如add函数的类型是 int(int int)
    //再例如Example中的add函数的函数类型：int(Example *, int ,int)
    cout << "f1()" << f1() << endl;//执行回调函数  这个函数是先注册后执行，这是延迟调用的思想
    f2 = func2();
    cout << "f2()" << f2() << endl;
}

延迟调用函数的应用

虚函数，如果派生类中把虚函数重写了，再调用的时候才会调用派生类里的该函数，也就是把编译的时候能够确定的事件延迟到运行时才能确定–c++的多态

==如何用c语言实现多态？==

使用结构体配合函数指针

函数指针的局限性

int fun3(int x){
    return x;
}

void test(){
    typedef int(*pFunc)();
    pFunc f = func3;//error 函数指针f的类型与func3的类型是不匹配的
}

包括了函数指针的定义、函数指针的延迟调用思想、函数指针可以注册回调函数与执行回调函数，函数指针只能执行某些类型的函数，不能随便指向其他类型的函数

vector中的push_back导致迭代器失效

//读的时候写会发生什么
vector<int> vec={1};
bool flag = true;
for(auto it =vec.begin(); it != vec.end(); ++it){
    cout << *it << " ";
    if(flag){
        //在执行push_back底层已经发生了扩容的操作，it指向的还是老的空间，但是vec.end()指向的是新的空间的尾部，这样还在使用老的空间的迭代器it就会失效
        vec.push_back(20);
        falg = false;
    }
}
//执行过程中发生了扩容，导致it还是指向的旧迭代器，而vec.end()已经是新迭代器的末尾了

解决，重置迭代器

vector<int> vec={1};
bool flag = true;
for(auto it =vec.begin(); it != vec.end(); ++it){
    cout << *it << " ";
    if(flag){
        vec.push_back(20);
        falg = false;
        it = vec.begin();
    }
}

或者，把就迭代器的vec.end()用一个变量保存一下，这样即使扩容，那么也不会出问题

晚上练习

第一题

Q:算法库中有哪些类型的操作？什么是函数对象？

A:算法库的分类：

非修改式的算法：count, find, for_each

修改式的算法：copy ,replace,remove,remove_if

排序操作:sort

二分查找：lower_bound, upper_bound

集合操作：set_intersection

堆相关的操作：make_heap,push_heap

取最值：max min

数值操作： accmulate

未初始化的内存操作：uninialized_copy

函数对象：

函数对象就是例如像类的实例，可以像函数一样被调用，具体是在该类中重载了（）运算符，也就是有一个operator()()函数，然后使用函数对象的时候就可以像一个函数一样的调用它了

第二题

Q:容器、迭代器、算法之间的关系是怎样的？他们是如何结合在一起的？

A:我认为容器是基础，迭代器是工具，算法可以利用迭代器来对容器进行一些需要的操作，三者通过协同工作来提供强大的数据操作能力

三者的结合方式：

容器提供迭代器，每个容器都提供一种或多种迭代器，用于访问其元素.

算法使用迭代器：算法一般通过迭代器来操作数据，算法函数通常接收一对迭代器作为参数，定义了操作的范围

迭代器提供统一的接口：迭代器提供了统一的接口，使得算法可以独立于容器进行设计和实现，这样算法可以应用于任何支持相应迭代器类型的容器

第三题

Q:什么是迭代器失效问题？该问题是如何产生的？怎样避免产生迭代器失效问题?

A:迭代器失效是指容器已经发生扩容或者其他情况，使得存储空间不再这片空间了，然后迭代器仍然指向的是旧空间，则该迭代器就已经失效了

一般情况的下是容器发生扩容，然后操作系统开辟了一片的新的空间，则原来这片空间就已经失效了，但是指向旧空间的迭代器并不知道该空间已经失效，然后就产生了迭代器失效的问题

每次使用迭代器之前就更新一下迭代器，例如 it = vec.begin();

第四题

Q:什么是回调函数，注册回调函数，执行回调函数？

A:回调函数是一个函数，它作为参数传递给另一个函数，在该函数执行过程中或者执行结束后被调用

注册回调函数是指将一个函数指针传递给另一个函数，以便在适当的时候调用它，这通常涉及保存函数指针，以便以后可以调用它

执行回调函数是指在适当的时候，通过调用保存的函数指针来执行回调函数的过程

第五题

Q:Leetcode 20题

https://leetcode-cn.com/problems/valid-parentheses/

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = “()”
输出：true
示例 2：

输入：s = “()[]{}”
输出：true
示例 3：

输入：s = “(]”
输出：false

提示：

1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for(int i = 0; i < s.size(); ++i){
            if(s[i] == '(' || s[i] == '[' || s[i] == '{'){
                st.push(s[i]);
            }
            else{
                if(st.empty()) return false;
                char ch = st.top();
                st.pop();
                if(ch == '(' && s[i] != ')') return false;
                else if(ch == '[' && s[i] != ']') return false;
                else if(ch == '{' && s[i] != '}') return false;
            }
        }
        if(!st.empty()) return false;
        return true;
    }
};