/*******************************************************************************
STL通用算法：                   Description：
1、非修正序列算法           不对其所作用的容器进行修改
2、修正序列算法             对其所作用的容器进行修改
3、排序算法                 对容器的内容进行不同方式的排序
4、数值算法                 对容器的内容进行数值计算
*******************************************************************************/

#include "stdafx.h"
#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
using namespace std;
////////////////////////////////////////////////////////////////////////////////////////////////////////////
第一类通用算法---非修正序列算法
////////////////////////////////////////////////////////////////////////////////////////////////////////////
/*******************************************************
 Function:  adjacent_find(first,last)
 Description： 搜索重复对
 Parameter：     搜索时的起始位置
 Return：      返回在该区间第一个重复的对.
 By:       capter
 Date:   2005-12-23
*******************************************************/

int _tmain(int argc, _TCHAR* argv[])
{
 multiset<int> intset;
 intset.insert(10);
 intset.insert(3);
 intset.insert(1);
 intset.insert(3);
 intset.insert(8);
 intset.insert(8);
 intset.insert(5);
 //显示该多重集合
 multiset<int>::iterator iter;
 for(iter=intset.begin(); iter!=intset.end(); iter++)
  cout<<*iter<<" ";
 cout<<endl;

 //查找第一个相等的值
 iter = adjacent_find(intset.begin(),intset.end());
 cout<<*iter<<endl;
 iter++;
 cout<<*iter<<endl;
 return 0;
}

/*******************************************************
 Function:      count(first,last,val)
 Description：     计算val出现的次数
 Parameter：     搜索时的起始位置和要计算的值
 Return：      返回出现的次数
 By:       capter
 Date:       2005-12-23
*******************************************************/
int main()
{
 multiset<int> intset;
 intset.insert(10);
 intset.insert(6);
 intset.insert(1);
 intset.insert(3);
 intset.insert(6);
 intset.insert(2);
 intset.insert(3);
 //显示该多重集合的值
 multiset<int>::iterator iter;
 for(iter=intset.begin(); iter!=intset.end(); iter++)
  cout<<*iter<<" ";
 cout<<endl;
 //搜索数字3出现的次数
 int n = count(intset.begin(),intset.end(),3);
 cout<<"数字3在该多重集合中共出现了："<<n<<"次"<<endl;
 return 0;
}

/*******************************************************
 Function:      for_each(first,last,func)
 Description：     对first,last范围内每个元素执行func定义的函数
 Parameter：     first,last要执行元素的范围，func自己定义的函数
 By:       capter
 Date:       2005-12-23
*******************************************************/
void showvalue(int x)
{
 cout<<x<<" ";
}

int main()
{
 multiset<int> intset;
 intset.insert(10);
 intset.insert(6);
 intset.insert(1);
 intset.insert(3);
 intset.insert(6);
 intset.insert(2);
 intset.insert(3);
 //显示该多重集合的值
 for_each(intset.begin(),intset.end(),showvalue);
 cout<<endl;
 return 0;
}
//////////////////////////////////////////////////
第一类--非修正序列算法还有其他函数
equal(first,last,first2)
find(first,last,val)
find_end(first,last,first2,last2)
find_first(first,last,first2,last2)
mismatch(first,last,first2)
search(first,last,first2,last2)
//////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////////////////////////////////
第二类通用算法---修正序列算法
////////////////////////////////////////////////////////////////////////////////////////////////////////////
/*******************************************************
 Function:      fill(first,last,val)
 Description：     把val的值赋给first,last中所有的元素
 Parameter：     起始位置和要赋的值
 By:       capter
 Date:       2005-12-23
*******************************************************/
void showvalue(int x)
{
 cout<<x<<" ";
}
int main()
{
 vector<int> intvector;
 for(int x=0;x<10;x++)
        intvector.push_back(x);
 //显示该向量的内容
 for_each(intvector.begin(),intvector.end(),showvalue);
 cout<<endl;
 //填充该值
 fill(intvector.begin(),intvector.begin()+5,0);
 //显示填充后的值
 for_each(intvector.begin(),intvector.end(),showvalue);
 cout<<endl;
 return 0;
}

/*******************************************************
 Function:      random_shuffle(first,last)
 Description：     在指示器first,last中随机排列元素
 Parameter：     起始位置
 By:       capter
 Date:       2005-12-23
*******************************************************/
void showvalue(int x)
{
 cout<<x<<" ";
}

int main()
{
 vector<int> intvector;
 for(int x=0;x<10;x++)
  intvector.push_back(x);
 //显示该向量的值
 for_each(intvector.begin(),intvector.end(),showvalue);
 cout<<endl;
 //对该向量进行随机排序
 random_shuffle(intvector.begin(),intvector.end());
 //显示随机排序后的值
 for_each(intvector.begin(),intvector.end(),showvalue);
 cout<<endl;
 return 0;
}

