STL算法

-----------------------------------------------------------
  更多内容详见：《The C++ Programming Language》第32章STL算法：
-----------------------------------------------------------
f=for_each(b,e,f): 对[b:e)中的每个x执行f(x);返回f 
例： 
void increment_all(vectorint>& v)  //递增v中每个元素
{
    for_each(v.begin(),v.end(),[](int& x){++x;});
}
---------------------------------------------------------------------
all_of(b,e,f)    [b:e)中所有x都满足f(x)吗？
any_of(b,e,f)    [b:e)中某个x满足f(x)吗？
none_of(b,e,f)   [b:e)中所有x都不满足f(x)吗？
例：
vectordouble> div;
assert(all_of(div.begin(),div.end(),[](double x){ return 0x;})); 
---------------------------------------------------------------------
x=count(b,e,v)        x为[b:e)中满足*p==v的元素*p的数目
x=count_if(b,e,f)     x为[b:e)中满足f(*p)的元素*p的数目 
例：
void f(const string& s)
{
    auto n_space = count(s.begin(),s.end(),‘ ‘);
    auto n_whitespace = count_if(s.begin,s.end(),isspace);
    //...
} 
---------------------------------------------------------------------------------------------------
p=find(b,e,v)                    p指向[b:e)中第一个满足*p==v的元素
p=find_if(b,e,f)                 p指向[b:e)中第一个满足f(*p)的元素
p=find_if_not(b,e,f)             p指向[b:e)中第一个满足!f(*p)的元素
p=find_first_of(b,e,b2,e2)       p指向[b:e)中第一个满足*p==*q的元素，其中q指向[b2:e2)中的某个元素
p=find_first_of(b,e,b2,e2,f)     p指向[b:e)中第一个满足f(*p,*q)的元素，其中q指向[b2:e2)中的某个元素
p=adjacent_find(b,e)             p指向[b:e)中第一个满足*p==*(p+1)的元素
p=adjacent_find(b,e,f)           p指向[b:e)中第一个满足f(*p,*(p+1))的元素
p=find_end(b,e,b2,e2)            p指向[b:e)中最后一个满足*p==*q的元素，其中q指向[b2:e2)中的某个元素
p=find_end(b,e,b2,e2,f)          p指向[b:e)中最后一个满足f(*p,*q)的元素，其中q指向[b2:e2)中的某个元素 
例：
void f(const string& s)
{
    auto p_space = find(s.begin(),s.end(),‘ ‘);
    auto p_whitespace = find_if(s.begin,s.end(),isspace);
    //...
} 

arrayint> x = {1,3,4};
arrayint> y = {0,2,3,4,5};
void f()
{
    auto p = find_first_of(x.begin(),x.end(),y.begin(),y.end());    //p=&x[1]
    auto q = find_first_of(p+1,x.end(),y.begin(),y.end());            //q=&x[2]
}
---------------------------------------------------------------------------------------------------
equal(b,e,b2)                    [b:e)和[b2:b2+(e-b))中所有对应元素都满足v==v2?
equal(b,e,b2,f)                  [b:e)和[b2:b2+(e-b))中所有对应元素都满足f(v,v2)?
pair(p1,p2)=mismatch(b,e,b2)     p1指向[b:e)中第一个满足!(*p1==*p2)的元素，p2指向[b2:b2+(e-b))中的
                                 对应元素；若不存在这样的元素，则p1==e
pair(p1,p2)=mismatch(b,e,b2,f)   p1指向[b:e)中第一个满足!f(*p1,*p2)的元素，p2指向[b2:b2+(e-b))中的
                                 对应元素；若不存在这样的元素，则p1==e
----------------------------------------------------------------------------------------------------
p=search(b,e,b2,e2)              p指向[b:e)中第一个满足[p:p+(e2-b2))等于[b2:e2)的*p
p=search(b,e,b2,e2,f)            p指向[b:e)中第一个满足[p:p+(e2-b2))等于[b2:e2)的*p，用f比较元素
p=search_n(b,e,n,v)              p指向[b:e)中第一个满足[p:p+n)间所有元素的值均为v的位置
p=search_n(b,e,n,v,f)            p指向[b:e)中第一个满足[p:p+n)间每个元素*q均满足f(*q,v)的位置 
例：
string quote{"Why waste time learning, when ignorance is instantaneous?"};
bool in_quote(const string& s)
{
    auto p = search(quote.begin(),quote.end(),s.begin(),s.end());
    return p!=quote.end();
}
void g()
{
    bool b1 = in_quote("learning");        //b1==true
    bool b2 = in_quote("lemming");        //b2==false
}
-----------------------------------------------------------------------------------------------------
p=transform(b,e,out,f)        对[b:e)中的每个元素*p1应用*q=f(*p1),结果写入[out:out+(e-b))中的对应元素
                              *q；p=out+(e-b)
