justification de std :: lower_bound et std :: upper_bound?

Si vous avez plusieurs éléments dans la plage [ first , last ] dont la valeur est égale à la valeur val vous recherchez, alors la plage [ l , u ] où

 l = std::lower_bound(first, last, val) u = std::upper_bound(first, last, val) 

est précisément la plage d’éléments égale à val dans l’intervalle [ first , last ]. Donc, l et u sont la “limite inférieure” et la “limite supérieure” pour la plage égale . Cela a du sens si vous êtes habitué à penser en termes d’intervalles à moitié ouverts.

(Notez que std::equal_range renverra les limites inférieure et supérieure dans une paire, en un seul appel.)

 std::lower_bound 

Renvoie un iterator pointant vers le premier élément de la plage [first, last] qui n’est pas inférieur à (c’est-à-dire supérieur ou égal à ).

 std::upper_bound 

Renvoie un iterator pointant vers le premier élément de la plage [first, last] supérieur à la valeur.

Donc, en mélangeant les limites inférieure et supérieure, vous pouvez décrire exactement où votre gamme commence et où elle se termine.

Est-ce que cela a du sens?

Oui.

Exemple:

imagine le vecteur

 std::vector data = { 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 }; auto lower = std::lower_bound(data.begin(), data.end(), 4); 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 // ^ lower auto upper = std::upper_bound(data.begin(), data.end(), 4); 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 // ^ upper std::copy(lower, upper, std::ostream_iterator(std::cout, " ")); 

estampes: 4 4 4

http://fr.cppreference.com/w/cpp/algorithm/lower_bound

http://fr.cppreference.com/w/cpp/algorithm/upper_bound

Dans ce cas, je pense qu’une image vaut mille mots. Supposons que nous les utilisons pour rechercher 2 dans les collections suivantes. Les flèches indiquent quels iterators les deux renverraient:

Donc, si vous avez plus d’un object avec cette valeur déjà présente dans la collection, lower_bound vous donnera un iterator faisant référence au premier d’entre eux et upper_bound donnera un iterator qui fait référence à l’object immédiatement après le dernier leur.

Cela (entre autres choses) rend les iterators renvoyés utilisables comme paramètre de hint à insert .

Par conséquent, si vous les utilisez comme indicateur, l’élément que vous insérez deviendra le nouveau premier élément avec cette valeur (si vous avez utilisé lower_bound ) ou le dernier élément avec cette valeur (si vous avez utilisé upper_bound ). Si la collection ne contenait pas auparavant un élément avec cette valeur, vous obtiendrez toujours un iterator qui peut être utilisé comme hint pour l’insérer au bon endroit dans la collection.

Bien sûr, vous pouvez également insérer sans indice, mais en utilisant un indice, vous obtenez la garantie que l’insertion se termine avec une complexité constante, à condition que le nouvel élément à insérer puisse être inséré immédiatement avant l’élément indiqué par l’iterator (comme dans ces deux cas).

Considérez la séquence

1 2 3 4 5 6 6 6 7 8 9

la limite inférieure pour 6 est la position des 6 premiers.

la limite supérieure pour 6 est la position du 7.

ces positions servent de paire (début, fin) commune désignant la série de 6 valeurs.

Exemple:

 #include  #include  #include  using namespace std; auto main() -> int { vector v = {1, 2, 3, 4, 5, 6, 6, 6, 7, 8, 9}; auto const pos1 = lower_bound( v.begin(), v.end(), 6 ); auto const pos2 = upper_bound( v.begin(), v.end(), 6 ); for( auto it = pos1; it != pos2; ++it ) { cout << *it; } cout << endl; } 

J’ai accepté la réponse de Brian, mais je viens juste de me rendre compte d’une autre façon utile d’y réfléchir, ce qui ajoute de la clarté pour moi, alors j’ajoute ceci pour référence.

Considérez l’iterator renvoyé comme pointant, pas à l’élément * iter, mais juste avant cet élément, c’est -à- dire entre cet élément et l’élément précédent de la liste s’il y en a un. En y repensant, les contrats des deux fonctions deviennent symésortingques: lower_bound trouve la position de la transition de = val et upper_bound trouve la position de la transition de <= val à> val. Autrement dit, lower_bound est le début de la plage d’éléments qui se compare à val (c’est-à-dire la plage renvoyée par std :: equal_range) et upper_bound est la fin de ceux-ci.

