メインメニューを開く

セット (抽象データ型)

計算機科学における抽象データ型の一種

セット: set)や集合とは、プログラミングで用いられる抽象データ型の一種。順序のないデータの集まりを表現する抽象データ型であり、同一のデータは一つしか含まれないことが保証される。

目次

重複したデータの挿入編集

データの同一性は与えられた比較関数で判定されるので、外の文脈で同一かどうかは関数依存である。例えば文字列"hoge"と"HOGE"は異なるデータと見ることもできるし、小文字化したものを比較すれば同一のデータと見ることもできるといった具合である。

そのような重複するデータを挿入しようとした場合はこれを処理する必要がある。

  • 無視する
  • 新しい物で置き換える
  • 多重化する(→マルチセット参照)

狭義のセットにおいては重複データは無視されるか新しいデータで置き換えるかされる。もしここで多重化することを選択した場合は複数回の削除を行わなければ値は完全に取り除かれない。

アクセス速度は実装により様々だが、二分木(TreeSet)やハッシュテーブル(HashSet)などのデータ構造を用いて高速化を図ることが多い。

その他の抽象データ型との違い編集

  • リストはそれぞれのデータに順序が定義される点が異なる。
  • 配列は順序が定義されるほか、静的配列ではさらに格納可能な要素数が変更できない。
  • マルチセットは同じデータを複数格納できるが、狭義のセットでは重複したデータは無視される。マルチセットはbagとも呼ばれる。

各プログラミング言語におけるセット編集

参照編集

関連項目編集