Devolver la clave más grande estrictamente menor que la clave dada en un mapa C++

Question

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

Lower key

Uso caso tengo un mapa con los tiempos como llaves de una manera ordenada en un modo MAPA

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

En este caso, si paso a esta T2.3 MAPA entonces se debe dar me valor2. Cómo hacer un límite distinto en el mapa y volver a un equivalente elemento de la "llave volviendo más estrictamente menor que dado clave", es decir

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

Answer 1

Si no se preocupan por el ordenamiento, se puede usar un mapa de límite superior :: para obtener el elemento que desea, pero necesita definir la clase de mapa con std :: greater para el argumento de rasgos, de modo que el orden sea alto a 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 2

me gustaría utilizar std :: find_if() con iteradores inversa, algo así como:

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

Vas a tener que definir la función de predicado is_less_than().

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

Answer 3

Sí, LOWER_BOUND se puede utilizar para eso, lo he visto antes y lo utilizó como esa.

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

en realidad devolver el más grande, aún más pequeño (si! = Map.begin() era cierto) una. Si estaba en .begin, entonces no hay una clave más pequeña. Buena idea de los comentarios es volver .end si no hay ningún elemento que es menos y el paquete de este material 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 debe trabajar para std::set también.

Answer 4

Su método funcionará, pero debe comprobar 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 5

siempre encuentro para calcular piso (x) y ceil (x) para ser útil 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;