1

要素を選択し、O（1）時間で可変リストから削除したいと思います。C++で私はすることができました 

std::list<Foo> lst;
std::list<Foo>::iterator it = //some choice
//And then, possibly in another function,
lst.erase(it);

Scalaで同等のコードを使用できますか、それともfilterまたはdiffを実行する必要がありますか？

編集：明確にするために、私は選択と削除を分離したいと思います。後ですばやくアクセス、変更、場合によっては削除できるように、要素にマークを付けたいと思います。選択した要素の後に別の要素を挿入できれば素晴らしいと思います。これがC++イテレータが提供する機能です。

4

2 に答える 2

3

O(1) の削除を行いたい場合、唯一のオプションは、それぞれの内部のリンクされたリストを ( でnext) 検索し、参照を保持することだと思います。

ものを使用するmutable.DoubleLinkedListと、少し簡単になります：

val li = DoubleLinkedList(1,2,3,4,5,6)
val elem = li.next.next.next // O(< n) until you find what you want
elem.remove() // O(1)

li == DoubleLinkedList(1,2,3,5,6)

しかし、それでも、C++ の変更可能な反復子インターフェイスの完全なミラーはありません。

そのようなものをサポートする適切な Scala リストがあるかどうかはわかりません。別の提案は、ジッパーの位置での操作に O(1) も提供するZipperを使用することです。

于 2012-07-20T09:20:01.430 に答える
3

例を見てくださいscala.collection.mutable.ArrayBuffer(もちろん他にもありますが、あなたがどのコレクションに興味を持っているかを言わなかったので、私は 1 つだけ選びました):

val a = ArrayBuffer(1, 2, 3, 4)
a -= 3

これは、C++ バージョンと同じセマンティクスです (ただし、C++ バージョンと同様に、O(n) のままです)。

于 2012-07-20T08:06:14.307 に答える