マップトップ列トレイトSeq, IndexedSeq, およびLinearSeq集合目次

集合

集合(Set)とは、重複する要素を含まないIterableです。 集合に対する演算は、一般的な集合については次の表に要約でき、 可変な集合についてはその後の表に要約できます。 演算は次のカテゴリに分類できます:

クラスSet内の演算
何であるか何をするか
テスト:
xs contains x xxsの要素であるか調べる。
xs(x) xs contains xと同じ。
xs subsetOf ys xsysの部分集合であるか調べる。
追加:
xs + x xsの全ての要素とxを含む集合。
xs + (x, y, z) xsの全ての要素と与えられた追加の要素を含む集合。
xs ++ ys xsの全ての要素とysの全ての要素を含む集合。
削除:
xs - x x以外のxsの全ての要素を含む集合。
xs - (x, y, z) 与えられた要素以外のxsの全ての要素を含む集合。
xs -- ys ysの全ての要素以外のxsの全ての要素を含む集合。
xs.empty xsと同じクラスの空集合。
二項演算:
xs & ys xsysの集合積。
xs intersect ys xs & ysと同じ。
xs | ys xsysの集合和。
xs union ys xs | ysと同じ。
xs &~ ys xsysの集合差。
xs diff ys xs &~ ysと同じ。

可変な集合はこの表に要約できるように、要素を追加・削除・更新するメソッドをさらに提供します。

クラスmutable.Set内の演算
何であるか何をするか
追加:
xs += x xsに要素xを副作用として追加し、xs自身を返す。
xs += (x, y, z) xsに与えられた要素を副作用として追加し、xs自身を返す。
xs ++= ys xsysの全ての要素を副作用として追加し、xs自身を返す。
xs add x xsに要素xを追加し、xが集合に含まれていなかったならtrue、含まれていたならfalseを返す。
削除:
xs -= x xsから要素xを副作用として取り除き、xs自身を返す。
xs -= (x, y, z) xsから与えられた要素を副作用として取り除き、xs自身を返す。
xs --= ys xsからysの全ての要素を副作用として取り除き、xs自身を返す。
xs remove x xsから要素xを取り除き、xが集合に含まれていたならtrue、含まれていなかったならfalseを返す。
xs retain p 述語pを満たすxsの要素のみを残す。
xs.clear() xsから全ての要素xを取り除く。
更新:
xs(x) = b (または書き下してxs.update(x, b)) もし真偽値の引数btrueであればxxsに追加し、そうでなければxxsから取り除く。
複製:
xs.clone xsと同じ要素を持つ新しい可変な集合。

不変な集合のように、可変な集合は要素の追加のために+および++演算を提供し、 要素の削除のために-および--演算を提供します。 しかしそれらは可変な集合では要素のコピーを伴うためあまり使われません。 より効率的な代わりとして更新メソッド+=および-=を提供します。 演算s += elemは集合selemを副作用として追加し、変更した集合を結果として返します。 同様にs -= elemは集合からelemを削除し、変更した集合を結果として返します。 +=および-=と関連して、一括演算である++=および--=もあり、 トラバーサブルまたはイテレータの全ての要素を追加または削除します。

メソッド名として+=および-=を選んだ結果、 可変な集合と不変な集合でよく似たコードが動作します。 まず不変な集合sを使った以下のREPLでの対話を考えます:

scala> var s = Set(123)
s: scala.collection.immutable.Set[Int] = Set(1, 2, 3)
scala> s += 4
scala> s -= 2
scala> s
res2: scala.collection.immutable.Set[Int] = Set(1, 3, 4)

ここでimmutable.Set型のvarに対して+=および-=を使いました。 s += 4のような式はs = s + 4の略です。 そのため、これは追加メソッド+を集合sに対して呼び出し、その結果を変数sに代入します。 ここで可変な集合による似たインタラクションを考えます。

scala> val s = collection.mutable.Set(123)
s: scala.collection.mutable.Set[Int] = Set(1, 2, 3)
scala> s += 4
res3: s.type = Set(1, 4, 2, 3)
scala> s -= 2
res4: s.type = Set(1, 4, 3)

最終的な効果は前のインタラクションととても似ています。 まずSet(1, 2, 3)から始めてSet(1, 3, 4)を得ました。 しかし、文としては以前と似ていても、これらは違うことをしています。 s += 4は可変な集合s+=メソッドを呼び出し、集合を直接変えています。 同様にs -= 2は同じ集合の-=メソッドを呼び出します。

2つのインタラクションを比較すると重要な原則が現れます。 多くの場合、valで保持している可変なコレクションはvarで保持している不変なコレクションで置き替えられ、その逆も成り立ちます。 これはコレクションを直接更新したのか新しいコレクションを作ったのか分かるような別の参照が無いかぎり成り立ちます。

可変な集合は+=および-=の変種としてaddおよびremoveを提供します。 違いとしてはaddおよびremoveは演算が効果があったか示すBooleanの結果を返します。

可変な集合の現在のデフォルト実装は要素の格納にハッシュテーブルを使います。 不変な集合のデフォルト実装は集合の要素数に合わせた表現を使います。 空の要素はシングルトンオブジェクトで表わされます。 大きさが4までの集合は全ての要素をフィールドとして保持する1つのオブジェクトとして表わされます。 それ以上の大きさでは、不変な集合はハッシュトライで実装されます。

このような表現方法の選択の結果、小さな(4ぐらいまでの)集合であれば、不変な集合は可変な集合よりもよりコンパクトで効率的です。 そのため、もし集合のサイズが小さいと期待できるなら不変にしてみてください。

集合の子トレイトとしてSortedSetおよびBitSetの2つがあります。 それらに関しては独立したページで説明します。

続いては:


マップトップ列トレイトSeq, IndexedSeq, およびLinearSeq集合目次