Fonctionnement de lower_bound / upper_bound / equal_range

Fonctionnement de lower_bound / upper_bound / equal_range - C++ - Programmation

Marsh Posté le 09-07-2012 à 09:23:40    

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 :
  1. int main(int, char**)
  2. {
  3. int ival;
  4. map<int, string, less<int> > MapIntString;
  5. cout << "### MapIntString ###" << endl;
  6. MapIntString[1] = "un";
  7. MapIntString[2] = "deux";
  8. MapIntString[3] = "trois";
  9. MapIntString[7] = "sept";
  10. MapIntString[8] = "huit";
  11. ival = 4;
  12. if (MapIntString.lower_bound(ival) != MapIntString.end())
  13.  cout << "Lower bound de " << ival << " = " << MapIntString.lower_bound(ival)->second << endl;
  14. if (MapIntString.upper_bound(ival) != MapIntString.end())
  15.  cout << "Upper bound de " << ival << " = " << MapIntString.upper_bound(ival)->second << endl;
  16. return (0);
  17. }


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

Code :
  1. ### MapIntString ###
  2. Lower bound de 4 = sept
  3. Upper bound de 4 = sept


 
Alors que je m'attendais à :
 

Code :
  1. ### MapIntString ###
  2. Lower bound de 4 = trois
  3. 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,

Reply

Marsh Posté le 09-07-2012 à 09:23:40   

Reply

Marsh Posté le 09-07-2012 à 14:49:20    

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 :
  1. lower_bound de 3 = 3
  2. 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 :
  1. template <class T>
  2. map<T>::iterator GetLastLowerElt(map<T> &myMap, const T &val)
  3. {
  4.      map<T>::iterator it = myMap.lower_bound(val);
  5.     if (it != myMap.end() && it != myMap.begin()) {
  6.        --it;
  7.     }
  8.    return it;
  9. }


 
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
Reply

Marsh Posté le 09-07-2012 à 15:12:40    

Malkav a écrit :


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

Code :
  1. template <class T>
  2. map<T>::iterator GetLastLowerElt(map<T> &myMap, const T &val)
  3. {
  4.      map<T>::iterator it = myMap.lower_bound(val);
  5.     if (it != myMap.end() && it != myMap.begin()) {
  6.        --it;
  7.     }
  8.    return it;
  9. }


 
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.


 
 
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
Reply

Marsh Posté le 09-07-2012 à 15:31:46    

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 :
  1. template <class T>
  2.     map<T>::iterator GetLastLowerElt(map<T> &myMap, const T &val)
  3.     {
  4.          map<T>::iterator it = myMap.lower_bound(val);
  5.         if (it == myMap.end()) {
  6.            // Val is > to the biggest key in map
  7.            // return  last element
  8.           if (myMap.size() > 0)
  9.             --it;
  10.         }
  11.         else if (it == myMap.begin() {
  12.            // no element is < val, return end
  13.           it = myMap.end();
  14.         }
  15.         else {
  16.           --it;
  17.         }
  18.        return it;
  19.     }


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

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

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed