c++Primer第十章：泛型算法（包含各种迭代器）

拼搏现实的明天。 2022-11-16 13:55 151阅读 0赞

### 目录 ###

*  算法概览
 *  定制
 *   *  谓词
     *  lambda表达式
     *   *  格式
         *  捕获列表
     *  参数绑定
     *   *  格式
     *  插入迭代器
     *  iostream 迭代器
     *   *  istream\_iterator
         *  ostream\_iterator
     *  反向迭代器

# 算法概览 #

一般都在algorithm，或者

<table> 
 <thead> 
  <tr> 
   <th>算法</th> 
   <th>使用</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>auto r = find(begin,end,val)</td> 
   <td>val:要查找的值，找不到返回end()</td> 
  </tr> 
  <tr> 
   <td>auto sum = accumulate(begin,end,0)</td> 
   <td>0是初始值，可以换为string("");</td> 
  </tr> 
  <tr> 
   <td>equal(L1.begin,L1.end,L2.begin)</td> 
   <td>L2中的元素数目&gt;=L1中元素数目，L1与L2做比较，如果全部相等就true，位置必须一一对应，逆序不行</td> 
  </tr> 
  <tr> 
   <td>fill(vec.begin,vec.end,0)</td> 
   <td>填充初始值，0可以修改，但是初始不可为空</td> 
  </tr> 
  <tr> 
   <td>fill_n(l.begin,n,0)</td> 
   <td>明确填充数量，l的大小</td> 
  </tr> 
  <tr> 
   <td>vector&lt; int &gt; vec fill_n(back_insert(vec),n,0)</td> 
   <td>插入迭代器，赋值后都会自动调用push_back</td> 
  </tr> 
  <tr> 
   <td>auto ret = cpoy(l1.begin,l1.end,l2)</td> 
   <td>注意l2的大小，返回最后一个插入元素之后的位置，即当l1.size()=l2.size()，ret是l2的尾元素之后的位置</td> 
  </tr> 
  <tr> 
   <td>repalce(l.begin,l.end,0,42)</td> 
   <td>所有等于0的值换成42</td> 
  </tr> 
  <tr> 
   <td>repalce_copy(l.begin,l.end,back_insert(vec),0,42)</td> 
   <td>vec是调整后序列的保存位置，保留了原序列</td> 
  </tr> 
  <tr> 
   <td>sort(begin,end)</td> 
   <td>排序</td> 
  </tr> 
  <tr> 
   <td>auto end_unique = unique(words.begin,words.end)</td> 
   <td>需要先进行排序，返回不重复范围末尾的迭代器，不会真正的删除元素，可以使用earse按照ret进行删除</td> 
  </tr> 
  <tr> 
   <td>stable_sort(begin,end,isShorter)</td> 
   <td>相同长度的元素按照字典序</td> 
  </tr> 
  <tr> 
   <td>auto it = find_if(begin,end,谓词)</td> 
   <td>返回第一个使谓词为真的元素，如果不存在，返回尾迭代器</td> 
  </tr> 
  <tr> 
   <td>for_each(begin,end,操作)</td> 
   <td>访问每个数据，并进行操作，具体看下面</td> 
  </tr> 
  <tr> 
   <td>remove_if(begin,end,谓词)</td> 
   <td>删除</td> 
  </tr> 
  <tr> 
   <td>remove_copy_if(v1.begin,v1.end,back_inserter(v2),谓词)</td> 
   <td>v1不变，v2中都是使谓词为false的值</td> 
  </tr> 
  <tr> 
   <td>lst.merge(lst2)</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>lst.merge(lst2,comp)</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>lst.remove(val)</td> 
   <td>会删除指定元素</td> 
  </tr> 
  <tr> 
   <td>lst.remove(一元谓词)</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>lst.reverse()</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>lst.sort()</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>lst.sort(comp)</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>lst.unique()</td> 
   <td>会删除指定元素</td> 
  </tr> 
  <tr> 
   <td>lst.unique(pred)</td> 
   <td>二元谓词</td> 
  </tr> 
  <tr> 
   <td>lst.splice ( iterator position, list&lt;T,Allocator&gt;&amp; x );</td> 
   <td>将所有的数据移向指定位置之前。_after是之后</td> 
  </tr> 
  <tr> 
   <td>void splice ( iterator position, list&lt;T,Allocator&gt;&amp; x, iterator it );</td> 
   <td>将 list x 中的由迭代器it指向的元素移到position处。_after是it之后的元素</td> 
  </tr> 
  <tr> 
   <td>void splice ( iterator position, list&lt;T,Allocator&gt;&amp; x, iterator first, iterator last );</td> 
   <td>将 list x 中的从迭代器 first 到迭代器 last 这一段元素移动到position处</td> 
  </tr> 
 </tbody> 
