Как я могу найти первый элемент карты, где ключ больше, чем val
у меня есть map<double,T> (сказать T==string) и я хотел найти первый элемент карты, чтобы ключ был больше заданного числа. Я заглянул в <algorithm> и найти верхняя граница а также нижняя граница.
Странно, я могу получить первый выше, используя lower_bound но нет upper_bound, Что я делаю неправильно?
#include <iostream>
#include <map>
#include <algorithm>
#include <string>
using namespace std;
bool lte (pair<double,string> x, const double y) {
return (x.first-y)<.001;
}
bool gte (pair<double,string> x, const double y) {
return (x.first-y)>.001;
}
int main()
{
map<double,string> myMap;
myMap[10.01] = "A";
myMap[14.62] = "B";
myMap[16.33] = "C";
myMap[45.23] = "D";
myMap[0.23] = "E";
map<double,string>::iterator it;
for(it = myMap.begin(); it != myMap.end() ; it++){
cout << it->first << " => " << it->second << endl;
}
map<double,string>::iterator firstAbove_1;
firstAbove_1 = lower_bound(myMap.begin(), myMap.end(), 15., lte); //
cout << "first greater that 15 is " << firstAbove_1->second << '\n';
//map<double,string>::iterator firstAbove_2;
//firstAbove_2 = upper_bound (myMap.begin(), myMap.end(), 15., gte); // ^
//cout << "first greater that 15 is " << firstAbove_2->second << '\n';
return 0;
}
Решение
ВАЖНЫЙ: Этот ответ объясняет почему вы получаете ошибку компиляции. Однако, когда это возможно, вы всегда должны отдавать предпочтение версиям-функциям-алгоритмам, а не версиям-функциям, потому что они предлагают лучшие гарантии сложности.
Таким образом, использование std::map::upper_bound() а также std::map::lower_bound, Тем не менее, следующее объясняет, почему вы получаете ошибку во время компиляции.
Порядок аргументов sdt::lower_bound а также std::upper_bound является поменять местами. См. Пункты 25.4.3.1-2 стандарта C ++ 11:
25.4.3.1 lower_bound [lower.bound]
template<class ForwardIterator, class T, class Compare>
ForwardIterator lower_bound(
ForwardIterator first,
ForwardIterator last,
const T& value,
Compare comp
);
1 требует: Элементы e of [first, last) должны быть разделены относительно выражения е < значение или комп (е, значение).
2 Возвращает: Самый дальний итератор i в диапазоне [first, last] такой, что для любого итератора j в диапазоне [first, i) выполняются следующие соответствующие условия: * J < значение или комп (* j, значение)! = ложь.
[…]
25.4.3.2 upper_bound [upper.bound]
template<class ForwardIterator, class T>
ForwardIterator upper_bound(
ForwardIterator first,
ForwardIterator last,
const T& value);
Compare comp
);
1 требует: Элементы e of [first, last) должны быть разделены относительно выражения !(значение < е) или! comp (значение, е).
2 Возвращает: Самый дальний итератор i в диапазоне [первый, последний] такой, что для любого итератора j в
[…]
range [first, i) выполняются следующие соответствующие условия: !(значение < * j) или comp (значение, * j)
== ложь
Вы должны изменить свою функцию компаратора соответственно:
bool lte (pair<double, string> x, const double y) {
...
}
bool gte (const double y, pair<double,string> x) {
...
}
Так же value_type из std::map<A, B> не является std::pair<A, B>, скорее std::pair<A const, B>, Чтобы избежать бесполезных преобразований и копий, я предлагаю использовать следующие подписи:
bool lte (pair<double const,string> const& x, double const y) {
// ^^^^^ ^^^^^^
...
}
bool gte (double const y, pair<double const, string> const& x) {
// ^^^^^ ^^^^^^
...
}
Другие решения
Используемая вами функция сравнения должна быть строго меньше, а не меньше или равна. В противном случае алгоритм может не работать.
Ради эффективности вы должны использовать функция-член upper_bound встроен в карту, а не в algorithm,
Если вам нужно учесть промах из-за несовпадений с плавающей запятой, сделайте это в качестве шага после.
map<double,string>::iterator it;
it = myMap.upper_bound(15.0);
if (it != myMap.begin())
{
map<double,string>::iterator it2 = it;
--it2;
if (it2->first > 15.0 - 0.001)
it = it2;
}
gte должно быть
bool gte (const double y, pair<double,string> x) {
return (y-x.first)<.001;
}
потому что вам нужно переключать аргументы вокруг. Это дает вам результаты, которые вы хотите, но это не идеально, потому что функция сравнения не симметрична. Любой, кто читает этот код, должен уделять много внимания тому, что происходит на какой стороне сравнения, чтобы понять, что вы делаете.
Ваша программа будет более читабельной, если вы используете функции-члены lower_bound а также upper_bound от твоего std::mapв отличие от диапазона std::lower_bound а также std::upper_bound:
firstAbove_1 = myMap.lower_bound(15.0);
firstAbove_2 = myMap.upper_bound(15.0);
Вот результаты выполнения этого:
0.23 => E
10.01 => A
14.62 => B
16.33 => C
45.23 => D
first greater than 15 is C
first greater than 15 is C
Ваша функция gte неверна. должно быть
bool gte (const double y, pair<double,string> x) {
return (x.first-y)>.001;
}
Прежде всего, лучше использовать map::lower_bound а также map::upper_bound потому что они будут работать в O(log n) operations, Не только O(log n) comparsions,
В любом случае я бы использовал lower/upper_bound без предиката, но с использованием значения (15. + .001)
/usr/lib/gcc/i686-pc-cygwin/3.4.4/include/c++/bits/stl_algo.h: In function `_ForwardIterator std::upper_bound(_ForwardIterator, _ForwardIterator, const _Tp&, _Compare) [with _ForwardIterator = std::_Rb_tree_iterator<std::pair<const double, std::string> >, _Tp = double, _Compare = bool (*)(std::pair<double, std::string>, double)]':
a.cpp:32: instantiated from here
/usr/lib/gcc/i686-pc-cygwin/3.4.4/include/c++/bits/stl_algo.h:2784: error: conversion from `const double' to non-scalar type `std::pair<double, std::string>' requested
stl — вонючий волосатый монстр беспорядка, когда дело доходит до выяснения проблем.
Ваша проблема связана с тем, что компаратор обычно сравнивает два элемента одного типа, но здесь вы пытаетесь использовать его для сравнения pair<double,string> и double, Благодаря чудесной магической незаметности шаблонов в c ++, компилятор не видит факта, что ваш компаратор использует два разных типа в качестве проблемы.
Реализация lower_bound всегда передает элемент карты в качестве первого параметра, а значение сравнения — в качестве правильного параметра, так что вам не нужен ваш странно типизированный компаратор. Но upper_bound меняет порядок параметров, поэтому вы получаете ошибку этого типа. Он пытается засунуть двойник туда, где должна идти пара.
Кроме того, вы передаете неправильный вид компаратора upper_bound, Как правило, вы должны проходить то же самое<Компаратор для обеих функций.
Как и другие говорили, используя map::upper_bound(keytype&) это лучшая идея.