STL源码剖析——set相关算法
程序员文章站
2022-03-23 11:35:43
...
STL 提供了4中与set集合相关算法
- 并集set_union
- 交集set_intersection
- 差集set_difference
- 对称差集set_symmetric_difference
四个算法所接受的set,必须在有序区间,元素值得重复出现,可以接受STL的set/multiset(改叫unordered_set)容器作为输入区间。
函数都提供了两个版本的函数原型:第一个版本是采用默认的排序比较方式operator<;第二个版本是用户通过仿函数comp自行指定排序方式。
使用他们必须包含< algorithm>
set_union
存在于[first1, last1)或存在于[first2, last2)内的所有元素
//并集,求存在于[first1, last1)或存在于[first2, last2)内的所有元素
//注意:输入区间必须是已排序
//版本一,默认是operator<操作的排序方式
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result) {
//两个区间都尚未到达区间尾端,执行以下操作
while (first1 != last1 && first2 != last2) {
/*在两区间内分别移动迭代器,首先将元素较小者(假设为A区)记录在目标区result
移动A区迭代器使其前进;同时另一个区的迭代器不变。然后进行一次新的比较,
记录较小值,移动迭代器...直到两区间中有一个到达尾端。若两区间存在元素相等,
默认记录第一区间的元素到目标区result.*/
if (*first1 < *first2) {
*result = *first1;
++first1;
}
else if (*first2 < *first1) {
*result = *first2;
++first2;
}
else {
*result = *first1;
++first1;
++first2;
}
++result;
}
/*只要两区间之中有一个区间到达尾端,就结束上面的while循环
以下将尚未到达尾端的区间剩余的元素拷贝到目标区
此刻,[first1, last1)和[first2, last2)至少有一个是空区间*/
return copy(first2, last2, copy(first1, last1, result));
}
//版本二,用户根据仿函数comp指定排序规则
template <class InputIterator1, class InputIterator2, class OutputIterator,class Compare>
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp) {
while (first1 != last1 && first2 != last2) {
if (comp(*first1, *first2)) {
*result = *first1;
++first1;
}
else if (comp(*first2, *first1)) {
*result = *first2;
++first2;
}
else {
*result = *first1;
++first1;
++first2;
}
++result;
}
return copy(first2, last2, copy(first1, last1, result));
}
set_intersection
存在于[first1, last1)且存在于[first2, last2)内的所有元素
//交集,求存在于[first1, last1)且存在于[first2, last2)内的所有元素
//注意:输入区间必须是已排序
//版本一,默认是operator<操作的排序方式
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result) {
//若两个区间都尚未到达尾端,则执行以下操作
while (first1 != last1 && first2 != last2)
//在两个区间分别移动迭代器,直到遇到相等元素,记录到目标区
//继续移动迭代器...直到两区间之中有一区到达尾端
if (*first1 < *first2)
++first1;
else if (*first2 < *first1)
++first2;
else {
*result = *first1;
++first1;
++first2;
++result;
}
return result;
}
//版本二,用户根据仿函数comp指定排序规则
template <class InputIterator1, class InputIterator2, class OutputIterator,
class Compare>
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp) {
while (first1 != last1 && first2 != last2)
if (comp(*first1, *first2))
++first1;
else if (comp(*first2, *first1))
++first2;
else {
*result = *first1;
++first1;
++first2;
++result;
}
return result;
}
set_difference
存在于[first1, last1)且不存在于[first2, last2)内的所有元素
//差集,求存在于[first1, last1)且不存在于[first2, last2)内的所有元素
//注意:输入区间必须是已排序
//版本一,默认是operator<操作的排序方式
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result) {
//若两个区间都尚未到达尾端,则执行以下操作
while (first1 != last1 && first2 != last2)
/*在两个区间分别移动迭代器,当第一区间元素等于第二区间元素时,表示两区间共同存在该元素
则同时移动迭代器;
当第一区间元素大于第二区间元素时,就让第二区间迭代器前进;
第一区间元素小于第二区间元素时,把第一区间元素记录到目标区
继续移动迭代器...直到两区间之中有到达尾端*/
if (*first1 < *first2) {
*result = *first1;
++first1;
++result;
}
else if (*first2 < *first1)
++first2;
else {
++first1;
++first2;
}
//若第二区间先到达尾端,则把第一区间剩余的元素复制到目标区
return copy(first1, last1, result);
}
//版本二,用户根据仿函数comp指定排序规则
template <class InputIterator1, class InputIterator2, class OutputIterator,
class Compare>
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp) {
while (first1 != last1 && first2 != last2)
if (comp(*first1, *first2)) {
*result = *first1;
++first1;
++result;
}
else if (comp(*first2, *first1))
++first2;
else {
++first1;
++first2;
}
return copy(first1, last1, result);
}
set_symmetric_difference
存在于[first1, last1)但不存在于[first2, last2)内的所有元素以及出现在[first2, last2)但不出现在[first1, last1)的所有元素
//对称差集,求存在于[first1, last1)但不存在于[first2, last2)内的所有元素以及出现在[first2, last2)但不出现在[first1, last1)的所有元素
//注意:输入区间必须是已排序
//版本一,默认是operator<操作的排序方式
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_symmetric_difference(InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2,
InputIterator2 last2,
OutputIterator result) {
//若两个区间都尚未到达尾端,则执行下面的操作
while (first1 != last1 && first2 != last2)
/*在两区间内分别移动迭代器。当两区间内的元素相等,就让两区同时前进;
当两区间内的元素不等,就记录较小值于目标区,并令较小值所在区间前进*/
if (*first1 < *first2) {
*result = *first1;
++first1;
++result;
}
else if (*first2 < *first1) {
*result = *first2;
++first2;
++result;
}
else {
++first1;
++first2;
}
return copy(first2, last2, copy(first1, last1, result));
}
//版本二,用户根据仿函数comp指定排序规则
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) {
while (first1 != last1 && first2 != last2)
if (comp(*first1, *first2)) {
*result = *first1;
++first1;
++result;
}
else if (comp(*first2, *first1)) {
*result = *first2;
++first2;
++result;
}
else {
++first1;
++first2;
}
return copy(first2, last2, copy(first1, last1, result));
}
测试
#include<algorithm>
#include<set>
#include<iterator>
#include<iostream>
using namespace std;
template<typename T>
struct display{
void operator()(const T& x) const{
cout << x << " ";
}
};
int main(){
int ia[] = { 1, 3, 5, 7, 9, 11 };
int ib[] = { 1, 1, 2, 3, 5, 8, 13 };
multiset<int> s1(begin(ia), end(ia));
multiset<int> s2(begin(ib), end(ib));
for_each(s1.begin(), s1.end(), display<int>());
cout << endl;
for_each(s2.begin(), s2.end(), display<int>());
cout << endl;
multiset<int>::iterator first1 = s1.begin();
multiset<int>::iterator last1 = s1.end();
multiset<int>::iterator first2 = s2.begin();
multiset<int>::iterator last2 = s2.end();
cout << "union of s1 and s2:";
set_union(first1, last1, first2, last2, ostream_iterator<int>(cout, " "));
cout << endl;
cout << "intersection of s1 and s2:";
set_intersection(first1, last1, first2, last2, ostream_iterator<int>(cout, " "));
cout << endl;
cout << "difference of s1 and s2:";
set_difference(first1, last1, first2, last2, ostream_iterator<int>(cout, " "));
cout << endl;
cout << "symmetric differenceof s1 and s2:";
set_symmetric_difference(first1, last1, first2, last2, ostream_iterator<int>(cout, " "));
cout << endl;
system("pause");
return 0;
}
上一篇: 对象的构造与析构