수치 알고리즘 (Numeric Algorithm)
// since C++11 until C++20
template< class ForwardIt, class T >
void iota( ForwardIt first, ForwardIt last, T value );
// since C++20
template< class ForwardIt, class T >
constexpr void iota( ForwardIt first, ForwardIt last, T value );
// ----------------------------------------------------------------------------------
#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
#include <numeric>
#include <random>
using namespace std;
int main() {
list<int> l(10);
iota(l.begin(), l.end(), -4);
vector<list<int>::iterator> v(l.size());
iota(v.begin(), v.end(), l.begin());
shuffle(v.begin(), v.end(), mt19937{random_device{}()});
cout << "Contents of the list: ";
for(auto n: l) cout << n << ' ';
cout << endl;
cout << "Contents of the list, shuffled: ";
for(auto i: v) cout << *i << ' ';
cout << endl;
return 0;
}
/*
$ g++ test.cpp -std=c++11
$ ./a.out
Contents of the list: -4 -3 -2 -1 0 1 2 3 4 5
Contents of the list, shuffled: -4 -2 1 5 3 4 -3 0 2 -1
*/
// until C++20
template< class InputIt, class T >
T accumulate( InputIt first, InputIt last, T init );
template< class InputIt, class T, class BinaryOperation >
T accumulate( InputIt first, InputIt last, T init, BinaryOperation op );
// since C++20
template< class InputIt, class T >
constexpr T accumulate( InputIt first, InputIt last, T init );
template< class InputIt, class T, class BinaryOperation >
constexpr T accumulate( InputIt first, InputIt last, T init, BinaryOperation op );
// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <functional>
using namespace std;
int main() {
vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int sum = accumulate(v.begin(), v.end(), 0);
int product = accumulate(v.begin(), v.end(), 1, multiplies<int>());
auto dash_fold = [](string a, int b) {
return move(a) + '-' + to_string(b);
};
// Start with first element
string s = accumulate(next(v.begin()), v.end(), to_string(v[0]), dash_fold);
// Right fold using reverse iterators
// Start with last element
string rs = accumulate(next(v.rbegin()), v.rend(), to_string(v.back()), dash_fold);
cout << "sum: " << sum << endl
<< "product: " << product << endl
<< "dash-separated string: " << s << endl
<< "dash-separated string (right-folded): " << rs << endl;
return 0;
}
/*
$ g++ test.cpp -std=c++11
$ ./a.out
sum: 55
product: 3628800
dash-separated string: 1-2-3-4-5-6-7-8-9-10
dash-separated string (right-folded): 10-9-8-7-6-5-4-3-2-1
*/
// until C++20
template< class InputIt1, class InputIt2, class T >
T inner_product( InputIt1 first1, InputIt1 last1, InputIt2 first2, T init );
template<class InputIt1, class InputIt2, class T,
class BinaryOperation1, class BinaryOperation2>
T inner_product( InputIt1 first1, InputIt1 last1, InputIt2 first2, T init,
BinaryOperation1 op1, BinaryOperation2 op2 );
// since C++20
template< class InputIt1, class InputIt2, class T >
constexpr T inner_product( InputIt1 first1, InputIt1 last1,
InputIt2 first2, T init );
template<class InputIt1, class InputIt2, class T,
class BinaryOperation1, class BinaryOperation2>
constexpr T inner_product( InputIt1 first1, InputIt1 last1, InputIt2 first2, T init,
BinaryOperation1 op1, BinaryOperation2 op2 );
// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <numeric>
#include <functional>
using namespace std;
int main() {
vector<int> a{0, 1, 2, 3, 4};
vector<int> b{5, 4, 2, 3, 1};
int r1 = inner_product(a.begin(), a.end(), b.begin(), 0);
cout << "Inner product of a and b: " << r1 << endl;
int r2 = inner_product(a.begin(), a.end(), b.begin(), 0, plus<>(), equal_to<>());
cout << "Number of pairwise matches between a and b: " << r2 << endl;
return 0;
}
/*
$ g++ test.cpp -std=c++14
$ ./a.out
Inner product of a and b: 21
Number of pairwise matches between a and b: 2
*/
// until C++20
template< class InputIt, class OutputIt >
OutputIt adjacent_difference( InputIt first, InputIt last, OutputIt d_first );
template< class InputIt, class OutputIt, class BinaryOperation >
OutputIt adjacent_difference( InputIt first, InputIt last,
OutputIt d_first, BinaryOperation op );
// since C++20
template< class InputIt, class OutputIt >
constexpr OutputIt adjacent_difference( InputIt first, InputIt last,
OutputIt d_first );
template< class InputIt, class OutputIt, class BinaryOperation >
constexpr OutputIt adjacent_difference( InputIt first, InputIt last,
OutputIt d_first, BinaryOperation op );
// since C++17
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardIt2 adjacent_difference( ExecutionPolicy&& policy,
ForwardIt1 first, ForwardIt1 last,
ForwardIt2 d_first );
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
class BinaryOperation >
ForwardIt2 adjacent_difference( ExecutionPolicy&& policy,
ForwardIt1 first, ForwardIt1 last,
ForwardIt2 d_first, BinaryOperation op );
// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <array>
#include <numeric>
#include <functional>
#include <iterator>
using namespace std;
int main() {
// Default implementation - the difference b/w two adjacent items
vector<int> v = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
adjacent_difference(v.begin(), v.end(), v.begin());
for (auto n : v) cout << n << ' ';
cout << endl;
// Fibonacci
array<int, 10> a {1};
adjacent_difference(begin(a), prev(end(a)), next(begin(a)), plus<> {});
copy(begin(a), end(a), ostream_iterator<int> {cout, " "});
cout << endl;
return 0;
}
/*
$ g++ test.cpp -std=c++14
$ ./a.out
2 2 2 2 2 2 2 2 2 2
1 1 2 3 5 8 13 21 34 55
*/
// until C++20
template< class InputIt, class OutputIt >
OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first );
template< class InputIt, class OutputIt, class BinaryOperation >
OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first,
BinaryOperation op );
// since C++20
template< class InputIt, class OutputIt >
constexpr OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first );
template< class InputIt, class OutputIt, class BinaryOperation >
constexpr OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first,
BinaryOperation op );
// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <numeric>
#include <iterator>
#include <functional>
using namespace std;
int main() {
vector<int> v = {2, 2, 2, 2, 2, 2, 2, 2, 2, 2}; // or vector<int>v(10, 2);
cout << "The first 10 even numbers are: ";
partial_sum(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
cout << endl;
partial_sum(v.begin(), v.end(), v.begin(), multiplies<int>());
cout << "The first 10 powers of 2 are: ";
for (auto n : v) cout << n << " ";
cout << endl;
return 0;
}
/*
$ g++ test.cpp -std=c++11
$ ./a.out
The first 10 even numbers are: 2 4 6 8 10 12 14 16 18 20
The first 10 powers of 2 are: 2 4 8 16 32 64 128 256 512 1024
*/
// since C++17 until C++20
template<class InputIt>
typename std::iterator_traits<InputIt>::value_type reduce(
InputIt first, InputIt last);
template<class InputIt, class T>
T reduce(InputIt first, InputIt last, T init);
// since C++20
template<class InputIt>
constexpr typename std::iterator_traits<InputIt>::value_type reduce(
InputIt first, InputIt last);
template<class InputIt, class T>
constexpr T reduce(InputIt first, InputIt last, T init);
// since C++17
template<class ExecutionPolicy, class ForwardIt>
typename std::iterator_traits<ForwardIt>::value_type reduce(
ExecutionPolicy&& policy,
ForwardIt first, ForwardIt last);
template<class ExecutionPolicy, class ForwardIt, class T>
T reduce(ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, T init);
template<class InputIt, class T, class BinaryOp>
constexpr T reduce(InputIt first, InputIt last, T init, BinaryOp binary_op);
template<class ExecutionPolicy, class ForwardIt, class T, class BinaryOp>
T reduce(ExecutionPolicy&& policy,
ForwardIt first, ForwardIt last, T init, BinaryOp binary_op);
// only C++17
template<class InputIt, class T, class BinaryOp>
T reduce(InputIt first, InputIt last, T init, BinaryOp binary_op);
// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <numeric>
#include <chrono>
#include <execution>
using namespace std;
int main() {
const vector<double> v(10'000'007, 0.5);
{
const auto t1 = chrono::high_resolution_clock::now();
const double result = accumulate(v.cbegin(), v.cend(), 0.0);
const auto t2 = chrono::high_resolution_clock::now();
const chrono::duration<double, milli> ms = t2 - t1;
cout << fixed << "accumulate result " << result;
cout << " took " << ms.count() << " ms" << endl;
}
{
const auto t1 = chrono::high_resolution_clock::now();
const double result = reduce(execution::par, v.cbegin(), v.cend());
const auto t2 = chrono::high_resolution_clock::now();
const chrono::duration<double, milli> ms = t2 - t1;
cout << "reduce result " << result << " took ";
cout << ms.count() << " ms" << endl;
}
return 0;
}
/*
$ g++ test.cpp -std=c++17
$ ./a.out
std::accumulate result 5000003.50000 took 12.7365 ms
std::reduce result 5000003.50000 took 5.06423 ms
*/
-
exclusive_scan 각 원소는 자신을 제외하고 앞의 원소까지만 누적 연산. ex) ret[3] = [0, 2] 범위에서만 연산을 수행한 결과. (C++17)
-
inclusive_scan 각 원소는 자신을 포함해서 누적 연산. ex) ret[3] = [0, 3] 범위에서만 연산을 수행한 결과. (C++17)
// since C++17 until C++20
template< class InputIt, class OutputIt, class T >
OutputIt exclusive_scan( InputIt first, InputIt last, OutputIt d_first, T init );
template< class InputIt, class OutputIt,
class T, class BinaryOperation >
OutputIt exclusive_scan( InputIt first, InputIt last,
OutputIt d_first, T init, BinaryOperation binary_op );
// since C++20
template< class InputIt, class OutputIt, class T >
constexpr OutputIt exclusive_scan( InputIt first, InputIt last,
OutputIt d_first, T init );
template< class InputIt, class OutputIt,
class T, class BinaryOperation >
constexpr OutputIt exclusive_scan( InputIt first, InputIt last, OutputIt d_first,
T init, BinaryOperation binary_op );
// since C++17
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class T >
ForwardIt2 exclusive_scan( ExecutionPolicy&& policy,
ForwardIt1 first, ForwardIt1 last,
ForwardIt2 d_first, T init);
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
class T, class BinaryOperation >
ForwardIt2 exclusive_scan( ExecutionPolicy&& policy,
ForwardIt1 first, ForwardIt1 last,
ForwardIt2 d_first, T init, BinaryOperation binary_op );
// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <iterator>
#include <functional>
#include <numeric>
using namespace std;
int main() {
vector data = {3, 1, 4, 1, 5, 9, 2, 6};
cout << "exclusive sum: ";
exclusive_scan(data.begin(), data.end(),
ostream_iterator<int>(cout, " "), 0);
cout << endl << "inclusive sum: ";
inclusive_scan(data.begin(), data.end(),
ostream_iterator<int>(cout, " "));
cout << endl << endl << "exclusive product: ";
exclusive_scan(data.begin(), data.end(),
ostream_iterator<int>(cout, " "), 1,
multiplies<>{});
cout << endl << "inclusive product: ";
inclusive_scan(data.begin(), data.end(),
ostream_iterator<int>(cout, " "),
multiplies<>{});
cout << endl;
return 0;
}
/*
$ g++ test.cpp -std=c++17
$ ./a.out
exclusive sum: 0 3 4 8 9 14 23 25
inclusive sum: 3 4 8 9 14 23 25 31
exclusive product: 1 3 3 12 12 60 540 1080
inclusive product: 3 3 12 12 60 540 1080 6480
*/
// since C++17 until C++20
template<class InputIt1, class InputIt2, class T>
T transform_reduce(InputIt1 first1, InputIt1 last1, InputIt2 first2, T init);
template <class InputIt1, class InputIt2, class T, class BinaryOp1, class BinaryOp2>
T transform_reduce(InputIt1 first1, InputIt1 last1, InputIt2 first2,
T init, BinaryOp1 binary_op1, BinaryOp2 binary_op2);
template<class InputIt, class T, class BinaryOp, class UnaryOp>
T transform_reduce(InputIt first, InputIt last,
T init, BinaryOp binop, UnaryOp unary_op);
// since C++20
template<class InputIt1, class InputIt2, class T>
constexpr T transform_reduce(InputIt1 first1, InputIt1 last1, InputIt2 first2, T init);
template <class InputIt1, class InputIt2, class T, class BinaryOp1, class BinaryOp2>
constexpr T transform_reduce(InputIt1 first1, InputIt1 last1, InputIt2 first2,
T init, BinaryOp1 binary_op1, BinaryOp2 binary_op2);
template<class InputIt, class T, class BinaryOp, class UnaryOp>
constexpr T transform_reduce(InputIt first, InputIt last,
T init, BinaryOp binop, UnaryOp unary_op);
// since C++17
template<class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class T>
T transform_reduce(ExecutionPolicy&& policy,
ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, T init);
template<class ExecutionPolicy,
class ForwardIt1, class ForwardIt2, class T, class BinaryOp1, class BinaryOp2>
T transform_reduce(ExecutionPolicy&& policy,
ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2,
T init, BinaryOp1 binary_op1, BinaryOp2 binary_op2);
template<class ExecutionPolicy,class ForwardIt, class T, class BinaryOp, class UnaryOp>
T transform_reduce(ExecutionPolicy&& policy,
ForwardIt first, ForwardIt last,
T init, BinaryOp binary_op, UnaryOp unary_op);
// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <numeric>
#include <functional>
#include <execution>
using namespace std;
int main() {
vector<double> xvalues(10007, 1.0), yvalues(10007, 1.0);
double result = transform_reduce(
execution::par,
xvalues.begin(), xvalues.end(),
yvalues.begin(), 0.0
);
cout << result << endl;
result = transform_reduce(
execution::par,
xvalues.begin(), xvalues.end(), 1.0,
plus<>(), [](double x) { return x * 2.0; }
);
cout << result << endl;
return 0;
}
/*
$ g++ test.cpp -std=c++17
$ ./a.out
10007
20015 <--- 1.0 + 2.0 * 10007
*/
// since C++17 until C++20
template< class InputIt, class OutputIt, class T,
class BinaryOperation, class UnaryOperation>
OutputIt transform_exclusive_scan( InputIt first, InputIt last,
OutputIt d_first, T init,
BinaryOperation binary_op,
UnaryOperation unary_op);
template< class InputIt, class OutputIt,
class BinaryOperation, class UnaryOperation >
OutputIt transform_inclusive_scan( InputIt first, InputIt last, OutputIt d_first,
BinaryOperation binary_op,
UnaryOperation unary_op );
template< class InputIt, class OutputIt,
class BinaryOperation, class UnaryOperation, class T >
OutputIt transform_inclusive_scan( InputIt first, InputIt last, OutputIt d_first,
BinaryOperation binary_op, UnaryOperation unary_op,
T init );
// since C++20
template< class InputIt, class OutputIt, class T,
class BinaryOperation, class UnaryOperation>
constexpr OutputIt transform_exclusive_scan( InputIt first, InputIt last,
OutputIt d_first,
T init, BinaryOperation binary_op,
UnaryOperation unary_op);
template< class InputIt, class OutputIt, class BinaryOperation, class UnaryOperation >
constexpr OutputIt transform_inclusive_scan( InputIt first, InputIt last,
OutputIt d_first,
BinaryOperation binary_op,
UnaryOperation unary_op );
template< class InputIt, class OutputIt,
class BinaryOperation, class UnaryOperation, class T >
constexpr OutputIt transform_inclusive_scan( InputIt first, InputIt last,
OutputIt d_first,
BinaryOperation binary_op,
UnaryOperation unary_op,
T init );
// since C++17
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
class T, class BinaryOperation, class UnaryOperation >
ForwardIt2 transform_exclusive_scan( ExecutionPolicy&& policy,
ForwardIt1 first, ForwardIt1 last,
ForwardIt2 d_first, T init,
BinaryOperation binary_op,
UnaryOperation unary_op );
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
class BinaryOperation, class UnaryOperation >
ForwardIt2 transform_inclusive_scan( ExecutionPolicy&& policy,
ForwardIt1 first, ForwardIt1 last,
ForwardIt2 d_first,
BinaryOperation binary_op,
UnaryOperation unary_op );
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
class BinaryOperation, class UnaryOperation, class T >
ForwardIt2 transform_inclusive_scan( ExecutionPolicy&& policy,
ForwardIt1 first, ForwardIt1 last,
ForwardIt2 d_first,
BinaryOperation binary_op,
UnaryOperation unary_op,
T init );
// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <iterator>
#include <functional>
#include <numeric>
using namespace std;
int main() {
vector data {3, 1, 4, 1, 5, 9, 2, 6};
auto times_10 = [](int x) { return x * 10; };
cout << "10 times exclusive sum: ";
transform_exclusive_scan(data.begin(), data.end(),
ostream_iterator<int>(cout, " "), 0,
plus<int>{}, times_10);
cout << endl;
cout << "10 times inclusive sum: ";
transform_inclusive_scan(data.begin(), data.end(),
ostream_iterator<int>(cout, " "),
plus<int>{}, times_10);
cout << endl;
return 0;
}
/*
$ g++ test.cpp -std=c++17
$ ./a.out
10 times exclusive sum: 0 30 40 80 90 140 230 250
10 times inclusive sum: 30 40 80 90 140 230 250 310
*/
