title: Standard Template Library lists - doubly linked or circularly linked?
body: <p>I've just noticed something about the <code>std::list</code> class in C++ I find curious. Briefly, it concerns the manner in which the list's iterators work. Consider the following code:</p>
  
  <pre><code>std::list&lt;int&gt; alist;
  alist.push_back(0);
  alist.push_back(1);
  alist.push_back(2);
  </code></pre>
  
  <p>Obviously enough, this creates a list with three integer elements in it. I can define an iterator to the start of the list and use it to, say, print out the value contained in the first element as follows:</p>
  
  <pre><code>std::list&lt;int&gt;::iterator iter = alist.begin();
  std::cout &lt;&lt; *iter &lt;&lt; std::endl;  // Prints "0" to stdout
  </code></pre>
  
  <p>What I find mildly odd is that if I now <em>decrement</em> the iterator, it "loops around" and ends up pointing at the last element in the list:</p>
  
  <pre><code>--iter;
  std::cout &lt;&lt; *iter &lt;&lt; std::endl;  // Prints "2" to stdout
  </code></pre>
  
  <p>Is this reasonable behaviour for something that's supposedly implemented as a doubly linked list? I'd quite expect to similar behaviour from the iterator if the list was a <em>circularly</em> linked list, but I find this quite odd. </p>
  
  <p>Are there any practical uses for this iterator behaviour that you've used in the past? Are there any gotchas associated with this behaviour that I should keep an eye out for?</p>
  
  <p>(By the way, this happens with gcc 4.7.0 (MinGW). I haven't tested it with any other version or compiler.)</p>