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

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

Нижний ключ

Случай использования У меня есть карта со временем как ключи отсортированным образом, поэтому в MAP

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

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

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

Ответы

Ответ 1

Да, для этого можно использовать 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() было true). Если он был на .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.

Ответ 2

Если вы не заботитесь о заказе, вы можете использовать map:: 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)

Ответ 3

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

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

Ответ 4

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

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

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

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

Ответ 5

Я всегда нахожу, чтобы вычислять пол (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;