From: jklowden@speakeasy.net   
      
   On Sun, 10 Mar 2013 16:20:11 -0700 (PDT)   
   brangdonj@googlemail.com (Dave Harris) wrote:   
      
   > 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 );   
      
   That was an interesting claim.  I wrote  a little test of my own which   
   supports it.   
      
   I inserted just 100,000 randomly generated integers in a std list,   
   vector, and set.  Not being a fan of O(n) performance, I'm not much of   
   a list user myself.  I was stunned at how slow it was:   
      
   list:		6m56.993s   
   vector:	0m1.388s   
   set: 		0m0.447s   
   empty: 	0m0.334s	(no container, just /dev/urandom)   
      
   Seven minutes versus 1 second.  Behold the power of the binary search!   
      
   On a machine operating at billions of instructions per second, std::list   
   manages less than 250 insertions per second.   
      
   Bumping N up to 250,000, skipping list and adding a deque,   
      
   deque:	real    0m25.088s   
   vector: 	real    0m7.258s   
   set: 		real    0m1.180s   
   empty: 	real    0m0.833s   
      
   which is a disappointing result for deque, if you ask me, but much to   
   your point: deque *should* be faster because inserts are cheaper, but   
   the effect of locality swamps it.   
      
   Nothing definitive, of course.  Just one program on one machine   
   using one compiler, run just a few times.  But it does look like   
   std::list is headed the way of the 9-track tape.   
      
   --jkl   
      
      
   --   
         [ 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)