C++ STL 某些用法

distance

很多时候我们希望在一个 vector ，或者 list ，或者什么其他东西里面，找到一个值在哪个位置，这个时候 find 帮不上忙，而有人就转而求助手写循环了，而且是原始的手写循环：


1for(inti=0; i<vect.size();++i)

2if( vect[i]==value )break;

如果编译器把 i 看作 for scope 的一部分，你还要把 i 的声明拿出去。真的需要这样么？看看这个：

1intdist=distance(col.begin(), find(col.begin(), col.end(),5));

其中 col 可以是很多容器，list, vector, deque... 当然这是你确定 5 就在 col 里面的情形，如果你不确定，那就加点判断：

1intdist;

2list<int>::iterator pos=find(col.begin(), col.end(),5);

3if( pos!=col.end() )

4dist=distance(col.begin(), pos);

我想这还是比手写循环来的好些吧。



--------------------------------------------------------------------------

max, min

这是有直接的算法支持的，当然复杂度是 O(n)，用于未排序容器，如果是排序容器...老兄，那还需要什么算法么？

max_element(col.begin(), col.end());

min_element(col.begin(), col.end());

注意返回的是 iterator ，如果你关心的只是值，那么好：

max_element(col.begin(), col.end());

min_element(col.begin(), col.end());

max_element 和 min_element 都默认用 less 来排序，它们也都接受一个 binary predicate ，如果你足够无聊，甚至可以把 max_element 当成 min_element 来用，或者反之：

max_element(col.begin(), col.end(), greater<int>());//返回最小值！

min_element(col.begin(), col.end(), greater<int>());//返回最大值

当然它们的本意不是这个，而是让你能在比较特殊的情况下使用它们，例如，你要比较的是每个元素的某个成员，或者成员函数的返回值。例如：

1#include<iostream>

2#include<list>

3#include<algorithm>

4#include<string>

5#include<boost/bind.hpp>

6

7usingnamespaceboost;

8usingnamespacestd;

9

10structPerson

11{

12Person(conststring&_name,int_age): name(_name), age(_age) {}

13intage;

14stringname;

15};

16

17intmain()

18{

19list<Person>col;

20list<Person>::iterator pos;

21

22col.push_back(Person("Tom",10));

23col.push_back(Person("Jerry",12));

24col.push_back(Person("Mickey",9));

25

26Person eldest=*max_element(col.begin(), col.end(),bind(&Person::age, _1)<bind(&Person::age, _2));

27cout<<eldest.name;

28}

输出是 Jerry ，这里用了 boost.bind ，原谅我不知道用 bind2nd, mem_fun 怎么写，我也不想知道...



-------------------------------------------------------------------------

copy_if

没错，STL 里面压根没有 copy_if ，这就是为什么我们需要这个：

1template<typename InputIterator, typename OutputIterator, typename Predicate>

2OutputIterator copy_if( InputIterator begin, InputIterator end, OutputIterator destBegin, Predicate p)

3{

4while(begin!=end)

5{

6if(p(begin))destBegin++=*begin;

7++begin;

8}

9returndestBegin;

10}

把它放在自己的工具箱里，是一个明智的选择。



------------------------------------------------------------------------

惯用手法：erase(iter++)

如果你要去除一个 list 中的某些元素，那可千万小心：（下面的代码是错的！！！）


1#include<iostream>

2#include<algorithm>

3#include<iterator>

4#include<list>

5

6intmain()

7{

8intarr[]={1,2,3,4,5,6,7,8,9,10};

9std::list<int>lst(arr, arr+10);

10

11for( std::list<int>::iterator iter=lst.begin();iter!=lst.end();++iter)

12if(*iter%2==0)

13lst.erase(iter);

14

15std::copy(lst.begin(), lst.end(), std::ostream_iterator<int>(std::cout,""));

16}

当 iter 被 erase 掉的时候，它已经失效，而后面却还会做 ++iter ，其行为无可预期！如果你不想动用 remove_if ，那么唯一的选择就是：

1#include<iostream>

2#include<algorithm>

3#include<iterator>

4#include<list>

5

6intmain()

7{

8intarr[]={1,2,3,4,5,6,7,8,9,10};

9std::list<int>lst(arr, arr+10);

10

11for( std::list<int>::iterator iter=lst.begin(); iter!=lst.end(); )

12if(*iter%2==0)

13lst.erase(iter++);

14else

15++iter;

16

17std::copy(lst.begin(), lst.end(),std::ostream_iterator<int>(std::cout,""));

18}

但是上面的代码不能用于 vector, string 和 deque ，因为对于这些容器， erase 不光令 iter 失效，还令 iter 之后的所有 iterator 失效！



-------------------------------------------------------------------------

erase(remove...) 惯用手法

上面的循环如此难写，如此不通用，如此不容易理解，还是用 STL 算法来的好，但是注意，光 remove_if 是没用的，必须使用 erase(remove...) 惯用手法：

1#include<iostream>

2#include<algorithm>

3#include<iterator>

4#include<list>

5#include<functional>

6#include<boost/bind.hpp>

7

8intmain()

9{

10intarr[]={1,2,3,4,5,6,7,8,9,10};

11std::list<int>lst(arr, arr+10);

12

13lst.erase(remove_if(lst.begin(), lst.end(),boost::bind(std::modulus<int>(), _1,2)==0),lst.end());

14std::copy(lst.begin(), lst.end(),std::ostream_iterator<int>(std::cout,""));

15}

当然，这里借助了 boost.bind ，让我们不用多写一个没用的 functor 。

Sometimes,我们需要手写循环(相对于for_each)来erase容器内某些元素，新手经常会犯一些错误。这里总结一下比较常用的固定写法。(删除所有偶数项，并打印出删除的项)

1. vector/queue

正确方法1：
1voiderase(vector<int>&v)

2{

3for(vector<int>::iterator vi=v.begin();vi!=v.end();)

4{

5if(vi%2==0)

6{

7cout<<"Erasing"<<vi<<endl;

8vi=v.erase(vi);

9}

10else++vi;

11}

12}

正确方法2：
1voiderase2(vector<int>&v)

2{

3for(vector<int>::reverse_iterator ri=v.rbegin();ri!=v.rend();)

4{

5if(ri%2==0)

6{

7cout<<"Erasing"<<ri<<endl;

8v.erase((++ri).base());

9}

10else++ri;

11}

12}

2.map/list


正确方法
1voiderase(map<int,int>&m)

2{

3for(map<int,int>::iterator mi=m.begin();mi!=m.end();)

4{

5if(mi->second%2==0)

6{

7cout<<"Erasing"<<mi->second<<endl;

8m.erase(mi++);

9}

10else++mi;

11}

12}

原文链接: https://www.cnblogs.com/hicjiajia/archive/2010/08/27/1809957.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