[C++]C++STL数值算法[转载]

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

generate,partial_sum,for_each
看看下面：

1.   std::vector<int> vect(10);
   
2.   std::partial_sum(vect.begin(), vect.end(), vect.begin(), _2 = _1 + 1);

复制代码

如果你现在把 vect 输出，你会得到：
0 1 2 3 4 5 6 7 8 9
乍看起来不太好理解，我来慢慢解释。
partial_sum 的第4个参数是一个双参数的 functor ，在这里，lambda 表达式 _2 = _1 + 1 充当了这个角色，它相当于


f(x, y)  {  y  =  x  +  1;  }


而 partial_sum 呢？它把一个序列的 partial sum 送到结果序列中去，例如如果输入一个数组 v[10] ，而输出是 r[10] ，那么它的计算就是


r[0] = v[0]            
r[1] = f( r[0], r[1] )
r[2] = f( r[1], r[2] )
......
r[9] = f( r[8], r[9] )


而当我们把 partial_sum 作用于 vect 本身，结果就成了
vect[0] = vect[0]                            // vect[0] = 0
vect[1] = (vect[1] = vect[0] + 1)   // vect[1] = 1
vect[2] = (vect[2] = vect[1] + 1)   // vect[2] = 2
......
vect[9] = (vect[9] = vect[8] + 1)   // vect[9] = 9


你一定发现其中的问题所在了：首先，我们必须依赖于编译器把 vect[0] 初始化为0，其次，vect[0] = vect[0] 是不可回避的。以我当前所想到的，也只能这样了。


推广一下，如果把 _2 = _1 + 1 中的常数 1 换成另外的数字，我们就可以用一句话得到从 0 开始的等差数列，例如

1.   std::partial_sum(vect.begin(), vect.end(), vect.begin(), _2 = _1 + 3);

复制代码

得到的是


0 3 6 9 12 15 18 21 24 27


如果再发挥一点想象力，你就可以构造出更复杂的 lambda 表达式，从而得到更复杂的数组（也许这里叫数列更好吧），例如

1. std::partial_sum(vect.begin(), vect.end(), vect.begin(), _2 = 2 * _1 + 1);

复制代码

得到的是 2 的 n 次方 - 1 数列


0 1 3 7 15 31 63 127 255 511


在 STL 算法中，adjacent_difference 和 partial_sum 是逆运算，因此，上面的事情也可以用 adjacent_difference 来做，只不过要把 lambda 表达式中的参数位置换一下，例如要得到 0, 3, 6... 的等差数列，只需要


  std::adjacent_difference(vect.begin(), vect.end(), vect.begin(), _1 = _2 + 3);


而 2 的 n 次方 - 1 数列也是同样道理


  std::adjacent_difference(vect.begin(), vect.end(), vect.begin(), _1 = 2*_2 + 1);


与之类似的还有 STL 的 partition 算法，它根据传入的 predicate 对一个序列进行划分，predicate 得到 true 的将放在前面，其余的放在后面，返回的是那些“ 放在 后面”的元素中的第一个，换言之就是分界点。下面的代码

1.   std::vector<int> vect(10);
   
2.   std::partial_sum(vect.begin(), vect.end(), vect.begin(), _2 = 2*_1 + 1);
   
3.   
   
4.   std::cout << *std::partition(vect.begin(), vect.end(), _1 > 100) << std::endl;
   
5.   
   
6.   std::for_each(vect.begin(), vect.end(), std::cout << _1 << " ");

复制代码

输出为


7
511 255 127 7 15 31 63 3 1 0


如果仔细观察，还可以发现上面的输出有点问题：数列中原有的顺序（0, 1, 3, 7...）不复存在，这是因为 partition 并不是一个稳定排序的算法，它不保证排序结果保有原来的顺序。如果需要稳定排序，可以使用 stable_partition 。只需要更改排序的那一句代码为


  std::cout << *std::stable_partition(vect.begin(), vect.end(), _1 > 100) << std::endl;
结果是


0
127 255 511 0 1 3 7 15 31 63


