Renvoyer la plus grande clé strictement inférieure à la clé donnée dans une mappe C++

Question

Est-ce que les mappes STL C++ supportent cela, étant donné que les commandes lower_bound et upper_bound sur les maps renvoient strictement la valeur supérieure à la valeur passée.

Lower key

cas d'utilisation J'ai une carte avec des temps que les clés d'une manière triée de façon dans une carte

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

Dans ce cas, si je passe à ce MAP T2.3 alors il devrait donner moi value2. Est-ce que faire un lower_bound sur la carte et retourner un élément équivalent au « retour clé plus strictement inférieur à clé donnée » à savoir

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

Answer 1

Si vous ne se soucient pas de la commande, vous pouvez utiliser la carte :: upper_bound pour obtenir l'élément que vous voulez, mais vous devez définir la classe map avec std :: greater pour l'argument traits, de sorte que l'ordre soit haut à bas.

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

J'utiliser std :: find_if() avec itérateurs inverse, quelque chose comme:

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

Vous devez définir la fonction sous-jacente is_less_than().

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

Answer 3

Ouais, lower_bound peut être utilisé pour cela, je l'ai vu avant et utilisé comme ça.

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

En fait, retournerait le plus grand, mais plus petit (si it! = Map.begin() était vrai). Si c'était à .begin, alors il n'y a pas de clé plus petite. Belle idée des commentaires est de retour .end s'il n'y a aucun élément qui est moins et emballer ce genre de choses en fonction:

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

Le modèle devrait fonctionner pour std::set aussi.

Answer 4

Votre méthode fonctionnera, mais vous devez vérifier que vous ne revenez pas au début de la carte. De plus, vous avez besoin de lower_bound, pas de upper_bound.

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

Answer 5

Je trouve toujours calculer étage (x) et Ceil (x) pour être utile 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;