Thread: List copy semantics efficiency

Originally Posted by iMalc

If you have an iterator pointing to the last element then you could not delete the item it points to AND correctly update the ltail pointer in anything less than O(n) time.

And that contradicts my point how?

That's on top of the fact that iterating through the list is also O(n). Therefore if you were to iterate over the list backwards,

Iterating backwards over a singly-linked list is O(n*n) already.

deleting as you go, it would be O(n*n).

Actually, it would even be O(n*n*n), because making the iterator valid after erasing its element is O(n) too. Unless you use erase_after and decrement before erasing. But erase_after is O(1), with or without a tail pointer.

I'm pretty sure this would be the main reason why there is no tail pointer.

Nope, still wrong.

Originally Posted by phantomatap

Nothing about an iterator for a singly linked list suggests that an implementation of 'erase' or 'insert' can't be O(1).

Depends on how you look at it. To have an erase or insert method be O(1), the iterator needs to consist of two pointers: one to the current node, and one to the node before it. That's because erase kills the current element, requiring the previous one for relinking. If it's not available, it must be searched, which is O(n). The same for insert, because insert inserts before the iterator. (That's why forward_list has insert_after and erase_after.)
Now, the semantics of std::list was that erase and insert invalidate only iterators pointing to the erased node (i.e. none for insert). If you want the same thing for forward_list, your iterators can't contain two pointers, though: erasing the node directly before an iterator's location would invalidate that iterator. So would inserting a node at the location. (The iterator's prev pointer now points to a node two away.)
So you have a choice between sane invalidation semantics and constant time.

Example: I think DinkumWare provides the 'slist' class as an extension to the STL where 'insert' and 'erase' are constant.

Their pop_back is linear. insert and erase talk of reallocation and invalidating all iterators beyond the current position, which makes me highly curious about their implementation.

SGI claims amortized constant time for their erase() and insert(), but those of the GNU C++ library, which is derived from SGI's, are most definitely linear, so I don't know where those claims come from.

Originally Posted by CornedBee

And that contradicts my point how?

Iterating backwards over a singly-linked list is O(n*n) already.

Yeah alright, fair point.

Actually, it would even be O(n*n*n), because making the iterator valid after erasing its element is O(n) too. Unless you use erase_after and decrement before erasing. But erase_after is O(1), with or without a tail pointer.

Nope, still wrong.

I was actually thinking more along the lines of if you had an array of iterators to every item in the list and deleted those items from those iterators in reverse order. I knew what I was thinking of was correct, I just accidentally and carelessly shortcutted my description of what I was thinking of. Yes I realise nobody would do such a stupid thing. Well I wont claim it's the most likely reason I guess. There's certainly more reasons that would have weighed in on it though.

Depends on how you look at it. To have an erase or insert method be O(1), the iterator needs to consist of two pointers: one to the current node, and one to the node before it. That's because erase kills the current element, requiring the previous one for relinking. If it's not available, it must be searched, which is O(n). The same for insert, because insert inserts before the iterator. (That's why forward_list has insert_after and erase_after.)
Now, the semantics of std::list was that erase and insert invalidate only iterators pointing to the erased node (i.e. none for insert). If you want the same thing for forward_list, your iterators can't contain two pointers, though: erasing the node directly before an iterator's location would invalidate that iterator. So would inserting a node at the location. (The iterator's prev pointer now points to a node two away.)
So you have a choice between sane invalidation semantics and constant time.

Nope, there's another alternative you haven't considered. An iterator could consist of a pointer to the next pointer of the previous node. Another way of thinking about it is that you don't need that second pointer because you can get it by following form the first one. Anyway, This approach means that accessing the value of an iterator is a double-dereference, but it certainly allows for constant time deletion and doesn't invalidate many iterators.
Deletion of the item before the one an iterator points to invalidates that iterator, or put another way, deleting an item results in invalidating any iterators to that item and the one after. Bah it could be worse.
I know they might not do that because iterators become slightly more expensive and two iterators are invalidated rather than one upon deletion, but it's not really that bad.

Their pop_back is linear. insert and erase talk of reallocation and invalidating all iterators beyond the current position, which makes me highly curious about their implementation.

Yeah it makes me "highly curious" as well to say the least. A vector or deque in disguise, or something like that, methinks.

Originally Posted by phantomotap

Nope. You have a choice between trivially efficient 'operator *', 'operator ->', 'insert_after', and 'erase_after' and slightly slower 'operator *', 'operator ->', a "normal" 'insert', and a "normal" 'erase'. This decision is more pressing.

That's exactly it. I guess they wouldn't go for it when every man and his dog would then complain that their home made one was faster (and actually be correct).

How would a single-pointer iterator be faster on dereference and insert/erase_after than the two-pointer iterator I described? The only thing that's faster (by one assignment, which probably amounts to nothing in real-world use cases) is incrementing. And they're smaller, of course.

How would a single-pointer iterator be faster on dereference and insert/erase_after than the two-pointer iterator I described?

Uh... I thought you were just kidding or something about the "two-pointer iterator" for a singly linked list. A list where each node links to the previous node and the next node is a doubly linked list. A list where an iterator points to a node and a previous node has a broken iterator implementation.

The comparison was between a traditional forward iterator for a singly linked list and a "one before" iterator for a singly linked list; both such iterators have only pointer and do not place any additional demands on the singly linked list node implementation.

Edit: Discussing a "two-pointer iterator" for a singly linked list is pointless.

Soma

You seem to have seriously misunderstood my post. The only part that is relevant is this:

A list where an iterator points to a node and a previous node has a broken iterator implementation.

And you give absolutely no argument as to why that is so.

Such an iterator would invalidate iterators to other nodes than the one erased?

Yes, but that also applies to the point-to-previous-node iterator. All the double pointer iterator does is trade the cost of the second dereferencing for the cost of holding a second pointer.

By the way, the question that started this discussion is, why doesn't the list itself hold a pointer to the last node? We seem to have lost track of this.

And at which point of that did you decide to deride me for thinking you were talking about what the other people in the discussion were talking?

The way you "corrected" me was derisive, yes. And I'm not so sensitive that you hurt my feelings, but I noticed it and I disapprove.