Thread: 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?

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

Originally Posted by phantomotap

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.

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).

Originally Posted by iMalc

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.

Originally Posted by iMalc

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.