「ソートも、サーチも、あるんだよ」
～標準C++ライブラリにみるアルゴリズムの面白さ

＜algorithm＞のソートたち

ソート列を対象とする集合演算

　最後に紹介するのはソートされた列を集合としたときの各種集合演算です。

includes:包含 X⊃Y

　 集合Yの全要素が集合Xに含まれるとき、trueを返します。

set_union:和集合 X∪Y

　X,Yのいずれかに含まれる要素からなる集合を作ります。

set_intersection:積集合 X∩Y

　X,Yの両方に含まれる要素からなる集合を作ります。

set_difference:差集合 X＼Y

　Xの要素のうちYに含まれない要素からなる集合を作ります。

set_symmetric_difference:対称差 XΔY

　X,Yのいずれか一方にのみ含まれる要素からなる集合を作ります。

array<int,20> num  = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20 };
array<int,10> mul2 = { 2,4,6,8,10,12,14,16,18,20 };
array<int,6>  mul3 = { 3,6,9,12,15,18 };
array<int,20> result;

// 包含
cout << boolalpha;
cout << "num  includes mul2 : " << includes(num.begin(),  num.end(),  mul2.begin(), mul2.end()) << endl;
cout << "mul2 includes mul3 : " << includes(mul2.begin(), mul2.end(), mul3.begin(), mul3.end()) << endl;

array<int,20>::iterator last;

// 和
last = set_union(mul2.begin(), mul2.end(), mul3.begin(), mul3.end(), result.begin());
cout << "               set_union : "; 
for_each(result.begin(), last, [](int x) { cout << x << ' '; });
cout << endl;

// 積
last = set_intersection(mul2.begin(), mul2.end(), mul3.begin(), mul3.end(), result.begin());
cout << "        set_intersection : "; 
for_each(result.begin(), last, [](int x) { cout << x << ' '; });
cout << endl;

// 差
last = set_difference(mul2.begin(), mul2.end(), mul3.begin(), mul3.end(), result.begin());
cout << "          set_difference : "; 
for_each(result.begin(), last, [](int x) { cout << x << ' '; });
cout << endl;

// 対称差
last = set_symmetric_difference(mul2.begin(), mul2.end(), mul3.begin(), mul3.end(), result.begin());
cout << "set_symmetric_difference : "; 
for_each(result.begin(), last, [](int x) { cout << x << ' '; });
cout << endl;

　おまけにこれら集合演算をC#の拡張メソッドで実装してみました。積集合（X∩Y）を以下に示します。

using System;
using System.Collections.Generic;

namespace CodeZine.Episteme.Extension {
  /// <summary>
  /// 昇順にソートされた集合を対象とする操作群
  /// </summary>
  public static class SetOperations {
    public static IEnumerable<T> 
      SetIntersection<T>(this IEnumerable<T> setX, 
                              IEnumerable<T> setY, 
                              Comparison<T> comp) {
      IEnumerator<T> X = setX.GetEnumerator();
      IEnumerator<T> Y = setY.GetEnumerator();
      bool hasmoreX = X.MoveNext();
      bool hasmoreY = Y.MoveNext();
      while ( hasmoreX && hasmoreY ) {
        int c = comp(X.Current, Y.Current);
        if ( c < 0 ) {
          hasmoreX = X.MoveNext();
        } else if ( c > 0 ) {
          hasmoreY = Y.MoveNext();
        } else {
          yield return X.Current;
          hasmoreX = X.MoveNext();
          hasmoreY = Y.MoveNext();
        }
      }
    }
  }
}

　残る集合演算は添付ソリューションに納めておきました。

新刊のお知らせ

　8月9日、C++の書籍『ストラウストラップのプログラミング入門』が出ます。C++の産みの親、Dr.Bjarne StroustrupのC++によるプログラミング入門書です。入門書のくせに1,000ページを超えてます。入門者だけでなく、C++を基礎からみっちり叩き込みたい方ぜひどうぞ。