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