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 中有等效的代码，还是必须进行过滤或区分？

编辑：澄清一下，我想分开选择和删除。我想标记一个元素，以便以后可以快速访问、修改和删除它。如果我也可以在选定的元素之后插入另一个元素，那就太好了。这就是 C++ 迭代器提供的功能。

4

2 回答 2

3

举个例子（当然还有其他的，但你scala.collection.mutable.ArrayBuffer没有说你对什么收藏感兴趣，所以我只挑了一个）：

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

这与您的 C++ 版本的语义相同（但它仍然是 O(n)，就像 C++ 版本一样）。

于 2012-07-20T08:06:14.307 回答
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)。

于 2012-07-20T09:20:01.430 回答