Как проверить карту :: Lower_bound Ошибка?
Я хочу получить пару ключ-вал из карты, ключ которой меньше или равен данному K.
Я хочу получить конец (или разорвать или любой признак ошибки), что так простой код а также почти такой же:
#include <iostream>
#include <map>
using namespace std;
int main() {
map<int, int> m;
m[56]= 666;
auto it = m.lower_bound(1);
if(it != m.end()) {
cout << it->first;
} else {
cout << "this was expected!=(";
}
return 0;
}
Я получаю один и тот же плохой результат для lower_bound и upper_bound. Что я делаю не так?
Решение
По данным cppreference.com:
lower_boundвозвращает Iterator, указывающий на первый элемент, который не менее чем ключupper_boundвозвращает Iterator, указывающий на первый элемент, который большая чем ключ
Поэтому в обоих случаях вы должны получать 666 за it->secondпотому что один элемент, который вы вставили (ключ = 56), удовлетворяет этим критериям.
Вот как бы я написал условное выражение:
int main() {
map<int, int> m;
m[56] = 666;
int myKey = 1;
auto it = m.upper_bound(myKey);
if (it == m.begin()) {
cout << "Key less than or equal to " << myKey << " doesn't exist\n";
} else {
--it; // <- This is the key you are looking for
}
return 0;
}
В этом случае мы проверяем, есть ли элемент больше, чем ваш ключ. Если это самый низкий ключ на карте, то то, что вы ищете, там нет. В противном случае мы просто получаем предыдущий элемент, найденный upper_bound,
Другие решения
Согласно это объяснение
Возвращает итератор, указывающий на первый элемент в контейнере, ключ не считается идти до к (т. е. либо эквивалентен, либо идет после).
Так что получение 56 в вашем примере ожидается, так как оно делает не идти до 1.
Для достижения вашей цели используйте upper_bound который возвращается гарантированный ключ выше, чем заданный ‘k’, и уменьшите итератор, если он найден:
auto it = m.upper_bound(key);
if (it == m.begin()) {
// First and all other values are higher than key
it == m.end();
}
else {
// Found higher value, one previous is equal or less than key
it--;
}