场景:
1. 计算std::vector A和 std::vector B里的同样的元素, 用于保留不删除.
2. 计算std::vector A和 std::vector B里各自的补集, 用于删除A的补集和加入B的补集，用在一些更新关联表的操作里. 比方联系人A所属分组B是一个集合BV, 把联系人A的所属分组
改动为集合CV, 就须要删除两个集合BV,CV的CV补集和新增BV补集.
3. C++标准库为我们提供了这些算法.
代码:
// test_AndroidAssistant.cpp : 定义控制台应用程序的入口点。
// #include "stdafx.h"
#include <algorithm>
#include <vector>
#include <string>
#include <iostream> #include "gtest/gtest.h" TEST(test_AndroidAssistant,SetIntersection)
{
std::vector<int> v1;
v1.push_back(3);
v1.push_back(121);
v1.push_back(5); std::vector<int> v2;
v2.push_back(2);
v2.push_back(89);
v2.push_back(3);
v2.push_back(5); std::sort(v1.begin(),v1.end());
std::sort(v2.begin(),v2.end()); std::vector<int> result;
std::set_intersection(v1.begin(),v1.end(),v2.begin(),v2.end(),std::back_inserter(result)); std::cout << "set_intersection" << std::endl;
for(int i = 0; i< result.size(); ++i)
{
std::cout << result[i] << std::endl;
} std::vector<int> d1;
std::vector<int> d2;
std::cout << "set_different" << std::endl;
//Copies the elements from the sorted range [first1, last1)
// which are not found in the sorted range [first2, last2) to the range beginning at d_first
std::set_difference(v1.begin(),v1.end(),result.begin(),result.end(),std::back_inserter(d1));
std::set_difference(v2.begin(),v2.end(),result.begin(),result.end(),std::back_inserter(d2)); std::cout << "set_difference d1" << std::endl;
for(int i = 0; i< d1.size(); ++i)
{
std::cout << d1[i] << std::endl;
} std::cout << "set_difference d2" << std::endl;
for(int i = 0; i< d2.size(); ++i)
{
std::cout << d2[i] << std::endl;
}
} int _tmain(int argc, _TCHAR* argv[])
{
testing::InitGoogleTest(&argc, argv);
RUN_ALL_TESTS();
return 0;
}
输出:
set_intersection
3
5
set_different
set_difference d1
121
set_difference d2
2
89
注意: 这里 std::back_inserter 是创建输出枚举类型.
看下set_intersection 的实现非常巧妙:
template<class InputIt1, class InputIt2, class OutputIt>
OutputIt set_intersection(InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
OutputIt d_first)
{
while (first1 != last1 && first2 != last2) {
if (*first1 < *first2) {
++first1;
} else {
if (!(*first2 < *first1)) {
*d_first++ = *first1++;
}
++first2;
}
}
return d_first;
}
再看下set_difference的实现非常巧妙:
template<class InputIt1, class InputIt2, class OutputIt>
OutputIt set_difference(InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
OutputIt d_first)
{
while (first1 != last1) {
if (first2 == last2) return std::copy(first1, last1, d_first); if (*first1 < *first2) {
*d_first++ = *first1++;
} else {
if (! (*first2 < *first1)) {
++first1;
}
++first2;
}
}
return d_first;
}