C++

Fonctionnement de lower_bound / upper_bound / equal_range

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : Fonctionnement de lower_bound / upper_bound / equal_range

G_Nathan

Bonjour,

je ne comprends pas clairement le fonctionnement dans une map des méthodes lower_bound / upper_bound ou equal_range (qui regroupe pour ce dernier les deux méthodes).

Sur l'exemple suivant :

Code :

int main(int, char**)
{
int ival;
map<int, string, less<int> > MapIntString;
cout << "### MapIntString ###" << endl;
MapIntString[1] = "un";
MapIntString[2] = "deux";
MapIntString[3] = "trois";
MapIntString[7] = "sept";
MapIntString[8] = "huit";
ival = 4;
if (MapIntString.lower_bound(ival) != MapIntString.end())
cout << "Lower bound de " << ival << " = " << MapIntString.lower_bound(ival)->second << endl;
if (MapIntString.upper_bound(ival) != MapIntString.end())
cout << "Upper bound de " << ival << " = " << MapIntString.upper_bound(ival)->second << endl;
return (0);
}

J'obtiens l'affichage suivant pour ce que je pensais être les valeurs encadrants 4 :

Code :

### MapIntString ###
Lower bound de 4 = sept
Upper bound de 4 = sept

Alors que je m'attendais à :

Code :

### MapIntString ###
Lower bound de 4 = trois
Upper bound de 4 = sept

Pourriez-vous m'expliquez d'où vient ce problème ?
(que je constate également avec les doubles).

Comment récupérez l'encadrement réel ?
Faut-il ne travaillez qu'avec un seul itérateur et utiliser ensuite une itération ?

D'avance merci de votre aide,

Publicité

Malkav

Le problème vient d'une erreur de compréhension de lower_bound, il faut relire la spec:
http://msdn.microsoft.com/en-us/li [...] 71%29.aspx

En français lower_bound ne renvoie pas une valeur inférieure à la valeur de clé que tu passes en paramètre mais une valeur supérieure ou égale.
upper_bound renvoie la prochaine valeur strictement supérieure.

Dans ton exemple

Code :

lower_bound de 3 = 3
upper_bound de 3 = 7

Comme dans une map de la STL les éléments sont ordonnés par valeur de clé croissante, si tu veux la valeur de clé inférieure à celle que tu cherches il te suffirait de prendre l'élément immédiatement avant lower_bound, après avoir vérifier que tu es bien dans la limite de la map évidemment.

par exemple, si tu veux écrire ta propre fonction:

Code :

template <class T>
map<T>::iterator GetLastLowerElt(map<T> &myMap, const T &val)
{
map<T>::iterator it = myMap.lower_bound(val);
if (it != myMap.end() && it != myMap.begin()) {
--it;
}
return it;
}

De plus si tu veux t'éviter des plantages avant de l'utiliser il faut vérifier si l'iterator donné par un appel à lower_bound ou upper_bound est bien != de la fin de la map (.end()), sinon boum.

Message cité 1 fois
Message édité par Malkav le 09-07-2012 à 15:02:41

---------------
Mes feedbacks * Ma galerie photo

Meumeu85

Malkav a écrit :

par exemple, si tu veux écrire ta propre fonction:

Code :

template <class T>
map<T>::iterator GetLastLowerElt(map<T> &myMap, const T &val)
{
map<T>::iterator it = myMap.lower_bound(val);
if (it != myMap.end() && it != myMap.begin()) {
--it;
}
return it;
}

Dans ton exemple, si val est supérieur au plus grand élément de la map, ça marche pas, dans ce cas là, il faudrait renvoyer un itérateur vers le dernier élément. Et si val est le premier élément, il faudrait renvoyer un truc du genre myMap.end() puisqu'il n'y a pas d'élément strictement inférieur.

---------------
Hiommziùr

Malkav

j'avoue que j'ai écris ça à l'arrache ss trop réfléchir y'a ss doute des merdes mais c'est pour illustrer le propos.
Pour les résultats attendus, en fait ça dépend de ce que l'on spécifie (.end() ou .begin() s'il n'y a pas d'éléments inférieurs, effectivement mon choix est critiquable et dans le cas où it == myMap.begin() on pourrait retourner .end()).
Si val est le plus grand élément de la map alors lower_bound doit retourner ce plus grand élément et ça marche, si val est > au plus grand élément de la map je ne sais pas si lower_bound renvoie .end() ou non (je suppose que oui).

Si on fait ces modifs ça devrait donner

Code :

template <class T>
map<T>::iterator GetLastLowerElt(map<T> &myMap, const T &val)
{
map<T>::iterator it = myMap.lower_bound(val);
if (it == myMap.end()) {
// Val is > to the biggest key in map
// return last element
if (myMap.size() > 0)
--it;
}
else if (it == myMap.begin() {
// no element is < val, return end
it = myMap.end();
}
else {
--it;
}
return it;
}

Message édité par Malkav le 09-07-2012 à 15:39:02

---------------
Mes feedbacks * Ma galerie photo

FORUM HardWare.fr

Programmation

C++

Fonctionnement de lower_bound / upper_bound / equal_range

Sujets relatifs
range et cells	Problème range paramètré
fonctionnement d'un simulateur java	besoin d'explication du fonctionnement de cette partie de programme!
Variable tableau / Range("A1:A" & i) = montab - ne fonctionne pas	fonctionnement getchar en C
fonctionnement d'un group by	reconstruire bases de données mysql et information_schema
[Résolu] Fonctionnement des include et headers	Longueur maximal dans un Range("...") [Résolu]
Plus de sujets relatifs à : Fonctionnement de lower_bound / upper_bound / equal_range

Page générée en 0.059 secondes