从可变列表中删除元素 [英] Removing elements from mutable lists

问题描述

我想选择一个元素，然后在 O(1) 时间内将其从可变列表中删除.在 C++ 中我可以做

I want to choose an element and then remove it from a mutable list in O(1) time. In C++ I could do

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

我可以在 Scala 中使用等效的代码，还是必须进行过滤或差异处理?

Can I have equivalent code in Scala, or do I have to do filter or diff?

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

to clarify, I want to separate choice and removal. I want to mark an element so that it can be later quickly accessed, modified and possibly removed. It would be great if I could insert another element after the selected one too. That's the functionality C++ iterators give.

推荐答案

如果你想做 O(1) 移除，我认为你唯一的选择是搜索各自的内部链表(使用 next) 并保留参考.

If you want to do O(1) removal, I think your only option is to search the respective inner linked lists (with next) and keep a reference.

如果你使用 mutable.DoubleLinkedList 事情会变得容易一些:

If you use a mutable.DoubleLinkedList things will become a bit easier:

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++ 可变迭代器接口的完整镜像.

But even then, you won’t have a complete mirror of C++s mutable iterator interface.

我不确定是否有合适的 Scala 列表可以支持类似的内容.另一种建议是使用 Zipper 它还为拉链位置的操作提供了 O(1).

I am not sure there is a proper Scala list which would support something like that. An alternative suggestion would be to use a Zipper which also provides O(1) for operations at the position of the zipper.

这篇关于从可变列表中删除元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！