From: firstname.dot.lastname@googlemail.com   
      
   On Mon, 11 Mar 2013 15:06:27 -0700, James K. Lowden wrote:   
      
   > 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:   
      
   > 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.   
      
   If I understand correctly, you've traded one O(N) algorithm for another:   
   in vector, the search is O(log N), and insert is O(N), whereas for list,   
   the search is O(N) and the insert is O(1).   
      
   In both cases, the linear time part will domainate, and for vector, it is   
   very much faster.   
      
   My own observations lead me to believe that if there's ever an O(N) part   
   of the algorithm you may as well use vector, since it will perform best   
   on the slowest bit.   
      
   Presumably, list still maintains superiority when used in other cases,   
   for instance if you have many insertions into a large list or frequent   
   splicing and cutting of large lists. Without, of course, having to find   
   that position through linear search first.   
      
   Of course, if copying is really eye-wateringly slow, vector may not be   
   the best choice as well.   
      
   In practice, I very rarely use list. vector (often with heap) and   
   [unordered] set/map are far more common for me.   
      
   -Ed   
      
      
   --   
         [ 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)