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.
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Fabien LE LEZ
Le #305466
On Wed, 28 Mar 2007 15:54:24 +0200, JBB
pour l'instant j'en suis à faire : upper_bound() -1
mais ça me pose des problèmes lorsque upper_bound() renvoi end()


...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;
}

James Kanze
Le #305444
On Mar 28, 3:54 pm, 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?)


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.

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() ( q ue ma map soit vide ou non)
( ce qui explique peut être le 1)


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

Publicité
Poster une réponse
Anonyme