当然，如果你还记得大学里的算法理论，就知道它们在效率上是有点区别的，partition 的复杂度保证为 O(n) ，具体地说是保证不超过 n/2 次交换；而 stable_partition 在最好情况下为 O(n) ，最差情况则达到 O(n*log(n)) 。


容器的初始化是如此的常见，以至于 boost 提供了一个 assign 库来简化这些操作。boost.assign 大量利用了重载的逗号和括号来简化赋值操作，提供了甚至比用数组更加简洁的语法：

1. #include <iostream>
   
2. #include <algorithm>
   
3. #include <vector>
   
4. #include <string>
   
5. 
   
6. #include <boost/assign/std/vector.hpp>
   
7. #include <boost/assign/std/list.hpp>
   
8. 
   
9. using namespace boost::assign;
   
10. 
    
11. int main()
    
12. {
    
13.   std::vector<int> vint;
    
14.   vint += 2,3,5,7,11,13,17,19,23;
    
15.   
    
16.   std::vector<std::string> vstr;
    
17.   vstr += "Amy","Ralph","Simon","Maggie";
    
18.   
    
19.   std::list<std::string> lstr;
    
20.   lstr += "Amy","Ralph","Simon","Maggie";
    
21.    
    
22.   std::for_each(vint.begin(), vint.end(), std::cout << _1 << " ");
    
23.   std::cout << std::endl;
    
24.   std::for_each(vstr.begin(), vstr.end(), std::cout << _1 << " ");
    
25.   std::cout << std::endl;
    
26.   std::for_each(lstr.begin(), lstr.end(), std::cout << _1 << " ");
    
27. }

复制代码

运行这个程序，输出与前面的大致相同，但是我们注意到初始化更加简洁了，而且也不需要额外的空间来存储数组，对于各种类型，都能够以统一的方式来初始化，真是妙不可言。有趣的是 assign 的作者在文档中还特意引用了 Bjarne Stroustrup 的话作为引子：
There appear to be few practical uses of operator,().
Bjarne Stroustrup, The Design and Evolution of C++


这也许就是 C++ 最大的魅力之一：你无法预料它可以办到些什么。


下面关于 map 的例子也使用 boost.assign ，可以看到重载的括号给我们带来了多少方便。

1. #include <iostream>
   
2. #include <algorithm>
   
3. #include <map>
   
4. #include <string>
   
5. 
   
6. #include <boost/lambda/lambda.hpp>
   
7. #include <boost/lambda/bind.hpp>
   
8. 
   
9. #include <boost/assign/list_inserter.hpp>
   
10. #include <boost/assign/list_of.hpp>
    
11. 
    
12. using namespace std;
    
13. using namespace boost::assign;
    
14. using namespace boost::lambda;
    
15. 
    
16. int main()
    
17. {
    
18.   map<string,int> months;  
    
19.   
    
20.   insert( months )
    
21.     ( "january",   31 )( "february", 28 )
    
22.     ( "march",     31 )( "april",    30 )
    
23.     ( "may",       31 )( "june",     30 )
    
24.     ( "july",      31 )( "august",   31 )
    
25.     ( "september", 30 )( "october",  31 )
    
26.     ( "november",  30 )( "december", 31 );
    
27.    
    
28.   map<int,string> persons = map_list_of
    
29.     (2,"Amy")(3,"Ralph")
    
30.     (5,"Simon")(7,"Maggie");
    
31.    
    
32.   for_each( months.begin(), months.end(),
    
33.     cout << bind(&map<string,int>::value_type::second, _1) << "\t"
    
34.          << bind(&map<string,int>::value_type::first, _1) << "\n"
    
35.   );
    
36.   cout << endl;
    
37.   for_each( persons.begin(), persons.end(),
    
38.     cout << bind(&map<int,string>::value_type::first, _1) << "\t"
    
39.          << bind(&map<int,string>::value_type::second, _1) << "\n"
    
40.   );  
    
41. }

复制代码

输出：

1. 30      april
   
2. 31      august
   
3. 31      december
   
4. 28      february
   
5. 31      january
   
