Benjamin

静以修身,俭以养德,非澹薄无以明志,非宁静无以致远。
随笔 - 279, 文章 - 0, 评论 - 196, 引用 - 0
数据加载中……

STL算法(Algorithms):合并(Merge)

1、merge:将两个序列合并成一个新的序列,并对新的序列排序
原型:
template <class InputIterator1, class InputIterator2, class OutputIterator>
  OutputIterator merge ( InputIterator1 first1, InputIterator1 last1,
                         InputIterator2 first2, InputIterator2 last2,OutputIterator result );
template <class InputIterator1, class InputIterator2,class OutputIterator, class Compare>
OutputIterator merge ( InputIterator1 first1, InputIterator1 last1,
                         InputIterator2 first2, InputIterator2 last2,OutputIterator result, Compare comp );
示例:

// merge algorithm example
#include <iostream>
#include 
<algorithm>
#include 
<vector>
using namespace std;

int main () {
  
int first[] = {5,10,15,20,25};
  
int second[] = {50,40,30,20,10};
  vector
<int> v(10);
  vector
<int>::iterator it;

  sort (first,first
+5);
  sort (second,second
+5);
  merge (first,first
+5,second,second+5,v.begin());

  cout 
<< "The resulting vector contains:";
  
for (it=v.begin(); it!=v.end(); ++it)
    cout 
<< " " << *it;

  cout 
<< endl;
  
  
return 0;
}



2、inplace_merge:将两个序列合并成一个新的序列,并对新的序列进行归并排序(这两个序列必须要进过排序)
原型:
template <class BidirectionalIterator>
void inplace_merge ( BidirectionalIterator first, BidirectionalIterator middle,
                       BidirectionalIterator last );

template <class BidirectionalIterator, class Compare>
 void inplace_merge ( BidirectionalIterator first, BidirectionalIterator middle,
                       BidirectionalIterator last, Compare comp );
示例:

// inplace_merge example
#include <iostream>
#include 
<algorithm>
#include 
<vector>
using namespace std;

int main () {
  
int first[] = {5,10,15,20,25};
  
int second[] = {50,40,30,20,10};
  vector
<int> v(10);
  vector
<int>::iterator it;

  sort (first,first
+5);
  sort (second,second
+5);

  copy (first,first
+5,v.begin());
  copy (second,second
+5,v.begin()+5);

  inplace_merge (v.begin(),v.begin()
+5,v.end());

  cout 
<< "The resulting vector contains:";
  
for (it=v.begin(); it!=v.end(); ++it)
    cout 
<< " " << *it;

  cout 
<< endl;
  
  
return 0;
}


 

3、includes:测试是一个序列是否在另一个序列中
原型:
template <class InputIterator1, class InputIterator2>
bool includes ( InputIterator1 first1, InputIterator1 last1,
                InputIterator2 first2, InputIterator2 last2 );
template <class InputIterator1, class InputIterator2, class Compare>
bool includes ( InputIterator1 first1, InputIterator1 last1,
                InputIterator2 first2, InputIterator2 last2, Compare comp );
示例:

// includes algorithm example
#include <iostream>
#include 
<algorithm>
using namespace std;

bool myfunction (int i, int j) { return i<j; }

int main () {
  
int container[] = {5,10,15,20,25,30,35,40,45,50};
  
int continent[] = {40,30,20,10};

  sort (container,container
+10);
  sort (continent,continent
+4);

  
// using default comparison:
  if ( includes(container,container+10,continent,continent+4) )
    cout 
<< "container includes continent!" << endl;

  
// using myfunction as comp:
  if ( includes(container,container+10,continent,continent+4, myfunction) )
    cout 
<< "container includes continent!" << endl;

  
return 0;
}


 

4、set_union:和merge类似,不过新序列中没有重复的元素
原型:
template <class InputIterator1, class InputIterator2, class OutputIterator> 
OutputIterator set_union ( InputIterator1 first1, InputIterator1 last1,         
                           InputIterator2 first2, InputIterator2 last2,OutputIterator result );
template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> 
OutputIterator set_union ( InputIterator1 first1, InputIterator1 last1,
                           InputIterator2 first2, InputIterator2 last2,OutputIterator result, Compare comp );
示例:

// set_union example
#include <iostream>
#include 
<algorithm>
#include 
<vector>
using namespace std;

