From: mordor.nospam@fly.srk.fer.hr   
      
   On 2012-02-12, Miles Bader  wrote:   
   >   
   > That sounds pretty suspicious -- it is O(1) in a decent implementation   
   > in this case.  [Were you perhaps using a debugging mode or version of   
   > the STL (which might do some sort of poisoning of deallocated regions   
   > or something)?]   
   >   
   It was release mode, but you're right.  I've taken another look at the   
   code and the method in question is implemented as:   
      
    aVector.clear(); aVector.resize(N, 0);   
    bVector.clear(); bVector.resize(N);   
      
   so it is/was my fault after all.  I remembered that I implemented a   
   closed hash with a vector as underlying storage, but I had forgotten   
   that it also uses O(N) space for tags (used/deleted/free), and this   
   space has to be reinitialized on every clear.   
      
   That said, my main objection against vector is that it is impossible   
   to "steal" the underlying storage.   
      
   >   
   > So I guess the lesson is: bad implementations exist.  But on the other   
   >   
   This is definitely true. I evaluated the vendor's hash implementation   
   before rolling my own, and the vendor's was too memory-hungry.  (It   
   was a "real-life" test, the hash was used in an algorithm needed by   
   the customer.)   
      
      
   --   
         [ 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)