title: Is there a way for std::map to give a counter of all keys <= target_key in O(1) time?
body: <p>I'm using <code>std::map</code> to store a set of numbers in sorted order. I would like to be able to obtain a counter of numbers less or equal than some target number in O(1) time (not including the time it takes to find the maximum key that is <code>&lt;= target</code>). Is there a way to do this?</p>
  <p>As an example, say I have the following numbers (duplicates CAN exist) <code>(1,0,5,2,3,8)</code> stored as keys in <code>std::map</code>, and I have a <code>target_key = 4</code>. I want to use <code>std::map</code> to give me the solution <code>4</code> since there are 4 numbers in the array <code>&lt;=4</code>.</p>
  <p>I'm not sure if <code>std::map</code> is set up to do this. The only thing I can think of is using <code>std::upper_bound</code> to get me the iterator for the greatest value <code>&lt;=4</code>, and then looping through the iterators and summing up the count of each key, but that's O(n) time.</p>
  <h1>EDIT 1:</h1>
  <p>Note that there may be duplicate numbers</p>
  <h1>EDIT 2:</h1>
  <p>I misstated that the search needs to be done in O(1) time. I understand that is not possible with any sorted container, and the best case is O(LogN). When I originally said O(1), I was envisioning already having found the maximum key that is <code>&lt;= target</code>, and then using this key to find the count in O(1) time. I was also originally envisioning using <code>std::map</code> to store the key-value pair, where the value is a count of the occurrences of key, or better, yet, the value is the count of number of keys (duplicates included) that is <code>&lt;= target</code>.</p>