Возвращает наибольший ключ строго меньше, чем данный ключ в C ++ Map

Question

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

Нижний ключ

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

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

В этом случае, если я перейду к этой MAP t2.3, тогда она должна дать мне значение2. Делает на карте значение lower_bound и возвращается на один элемент, эквивалентный «возвращению наибольшего ключа строго меньше, чем заданный ключ», т.е.

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

Answer 1

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

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

На самом деле вернул бы самый большой, но меньший (если это! Если это было в .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 2

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

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 3

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

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

Answer 4

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

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

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

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

Answer 5

Я всегда нахожу, что вычислить floor (x) и ceil (x) очень полезно

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;