From: jklowden@speakeasy.net   
      
   On Tue, 12 Mar 2013 05:23:00 CST   
   Francis Glassborow  wrote:   
      
   > However it certainly looks as if the lack of locality makes list (in   
   > any of its forms) uncompetitive. This is an excellent lesson for   
   > students to learn (that they need to take into account much more than   
   > simply big O)   
      
   Yes and no.  My test was of the form   
      
         auto offset = std::lower_bound( begin(v), end(v), item );   
         v.insert( offset, item );   
      
   which combines finding the element with inserting it.  Old schools says   
   moving memory around is expensive, so don't resize your vectors.   
   Locality says resizing is OK.  That's great, but O(n log(n)) still beats   
   O(n) every time.  The sorry performance of std::list owed to the fact   
   that it has no random-access iterator, not its locality.   
      
   To demonstrate, I reran my test without lower_bound, simply inserting at   
   begin() (except for set).  The results are again consistent with the   
   big O:   
      
   deque:	0m0.849s   
   vector:	0m12.554s   
   list: 		0m0.869s   
   set:		0m1.172s   
   empty:	0m0.831s   
      
   That's interesting because it shows a set will maintain a sorted order   
   for you (and enforce uniqueness) for about 50% overhead versus anything   
   else.  (Also impressive is how exceedingly fast these containers are   
   relative to simply reading from /dev/urandom.)   
      
   To your point, inserting in the middle is what really shows locality.   
   Below are times for v.insert(v.begin() + v.size()/2, item) for 250,000   
   integers:   
      
   deque:	0m48.158s   
   vector:	0m7.167s   
      
   That's the eye-opener for me.  We know vector must maintain a   
   contiguous block, and we know deque need not.  Therefore reallocation   
   should be cheaper for a deque.  Seek time shouldn't be that much   
   slower; deque::operator[] is O(1).  Yet vector is 7x faster.   
   Reallocation isn't free, but it's a lot cheaper than it used to be.   
      
   Henry Spencer was right: All the world is not a VAX.   
      
   --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)