Why does HP / Microsoft STL list use the same structure for list head and node?

This is a discussion on Why does HP / Microsoft STL list use the same structure for list head and node? within the C++ Programming forums, part of the General Programming Boards category; From HP / Microsoft (Visual Studio C++) <list>: Code: struct _Node { // list node _Genptr _Next; // successor node, ...

  1. #1
    Registered User
    Join Date
    Apr 2013
    Posts
    1,164

    Why does HP / Microsoft STL list use the same structure for list head and node?

    From HP / Microsoft (Visual Studio C++) <list>:

    Code:
        struct _Node
        {    // list node
            _Genptr _Next;    // successor node, or first element if head
            _Genptr _Prev;    // predecessor node, or last element if head
            _Ty _Myval;       // the stored value, unused if head
        };
    The stored value is wasted space for the list head. Is there any advantage to implementing list using the same structure for a list head and node?

  2. #2
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    3,809
    O_o

    I would speculate that they are treating the head as being a simple sentinel allowing them to treat all operations the same without referring back to the container or other nodes.

    That said, stop looking at the implementation of the standard library you have; you'll wind up coding to an implementation instead of an interface.

    Soma

  3. #3
    Registered User
    Join Date
    Apr 2013
    Posts
    1,164
    Quote Originally Posted by phantomotap View Post
    That said, stop looking at the implementation of the standard library you have; you'll wind up coding to an implementation instead of an interface.
    In my code, I use separate structures for list and node, but I'm not writing templates. Perhaps it saved some template code by being able to use the same allocator for both lists and nodes. I was curious if there was any other valid reason for doing this. The reason I was looking at the implementation was to examine the sort code used for list and vectors.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,264
    The "dummy node" approach greatly simplifies implementation.
    E.g. when deleting an item, there is no longer a special case for deleting from the head.
    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"

  5. #5
    Registered User
    Join Date
    Apr 2013
    Posts
    1,164
    I looked at <list> some more. It uses a circular list with a head (dummy) node. The function list::end() just returns an iterator to the head node. As mentioned above, the reason I was looking at <list> and <algorithms> was to look at their sort code. list::sort() is somewhat clever, using an array of lists bin[] where each bin[i] contains 2^i (or zero) sorted nodes, all created using list::merge() (a bottom up merge that "gets" one node at a time).

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,264
    Quote Originally Posted by rcgldr View Post
    I looked at <list> some more. It uses a circular list with a head (dummy) node. The function list::end() just returns an iterator to the head node. As mentioned above, the reason I was looking at <list> and <algorithms> was to look at their sort code. list::sort() is somewhat clever, using an array of lists bin[] where each bin[i] contains 2^i (or zero) sorted nodes, all created using list::merge() (a bottom up merge that "gets" one node at a time).
    That desription exactly matches depth-first merge sort using an explicit stack. It won't be an actual bin-sort because that requires more than just an operator less-than.

    You can get a faster sort that list::sort, by implementing your own binsort. But then a linked-list is seldom the data structure of choice when there are a large number of items anyway. High cache-miss rate, and high per-item overhead.

    You can also get by without the dummy node containing the 'value' as well. Simply make a struct containing only the next and prev pointers, then make another struct with that and the value. Some casting is then involved of course, which makes it less palatable.
    It's interesting that there is space for the 'value' in the MS implementation, but that's not to say that the 'value' itself is actually initialised. I.e. There shouldn't be a constructor call invoked.
    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. #7
    Registered User
    Join Date
    Apr 2013
    Posts
    1,164
    Quote Originally Posted by iMalc View Post
    That desription exactly matches depth-first merge sort using an explicit stack. It won't be an actual bin-sort because that requires more than just an operator less-than.
    Yes it's not a radix (bin) sort, but it's done reasonably well.

    Quote Originally Posted by iMalc View Post
    It's interesting that there is space for the 'value' in the MS implementation, but that's not to say that the 'value' itself is actually initialized. I.e. There shouldn't be a constructor call invoked.
    The head / dummy node value is never initialized or used. The constructor only creates a list structure with a pointer to the head node, and sets the two head node pointers to point to the head node itself.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked list, Head pointing to second node
    By nkbxwb in forum C Programming
    Replies: 3
    Last Post: 10-01-2011, 06:38 PM
  2. Replies: 7
    Last Post: 11-04-2010, 01:18 PM
  3. Replies: 0
    Last Post: 09-16-2008, 05:04 AM
  4. Another List Q - Seg fault on head-tail list
    By JimpsEd in forum C Programming
    Replies: 11
    Last Post: 05-10-2006, 12:53 AM
  5. traversing a linked list with a node and list class
    By brianptodd in forum C++ Programming
    Replies: 2
    Last Post: 04-24-2003, 11:57 AM

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