From: brangdonj@googlemail.com   
      
   In article <20130309115333.e97f4363.jklowden@speakeasy.net>,   
   jklowden@speakeasy.net (James K. Lowden) wrote:   
   > A linked list is, from a theoretical standpoint, a perfectly   
   > reasonable data structure for ordered data.  Sure, a binary tree   
   > is faster to seek over.  But a list is perfectly adequate for   
   > "small N, and N is usually small" as Rob Pike put it, and has   
   > nothing like the complexity of a tree.   
      
   I think for a long time it's been rare to beat a vector. If N is   
   small, then the time taken to shuffle up elements when inserting   
   in the middle will also be small. If you need to keep it sorted,   
   that's trivial with the std library. As I recall, it's something   
   like:   
      
       auto i = std::lower_bound( begin(v), end(v), item );   
       v.insert( i, item );   
      
   What those old theoretical standpoints tend to leave out is that   
   modern hardware loves to access contiguous memory in sequential   
   order. It can predict where your next access will be and pre-fetch   
   it. Any kind of node-based structure, whether tree or list, is unfriendly   
   to the hardware because it appears more random. In   
   addition, the nodes add some memory overhead which further reduces   
   locality of reference. Having insertion at a random location be   
   fast doesn't help much if you need a linear scan to figure out   
   where that random location is. As a result of this, vector normally   
   beats linked list even for large N. /Especially/ for large N.   
      
   C++11 has increased the advantages of vector further, through   
   move semantics. For example, inserting at the start of a vector   
   of strings will not need to copy all the characters in all the   
   strings.   
      
   Of course writing a linked list is still a valuable learning   
   exercise for newcomers to C++. I don't think we should be   
   encouraging them to use linked lists in production code. Instead   
   we should recommend they use vector by default, unless they have   
   specific measurements that prove a linked list is better.   
      
   I found an article, with measurements and graphs, here:   
   http://kjellkod.wordpress.com/2012/02/25/why-you-should-never-ever-ever-us   
   e-linked-list-in-your-code-again/   
      
   -- Dave Harris, Nottingham, UK.   
      
      
   --   
         [ See http://www.gotw.ca/resources/clcm.htm for info about ]   
         [ comp.lang.c++.moderated.    First time posters: Do this! ]   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)