programas - Devolver la clave más grande estrictamente menos que la clave dada en un mapa de C++

programacion basica c++

Question

¿Hay alguna manera de que C ++ STL Maps lo apoye, ya que lower_bound y upper_bound en los mapas devuelven estrictamente el valor mayor que el valor pasado.

Tecla inferior

Caso de uso Tengo un mapa con los tiempos como claves de una manera ordenada por lo que en un mapa

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

En este caso, si paso a este MAP t2.3, entonces debería darme value2. Hacer un lower_bound en el mapa y retroceder un elemento equivalente a la "clave más grande que retorna estrictamente menos que la clave dada", es decir,

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

Answer 1

Sí, lower_bound se puede usar para eso, lo he visto antes y lo he usado así.

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

En realidad devolvería el más grande, pero más pequeño (si it! = Map.begin () era verdadero) one. Si estaba en .begin, entonces no hay una clave más pequeña. La buena idea de los comentarios es devolver .end si no hay ningún elemento que sea menor y empacar todo esto en una función:

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();
}

La plantilla debería funcionar también para std::set .

Answer 2

Si no le importa el orden, puede usar map :: upper_bound para obtener el elemento que desea, pero necesita definir la clase de mapa con std :: greater para el argumento de rasgos, para que el orden sea alto. -bajo.

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

Su método funcionará, pero debe verificar para asegurarse de no retroceder sobre el comienzo del mapa. Además necesitas lower_bound, no upper_bound.

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

Answer 4

Utilizaría std :: find_if () con iteradores inversos, algo así como:

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

Tendrá que definir la función de predicado is_less_than ().

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

Answer 5

Siempre encuentro calcular el piso (x) y el techo (x) para que sean útiles patricularmente

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;