std::map::lower_bound
Le
JBB
d'apres la doc: lower_bound(k)
Finds the first element whose key is not less than k.
si j'ai un map de clefs : 1 4 10
lower_bound(2) -> 4
lower_bound(4) -> 4
upper_bound(k)
Finds the first element whose key greater than k.
upper_bound(2) -> 4
upper_bound(4) -> 10
Je ne trouve pas le méthode qui donnerait:
f(2) -> 1
f(4) -> 4
cad à dire qui me trouve le dernier élément de clef inférieure à k.
1) pourquoi une telle méthode n'existe pas? (à cause de l'implémentation des map?)
2) y a t'il un moyen simple de réaliser ça.
pour l'instant j'en suis à faire : upper_bound() -1
mais ça me pose des problèmes lorsque upper_bound() renvoi end() ( que ma map soit vide ou non)
( ce qui explique peut être le 1)
3) sinon je met greater ou lieu de less par défaut dans la méthode de comparaison à la déclaration de ma map.
du coup upper_bound() me convient.
Mais quand je veux parcourir ma map il faut que je fasse des rbegin() et rend() avec des reverse_iterator ce qui ne me plais guère.
Dans mon cas concret, la clef représente une date, et je stocke un map d'états, le but étant d'insérer dans la map chaque
changement d'état ( date + nouvel état), et récupérer ainsi rapidement l'état à n'importe quelle date donnée.
Finds the first element whose key is not less than k.
si j'ai un map de clefs : 1 4 10
lower_bound(2) -> 4
lower_bound(4) -> 4
upper_bound(k)
Finds the first element whose key greater than k.
upper_bound(2) -> 4
upper_bound(4) -> 10
Je ne trouve pas le méthode qui donnerait:
f(2) -> 1
f(4) -> 4
cad à dire qui me trouve le dernier élément de clef inférieure à k.
1) pourquoi une telle méthode n'existe pas? (à cause de l'implémentation des map?)
2) y a t'il un moyen simple de réaliser ça.
pour l'instant j'en suis à faire : upper_bound() -1
mais ça me pose des problèmes lorsque upper_bound() renvoi end() ( que ma map soit vide ou non)
( ce qui explique peut être le 1)
3) sinon je met greater ou lieu de less par défaut dans la méthode de comparaison à la déclaration de ma map.
du coup upper_bound() me convient.
Mais quand je veux parcourir ma map il faut que je fasse des rbegin() et rend() avec des reverse_iterator ce qui ne me plais guère.
Dans mon cas concret, la clef représente une date, et je stocke un map d'états, le but étant d'insérer dans la map chaque
changement d'état ( date + nouvel état), et récupérer ainsi rapidement l'état à n'importe quelle date donnée.
Poser une question
...ou begin().
On peut écrire "upper_bound()-1" ainsi :
template <class Map, class Clef>
Map::const_iterator f (Map const& m, Clef const& c)
{
Map::const_iterator reponse= m.upper_bound (c);
if (reponse != m.end() && reponse != m.begin())
--reponse;
return reponse;
}
et la même chose en non-const :
template <class Map, class Clef>
Map::iterator f (Map& m, Clef const& c)
{
Map::iterator reponse= m.upper_bound (c);
if (reponse != m.end() && reponse != m.begin())
--reponse;
return reponse;
}
Parce que toute la STL tourne autour du concepte de l'intervale
mi-ouvert, avec une borne inférieur inclusive, et une borne
supérieur exclusive.
Moi, je ferais quelque chose du genre :
Map::iterator i = map.lower_bound( i ) ;
if ( i != map.begin() && i->first != i ) {
-- i ;
}
(Mais le problème, c'est qu'est-ce que tu veux pour f(0) ?
Trouver un itérateur vers un élément dont le clé est inférieur
ou égal à 0 va être difficile.)
--
James Kanze (GABI Software) email:
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34