p=transform(b,e,b2,out,f)     对[b:e)中的每个元素*p1及其在[b2:b2+(e-b))中的对应元素*p2应用*q=f(*p1,*p2),
                              结果写入[out,out+(e-b))中的对应元素*q；p=out+(e-b)
例：
void toupper(string& s)    //转换为大写
{
    transform(s.begin(),s.end(),s.begin(),toupper);
}
------------------------------------------------------------------------------------------------------
p=copy(b,e,out)              将[b:e)中的所有元素拷贝到[out:p); p=out+(e-b)
p=copy_if(b,e,out,f)         将[b:e)中满足f(x)的元素x拷贝至[out:p)
p=copy_n(b,n,out)            将[b:b+n)间的前n个元素拷贝至[out:p); p=out+n
p=copy_backward(b,e,out)     将[b:e)中的所有元素拷贝至[out:p)，从尾元素开始拷贝；p=out+(e-b)
p=move(b,e,out)              将[b:e)中的所有元素移动至[out:p)；p=out+(e-b)
p=move_backward(b,e,out)     将[b:e)中的所有元素移动至[out:p)，从尾元素开始移动；p=out+(e-b)
例：
void f(list& lc, ostream& os)
{
    copy(lc.begin(),lc.end(),ostream_iterator(os));
}
数据的写入操作不能超出目标序列末尾。有一种方法可以确保不出现这种情况：使用一个插入器按需增长目标序列。
例：
void f(const vectorchar>& vs, vectorchar>& v)
{
    copy(vs.begin(),vs.end(),v.begin());        //可能超出v的末尾
    copy(vs.begin(),vs.end(),back_inserter(v));    //将vs中的元素追加到v的末尾 
} 
输入序列和输出序列可能重叠。只有当两个序列不重叠或输出序列的末尾位于输入序列内部时，我们才可以使用copy()。
我们用copy_if()拷贝满足某种标准的元素。
例：
void f(listint>& ld, int n)
{
    copy_if(ld.begin(),ld.end(),
            ostream_iteratorint>(cout," "),
            [&](int x){return x>n;});
}
------------------------------------------------------------------------------------------------------------
p=unique(b,e)              移动[b:e)中的一些元素，使得[b:p)中无连续重复元素
p=unique(b,e,f)            移动[b:e)中的一些元素，使得[b:p)中无连续重复元素；“重复”由f(*p,*(p+1))判定
p=unique_copy(b,e,out)     将[b:e)中的元素拷贝至[out:p)；不拷贝连续重复元素
p=unique_copy(b,e,out,f)   将[b:e)中的元素拷贝至[out:p)；不拷贝连续重复元素；“重复”由f(*p,*(p+1))判定 
例：
templateclass C>
void eliminate_duplicates(C& c)
{
    sort(c.begin(),c.end());                //排序 
    auto p = unique(c.begin(),c.end());      //紧凑存储 
    c.erase(p,c.end());                     //收缩 
} 
实现的最后两行也可以写成 c.erase(unique(c.begin(),c.end()),c.end()) 。
-------------------------------------------------------------------------------------------------------------- 
p=remove(b,e,v)                从[b:e)中删除值为v的元素，使得[b:p)中的元素都满足!(*q==v)
p=remove_if(b,e,f)             从[b:e)中删除元素*q，使得[b:p)中的元素都满足!f(*q) 
p=remove_copy(b,e,out,v)       将[b:e)中满足!(*q==v)的元素拷贝至[out:p)
p=remove_copy_if(b,e,out,f)    将[b:e)中满足!f(*q)的元素拷贝至[out:p)
这些算法不能改变输入序列的大小，类似unique(),它是通过将元素移动到左侧来实现“删除”的。
例：
string s{"*CamelCase*IsUgly*"};
cout ‘\n‘;                                    //输出*CamelCase*IsUgly* 
auto p = remove(s.begin(),s.end(),‘*‘);
copy(s.begin(),p,ostream_iteratorchar>{cout});        //输出CamelCaseIsUgly 
cout ‘\n‘;                                     //输出CamelCaseIsUglyly*
--------------------------------------------------------------------------------------
reverse(b,e)                   将[b:e)中的元素逆序排列
p=reverse_copy(b,e,out)        将[b:e)中的元素逆序拷贝至[out:p)
-------------------------------------------------------------
replace(b,e,v,v2)               将[b:e)中满足*p==v的元素替换为v2
replace_if(b,e,f,v2)            将[b:e)中满足f(*p)的元素替换为v2
p=replace_copy(b,e,out,v,v2)    将[b:e)中的元素拷贝至[out:p)，其中满足*p==v的元素被替换为v2
p=replace_copy_if(b,e,out,f,v2) 将[b:e)中的元素拷贝至[out:p)，其中满足f(*p)的元素被替换为v2