# Benjamin

## 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 阅读(10066) 评论(0)  编辑 收藏 引用 所属分类: 泛型编程

 只有注册用户登录后才能发表评论。 相关文章: