STL: vector, pair, iteratori și căutare binară

Biblioteca standard C++ oferă containere pentru date și algoritmi care lucrează pe intervale. std::vector gestionează o secvență dinamică, std::pair grupează două valori, iar iteratorii descriu poziții într-un container. Înțelegerea acestor convenții contează mai mult decât memorarea unor apeluri.

Vom sorta numere și vom găsi intervalul tuturor aparițiilor unei valori cu lower_bound și upper_bound. Începem cu tabloul clasic, apoi folosim un vector cu aceeași dimensiune logică și același rezultat.

Cum funcționează

Un interval standard este de obicei semi-deschis: [first,last). Poziția first este inclusă, last este exclusă. Pentru un tablou cu n elemente, a și a+n descriu exact intervalul valid, chiar dacă a+n nu poate fi dereferențiat. Pentru vector, begin() și end() joacă rolurile corespunzătoare. Intervalul gol are începutul egal cu sfârșitul.

După sortare crescătoare, lower_bound întoarce prima poziție unde elementul nu este mai mic decât x, adică este >=x. upper_bound întoarce prima poziție cu element >x. Dacă poziția nu există, rezultatul este end(). Diferența dintre cele două poziții este numărul aparițiilor lui x. Căutarea are nevoie de ordinea compatibilă cu comparatorul; folosirea ei pe date arbitrare nu este o căutare corectă.

std::pair<int,int> poate memora cele două capete. Câmpurile first și second nu au semnificație specială pentru bibliotecă; programul decide că reprezintă începutul inclusiv și sfârșitul exclusiv. Pentru vector, scăderea iteratorilor este permisă deoarece aceștia oferă acces aleator. Aceeași expresie nu funcționează pentru orice container, de exemplu pentru iteratorii unui set.

Dimensiunea size() spune câte elemente există. Capacitatea capacity() spune câte pot încăpea înainte de o posibilă realocare. reserve(100) rezervă spațiu, dar nu creează o sută de elemente; resize(100) modifică dimensiunea. push_back adaugă la sfârșit și poate invalida iteratorii și referințele dacă realocă. Programul de mai jos creează direct n elemente, cu 0 <= n <= 100000, apoi nu schimbă dimensiunea, deci iteratorii utilizați rămân valizi pe durata căutărilor.

Exemplu urmărit pas cu pas

Pentru intrarea 4,2,4,1,4 și ținta 4, sortarea produce 1,2,4,4,4. lower_bound dă indicele 2, iar upper_bound indicele 5, care este sfârșitul exclusiv. Diferența este 3.

Pentru ținta 3 în același vector, ambele funcții dau poziția 2 și numărul aparițiilor este zero. Acea poziție este locul unde 3 ar putea fi inserat păstrând ordinea. Pentru ținta 9, ambele rezultate sunt n; nu accesăm a[n], ci folosim doar poziția.

Implementare C++17

Varianta clasică:

#include <algorithm>
#include <iostream>
#include <utility>
int main() {
    int n, x;
    std::cin >> n >> x;
    int a[100000];
    for (int i = 0; i < n; ++i)
        std::cin >> a[i];
    std::sort(a, a + n);
    int l = std::lower_bound(a, a + n, x) - a;
    int r = std::upper_bound(a, a + n, x) - a;
    std::pair<int, int> range = {l, r};
    std::cout << range.first << ' ' << range.second << ' ' << r - l << '\n';
}

Varianta vector folosește begin() și end():

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
int main() {
    int n, x;
    std::cin >> n >> x;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i)
        std::cin >> a[i];
    std::sort(a.begin(), a.end());
    int l = std::lower_bound(a.begin(), a.end(), x) - a.begin();
    int r = std::upper_bound(a.begin(), a.end(), x) - a.begin();
    std::pair<int, int> range = {l, r};
    std::cout << range.first << ' ' << range.second << ' ' << r - l << '\n';
}

Vector cu dimensiune care crește la citire

Păstrăm numai valorile strict pozitive din cel mult 100000 de numere. În tabloul clasic, size este dimensiunea logică, iar capacitatea este 100000. În vector pornim cu zero elemente și folosim push_back. reserve(n) reduce realocările, fără să creeze elemente. Nu accesăm positive[0] imediat după reserve, deoarece vectorul poate fi încă gol.

Ambele variante păstrează ordinea și au timp O(n), cu memorie O(n) în cazul nefavorabil. Varianta dinamică află numărul păstrat prin size(). Dacă elimini reserve, rezultatul rămâne același, însă pot exista realocări pe parcurs; costul inserării la sfârșit rămâne amortizat constant.

Varianta clasică:

#include <iostream>
int main() {
    int n;
    std::cin >> n;
    int positive[100000], size = 0;
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        if (x > 0)
            positive[size++] = x;
    }
    std::cout << size << '\n';
    for (int i = 0; i < size; ++i)
        std::cout << positive[i] << ' ';
    std::cout << '\n';
}

Varianta dinamică std::vector:

#include <iostream>
#include <vector>
int main() {
    int n;
    std::cin >> n;
    std::vector<int> positive;
    positive.reserve(n);
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        if (x > 0)
            positive.push_back(x);
    }
    std::cout << positive.size() << '\n';
    for (int x : positive)
        std::cout << x << ' ';
    std::cout << '\n';
}

De ce funcționează și cât costă

Sortarea face ca predicatele a[i]<x și a[i]<=x să aibă câte o frontieră. Căutarea binară localizează aceste frontiere, iar toate elementele egale cu x sunt exact între ele. Perechea capetelor păstrează intervalul fără a copia elementele.

Sortarea costă O(n log n), cele două căutări O(log n) pe tablouri sau vectori. Numărarea prin diferența capetelor este O(1). Programul memorează O(n) date; vectorul gestionează automat memoria sa, dar nu elimină costul algoritmilor.

Greșeli frecvente

Nu dereferenția end(). Nu indexa un vector doar rezervat, fără elemente create. Nu păstra iteratori peste operații care îi invalidează. Nu folosi comparator cu <= la sortare: ordinea trebuie să fie strictă. Pentru date deja sortate, sortarea inițială poate fi omisă.

Exersează

Pentru 1,2,2,2,5, găsește capetele intervalului valorii 2 și ale valorii 4.

Rezolvare explicată: Pentru 2, capetele sunt 1 și 4, deci trei apariții. Pentru 4, ambele sunt 4, deci zero apariții și poziție de inserare înaintea lui 5.

Continuă să înveți

Căutare, sortare și inserare.

Întrebări frecvente

Ce întoarce lower_bound dacă valoarea lipsește?

Prima poziție unde valoarea ar putea fi inserată înaintea unui element mai mare, sau sfârșitul intervalului. Nu întoarce automat un indicator separat de eroare.

Cum număr valorile egale cu x?

Într-un interval sortat, scazi lower_bound din upper_bound. Rezultatul este lungimea intervalului ocupat de toate aparițiile lui x.

reserve și resize sunt echivalente?

Nu. reserve modifică rezerva de memorie, iar resize modifică numărul elementelor existente. Accesul prin indice trebuie să fie sub size(), nu doar sub capacity().

Pot citi valoarea de la end()?

Nu. end() marchează poziția de după ultimul element. Poate fi comparat sau folosit drept capăt exclusiv, dar nu dereferențiat.

La ce folosește pair?

Grupează două valori într-un singur obiect, accesibile prin first și second. Este util pentru coordonate, intervale sau rezultate cu două componente, dacă semnificația lor este clară.