lower_bound vs upper_bound: limitele unei valori

Într-o secvență sortată crescător, lower_bound găsește prima poziție cu valoare mai mare sau egală cu ținta. upper_bound găsește prima poziție cu valoare strict mai mare. Diferența dintre cele două poziții descrie toate aparițiile țintei.

Urmărește două margini

Pentru 1 3 3 3 7 și ținta 3, limita inferioară este indicele 1, iar limita superioară este indicele 4. Aparițiile ocupă intervalul cu început inclus și final exclus [1,4). Numărul lor este 4-1=3.

Pentru ținta 2, ambele limite sunt indicele 1, unde ar putea fi inserată valoarea fără să strice ordinea. Intervalul este gol, deci ținta lipsește. Rezultatul lower_bound nu confirmă singur existența unei valori egale.

Poziția de după ultimul element

Dacă nu există un element care să satisfacă limita căutată, rezultatul este end. Aceasta este poziția de după ultimul element, nu un element suplimentar. Nu o dereferenția și nu accesa tabloul la indicele n.

Pentru a verifica existența cu lower_bound, verifici mai întâi că rezultatul diferă de end și apoi că valoarea de acolo este egală cu ținta. Ordinea condițiilor contează: citirea valorii înainte de verificarea limitei poate fi invalidă.

În 1,3,3,3,7, pentru ținta 3 lower_bound este poziția 1, iar upper_bound este poziția 4. Intervalul [1,4) conține trei apariții.Mărește schema ↗

Ordinea trebuie să fie compatibilă

Pentru această utilizare simplă, sortează crescător și folosește comparația obișnuită. Dacă sortezi după alt comparator, căutarea trebuie să folosească o ordine compatibilă. O secvență nesortată nu devine potrivită doar fiindcă apelul funcției compilează.

Pe un tablou sau vector, accesul la poziția din mijloc este direct, iar căutarea folosește un număr logaritmic de pași. Nu transfera automat aceeași analiză de deplasare către orice tip de iterator: unele structuri nu permit saltul direct la mijloc.

Cazurile pe care merită să le testezi

Testează ținta înaintea tuturor elementelor, după toate elementele, prezentă o dată și repetată pe întreaga secvență. Include vectorul gol dacă funcția ta îl acceptă. Pentru o secvență goală, ambele limite sunt end și frecvența este zero.

Un desen cu pozițiile 0..n ajută mai mult decât memorarea numelor: elementele ocupă 0..n-1, iar poziția n poate reprezenta o margine validă a unui interval, fără să fie un indice valid pentru citire.

Continuă cu căutarea binară, iteratorii STL și sortarea.

Întrebări frecvente

Care este diferența dintre lower_bound și upper_bound?

Într-un tablou sortat crescător, lower_bound găsește prima valoare cel puțin egală cu ținta, iar upper_bound prima valoare strict mai mare. Ele delimitează grupul de valori egale.

Cum număr aparițiile unei valori cu lower_bound și upper_bound?

Pentru un tablou sau vector sortat, scade iteratorul întors de lower_bound din cel întors de upper_bound. Diferența este numărul aparițiilor, inclusiv zero dacă valoarea lipsește.

Pot accesa direct rezultatul unei căutări bound?

Nu fără verificare. Rezultatul poate fi iteratorul de sfârșit, care nu desemnează un element. Pentru testarea existenței țintei, verifică sfârșitul și apoi egalitatea valorii găsite.