J’aimerais qu’ils en parlent comme ça (ou l’une des autres bonnes réponses données) dans les docs; cela le rendrait beaucoup moins mystifiant!

Les deux fonctions sont très similaires, car elles trouveront un point d’insertion dans une séquence sortingée qui conservera le sorting. S’il n’y a aucun élément existant dans la séquence qui soit égal à l’élément de recherche, ils renverront le même iterator.

Si vous essayez de trouver quelque chose dans la séquence, utilisez lower_bound – il pointera directement sur l’élément s’il est trouvé.

Si vous insérez dans la séquence, utilisez upper_bound – cela préserve le upper_bound original des doublons.

Il y a déjà de bonnes réponses sur ce que std::lower_bound et std::upper_bound est.

Je voudrais répondre à votre question “comment s’en souvenir” ?

Il est facile de comprendre / se souvenir si nous faisons une analogie avec les méthodes STL begin() et end() de tout conteneur. begin() renvoie l’iterator de départ au conteneur tandis que end() renvoie l’iterator qui se trouve juste en dehors du conteneur et nous soaps tous à quel point ils sont utiles lors de l’itération.

Maintenant, sur un conteneur sortingé et une valeur donnée, lower_bound et upper_bound gamme d’iterators pour cette valeur facile à itérer (tout comme début et fin)

Utilisation pratique ::

Outre l’utilisation mentionnée ci-dessus sur la liste sortingée pour accéder à la plage pour une valeur donnée, l’une des meilleures applications de upper_bound consiste à accéder aux données ayant une relation plusieurs-à-un dans une carte.

Par exemple, considérons la relation suivante: 1 -> a, 2 -> a, 3 -> a, 4 -> b, 5 -> c, 6 -> c, 7 -> c, 8 -> c, 9 – > c, 10 -> c

Les 10 correspondances ci-dessus peuvent être enregistrées sur la carte comme suit:

 numeric_limits::lowest() : UND 1 : a 4 : b 5 : c 11 : UND 

Les valeurs peuvent être accessibles par l’expression (--map.upper_bound(val))->second .

Pour les valeurs de T allant de la plus basse à 0, l’expression retournera UND . Pour les valeurs de T allant de 1 à 3, il retournera “a” et ainsi de suite.

Maintenant, imaginons que nous ayons 100 mappages de données sur une valeur et 100 sur de tels mappages. Cette approche réduit la taille de la carte et la rend ainsi efficace.

Pour un tableau ou un vecteur:

std :: lower_bound: Retourne un iterator pointant vers le premier élément de la plage

• inférieure ou égale à valeur (pour tableau ou vecteur dans l’ordre décroissant)
• supérieure ou égale à valeur (pour un tableau ou un vecteur dans l’ordre croissant)

std :: upper_bound: Retourne un iterator pointant vers le premier élément de la plage

• valeur inférieure à (pour tableau ou vecteur dans l’ordre décroissant)

• supérieur à la valeur. (pour tableau ou vecteur dans l’ordre croissant)

Oui. La question a absolument un point. Quand quelqu’un donnait leur nom à ces fonctions, ils ne pensaient qu’à des tableaux sortingés avec des éléments répétés. Si vous avez un tableau avec des éléments uniques, “std :: lower_bound ()” ressemble plus à une recherche d’une “limite supérieure”, à moins qu’il ne trouve l’élément réel.

C’est ce que je retiens de ces fonctions:

• Si vous effectuez une recherche binary, envisagez d’utiliser std :: lower_bound () et lisez le manuel. std :: binary_search () y est également basé.
• Si vous voulez trouver la “place” d’une valeur dans un tableau sortingé de valeurs uniques, considérez std :: lower_bound () et lisez le manuel.
• Si vous avez une tâche arbitraire de recherche dans un tableau sortingé, lisez le manuel des deux std :: lower_bound () et std :: upper_bound ().

Si vous ne lisez pas le manuel au bout d’un mois ou deux depuis que vous avez utilisé ces fonctions pour la dernière fois, cela conduit presque certainement à un bogue.