Нахождение значения диапазона меньше или больше, чем из класса контейнера

Question

В настоящее время у меня есть таблица std::map <DWORD, DWORD>, и я ищу значение ключа, соответствующее определенному диапазону.

Например:

Найти значение ключа из карты, значение которого должно быть меньше или меньше 50 или больше 50 от искомого значения ключа.

Если искомое значение ключа было 20, тогда я хотел бы, чтобы значение ключа диапазона от карты, т.е.

-70.............20............+70

Есть ли лучший способ найти значение ключа, отличное от использования двухпетлевого цикла (сначала менее чем, второй более чем) или подходящий способ хранения данных таблицы для такой операции?

Answer 1

Для этого можно использовать map::lower_bound и map::upper_bound, если вы заранее знаете значение среднего уровня.

map<int, MyClass>::const_iterator lower = 
    myMap.lower_bound(-30);   // or -70 if you prefer
map<int, MyClass>::const_iterator upper = myMap.lower_bound(70);

Оба итератора должны быть проверены на myMap.end() перед разыменованием.

Этот фрагмент основан на том, что ваш порядок является обычным возрастающим порядком - пользовательский порядок может изменить это так, что после + ve появляются цифры -ve. Нет лучшего способа сделать это - с помощью построения map в виде двоичного дерева это будет эффективно.

См. Также онлайн-примеры для lower_bound и upper_bound .

Обратите внимание, что DWORD без знака, поэтому использование отрицательных чисел на вашей карте может привести к ошибке предупреждения, а -70 неожиданно> 70.