/*******************************************************
 Function:      partition(first,last,pred)
 Description：     在指示器first,last中经过谓词的判断后一分为二
 Parameter：     起始位置和谓词
 By:       capter
 Date:       2005-12-23
*******************************************************/
void showvalue(int x)
{
 cout<<x<<" ";
}
//谓词函数
bool equals5(int val)
{
 return (val == 5);
}
int main()
{
 vector<int> intvector;
 intvector.push_back(8);
 intvector.push_back(5);
 intvector.push_back(7);
 intvector.push_back(5);
 intvector.push_back(2);
 intvector.push_back(5);

 //显示该向量的内容
 for_each(intvector.begin(),intvector.end(),showvalue);
 cout<<endl;
 //对该向量进行分段
 partition(intvector.begin(),intvector.end(),equals5);

 //显示新内容
 for_each(intvector.begin(),intvector.end(),showvalue);
 cout<<endl;
 return 0;
}

/*******************************************************
 Function:      rotate(first,middle,last)
 Description：     把从middle到last的元素旋转到first范围处
 Parameter：     起始位置和开始旋转位置
 By:       capter
 Date:       2005-12-23
*******************************************************/
void showvalue(char x)
{
 cout<<x<<" ";
}

int main()
{
 vector<char> charvector;
    for(int i=0;i<10;i++)
     charvector.push_back(65+i);

 //显示向量内容
 for_each(charvector.begin(),charvector.end(),showvalue);
 cout<<endl;
 //旋转
 rotate(charvector.begin(),charvector.begin()+6,charvector.end());
 //显示旋转后的内容
 for_each(charvector.begin(),charvector.end(),showvalue);
 cout<<endl;
 return 0;
}
//////////////////////////////////////////////////
copy(first,last,first2)
copy_backward(first,last,first2)
generate(first,last,func)
remove(first,last,val)
replace(first,last,val1,val2)
reverse(first,last)
swap(it1,it2)
swap_ranges(first,last,first2)
transform(first,last,first2,func)
unique(first,last)
//////////////////////////////////////////////////

/////////////////////////////////////////////////////////////////////////////////////////////////////
第三类通用算法---排序算法
/////////////////////////////////////////////////////////////////////////////////////////////////////

/*******************************************************
 Function:      sort(first,last)
 Description：     排序
 Parameter：     起始位置
 By:       capter
 Date:       2005-12-23
*******************************************************/
void show(char val)
{
 cout<<val<<" ";
}
int main()
{
 vector<char> charvector;
 charvector.push_back('Z');
 charvector.push_back('D');
 charvector.push_back('F');
 charvector.push_back('S');
 charvector.push_back('A');
 charvector.push_back('Q');
 charvector.push_back('C');
 charvector.push_back('G');
 charvector.push_back('M');
 charvector.push_back('Y');
 //显示向量
 for_each(charvector.begin(),charvector.end(),show);
 cout<<endl;
 //排序
 sort(charvector.begin(),charvector.end());
 //显示排序后的向量
 for_each(charvector.begin(),charvector.end(),show);
 cout<<endl;
 return 0;
}

/*******************************************************
 Function:  partial_sort(first,middle,last)
 Description： 进行偏序排序
 Parameter：     起始位置
 By:       capter
 Date:   2005-12-23
*******************************************************/
void show(string val)
{
 cout<<val<<endl;
}
int main()
{
 vector<string> strvector;
 strvector.push_back("zebra");
 strvector.push_back("deer");
 strvector.push_back("fish");
 strvector.push_back("snake");
 strvector.push_back("bat");
 strvector.push_back("cat");
 strvector.push_back("bird");
 strvector.push_back("turtle");
 strvector.push_back("horse");
 strvector.push_back("cow");
 //显示向量内容
 for_each(strvector.begin(),strvector.end(),show);
 cout<<endl;
 //进行偏序排序
 partial_sort(strvector.begin(),strvector.begin()+5,strvector.end());
 //显示排序后的内容
 for_each(strvector.begin(),strvector.end(),show);
 cout<<endl;
 return 0;
}

/*******************************************************
 Function:      nth_element(first,nth,last)
 Description：     排序
 Parameter：     起始位置
 By:       capter
 Date:       2005-12-23
*******************************************************/
void show(string val)
{
 cout<<val<<endl;
}
int main()
{
 vector<string> strvector;
 strvector.push_back("zebra");
 strvector.push_back("deer");
 strvector.push_back("fish");
 strvector.push_back("snake");
 strvector.push_back("bat");
 strvector.push_back("cat");
 strvector.push_back("bird");
 strvector.push_back("turtle");
 strvector.push_back("horse");
 strvector.push_back("cow");
 //显示向量内容
 for_each(strvector.begin(),strvector.end(),show);
 cout<<endl;
 //进行偏序排序
 nth_element(strvector.begin(),strvector.begin()+5,strvector.end());
 //显示排序后的内容
 for_each(strvector.begin(),strvector.end(),show);
 cout<<endl;
 return 0;
}

