CODEWITHSUNDEEP
scala
Karolis Juodelė
Karolis Juodelė

Reputation: 3771

Removing elements from mutable lists

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);

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

Edit: 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.

Upvotes: 1

Views: 4604

Answers (2)

Debilski
Debilski

Reputation: 67898

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.

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)

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

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.

Upvotes: 3

Derek Wyatt
Derek Wyatt

Reputation: 2727

Look at scala.collection.mutable.ArrayBuffer for example (there are others, of course, but you didn't say what collection you were interested in, so I just picked one):

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

That's the same semantics as your C++ version (but it's still O(n), just like the C++ version).

Upvotes: 3

Related Questions