从可变列表中删除元素 [英] 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屋!