List copy semantics efficiency

This is a discussion on List copy semantics efficiency within the C++ Programming forums, part of the General Programming Boards category; If you have an iterator pointing to the last element then you could not delete the item it points to ...

  1. #16
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,395
    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. 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, deleting as you go, it would be O(n*n).
    I'm pretty sure this would be the main reason why there is no tail pointer.
    You're both wrong. They just made a decision; they wanted iterators to be faster on average. Nothing about an iterator for a singly linked list suggests that an implementation of 'erase' or 'insert' can't be O(1).

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

    Soma

  2. #17
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    Quote Originally Posted by iMalc View Post
    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.

    Quote 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.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  3. #18
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by CornedBee View Post
    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.
    Last edited by iMalc; 05-23-2008 at 04:33 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #19
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,395
    Depends on how you look at it.
    It doesn't depend on how you look at it. It is simply one option for implementation.

    The same for insert, because insert inserts before the iterator.
    Which is why I took care to list 'insert' as well as 'erase', 'insert_after' is obviously constant.

    So you have a choice between sane invalidation semantics and constant time.
    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.

    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.
    *shrug*

    It has been a while. I may have simply been wrong about the distributer.

    Soma

  5. #20
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by phantomotap View Post
    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).
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #21
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,395
    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).
    Correct? Color me confused...

    Soma

  7. #22
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    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.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  8. #23
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,395
    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
    Last edited by phantomotap; 05-23-2008 at 08:52 AM.

  9. #24
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    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.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  10. #25
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Such an iterator would invalidate iterators to other nodes than the one erased?
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  11. #26
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    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.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  12. #27
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,395
    By the way, the question that started this discussion is, why doesn't the list itself hold a pointer to the last node?
    O_o

    I joined the discussion because suggestions were made that 'insert' and 'erase' must be O(n) for a singly linked list.

    I continued with the discussion when you suggested that for those methods to be constant a "two pointer" iterator implementation must be used. (I erased this bit of the relevant post because iMalc had just described a "one before" iterator.)

    I remained to post an explanation because you didn't bother to understand what was posted or simply didn't read the posts. (How can you have thought anyone was saying that the "two pointer" approach would be slower than a single pointer approach? Your the only person to bring that up.)

    As for that question, from my perspective it isn't worth discussing without knowing the exact implementation details. It might have been consider too expensive, it may have been an oversight, it may even cache a pointer to the last node and not provide access to it, etc..

    Soma

  13. #28
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    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?
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  14. #29
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,395
    O_o

    Correcting you is derisive?
    Explaining a situation is derisive?

    *shrug*

    Even PeterB isn't that sensitive. (That statement and this one is derisive.)

    Soma

  15. #30
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    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.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

Page 2 of 3 FirstFirst 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. SO new to C++
    By black_spot1984 in forum C++ Programming
    Replies: 5
    Last Post: 09-30-2008, 02:32 AM
  2. deleting a node in linked list
    By BoneXXX in forum C Programming
    Replies: 18
    Last Post: 12-17-2007, 12:30 PM
  3. urgent help please...
    By peter_hii in forum C++ Programming
    Replies: 11
    Last Post: 10-30-2006, 06:37 AM
  4. Replies: 3
    Last Post: 03-04-2005, 02:46 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21