セット

セット

数学などにおいては、 「集合（set）」というと、 要素を包含するかどうかだけが問題で、 挿入された順序等は意味を持ちません。

ということで、要素の順序は関係ないという状況下で、 要素の挿入・削除・検索を高速で行えるようなコレクションをセット（set）と呼びましょう。 （「集合」だとコレクションと紛らわしいので、英語のままにしておきます。 ちなみに、数学用語的には、collection は「集まり」と訳します。）

ソート済み配列、 ハッシュテーブル、 2分探索木等は全てこの要件を満たしています。 要するに、これらはいずれもセットと呼ぶに値する機能を持っています。 そこで、セットは、以下のようなインターフェースとして定義します。

/// <summary>
/// セット。
/// 数学で「集合」と呼ぶ奴。
/// 要素の順序には意味がなくて、要素が含まれているかどうかだけが問題。
/// </summary>
/// <typeparam name="T">要素の型</typeparam>
interface ISet<T> : IEnumerable<T>
{
  /// <summary>
  /// 新しい要素の挿入。
  /// </summary>
  /// <param name="elem">新しい要素</param>
  void Insert(T elem);

  /// <summary>
  /// 要素の削除。
  /// </summary>
  /// <param name="elem">削除したい要素</param>
  void Erase(T elem);

  /// <summary>
  /// 要素を含むかどうか。
  /// </summary>
  /// <param name="elem">検索したい要素</param>
  /// <returns>見つかった場合 true</returns>
  bool Contains(T elem);
}

ソート済み配列、 ハッシュテーブル、 2分探索木は、 この ISet インターフェースを実装します。

サンプルソース

C# サンプルソースを示します。

Set.cs