/*******************************************************
 Function:      merge(first,last,first2,last2,result)
 Description：     合并排序
 Parameter：     起始位置和结果集
 By:       capter
 Date:       2005-12-23
*******************************************************/
void show(string val)
{
 cout<<val<<endl;
}
int main()
{
 vector<string>  strvector1,strvector2;
 vector<string>  strvector3(10);
 strvector1.push_back("zebra");
 strvector1.push_back("deer");
 strvector1.push_back("fish");
 strvector1.push_back("snake");
 strvector1.push_back("bat");

 strvector2.push_back("cat");
 strvector2.push_back("bird");
 strvector2.push_back("turtle");
 strvector2.push_back("horse");
 strvector2.push_back("cow");
 //显示向量内容
 for_each(strvector1.begin(),strvector1.end(),show);
 cout<<endl;
 //显示排序后的内容
 for_each(strvector2.begin(),strvector2.end(),show);
 cout<<endl;
 sort(strvector1.begin(),strvector1.end());
 sort(strvector2.begin(),strvector2.end());
 merge(strvector1.begin(),strvector1.end(),strvector2.begin(),strvector2.end(),strvector3.begin());
 //显示排序后的结果
 for_each(strvector3.begin(),strvector3.end(),show);
 cout<<endl;
 return 0;
}
/////////////////////////////////////////////////////////////////////
第二种通用算法还有以下几种
binary_search(first,last,val)
equal_range(first,last,val)
includes(first,last,first2,last2)
lexicographical_compare(first,last,first2,last2)
lower_bound(first,last,val)
make_heap(first,last)
max(val1,val2)
max_element(first,last)
min(val1,val2)
next_permutation(first,last)
partial_sort_copy(first,last,first2,last2);
pop_heap(first,last)
prev_permutation(first,last)
push_heap(first,last)
set_difference(first,last,first2,last2,result)
set_intersection(first,last,first2,last2,result)
set_symmetric_difference(first,last,first2,last2,result)
set_union(first,last,first2,last2,result)
sort(first,last)
sort_heap(first,last)
stable_sort(first,last)
upper_bound(first,last,val)
////////////////////////////////////////////////////////////////////

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////
第四种算法---数值算法
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/*******************************************************
 Function:      accumulate(first,last,init)
 Description：     求和
 Parameter：     起始位置和初始参数
 Return：           结果
 By:       capter
 Date:       2005-12-23
*******************************************************/
void show(int x)
{
 cout<<x<<" ";
}

int main()
{
 vector<int> intvector;
 for(int x=0; x<5; ++x)
  intvector.push_back(x);
 //显示内容
 for_each(intvector.begin(),intvector.end(),show);
 //求和
 int result = accumulate(intvector.begin(),intvector.end(),5);
 cout<<result<<endl;
 return 0;
}

/*******************************************************
 Function:      inner_product(first,last,first2,init)
 Description：     两向量对应的值相加，然后再求和
 Parameter：     起始位置和初始参数
 Return：           结果
 By:       capter
 Date:       2005-12-23
*******************************************************/
void show(int x)
{
 cout<<x<<" ";
}

int main()
{
 vector<int> vector1,vector2;
 for(int i=0;i<5;i++)
  vector1.push_back(i);
 for(int i=2;i<7;i++)
  vector2.push_back(i);
 for_each(vector1.begin(),vector1.end(),show);
 cout<<endl;
 for_each(vector2.begin(),vector2.end(),show);
 cout<<endl;

 int result = inner_product(vector1.begin(),vector1.end(),vector2.begin(),0);
 cout<<result<<endl;
 
 return 0;
}

/*******************************************************
 Function:      partial_sum(first,last,first2,init)
 Description：     求部分和
 Parameter：     起始位置和初始参数
 Return：           结果
 By:       capter
 Date:       2005-12-23
*******************************************************/
void show(int x)
{
 cout<<x<<" ";
}

int main()
{
 vector<int> vector1;
 vector<int> vector2(5);
 for(int i=2;i<7;++i)
  vector1.push_back(i);
 //显示向量内容
 for_each(vector1.begin(),vector1.end(),show);
 cout<<endl;
 //求部分和
 partial_sum(vector1.begin(),vector1.end(),vector2.begin());
 //显示求和后的结果
 for_each(vector2.begin(),vector2.end(),show);
 cout<<endl;

 return 0;
}

/*******************************************************
 Function:      adjacent_difference(first,last,first2,result)
 Description：     两向量对应的值相加，然后再求和
 Parameter：     起始位置和初始参数
 Return：           结果
 By:       capter
 Date:       2005-12-23
*******************************************************/
void show(int x)
{
 cout<<x<<" ";
}

int main()
{
 vector<int> vector1;
 vector<int> vector2(5);
 vector1.push_back(3);
 vector1.push_back(4);
 vector1.push_back(12);
 vector1.push_back(6);
 vector1.push_back(10);

    显示向量内容
 for_each(vector1.begin(),vector1.end(),show);
 cout<<endl;
 求部分差
 adjacent_difference(vector1.begin(),vector1.end(),vector2.begin());
 显示求和后的结果
 for_each(vector2.begin(),vector2.end(),show);
 cout<<endl;

 return 0;
}