Найдите диапазон ключей, который существует в «диапазоне запроса» в std::map в C++
Как узнать, есть ли у меня ключи в диапазоне . Я пытаюсь ниже:
Цель состоит в том, чтобы получить -2 and 2 как ключевой граничный диапазон (который фактически существует на карте) в пределах диапазона запроса [-3,3]
std::map<int, char> m{ {-2,'B'}, {1, 'C'}, {2, 'A'}};
auto itCurrent = m.lower_bound(-3);
auto itNext = m.upper_bound(-3);
auto it1 = m.lower_bound(3);
auto it2 = m.upper_bound(3);
Я получаю ценность -2 за itCurrent и itNext, но почему я получаю end за it1 и it2 оба. Я ожидал, что m.lower_bound(3) должен вернуться 2.
Вероятно, то же коренное недоразумение, что и обоснование std::lower_bound и std::upper_bound? . Диаграмма в A: Разница между Upper_bound и Lower_bound в stl может помочь. (Должно ли это быть помечено как дубликат?)
@MSalters Другими словами, мне нужно найти ближайшие существующие ключи в моем диапазоне (3,3) или [-3,3] . Итак, я хочу получить ключи -2 и 2 в том виде, в котором они существуют на карте и в моем диапазоне запроса.
@GauravK Я отменил ваше редактирование, потому что вы не должны редактировать вопрос таким образом, чтобы сделать существующие ответы недействительными. Пожалуйста, опубликуйте новый вопрос.
Также если диапазон не содержит слишком много ключей, вы можете просто перебирать их и выбирать нужные по любому критерию.
@GauravK: Я понимаю, что +2 и -2 определенно находятся в пределах этого диапазона. Но поскольку вы пишете «мой диапазон (3,3) или [-3,3]», я вынужден сделать вывод, что вы не уверены в открытии или закрытии, но вы определенно не имеете в виду полуоткрытый интервал [-3] , +3), что является обычным соглашением C++. Это объясняет, почему вы видите такое поведение: lower_bound и upper_bound возвращают здесь один и тот же тип полуоткрытого интервала.
@MSalters Я знаю разницу между [-3,3], (-3,3) или [-3,3). В моем конкретном примере это не имеет значения, поскольку ключи находятся в диапазоне [-2,2]. И поэтому сказал enquiry range (3,3) or [-3,3]
@GauravK: Программировать простые случаи легко. Правильно разобраться в крайних случаях сложно. И в данном случае речь идет о буквальном крае интервала. Если вы даже не можете определить, что должна делать ваша функция, как мы можем сказать вам, как ее реализовать? Кроме того, подумайте, что должна делать ваша функция, например, когда карта пуста — спецификация не может просто игнорировать это.
Ответы 1
Как вы можете видеть в документации std::map::lower_bound:
Возвращаемое значение
Итератор, указывающий на первый элемент, который не меньше ключа. Если такой элемент не найден, используется итератор прошедшего конца (см. end()). вернулся.
(выделено мной)
У вас нет ключа не меньше 3, поэтому m.lower_bound(3) возвращает end().
Аналогично с std::map::upper_bound:
Возвращаемое значение
Итератор, указывающий на первый элемент, который больше ключа. Если нет такой элемент найден, возвращается итератор прошлого конца (см. end()).
(выделено мной)
У вас нет ключа больше 3, поэтому m.upper_bound(3) возвращает end().
Это также имеет смысл для вашей цели поиска элементов в диапазоне:
Все ваши элементы находятся до конца диапазона (и включены в него) — именно это и означает возвращаемое значение end().
Для закрытого диапазона, такого как [-3,3], все элементы от m.lower_bound(-3) до m.upper_bound(3) (но не включая) находятся в диапазоне.
Если вам нужны те, которые ближе всего к границам диапазона, это:auto it_low = m.lower_bound(-3);
иauto it_high = m.upper_bound(3); std::advance(it_high , -1);
(std::advance с -1 используется для получения одного элемента перед итератором, который находится сразу после диапазона).
Как найти ближайшие клавиши в диапазоне [-3,3]? Есть ли простой способ.
Я думаю, что все элементы от itCurrent до (кроме it2) находятся в этом диапазоне.
Мне нужно найти ближайшие ключи к -3 и 3.
Если вам нужно найти один ближайший ключ, это либо itCurrent, либо один перед it2. Но ваш вопрос заключался в том, как найти все ключи в диапазоне (на который, кажется, я ответил) – не так ли? Может быть, вы можете опубликовать новый вопрос?
Редактирую пост.
@GauravK, вам не следует редактировать вопрос таким образом, чтобы сделать недействительными существующие ответы. Вам следует опубликовать новый вопрос.
Под
[-3, +3]вы имеете в виду закрытый интервал (включая оба предела)? Поскольку C, C++ и большинство родственных языков по умолчанию используют полуоткрытые интервалы, например.[-3, +3)с включенным -3 и без +3. См. границы массива,int a[5]имеет отa[0]доa[4], но неa[5].