title: Finding "best matching key" for a given key in a sorted STL container
body: <h2>Problem</h2>
  
  <p>I have timestamped data, which I need to search based on the timestamp in order to get the one existing timestamp which matches my input timestamp the closest.<br>
  Preferably this should be solved with the STL. boost::* or stl::tr1::* (from VS9 with Featurepack) are also possible.<br>
  Example of timestamped data:</p>
  
  <pre><code>struct STimestampedData
  {
   time_t m_timestamp; // Sorting criterion
   CData m_data;       // Payload
  }
  </code></pre>
  
  <h2>Approach with <code>stl::vector</code>, <code>sort()</code> and <code>equal_range()</code></h2>
  
  <p>Since a <code>map</code> or <code>set</code> only allows me to find exact matches, I don't get any further using one of these.
  So now I have a <code>vector</code> to which I append data as it is coming in. Before searching I use <code>&lt;algorithm&gt;</code>'s <code>sort()</code> and supply it with a custom comparison function.<br>
  After that I use <code>&lt;algorithm&gt;</code>'s <code>equal_range()</code> to find the two neighbors of a specified value <code>x</code>.
  From these two values I check which one is closest to <code>x</code> and then I have my best match.</p>
  
  <p><br>
  While this is not too complex, I wonder if there are more elegant solutions to this.<br>
  Maybe the STL already has an algorithm which does exactly that so I'm not re-inventing something here?</p>
  
  <h2>Update: Linear vs. binary search</h2>
  
  <p>I forgot to mention that I have quite a lot of data to handle so I don't want to have to search linearly.<br>
  The reason I am sorting a vector with <code>sort()</code> is because it has random access iterators which is not the case with a <code>map</code>. Using a <code>map</code> would not allow <code>equal_range()</code> to do a search with twice logarithmic complexity.<br>
  Am I correct?</p>