Возврат наибольшей клавиши строго ниже заданного ключа на карте C++

Question

Есть ли способ, которым поддерживают C++ STL Maps, так как lower_bound и upper_bound на картах строго возвращают значение, большее, чем переданное значение.

Lower key

Используйте случай у меня есть карта с раз в качестве ключей в отсортированном порядке, поэтому в MAP

time t1 = value1 
time t2 = value2 
time t2.5 = value3 

В этом случае, если я перехожу на эту карту Т2.3, то он должен дать меня значение2. Имеет ли делать LOWER_BOUND на карте и вернуться один элемент, эквивалентный к «возвращающемуся наибольшему ключу строго меньше заданного ключ», т.е.

iterator = map.upper_bound(2.3) 
and then 
iterator--; 

Answer 1

Если вы не заботитесь о упорядоченности, вы можете использовать карту :: upper_bound для получения нужного элемента, но вам нужно определить класс карты с помощью std :: больше для аргумента признаков, чтобы порядок был высоким-низким.

typedef std::map<double,MyClass,std::greater<double> > MyMap; 
MyMap myMap; 
myMap[1.5] = value1; 
myMap[2.0] = value2; 
myMap[3.0] = value3; 

MyMap::iterator elt = myMap.upper_bound(2.5); // should be pair(2.0,value2) 

Answer 2

Я хотел бы использовать зЬй :: find_if() с обратными итераторами, что-то вроде:

find_if(map.rbegin(), map.rend(), is_less_than); 

Вы должны определить функцию предиката is_less_than().

(см http://www.cplusplus.com/reference/algorithm/find_if.html)

Answer 3

Да, lower_bound может быть использован для того, я видел его раньше, и использовал его как это.

map_type::iterator it = map.lower_bound(2.3); 
if(it != map.begin()) { 
    --it; 
    // it now points at the right element 
} 

Фактически будет возвращено наибольшее, но меньшее (если оно! = Map.begin() было истинным). Если он был на .begin, тогда нет меньшего ключа. Хорошая идея от комментариев является возвращение .end, если нет ни одного элемента, который меньше и упаковать этот материал в функцию:

template<typename Map> typename Map::const_iterator 
greatest_less(Map const& m, typename Map::key_type const& k) { 
    typename Map::const_iterator it = m.lower_bound(k); 
    if(it != m.begin()) { 
     return --it; 
    } 
    return m.end(); 
} 

template<typename Map> typename Map::iterator 
greatest_less(Map & m, typename Map::key_type const& k) { 
    typename Map::iterator it = m.lower_bound(k); 
    if(it != m.begin()) { 
     return --it; 
    } 
    return m.end(); 
} 

Шаблон должен работать на std::set тоже.

Answer 4

Ваш метод будет работать, но вам нужно проверить, чтобы вы не вернулись к началу карты. Кроме того, вам нужно lower_bound, а не upper_bound.

iterator = map.lower_bound(2.3) 
if (iterator != map.begin()) 
    --iterator; 

Answer 5

Я всегда нахожу, чтобы вычислить пол (х) и CEIL (х), чтобы быть полезным patricularly

floor(x) -> greatest element <=x 
ceil(x) -> smallest element >= x 

floor_it = m.lower_bound(x); 
if (floor_it != m.end() && floor_it->first != x) 
     --floor_it; 

ceil_it = m.upper_bound(x); 
if (ceil_it != m.end() && (ceil_it-1)->first == x) 
    --ceil_it;