Is there a way for std::map to give a counter of all keys <= target_key in O(1) time?

I'm using std::map 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 <= target). Is there a way to do this?

As an example, say I have the following numbers (duplicates CAN exist) (1,0,5,2,3,8) stored as keys in std::map, and I have a target_key = 4. I want to use std::map to give me the solution 4 since there are 4 numbers in the array <=4.

I'm not sure if std::map is set up to do this. The only thing I can think of is using std::upper_bound to get me the iterator for the greatest value <=4, and then looping through the iterators and summing up the count of each key, but that's O(n) time.

EDIT 1:

Note that there may be duplicate numbers

EDIT 2:

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 <= target, and then using this key to find the count in O(1) time. I was also originally envisioning using std::map 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 <= target.

Solution

This is called a rank query, and std::map does not provide any way of doing it in better than linear time.

It's true that you can find the iterator in logarithmic time but there is no way to get the distance between that iterator and begin() in better than linear time. In order for std::map to provide such functionality, it would have to keep a count of subtree size in each node of the red-black tree, which would slow down each update operation, including for users who don't care about doing rank queries.

If you do augment the tree with subtree sizes, you can do the rank query in logarithmic time. Boost.Intrusive can help (I imagine there are people who have already written the necessary libraries to do rank queries, but I can't find them on Google right now).