</table>

# 定制 #

## 谓词 ##

二元谓词

bool isShorter(const string &s1,const string &s2){
    	return s1.size()>s2.size();
    }

## lambda表达式 ##

### 格式 ###

\[捕获参数\] (参数列表) ->返回值类型 \{函数体\}  
可以忽略参数列表和返回值类型，但是捕获参数和函数体不能省略

auto f = []{return 42;}

重写isShorter函数

[] (const string &s1,const string &s2){return a.size()<b.size();}

使用表达式

stable_sort(begin,end,[] (const string &s1,const string &s2){return a.size()<b.size();})

### 捕获列表 ###

lambda 只有在其捕获列表中捕获它所在函数中的局部变量，才能在函数体中使用该变量。但是可以直接使用局部静态变量

[sz] (const string &s) {return s.size()>sz;}

for\_each算法  
打印数据每个数据后面跟一个空格

for_each(begin,end,[](const strong &s){cout<<s<<" ";});

整合的代码

void elimDups(vector<string> &words){ 
    	stable_sort(words.begin(),words.end(),[](const string &s1,const string &s2){ return s1.size()<s2.size();});
    	auto end_unique = unique(words.begin(),words.end());
    	// while(end_unique!=words.end()){ 
    	// end_unique = words.erase(end_unique);
    	// end_unique++;
    	// }
    	words.erase(end_unique,words.end());
    }
    
    void biggies(vector<string> &words,vector<string>::size_type sz){ 
    	elimDups(words);
    	auto wc = find_if(words.begin(),words.end(),[sz](const string &s){ return s.size()>sz;});
    	auto count = words.end() - wc;
    	cout<<"count="<<count<<endl;
    	for_each(wc,words.end(),[](const string &s){ cout<<s<<" ";});
    	cout<<endl;
    }
    
    vector<string> vs{ "sadsad","daddv","sa","rffdsvfegt","sda","addvgwe","dsadsadas","q","sadsad","daddv","sa","rffdsvfegt"};
    biggies(vs,5);

结果  
![在这里插入图片描述][20210408152338801.png]

1.  值捕获  
    在lambda表达式创建时创建拷贝

int v=41;
    auto f = [v1]{ return v1};
    v1=10;
    auto j = f();//j=41

2.引用捕获

int v=41;
    auto f = [&v1]{ return v1};
    v1=10;
    auto j = f();//j=10

ostream流只能使用引用捕获

ostream &os=cout;
    for_each(words.begin(),words.end(),[&os,c](const string &c){ os<<s<<c;});

3.隐式捕获

[&,identifier_list],identifier_list是值捕获
    [=,identifier_list],identifier_list是引用捕获

4.修改捕获的值  
效果和刚刚一样，外部值改变不影响表达式；

v=42
    [v] () mutable {return ++v;}
    v=0;
    调用之后v=43

外部值改变会影响表达式

[&v] () mutable {return ++v;}
    v=0;
    调用之后值为1；

5.注意lambda表达式的返回值，条件运算符不用操心。

## 参数绑定 ##

### 格式 ###

bind只能拷贝参数

auto newCallable = bind(callable,arg_list);

使用案例  
\_1表示占位符

auto check6 = bind(check_size,_1,6);
    string s="hello";
    bool b = check6(s);
    //就不需要值捕获了
    auto wc = find_if(words.begin(),words.end(),bind(check_size,_1,sz));

重排参数顺序  
从小到大->从大到小

bool isShorter(const string &s1,const string &s2)
    {...}
    sort(begin,end,bind(isShorter(_2,_1)))

bind捕获os，使用ref，传递一个对象但是不拷贝

for_each(words.bigen(),words.end(),bind(print,ref(os),-1,' '));

## 插入迭代器 ##

<table> 
 <thead> 
  <tr> 
   <th>项目</th> 
   <th>Value</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>back_inserter</td> 
   <td>创建一个使用push_back的迭代器</td> 
  </tr> 
  <tr> 
   <td>front_inserter</td> 
   <td>创建一个使用push_front的迭代器</td> 
  </tr> 
  <tr> 
   <td>inserter</td> 
   <td>插入给定元素之前</td> 
  </tr> 
 </tbody> 
