Workings of MS STL list begin() and end() methods

[jetimms]

I've been trying to create a simplified version of the list container for an example in "Accelerated C++", however I'm having a tough time wrapping my head around the concept of begin() and end() where there is no single allocated buffer of memory, as in the case of a vector.

I understand the idea of the first allocated object gets head and tail pointed to it. As things are inserted on the back, the tail moves continually to the end.

I would expect that begin() would always point to the head, but I don't understand where end() could point to since the addresses of the node objects in the list can be anywhere as long as their previous and next pointers point to one another. In the vector, end() always pointed to the first address after the last used in the allocated space of contiguous memory alloted to that vector. Unless I'm mistaken, list's don't have contiguous memory, so there is no "one-after" situation.

I'm using VS 9.0 Express to compile (I guess that's the Windows Server 2003 compiler by Dinkumware) and for the begin() and end() it has this.

from <list>

// return reference to successor pointer in node
static _Nodepref _Nextnode(_Nodeptr _Pnode)
{
  return ((_Nodepref)(*_Pnode)._Next);
}
...
// return iterator for beginning of mutable sequence
iterator begin() {
  return (iterator(_Nextnode(_Myhead)));
}
...
// return iterator for end of mutable sequence
iterator end() {
  return (iterator(_Myhead));
}

This leads to further confusion given my (flawed) theory. Here, end() returns the head and begin() returns to head->next.

Thanks for any insight you can provide.

[Hammurabi]

It looks like _Myhead is a sentinel node that points to the first real node, and which is pointed to by the last node. That's one possible implementation. Another is to forgo the sentinel node and have end() return an iterator initialized to the null pointer.

[jetimms]

I see. So the sentinel node works like a terminal for the beginning and ending of the list? It's kind of like a belt, to put it simply, where the buckle binds the the beginning and end.

That makes sense now. I guess that's why they don't mention a "tail" in the Dinkumware interpretation.

I believe I will go this route with my container.

Thanks.