[C/C++標準ライブラリ][初級][交差と補完]


シーン:
1.stdを計算する::vectorAとstd::vectorBの同じ要素を削除しないように保持する.
2.stdを計算する::vectorAとstd::vectorBのそれぞれの補完セットは、Aの補完セットを削除し、Bの補完セットを追加するために使用され、関連テーブルを更新する操作に使用される.例えば連絡先Aが属するグループBは集合BVであり、連絡先Aの属するグループを
集合CVに変更するには、2つの集合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;
}