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

Quote:

---

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.

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.

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

Quote:

---

Originally Posted by rcgldr

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.

Quote:

---

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.

Quote:

---

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.