</table>

代码

it = c.insert(it,val);
    ++it;指向原来的元素

list<int> l1{1,2,3,4};
    list<int> lst2,lst3;
    copy(l1.cbegin(),l1.cend(),front_inserter(lst2));
    //st2={4,3,2,1};
    copy(l1.cbegin(),l1.cend(),inserter(lst3,lst3.begin()));
    //lst3={1,2,3,4};

## iostream 迭代器 ##

### istream\_iterator ###

<table> 
 <thead> 
  <tr> 
   <th>项目</th> 
   <th>Value</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>istream_iterator&lt; T &gt; in(is)</td> 
   <td>in从输入流is读取类型为T的值</td> 
  </tr> 
  <tr> 
   <td>istream_iterator&lt; T &gt; end</td> 
   <td>表尾后位置</td> 
  </tr> 
 </tbody> 
</table>

使用流从标准输入读取数据

istream_iterator<int> in_it(cin);
    istream_iterator<int> in_eof;
    vector<int> vec;
    while (in_it!=in_eof)
    { 
    	vec.push_back(*in_it++);
    }
    for(auto e:vec)
    	cout<<e<<" ";
    cout<<endl;
    //vector<int> vec(in_iter,eof)

结果  
![在这里插入图片描述][20210408162224204.png]

使用流读取文件

vector<string> vec_str;
    cout<<"start"<<endl;
    ifstream  input ("text.txt");
    istream_iterator<string> str_it(input);
    if(!input){ 
    	cout<<"no such file"<<endl;
    	return 0;
    }
    istream_iterator<string> str_eof;
    cout<<*str_it<<endl;
    while(str_it!=str_eof){ 
    	vec_str.push_back(*str_it++);
    }
    cout<<vec_str.size()<<endl;
    for(auto e: vec_str){ 
    	cout<<e<<" ";
    }
    cout<<endl;
    if(input.is_open()){ 
    	cout<<"close file"<<endl;
    	input.close();
    }

结果  
![在这里插入图片描述][20210408161628850.png]

### ostream\_iterator ###

<table> 
 <thead> 
  <tr> 
   <th>项目</th> 
   <th>Value</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>ostream_iterator&lt; T &gt; out(os)</td> 
   <td>out将值写到输出流os</td> 
  </tr> 
  <tr> 
   <td>ostream_iterator&lt; T &gt; out(os,d)</td> 
   <td>out将值写到输出流os，每个值后面带个d</td> 
  </tr> 
  <tr> 
   <td>out = val</td> 
   <td>使用&lt;&lt;运算符将val写入到out所绑定的ostream中</td> 
  </tr> 
 </tbody> 
</table>

代码

vector<string> vs{"sadsad","daddv","sa","rffdsvfegt","sda","addvgwe","dsadsadas","q","sadsad","daddv","sa","rffdsvfegt"};
    	ostream_iterator<string> out_iter(cout," ");
    	for(auto e:vs){
    		*out_iter = e;
    		out_iter++;
    	}

结果  
![在这里插入图片描述][20210408163455449.png]  
使用流处理类类型  
不知道怎么回事out\_iter有问题，老是类型不匹配，有没有大佬可以看一下怎么回事吗

istream_iterator<sales_data> item_iter(cin),eof;
        ostream_iterator<sales_data> out_iter(cout," ");
        sales_data sum = *item_iter++;
        // while(item_iter!=eof){
        //     if(item_iter->isbn()==item_iter->isbn()){
        //         // sum = sum + *item_iter;
        //         // item_iter++;//读取下一条记录
        //         sum += *item_iter++; 
        //     }
        //     else{
        //         out_iter = sum;
        //         sum += *item_iter++; 
        //         // sum = *item_iter;
        //         // item_iter++;//读取下一条记录
        //     }
        // }
        //out_iter = sum;

## 反向迭代器 ##

逆序

sort(v.rbegin(),v.rend());

使用.base转换反向迭代器为普通迭代器

auto rcomma = find(line.crbegin,line.crend(),',');
    cout<<string(rcomma.base(),line.end());

[20210408152338801.png]: /images/20221022/46aab968f2b745018c25244413742fb2.png
[20210408162224204.png]: /images/20221022/9b4a72bd51b74ceb9270769d3efe0fd8.png
[20210408161628850.png]: /images/20221022/46b495089ac247e88899cd47729d6944.png
[20210408163455449.png]: /images/20221022/e8652a5dc4d043779bf18da8b26edce0.png