Есть ли способ для std :: map дать счетчик всех ключей <= target_key за O (1) время?

Question

Я использую std::map для хранения набора чисел в отсортированном порядке. Я хотел бы иметь возможность получить счетчик чисел, меньший или равный некоторому целевому числу за O (1) время (не включая время, которое требуется, чтобы найти максимальный ключ, равный <= target). Есть ли способ сделать это?

В качестве примера, скажем, у меня есть следующие числа (могут существовать дубликаты) (1,0,5,2,3,8), хранящиеся в виде ключей в std::map, и у меня есть target_key = 4. Я хочу использовать std::map, чтобы дать мне решение 4, поскольку в массиве <=4 4 числа.

Я не уверен, настроен ли std::map для этого. Единственное, о чем я могу думать, это использовать std::upper_bound, чтобы получить итератор для наибольшего значения <=4, а затем перебирать итераторы и суммировать счетчик каждого ключа, но это O (n) время.

РЕДАКТИРОВАТЬ 1:

Обратите внимание, что могут быть повторяющиеся числа

РЕДАКТИРОВАТЬ 2:

Я неправильно указал, что поиск должен быть выполнен в O (1 Время Я понимаю, что это невозможно с любым отсортированным контейнером, и лучший вариант - O (LogN). Когда я первоначально сказал O (1), я предполагал, что уже нашел максимальный ключ, равный <= target, и затем использовал этот ключ, чтобы найти счет за время O (1). Я также первоначально предполагал использовать std::map для хранения пары ключ-значение, где значение - это число вхождений ключа, или, что еще лучше, но значение - это количество ключей (включая дубликаты), которые <= target.

Answer 1

Это называется запросом rank , а std::map не предоставляет никакого способа сделать это лучше, чем линейное время.

Это правда, что вы можете найти итератор в логарифмировании c время, но нет способа получить расстояние между этим итератором и begin() лучше, чем линейное время. Чтобы std::map предоставлял такую ​​функциональность, он должен был бы вести подсчет размера поддерева в каждом узле красно-черного дерева, что замедляло бы каждую операцию обновления, в том числе для пользователей, которые не заботятся о ранжировании. запросы.

Если вы дополняете дерево размерами поддерева, вы можете выполнить ранговый запрос в логарифмическом c времени. Boost.Intrusive может помочь (я думаю, что есть люди, которые уже написали необходимые библиотеки для выполнения ранговых запросов, но я не могу найти их в Google прямо сейчас).

Answer 2

Я думаю, что в std::map/std::multimap нет способа получить расстояние между двумя итераторами постоянной сложности. std::map/std::multimap предлагает LegacyBidirectionalIterator и использование std::distance для определения расстояния между двумя итераторами имеет линейную сложность.