1.連續計算類
adjacent_difference,count,partial_sum,accumulate,count_if 均是以線性複雜度
accumulate
#include <numeric>
TYPE accumulate( iterator start, iterator end, TYPE val );
TYPE accumulate( iterator start, iterator end, TYPE val, BinaryFunction f );
The accummulate() function computes the sum of val and all of the elements in the range[start,end).
If the binary function f if specified, it is used instead of the + operator to perform thesummation
#include "stdafx.h"
#include <iostream>
#include <functional>
#include <numeric>
#include <vector>
#if 0
int main()
{
using namespace std;
vector<int>v1, v2();
vector<int>::iterator iter1, iter2;
for (auto i = ; i < ; i++)
{
v1.push_back(i);
}
cout << "V1:" << endl;
for (auto i = ; i < ; i++)
{
cout << v1[i] << " ";
}
cout << endl;
auto total = accumulate(v1.begin(), v1.end(), );
cout << "0 begin:"<<total << endl;
total = accumulate(v1.begin(), v1.end(), );
cout << "10 begin"<<total << endl;
int j = ;
int partotal;
for (iter1 = v1.begin(); iter1 != v1.end(); iter1++)
{
partotal = accumulate(v1.begin(), iter1 + , );
v2[j] = partotal;
j++;
}
cout << "partotal:" << partotal << endl;
cout << "The vector of partial sums is:\n ( ";
for (iter2 = v2.begin(); iter2 != v2.end(); iter2++)
cout << *iter2 << " ";
cout << ")." << endl << endl;
//output: 1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136 153 171 190 210
// The second member function for the accumulated product
int tmp[] = {,,,,,,,,,};
vector <int> v3(tmp,tmp+), v4();
int ptotal;
ptotal = accumulate(v3.begin(), v3.end(), , multiplies<int>());
cout << "The product of the integers from 1 to 10 is: "
<< ptotal << "." << endl;
vector <int>::iterator iter3, iter4;
// Constructing a vector of partial products
int k = , ppartotal;
for (iter3 = v3.begin(); iter3 != v3.end(); iter3++) {
ppartotal = accumulate(v3.begin(), iter3 + , , multiplies<int>());
v4[k] = ppartotal;
k++;
}
cout << "The vector of partial products is:\n ( ";
for (iter4 = v4.begin(); iter4 != v4.end(); iter4++)
cout << *iter4 << " ";
cout << ")." << endl;
//output: 1 2 6 24 120 720 5040 40320 362880 3628800
return ;
}
#endif
adjacent_difference
Syntax:
#include <numeric>
iterator adjacent_difference( iterator start, iterator end, iterator result );
iterator adjacent_difference( iterator start, iterator end, iterator result, BinaryFunction f );
The adjacent_difference() function calculates the differences between adjacent elements
**in the range [start,end) and stores the result starting at result.
If a binary function f is given, it is used instead of the - operator to compute the differences.**
#include <vector>
#include <list>
#include <numeric>
#include <functional>
#include <iostream>
#if 0
int main()
{
using namespace std;
vector<int> V1(), V2();
vector<int>::iterator VIter1, VIter2, VIterend, VIterend2;
list <int> L1;
list <int>::iterator LIter1, LIterend, LIterend2;
int t;
for (t = ; t <= ; t++)
{
L1.push_back(t * t);
}
cout << "The input list L1 is:\n ( ";
for (LIter1 = L1.begin(); LIter1 != L1.end(); LIter1++)
cout << *LIter1 << " ";
cout << ")." << endl;
// The first member function for the adjacent_differences of
// elements in a list output to a vector
VIterend = adjacent_difference(L1.begin(), L1.end(),
V1.begin());
cout << "Output vector containing adjacent_differences is:\n ( ";
for (VIter1 = V1.begin(); VIter1 != VIterend; VIter1++)
cout << *VIter1 << " ";
cout << ")." << endl;
//output: 1 3 5 7 9 11 13 15 17 19
// The second member function used to compute
// the adjacent products of the elements in a list
VIterend2 = adjacent_difference(L1.begin(), L1.end(), V2.begin(),multiplies<int>());
cout << "The output vector with the adjacent products is:\n ( ";
for (VIter2 = V2.begin(); VIter2 != VIterend2; VIter2++)
cout << *VIter2 << " ";
cout << ")." << endl;
//output: 1 4 36 144 400 900 1764 3136 5184 8100
// Computation of adjacent_differences in place
LIterend2 = adjacent_difference(L1.begin(), L1.end(), L1.begin());
cout << "In place output adjacent_differences in list L1 is:\n ( ";
for (LIter1 = L1.begin(); LIter1 != LIterend2; LIter1++)
cout << *LIter1 << " ";
cout << ")." << endl;
//output: 1 3 5 7 9 11 13 15 17 19
}
#endif
partial_sum
#include <numeric>
iterator partial_sum( iterator start, iterator end, iterator result );
iterator partial_sum( iterator start, iterator end, iterator result,BinOp p );
The partial_sum() function calculates the partial sum of a range defined by [start,end),storing the output at result.
- start is assigned to *result, the sum of *start and (start + 1) is assigned to (result + 1), etc.*
#include <vector>
#include <list>
#include <numeric>
#include <functional>
#include <iostream>
#if 0
int main()
{
using namespace std;
vector<int> V1(), V2();
vector<int>::iterator VIter1, VIter2, VIterend, VIterend2;
list <int> L1;
list <int>::iterator LIter1, LIterend;
int t;
for (t = ; t <= ; t++)
{
L1.push_back(t);
}
cout << "The input list L1 is:\n ( ";
for (LIter1 = L1.begin(); LIter1 != L1.end(); LIter1++)
cout << *LIter1 << " ";
cout << ")." << endl;
// The first member function for the partial sums of
// elements in a list output to a vector
VIterend = partial_sum(L1.begin(), L1.end(),
V1.begin());
cout << "The output vector containing the partial sums is:\n ( ";
for (VIter1 = V1.begin(); VIter1 != VIterend; VIter1++)
cout << *VIter1 << " ";
cout << ")." << endl;
//output: 1 3 6 10 15 21 28 36 45 55
// The second member function used to compute
// the partial product of the elements in a list
VIterend2 = partial_sum(L1.begin(), L1.end(), V2.begin(),
multiplies<int>());
cout << "The output vector with the partial products is:\n ( ";
for (VIter2 = V2.begin(); VIter2 != VIterend2; VIter2++)
cout << *VIter2 << " ";
cout << ")." << endl;
// output:1 2 6 24 120 720 5040 40320 362880 3628800
// Computation of partial sums in place
LIterend = partial_sum(L1.begin(), L1.end(), L1.begin());
cout << "The in place output partial_sum list L1 is:\n ( ";
for (LIter1 = L1.begin(); LIter1 != LIterend; LIter1++)
cout << *LIter1 << " ";
cout << ")." << endl;
//output:1 3 6 10 15 21 28 36 45 55
}
#endif
count_if(count)
#include <algorithm>
size_t count_if( iterator start, iterator end, UnaryPred p );
size_t count( iterator start, iterator end, const TYPE& val );
The count_if() function returns the number of elements between start and end for which the predicate p returns true
The count() function returns the number of elements between start and end that match val
int nums[] = { , , , , , , , , };
int start = ;
int end = ;
int target_value = ;
int num_items = count_if( nums+start,nums+end,
bind2nd(equal_to<int>(), target_value) );
cout << "nums[] contains " << num_items << " items matching "<< target_value << endl;
output:nums[] contains items matching