int main () {
  
int first[] = {5,10,15,20,25};
  
int second[] = {50,40,30,20,10};
  vector
<int> v(10);                           // 0  0  0  0  0  0  0  0  0  0
  vector<int>::iterator it;

  sort (first,first
+5);     //  5 10 15 20 25
  sort (second,second+5);   // 10 20 30 40 50

  it
=set_union (first, first+5, second, second+5, v.begin());
                                               
// 5 10 15 20 25 30 40 50  0  0

  cout 
<< "union has " << int(it - v.begin()) << " elements.\n";

  
return 0;
}


 

5、set_intersection:两个序列的交集
原型:
template <class InputIterator1, class InputIterator2, class OutputIterator> 
OutputIterator set_intersection ( InputIterator1 first1, InputIterator1 last1,
                                  InputIterator2 first2, InputIterator2 last2,OutputIterator result );
template <class InputIterator1, class InputIterator2,class OutputIterator, class Compare>
OutputIterator set_intersection ( InputIterator1 first1, InputIterator1 last1,
                                  InputIterator2 first2, InputIterator2 last2,OutputIterator result, Compare comp );
示例:

// set_intersection example
#include <iostream>
#include 
<algorithm>
#include 
<vector>
using namespace std;

int main () {
  
int first[] = {5,10,15,20,25};
  
int second[] = {50,40,30,20,10};
  vector
<int> v(10);                           // 0  0  0  0  0  0  0  0  0  0
  vector<int>::iterator it;

  sort (first,first
+5);     //  5 10 15 20 25
  sort (second,second+5);   // 10 20 30 40 50

  it
=set_intersection (first, first+5, second, second+5, v.begin());
                                               
// 10 20 0  0  0  0  0  0  0  0

  cout 
<< "intersection has " << int(it - v.begin()) << " elements.\n";

  
return 0;
}


 

6、set_difference:序列(first1,last1)不在序列(first2,last2)中的元素
原型:
template <class InputIterator1, class InputIterator2, class OutputIterator> 
OutputIterator set_intersection ( InputIterator1 first1, InputIterator1 last1,
      InputIterator2 first2, InputIterator2 last2,outputIterator result );
template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> 
OutputIterator set_intersection ( InputIterator1 first1, InputIterator1 last1,
                                  InputIterator2 first2, InputIterator2 last2,OutputIterator result, Compare comp );
示例:

// set_difference example
#include <iostream>
#include 
<algorithm>
#include 
<vector>
using namespace std;

int main () {
  
int first[] = {5,10,15,20,25};
  
int second[] = {50,40,30,20,10};
  vector
<int> v(10);                           // 0  0  0  0  0  0  0  0  0  0
  vector<int>::iterator it;

  sort (first,first
+5);     //  5 10 15 20 25
  sort (second,second+5);   // 10 20 30 40 50

  it
=set_difference (first, first+5, second, second+5, v.begin());
                                               
// 5 15 25  0  0  0  0  0  0  0

  cout 
<< "difference has " << int(it - v.begin()) << " elements.\n";

  
return 0;
}


 

7、set_symmetric_difference:所有不在序列(first1,last1)和序列(first2,last2)中的元素
原型:
template <class InputIterator1, class InputIterator2, class OutputIterator> 
OutputIterator    set_symmetric_difference ( InputIterator1 first1, InputIterator1 last1,
                                             InputIterator2 first2, InputIterator2 last2,OutputIterator result );
template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator    set_symmetric_difference ( InputIterator1 first1, InputIterator1 last1,
                                             InputIterator2 first2, InputIterator2 last2,OutputIterator result, Compare comp );
示例:

// set_symmetric_difference example
#include <iostream>
#include 
<algorithm>
#include 
<vector>
using namespace std;

int main () {
  
int first[] = {5,10,15,20,25};
  
int second[] = {50,40,30,20,10};
  vector
<int> v(10);                           // 0  0  0  0  0  0  0  0  0  0
  vector<int>::iterator it;

  sort (first,first
+5);     //  5 10 15 20 25
  sort (second,second+5);   // 10 20 30 40 50

  it
=set_symmetric_difference (first, first+5, second, second+5, v.begin());
                                               
// 5 15 25 30 40 50  0  0  0  0

  cout 
<< "symmetric difference has " << int(it - v.begin()) << " elements.\n";

  
return 0;
}


posted on 2012-02-05 21:33 Benjamin 阅读(9844) 评论(0)  编辑 收藏 引用 所属分类: 泛型编程


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理