10-泛型算法

今天药忘吃喽~ 2022-06-08 10:54 200阅读 0赞

#### 泛型算法 ####

*  泛型算法:表示的是可以用于不同类型的元素和多种容器类型的一些经典算法的公共接口,算法的头文件包含在`algorithm`以及`numeric`里面;
 *  通常来说,这些算法并不直接作用于容器,而是使用两个迭代器指定一个元素的范围来进行操作;
 *  `find(a.begin(),a.end(),val)`:前两个参数分别表示迭代器,后面的参数表示的是查找的关键字;
 *  迭代器算法并不依赖于容器的类型,但是算法依赖于元素类型的操作;
 *  泛型算法本身不会执行容器的操作,他们只会运行与迭代器之上;
 *  泛型算法不会改变底层容器的大小,算法可能改变,移动,但是不能够添加或者添加删除元素;
 *  常用的泛型算法:
    
     *  只读算法
        
         *  `accumulate(v.cbegin(),vec.cend(),0)`:第三个参数表示的是初始值为０，然后按照迭代器的范围进行求和;
         *  需要注意的第三个参数:序列中元素的类型必须与第三个参数类型进行匹配,或者能够转换为第三个参数的类型;  
            例如:`string sum = accumulate(v.cbegin(),v.end(),string(""))`,也就是说对于`string`类型也是能够进行转换的;
         *  `equal`:用于确定两个序列是否保存相同的值.如果元素都相等,返回`true`,否则返回值就是`false`;
         *  对于那些只接受一个单一迭代器来表示第二个序列的算法,都假定第二个序列与第一个序列一样长;
         *  写容器的算法:  
            
            
             *  算法不能够改变容器的大小,所以在执行写操作时,需要保证容器的空间足够;
             *  `fill(vec.begin(),vec.end(),0)`:用于将容器里面的所有值置为0;
             *  这些算法并不检查写操作,`fill_n(deat,n,val)`;
             *  当需要向目的位置迭代器写入数据的算法,必须保证目的的位置足够大,能够容纳所有的元素;
         *  插入迭代器:  
            
            
             *  插入迭代器可以用于保证有足够的元素空间来容纳输出数据的方法,`back_inseter` 定义在`iterator`头文件里面;
             *  `back_inserter`接受一个指向容器的引用,返回一个与该容器绑定的插入迭代器;
         *  拷贝算法:  
            
            
             *  拷贝算法是另一个向目的位置迭代器指向的输出序列中的元素写入数据的算法,这个算法接受三个迭代器,前两个表示一个输入范围,第三个表示  
                目的序列的起始位置;
             *  常用的提供的拷贝算法通常不会将需要复制的内容放到当前序列的末尾,而通常是创建一个新的序列;
             *  重排容器的算法:  
                
                
                 *  `sort` :是一个用来进行排序的算法;
                 *  `unique`:表示的含义是用来消除某些重复值,但是重复值必须是连续的;
                 *  标准可算法对迭代器进行操作,而不是对容器进行曹组,所以算法并不能够直接添加或者删除某些元素;
         *  使用特定的操作:
            
             *  谓词:谓词是一个可以调用的表达式,返回值结果是能用做条件的值,谓词分为两类:
                
                 *  一元谓词:表示只能接收单一参数;
                 *  二元谓词:表示只有两个参数;
                 *  接受谓词参数的算法对输出序列中的元素调用谓词,因此,元素类型必须转换为谓词的参数类型;
                 *  举个例子来说,`sort`默认是接受二元谓词的,默认是使用`<`来比较元素的,  
                    `bool inShorter(const string& s1,const string &s2){ return s1.size() < s2.size()}; sort(word.begin(),words.end(),isShorter)`;
                 *  `stable_sort()`:算法表示的含义是具有相同长度的元素可以按照字典序排列;
             *  `lambda`表达式
                
                 *  可以想算法传递任何类型的可调用对象，对于一个对象或者一个表达式，如果可以对其使用调用运算符，就称其为可调用的;
                 *  常用的可调用对象包括:函数,函数指针,重载了函数调用运算符的类,以及`lambda`表达式;
                 *  一个`lambda`表达式表示一个可调用的代码单元,一个`lambda`包含一个返回类型,一个参数列表和一个函数体,但是`lambda`可以定义在  
                    函数内部,例如:`[capture list] (parameter list)->return type {function body}`,解释一下:`[capture list]`:是一个`lambda`所在  
                    函数中定义的局部变量的列表,通常为空;`return type`,`parameter list`,`function body`分别表示返回类型,参数列表和函数体,  
                    但是`lambda`必须使用尾置返回来制定返回类型;
                 *  `lambda`的调用表达式和函数的调用表达式相同,使用函数调用表达式式就可以;
                 *  如果忽略`lambda`的返回值类型,那么`lambda`可以自动根据函数体来推断返回类型;如果函数体只有`return`语句,那么可以是根据`return`  
                    语句来推断`lambda`函数的返回值类型;
                 *  如果函数体包含任何单一的`return`语句之外的内容,且未指定返回类型,那么默认的返回类型是`void`;
                 *  `lambda`的实参和形参类型必须相匹配,但是`lambda`不能够又默认的参数;
                 *  `lambda`调用的实参数目永远与形参数目相等;
                    
                        [] (const string &s1,const string &s2){
                            return s1.size() < s2.size();
                        }
                        stable_sort(words.begin(),word.end(),[](const string &a,const string &b){
                                return a.size() < b.size();
                                });
                 *  关于捕获列表:`lambda`表达式通过将局部变量包含在其捕获列表中来指出将会使用这些变量.
                    
                        [sz](const string &a){
                         return a.size() >=sz;
                        } 
                        //sz表示的是捕获列表,如果捕获列表为空,那么这个函数编译就会出错;
                 *  一个`lambda`表达式只有在其捕获列表中不活一个它所在函数中的局部变量,才能够在函数体中使用改变量;
                 *  `for_each`使用的一个例子
                    
                        for_each(wc,words.end(),[] (const string &s){
                                cout << s << " ";
                                });
                        cout << endl;
                 *  一个`lambda`可以直接使用定义在当前函数之外的名字;
                 *  捕获列表志勇于局部非`static`变量,`lambda`可以直接使用局部`static`变量和他所在函数之外声明的名字;
                 *  一个完整的程序:
                    
                        void biggies(vector<string> &words,vector<string>::size_type sz){
                            elimDups(words);
                            stable_sort(words.begin(),words.end(),[](const string &a,const string &b){
                                    return a.size() < b.size();
                                    });
                        }
                        auto wc = find_if(words.begin(),words.end(),[sz](const string &a){
                            return a.size() >= sz;
                                    });
                        auto count = words.end()-wc;
                        cout << count << " " << make_plural(count,"word","s") << " of length " << sz << " or longer" << endl;
                        
                        for_each(ec,words.end(),
                                [](const string &s){
                                cout << s << " ";
                                });
                        cout << endl;
                 *  `lambda`捕获列表:  
                    ![这里写图片描述][SouthEast]
                 *  `lambda`:当定义一个`lambda`表达式时,编译器会生成一个与`lambda`对应的新的类类型,也就是说当像一个函数传递一个`lambda`时,同时  
                    定义了一个新的类型和该类型的一个对象,传递的参数就是编译器生成的类类型的未命名对象;
                 *  默认情况下,从`lambda`生成的类包含一个对应该`lambda`所捕获的变量的数据成员,`lambda`的数据成员在`lambda`对象被创建时被初始化;
                 *  变量捕获的方式包括值和引用:  
                    
                    
                     *  当`lambda`采用值捕获的方式,值传递的方式前提是这个变量可以进行拷贝,这个变量在`lambda`创建时,救回被拷贝,而不是在调用时  
                        拷贝,被捕获变量的值在`lambda`创建时拷贝,因此执行的修改并不会影响到`lambda`内对应的值;
                     *  引用捕获:使用引用的方式捕获的变量和其他类型引用的行为类似,首先需要确保的是所引用的对象必须存在;
                     *  当以引用方式捕获一个变量时,必须保证`lambda`执行时,变量是存在的;
                     *  尽量避免使用指针或者引用捕获;
                     *  引用捕获:  
                        `auto wc = find_if(words.begin(),words.end(),[=](const string &s){ return s.size() >= sz; });`
                     *  上面`=`:表示的是采用值传递的方式,并且能够让编译器自动推导使用参数的类型;
                     *  上面`&`:表示的是使用引用的方式进行捕获,并且能够让编译器自动推导使用参数的类型;
                     *  混合使用隐式捕获的例子:  
                        `void biggies(vector<string> &words, vector<string>::size_type sz; ostream &os = cout,char c = ' '){ for_each(words.begin(),words.end(),[&,c](const string &s){ os << s << c; }); for_each(words.begin(),words.end(),[=,&os](const string &s){ os << s << c; }); }`
                     *  当混合使用隐式捕获和显式捕获,捕获列表中的第一个元素必须是一个`&`或者`=`,用于限定默认捕获方式为引用或者值;
                     *  当混合使用隐式和显式捕获时,隐式捕获和显式捕获必须使用不同的类型,否则会冲突;
                 *  可变`lambda`:
                    
                     *  默认的情况下,对于一个值被拷贝的变量,`lambda`都不会改变其值,如果我们希望改变一个被捕获的变量的值,就必须在参数列表首加上关键字`mutable`;
                        
                            void func(){
                                size_t v1 = 42;
                                auto f = [v1] () mutable {
                                           return ++v1};
                                v1 = 0;
                                auto j =f();
                            }
                     *  一个引用所捕获的变量是否可以修改依赖于引用所指向的是一个`const`类型还是一个非`const`类型;
                     *  用于指定`lambda`返回类型
                        
                         *  默认情况下,如果一个`lambda`体包含`return`之外的任何语句,则编译器嘉定次`lambda`返回类型是`void`;
                        
                            transform(vi.begin(),vi.end(),vi.begin(),[](int i){ return i < 0 ? -i : i;
                                    });
                        
                         *  函数`transform`接受三个迭代器和一个可调用对象,前两个迭代器表示输入序列,第三个迭代器表示目的位置,算法对于输入序列  
                            每个元素调用可调用对象,并将结果写到目的位置;如果需要执行返回值:
                            
                                transform(vi.begin(),vi.end(),vi.begin(),
                                        [](int i)-> int {
                                        if(i<0)
                                            return -i;
                                        else
                                            return i;
                                        });
                         *  在除了`return`之外的语句时,如果需要返回值类型,需要使用尾置类型,比如上面的:`[](int i)->int`,表示返回值的类型是`int`;
                     *  关于参数绑定
                        
                         *  标准库`bind`函数:定义在`functional`里面,`bind`更像是一个通用的函数适配器,接受一个可调用对象,生成一个新的可调用对象  
                            来适应原对象的参数列表,bind的一般形式:`auto newCallable = bind(callable,org_list)`,其中`newCallable`:本身表示一个可  
                            以调用的对象,`arg_list`:是一个逗号分隔的参数列表,对应给定的`callable`的参数,也就是说当我们在调用`newCallable`时,  
                            `newcallable`会调用`callable`并传递给它`arg_list`中的参数,`arg_list`里面的参数包含形如`_n`的名字,其中`n`是一个整数,  
                            \_1:表示`newCallable`中的第一个参数,\_2:表示里面的第二个参数;
                         *  例如:`auto check6 = bind(check_size,_1,6);`表示的含义是,`check_size`,接受两个参数,但是`check6`只接受一个参数,`_1`  
                            表示的含义还包括:`ckeck6`接受的参数表示的`check_size`的第一个参数;如果需要绑定第二个参数,就需要使用`_2`来进行绑定;
                         *  名字`_n`定义在一个名为`placeholders`的命名空间里面,这个命名空间又定义在`std`里面;
                         *  `auto g=bind(f,a,b_2,c,_1)`:函数`f`需要有5个参数,第三个和第五个分别和`g(_1,_2)`的第二个,第一个进行绑定;
                         *  有时对于有些绑定的参数需要使用引用进行传递,或者要绑定的参数类型无法进行绑定,比如`os`类型就无法进行绑定操作,所以需  
                            要使用`ref`函数;  
                            `for_each(words.begin(),words.end(),bind(print,ref(os),_1,' '));`
     *  关于迭代器
        
         *  插入迭代器(insert iterator):迭代器被绑定在一个容器上面,可以用来向容器里面查入元素;
            
             *  插入迭代器适配器包括三种类型:  
                
                
                 *  `back_inserter`:用于创建一个使用`push_back()`的迭代器,
                 *  `front_inserter`:用于创建一个使用`push_front`的迭代器,总是将元素插入当前队列的前面;
                 *  `inserter`:创建一个使用`insert`的迭代器,这个操作用于将元素插入制定迭代器所表示的元素之前;例如`it = c.insert(it,val);++it;`;
         *  流迭代器(stream iterator):被绑定在输入或者输出流上面,用来遍历所关联的流;
            
             *  在创建一个流迭代器时,必须指定流迭代器要读写对象的类型,需要注意的是`istream_iterator`被绑定到一个流时,标准库并不保证迭代器立即可以  
                从流里面读取数据,保证的是再进行迭代器解引用之前,迭代器的数据读取工作就已经完成了;
             *  使用流迭代器处理类类型:如果某个定义了`<<`以及`>>` 运算符的类型创建`istream_iterator`以及`ostream_iterator`对象,也就是自己定义的类型  
                也是可以使用流迭代器的;
         *  反向迭代器(reverse iterator):迭代器从后向前移动,基本上除了`forward_list`之外的标准库容器都有反向迭代器;
            
             *  对于反向迭代器来说,自加自减操作和正向迭代器是反过来的;基本上除了`forward_list`之外,所有的迭代器都支持反向迭代器;
             *  在使用反向迭代器时,有时会出现需要将最后的字符进行打印,但是由于是反向迭代器,输出的字符顺序也就是反向的,所以需要使用`reverse_iterator`的`base()`成员来完成转换;
            
                auto rcomma = find(line.crbegin(),line.crend(),',');
                cout << string(rcomma.base(),line.cend()) << endl;
            
             *  反向迭代器使用普通迭代器进行初始化时,或者普通迭代器使用反向迭代器进行赋值操作时,赋值的结果会出错;
         *  移动迭代器(move iterator):迭代器用于移动某些元素;
     *  泛型算法结构  
        
        
         *  五种类型的迭代器:  
            
            
             *  输入迭代器:只读,不写,单遍扫描,只能递增;
             *  输出迭代器:只写,不读,单遍扫描,只能递增;
             *  前向迭代器:可读写,单遍扫描,只能够递增;
             *  双向迭代器:可读写,多遍扫描,可以递增也可以递减;
             *  随机访问迭代器:可读写,多遍扫描,支持全部迭代器类型;
         *  对于像一个算法传递错误类别的迭代器,编译器不会给出任何警告或者提示;  
            
            
             *  输入迭代器需要支持:  
                
                
                 *  用于比较两个迭代器相等或者不想等`(`==和!=`)`;
                 *  用于推进迭代器前置和后置运算`(++)`;
                 *  用于读取元素的解引用运算符(\*),解引用运算符只会出现在赋值运算符的右侧;
                 *  箭头`(->)`运算符等价于(\*it).member,也就是解引用运算符,并且提取对象成员;
                 *  单向顺序访问,算法`find`和`acculumate`要求输入迭代器;
             *  输出迭代器:  
                
                
                 *  只写但是不读元素;
                 *  用于推进迭代器的前置和后置递增运算符(++);
                 *  解引用运算符`(*)`,指出现在赋值运算符的左侧(向一个已经解引用的输出迭代器赋值,就是将值写入它所指项的元素);
                 *  `copy`函数的第三个参数就是输出迭代器,`ostream_iterator`类型也是输出迭代器;
             *  前向迭代器:  
                
                
                 *  可以用于读或者写元素,这类迭代器只能够在序列中眼一个方向移动,前向迭代器支持所有输入和输出迭代器的操作,而且可以多次读或者写同一个元素.
                 *  常用的算法`replace`和`forward_list`要求前向迭代器;
             *  双向迭代器:  
                
                
                 *  可以正向反向读或者写迭代器里面的元素支持所有的前向迭代器的操作,还支持前置和后置递减操作`(--)`;
                 *  常用算法`reverse`要求双向迭代器;
             *  随机访问迭代器  
                
                
                 *  提供在常量时间访问序列里面任意元素的能力.此类迭代器支持双向迭代器的所有功能;
                 *  用于比较两个迭代器相对位置的关系运算符`(<,<=,>和>=)`;
                 *  迭代器和一个证书质的加减运算`(+,+=,-,-=)`,计算的结果是迭代器在序列中前进(或者后退)给定整数个元素后的位置;
                 *  两个迭代器上面的减法操作,得到两个迭代器的距离
                 *  下表运算符(iter\[n\])和`*(iter[n])`等价;
             *  常用算法的参数模式:  
                
                
                 *  `alg(beg,end,other args)`
                 *  `alg(beg,end,dest,other args)`
                 *  `alg(beg,end,beg2,other args)`
                 *  `alg(beg,end,beg2,end2,other args)`
                 *  向输出迭代器写入数据的算法都要求目标空间足够容纳写入的数据;
             *  算法的明明规范:  
                
                
                 *  一些算法可以通过冲在像是传递谓词的方式;  
                    
                    
                     *  `uniqie(beg,end)`:使用`==`运算符符来判断元素是否重复;
                     *  `unique(beg,end,comp)`:是通过`comp`函数来判断元素是否重复,然后进行删除;
                 *  `_if`版本的算法:  
                    
                    
                     *  接受谓词参数的算法都有附加的`_if`前缀;  
                        
                        
                         *  `find(beg,end,val)`:用于查找输入范围里面第一次出现`val`的位置;
                         *  `find_if(beg,end,pred)`:查找第一个令`pred`为真的元素;
                 *  算法是否进行拷贝操作  
                    
                    
                     *  在默认情况下,算法将重新排列后的元素重新写回给定的输入序列里面,但是也允许将序列写入指定的位置,这类算法后面都有`_copy`后缀;
                     *  `reverse(beg,end)`:这种算法将元素写入原来的序列里面;
                     *  `reverse_copy(beg,end,dest)`:这种算法用于将元素写入给定的序列`dest`里面;
                 *  特定容器算法  
                    
                    
                     *  对于链表类型`list`和`forward_list`自己的成员函数包含一些算法,所以应该优先使用这些算法;  
                        ![这里写图片描述][SouthEast 1]
                     *  链表特有版本的算法会改变底层的容器,但是通用版本的算法不会改变容器;

[SouthEast]: /images/20220608/4b955dbf08814e8ebff41d6e41b17060.png
[SouthEast 1]: /images/20220608/ae20ed0b0afc46f1843c6d9effe83d03.png