Forum Navigation

Insert in the middle of a list?

Moderators: larsivi kris

Ansible

Joined: 03/04/07

Posts: 8

Posted: 03/10/07 06:05:03

Ummm... I'm sure this will seem obvious in hindsight, but right now I can't seem to figure out how to insert an item into the middle of an LinkSeq?, using an iterator as a reference point. I see how to add it using an integer index, but it seems like there should be a way to do it using an iterator in an o(1) operation. Am I missing something here?

Author Message

torhu

Joined: 03/31/06

Posts: 69

Posted: 03/10/07 13:48:41

Seems to me you can't. And from browsing the docs and source, it might be faster to implementent your own linked list class than to try to figure out how to add that feature to Tango's.

larsivi

Joined: 03/27/04

Posts: 614

Posted: 03/10/07 14:01:48

The typical problem with modifying the collection in an iterator, is that it is not an operation that is guaranteed to be successful using D's foreach. Also when not using foreach, this is not usually an efficient thing to do as a general solution needs to account for the possibility that the collection is shared between threads, and thus modification needs to lock the resource.

Ansible

Joined: 03/04/07

Posts: 8

Posted: 03/10/07 15:05:23

I see that the iterators in Tango get invalidated if the collection has been modified. I guess that model is why the function is not available, because the iterator would be corrupted as a result. But using an insert at the front or insert by int index will also corrupt the iterator, so I don't see why that's a good reason not to have iterator based insert. You could have the iterator insert return a valid iterator so you wouldn't lose your place, something like this (specific types are probably wrong here):

Iterator!(T) addAfter(Iterator!(T) here, T element) {

<splice 'element' in after 'here'> <make a new iterator pointing at 'element'> return newiter;

}

Then you'd use it like this:

iter = list.addAfter(iter, "new item");

Re the multithread protection: doesn't any insert have to keep track of multithread access, whether it uses an iterator or not? It seems like inserting an item at the front of a list or at an int index would have the same multithread protection overhead.