title: A fast data structure for lower bound and upper bound queries on integers?
body: <p>i have to maintain a list of numbers, count up to 100,000... </p>
  
  <p>if the data is (for example)</p>
  
  <p><code>1, 4, 9, 12, 20, 35, 52, 77, 91</code></p>
  
  <p>and i query for a number, say 27, i want the number just immediately previous to 27, available in the list, so that will be: 20</p>
  
  <p>the data is also going to be modified frequently, like lots of Inserts and erases.</p>
  
  <p>currently i am using <code>stl::set</code> coupled with </p>
  
  <p><code>set&lt;int&gt;iterator it = lower_bound(values.begin(), values.end(), n);</code></p>
  
  <p>so</p>
  
  <p><code>*it = 35</code>
  and with <code>it--</code>, i get 20... but this is not fast enough, the number to queries are large, up to 500,000.. which include changing of my values or look up value.</p>
  
  <p>please give me some pointers.</p>