セット

キーワード

セット

セット

数学などにおいては、「集合（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 インターフェースを実装します。