6. 31      july
   
7. 30      june
   
8. 31      march
   
9. 31      may
   
10. 30      november
    
11. 31      october
    
12. 30      september
    
13. 
    
14. 2       Amy
    
15. 3       Ralph
    
16. 5       Simon
    
17. 7       Maggie

复制代码

一个例子

1. ///////////////////////////////////////////////////////////////////////
   
2. //
   
3. // Compile options needed: /GX
   
4. //
   
5. // partial_sum.cpp : Demonstrates the use of partial_sum().
   
6. //
   
7. // Description of partial_sum(first,last,first2,init)
   
8. //                partial_sum(first,last,first2,init,binary_op):
   
9. //
   
10. //    Assigns to every iterator i in the range
    
11. //    [result,result + (last - first)) a value correspondingly equal to
    
12. //    ((...(*first + *(first + 1)) + ...) + *(first + (i - result)))
    
13. //
    
14. //     - or -
    
15. //
    
16. //    binary_op(binary_op(..., binary_op(*first, *(first  +  1)),...),
    
17. //    *(first + (i - result)))
    
18. //
    
19. //    In other words,
    
20. //    *(result+i) = init + *(first+0) + *(first+1) + ... + *(first+i)
    
21. //
    
22. // Written by Shaun Miller
    
23. // of Microsoft Product Support Services, Languages Developer Support.
    
24. // Copyright (c) 1996 Microsoft Corporation. All rights reserved.
    
25. ///////////////////////////////////////////////////////////////////////
    
26. 
    
27. #include <iostream>
    
28. #include <numeric>
    
29. #include <functional>
    
30. #include <vector>
    
31. #include <iterator>
    
32. 
    
33. 
    
34. #if _MSC_VER > 1020   // if VC++ version is > 4.2
    
35.    using namespace std;  // std c++ libs implemented in std
    
36.    #endif
    
37. 
    
38. typedef vector < int, allocator < int > > IntArray;
    
39. typedef ostream_iterator < int, char, char_traits<char> > IntOstreamIt;
    
40. 
    
41. void main ()
    
42. 
    
43. {
    
44. 
    
45.     IntOstreamIt itOstream(cout," ");
    
46. 
    
47.     // Initialize the array
    
48.     IntArray rgI;
    
49.     for (int i=1; i<=10; i++) rgI.push_back(i);
    
50. 
    
51.     // Print the arrays
    
52.     cout << "Array: ";
    
53.     copy(rgI.begin(),rgI.end(),itOstream);
    
54.     cout << endl;
    
55. 
    
56.     // The result array must be at least the same size as the data array
    
57.     IntArray rgIresult(rgI.size());
    
58. 
    
59.     // Compute the partial sum of the array
    
60.     partial_sum(rgI.begin(),rgI.end(),rgIresult.begin());
    
61. 
    
62.     // Print the array of partial sums
    
63.     cout << "Array of partial sums: ";
    
64.     copy(rgIresult.begin(),rgIresult.end(),itOstream);
    
65.     cout << endl;
    
66. 
    
67.     // Compute the partial product of the array
    
68.     partial_sum(rgI.begin(),rgI.end(),rgIresult.begin(),multiplies<int>());
    
69. 
    
70.     // Print the array of partial products
    
71.     cout << "Array of partial products: ";
    
72.     partial_sum(rgIresult.begin(),rgIresult.end(),itOstream);
    
73.     cout << endl;
    
74. 
    
75. }

复制代码

                       
程式輸出為：

1. Array: 1 2 3 4 5 6 7 8 9 10
   
2. Array of partial sums: 1 3 6 10 15 21 28 36 45 55
   
3. Array of partial products: 1 3 9 33 153 873 5913 46233 409113 4037913

复制代码

                               

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏3 回帖

关键词：STL difference partition adjacent generate generate 表达式 角色

C++居然还没被C#所取代

厉害！但对我来讲太深奥了

hkmonte 发表于 2015-4-13 23:56
厉害！但对我来讲太深奥了

转载的 我觉得不错 就分享了

学习学习！！