Geek Answers Handbook

Removing items from modified lists

I want to select an item and then remove it from the mutable list O (1) times. 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);

Is it possible to have equivalent code in Scala, or do I need to do a filter or diff?

Edit: To clarify, I want to separate selection and deletion. I want to mark an element so that it can be quickly retrieved, changed, and possibly deleted. It would be great if I could insert another element after the selected one. What the C ++ functionality iterators give.

+1
source share
2 answers

If you want to remove O (1), I think your only option is to search for the corresponding internal linked lists (with next ) and save the link.

If you use mutable.DoubleLinkedList , the situation will become a little 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 full mirror with the mutable C ++ iterator interface.

I'm not sure if there is a valid Scala list that will support something like this. An alternative would be to use Zipper , which also provides O (1) for operations in the zipper position.

+3
source

Look at scala.collection.mutable.ArrayBuffer for example (there are, of course, others, but you did not say which collection you are interested in, so I just chose one):

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

This is the same semantics as your C ++ version (but it is still O (n), like the C ++ version).

+3
source

More articles:


All Articles