Linked List

This is a discussion on Linked List within the C++ Programming forums, part of the General Programming Boards category; A weak_ptr is not a direct replacement for a plain pointer, because it has to be associated with some shared_ptr ...

  1. #16
    The larch
    Join Date
    May 2006
    Posts
    3,573
    A weak_ptr is not a direct replacement for a plain pointer, because it has to be associated with some shared_ptr that actually manages the memory.

    You can't just drop in shared_ptr's because nodes refer to each other.

    With a plain pointer it is trivial to establish who owns the nodes: the list class itself.

    With smart pointers it's making my head hurt. So each node owns the following node, but doesn't own the previous node?
    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).

  2. #17
    C++ Junkie Mozza314's Avatar
    Join Date
    Jan 2011
    Location
    Australia
    Posts
    174
    Good point, I've exposed a hole in my knowledge here. What I intended though was to make a pointer wrapper class emulating a pointer and use that.

  3. #18
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Posts
    23,012
    Quote Originally Posted by anon View Post
    With smart pointers it's making my head hurt. So each node owns the following node, but doesn't own the previous node?
    Sounds logical to me.
    Node A owns node B; thus node B cannot own node A.
    A linked list is a trivial example where you have to think a little and not just throw in shared pointers. Which is a good exercise.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  4. #19
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Good point, I've exposed a hole in my knowledge here. What I intended though was to make a pointer wrapper class emulating a pointer and use that.
    I think something like auto_ptr or unique_ptr should have virtually no overhead. I guess a linked list would be possible where the next pointer is stored in a unique_ptr and the previous pointer in a unique_ptr with a do-nothing deleter.

    But then again, I don't quite see the usefulness of smart pointers when implementing basic data types. The hardest part, IMO, about writing a linked list is hooking up the nodes correctly (which using an assortment of smart pointers can only make more difficult) and managing memory is trivial compared to that.
    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).

  5. #20
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Posts
    23,012
    Quote Originally Posted by anon View Post
    ...The hardest part, IMO, about writing a linked list is hooking up the nodes correctly (which using an assortment of smart pointers can only make more difficult) and managing memory is trivial compared to that.
    Not difficult at all, if you just think about it. And a little experience. Which is why it's such a good exercise.
    In a single linked list, it's super easy. Put in shared_ptr or unique_ptr and you're done.
    With double linked lists, you must make sure no node is owned by more than one. If you think about it, since the linked list class itself has a pointer to the first node, the node after the first node cannot have a shared_ptr to its previous node since it's owned by the class. Thus, all previous pointers should be weak_ptr and you're done.
    Great exercise to learn about the problems with smart pointers which you really have to deal with in real code anyway.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  6. #21
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by Mozza314 View Post
    Don't implement operator[] - linked list are not for random access, it's inefficient to have to traverse an average of half the list to get an element out.
    Finally, someone else who points out this kind of thing! I wholeheartedly agree.

    You should keep track of the size of the list as you add and remove elements so that when you call length() you can return a number straight away. Traversing the list just for this is extremely inefficient!
    GCC actually walks the list to get the size. The reason that some implementations do and some don't is that there is a trade off between constant time size() and linear time splice() vs linear time size() and constant time splice(). Can't do both in constant time.


    C++ has the notion that you only pay for what you use. If you don't need a smart pointer in there then you should not be forced to. Simply allow the user of the class to use a smart pointer as their templated type.

    Or you mean as the links themselves? That's actually not a good idea. If you utilised that to automatically delete the whole list by deleting just the first node say, then you end up with a recursive delete and could blow the stack, for example.
    In a list, nodes don't own subsequent nodes. It's just a sequence. Enforcing some kind of ownership semantics where it doesn't belong is just wrong.
    Last edited by iMalc; 02-23-2011 at 12:23 PM.
    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"

  7. #22
    C++ Junkie Mozza314's Avatar
    Join Date
    Jan 2011
    Location
    Australia
    Posts
    174
    Quote Originally Posted by iMalc View Post
    GCC actually walks the list to get the size. The reason that some implementations do and some don't is that there is a trade off between constant time size() and linear time splice() vs linear time size() and constant time splice(). Can't do both in constant time.
    I actually learned about this complication just the other day flicking through Scott Meyers' "Effective STL". Really makes the point that you should never do

    Code:
    someList.size() == 0
    since that can be linear time and you have the perfectly appropriate empty() function you can use instead.

    Of course, if you're not implementing splice(), size() should be constant time.

    I just took a look at the GNU STL implementation. I'm somewhat shocked that it always traverses the list to do size(), I thought at least it would return a known size when it could. I suppose there is an overhead to doing that, but surely it's minimal. I definitely won't be calling list::size() without giving it a second thought from now on.

  8. #23
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by Mozza314 View Post
    I actually learned about this complication just the other day flicking through Scott Meyers' "Effective STL". Really makes the point that you should never do

    Code:
    someList.size() == 0
    since that can be linear time and you have the perfectly appropriate empty() function you can use instead.
    I find myself reasonably often bringing this up in code reviews or running into it in older code. Other's at work only use Microsoft's compilers, and simply don't know that the difference can be quite important if you're writing portable code.
    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"

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 11:03 AM
  2. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 11:10 AM
  3. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 11:01 AM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 09:07 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