title: ordered associative data structure optimised for fast lookup?
body: <p>I'm looking for a <code>std::map</code>-esque data structure optimised for <strong>fast lookup</strong>.</p>
  
  <p>One approach would be to implement map's interface utilising a sorted <code>std::vector</code> as the underlying storage - this will offer fast <code>binary_search</code> thanks to random-access iterators and cache locality.</p>
  
  <p>However, this sounds like reinvention of the wheel. Surely something like this already exists?</p>
  
  <p>Is there an open-source ordered associative data structure which uses a std::vector for storage?</p>
  
  <p><strong>Edit:</strong></p>
  
  <p>In response to the comments suggesting <em>just use std::map</em> - please read here: <a href="http://lafstern.org/matt/col1.pdf" rel="nofollow">http://lafstern.org/matt/col1.pdf</a></p>