参考：《STL源码剖析》第6章 算法
#include <iostream>
#include <vector>
#include <functional>
/*********************************************************************/
template<class InputIterator, class T>
T accumulate(InputIterator first, InputIterator last, T init)
{
for (; first != last; ++first){
init = init + *first;
}
return init;
}
template<class InputIterator, class T, class BinaryOp>
T accumulate(InputIterator first, InputIterator last, T init, BinaryOp f)
{
for (; first != last; ++first){
init = f(init, *first);
}
return init;
}
int multi(int a, int b)
{
return a*b;
}
/*********************************************************************/
template<class InputIterator, class OutputIterator>
OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result)
{
*result = *first;
auto value = *first;
while (++first != last){
auto tmp = *first; // 这一步很重要，避免result与first相同产生错误
*++result = tmp - value;
value = tmp;
}
return ++result;
}
/*********************************************************************/
template<class T>
T power(T x, int n)
{
static int cnt = 0;
cnt++;
if (n == 0){
std::cout << "cnt is "<<cnt << std::endl;
return 1;
}
return x*power(x, n - 1);
}
template<class T>
T power_2(T x, int n)
{
static int cnt = 0;
cnt++;
if (n == 0){
std::cout << "cnt is " << cnt << std::endl;
return 1;
}
if (n & 0x1){
// n 为奇数
int result = power_2(x, n >> 1);
return x*result*result;
}
else{
// n 为偶数
int result = power_2(x, n >> 1);
return result*result;
}
}
/*********************************************************************/
template<class InputIterator>
void for_each(InputIterator first, InputIterator last)
{
for (; first != last; ++first){
std::cout << *first << std::endl;
}
}
template<class InputIterator, class UnaryOp>
void for_each(InputIterator first, InputIterator last, UnaryOp op)
{
for (; first != last; ++first){
op(*first);
}
}
template<class T>
void display(T t)
{
std::cout << t << std::endl;
}
template<class T>
class Display
{
public:
void operator()(const T &t){
std::cout << t << std::endl;
}
};
/*********************************************************************/
template<class T>
T max(const T &a, const T &b)
{
return a > b ? a : b;
}
template<class T, class BinaryOp>
T max(const T &a, const T &b, BinaryOp cmp)
{
return cmp(a,b)? a : b;
}
template<class T>
bool cmp(const T &a, const T &b)
{
return a < b;
}
/*********************************************************************/
template<class InputIterator1, class InputIterator2, class BinaryOp>
std::pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2,
BinaryOp op)
{
for (; first1 != last1; ++first1, ++first2){
if (!op(*first1, *first2)){
break;
}
}
return std::make_pair(first1, first2);
}
struct int2
{
int value;
};
bool cmp_int_int2(int a, const int2 &b)
{
return a == b.value;
}
/*********************************************************************/
template<class ForwardIterator/*, class BinaryOp*/>
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last/*, BinaryOp op*/)
{
for (; first+1 != last;++first){
if (*first == *(first + 1)){
return first;
}
}
return last;
}
/*********************************************************************/
// sorted 为前提
template<class InputIterator, class OutputIterator>
OutputIterator merge(InputIterator first1, InputIterator last1,
InputIterator first2, InputIterator last2,
OutputIterator result)
{
while (first1 != last1 && first2 != last2){
if (*first1 < *first2){
*result = *first1;
++first1;
}
else{
*result = *first2;
++first2;
}
++result;
}
while (first1 != last1){
*result++ = *first1++;
}
while (first2 != last2){
*result++ = *first2++;
}
return result;
}
/*********************************************************************/
template<class InputIterator>
void iterator_swap(InputIterator first, InputIterator second)
{
auto tmp = *first;
*first = *second;
*second = tmp;
}
template<class BidirectionalIterator, class Predicate>
BidirectionalIterator partition(BidirectionalIterator first, BidirectionalIterator last, Predicate unaryop)
{
while (true){
// left
while (true){
if (first == last){
return first;
}
if (unaryop(*first)){
++first;
}
else{
break;
}
}
// right
--last;
while (true){
if (first == last){
return first;
}
if (!unaryop(*last)){
--last;
}
else{
break;
}
}
// swap
iterator_swap(first, last);
// next
++first;
}
}
bool parity(int n)
{
return n & 0x1;
}
/*********************************************************************/
// greateast common divisor ==> gcd
// 辗转相除法 求 最大公约数
// int big = a > b ? a : b;
// int little = a < b ? a : b;
int gcd(int big, int little)
{
if (big % little == 0){
return little;
}
return gcd(little, big%little);
}
/*********************************************************************/
template<class ForwardIterator>
int my_distance(ForwardIterator first, ForwardIterator last)
{
int len = 0;
while (first != last){
len++;
first++;
}
return len;
}
template<class ForwardIterator>
ForwardIterator my_advance(ForwardIterator first, int steps)
{
while (steps--){
first++;
}
return first;
}
template<class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T &value)
{
int len = my_distance(first, last);
std::cout << len << std::endl;
int half = 0;
ForwardIterator middle;
while (len > 0){
half = len >> 1;
middle = my_advance(first, half);
std::cout << *middle << std::endl;
if (*middle < value){
first = middle;
++first;
len = len - half -1;
}
else{
len = half;
}
}
return first;
}
void test_lower_bound()
{
std::vector<int> v = {12,17,20,21,22,23,30,33,40};
std::vector<int>::iterator iter = lower_bound(v.begin(), v.end(), 21);
std::cout << *iter << std::endl;
}
template<class ForwardIterator, class T>
bool my_binary_search(ForwardIterator first, ForwardIterator last, const T &value)
{
ForwardIterator iter = lower_bound(first, last, value);
return iter != last && !(value<*iter);
}
void test_binary_search()
{
std::vector<int> v = { 12, 17, 20, 21, 22, 23, 30, 33, 40 };
std::cout << my_binary_search(v.begin(), v.end(), 27) << std::endl;
}
/*********************************************************************/
int main()
{
std::vector<int> v = { 1, 2, 3, 4, 5 };
int result = accumulate(v.begin(), v.end(), 0);
//std::cout << result << std::endl;
for_each(v.begin(), v.end());
result = accumulate(v.begin(), v.end(), 1, multi);
std::cout << result << std::endl;
result = accumulate(v.begin(), v.end(), 0, std::plus<int>());
std::cout << result << std::endl;
result = accumulate(v.begin(), v.end(), 1, std::multiplies<int>());
std::cout << result << std::endl;
adjacent_difference(v.begin(), v.end(), v.begin());
//for (auto e : v){
// std::cout << e << std::endl;
//}
for_each(v.begin(), v.end(), Display<int>());
std::cout << power(2, 25) << std::endl;
std::cout << power_2(2, 25) << std::endl;
std::cout << max(4, 7) << std::endl;
std::cout << max(4, 7, cmp<int>) << std::endl;
std::vector<int> v1 = { 1, 2, 3, 4, 5 };
std::vector<int2> v2 = { { 1 }, { 2 }, { 5 }, { 4 }, { 5 } };
std::pair<std::vector<int>::iterator, std::vector<int2>::iterator> result_pair = mismatch(v1.begin(), v1.end(), v2.begin(), cmp_int_int2);
std::cout << *result_pair.first << " " << result_pair.second->value << std::endl;
std::vector<int> v3 = { 1, 2, 3, 3, 5 };
std::vector<int>::iterator iter = adjacent_find<std::vector<int>::iterator>(v3.begin(), v3.end());
std::cout << "adjacent find " << *iter << " " << *(iter + 1) << std::endl;
std::vector<int> v4;
v4.resize(v1.size() + v3.size());
merge(v1.begin(), v1.end(), v3.begin(), v3.end(), v4.begin());
for_each(v4.begin(), v4.end());
std::cout << std::endl;
partition(v4.begin(), v4.end(), parity);
for_each(v4.begin(), v4.end());
std::cout << "gcd(4,10)= " << gcd(4, 10) << std::endl;
std::cout << "gcd(123456, 7890)= " << gcd(123456, 7890) << std::endl;
test_lower_bound();
test_binary_search();
return 0;
}
2. set的4个操作
#include <set>
void SetTest()
{
std::set<int> s = { 1, 4, 2, 5, 7, 3 };
std::set<int> s2 = { 1, 4, 33};
std::vector<int> result(s.size() + s2.size());
std::set_union(s.begin(), s.end(), s2.begin(), s2.end(), result.begin());
std::for_each(result.begin(), result.end(), [](int a){cout << a << " "; });
cout << endl;
std::fill(result.begin(),result.end(),0);
std::set_intersection(s.begin(), s.end(), s2.begin(), s2.end(), result.begin());
std::for_each(result.begin(), result.end(), [](int a){cout << a << " "; });
cout << endl;
std::fill(result.begin(), result.end(), 0);
std::set_difference(s.begin(), s.end(), s2.begin(), s2.end(), result.begin());
std::for_each(result.begin(), result.end(), [](int a){cout << a << " "; });
cout << endl;
std::fill(result.begin(), result.end(), 0);
// (s-s2)U(s2-s)
std::set_symmetric_difference(s.begin(), s.end(), s2.begin(), s2.end(), result.begin());
std::for_each(result.begin(), result.end(), [](int a){cout << a << " "; });
cout << endl;
}