Programare Competitivă

Alte funcții utile din STL

Biblioteca <algorithm> și alte headere conțin funcții mici dar extrem de utile la concursuri. Le prezentăm pe cele mai frecvente.

#include <algorithm>

min și max

cout << min(3, 7);     // 3
cout << max(3, 7);     // 7

// Cu mai multe valori:
cout << min({3, 7, 2, 9}); // 2
cout << max({3, 7, 2, 9}); // 9

min_element și max_element pe vectori

vector<int> v = {3, 7, 2, 9, 4};

auto it = min_element(v.begin(), v.end());
cout << *it;                  // 2
cout << it - v.begin();       // 2 (indexul)

auto it2 = max_element(v.begin(), v.end());
cout << *it2;                 // 9

swap

Interschimbă două valori:

int a = 3, b = 7;
swap(a, b);
cout << a << " " << b; // 7 3

Funcționează cu orice tip: int, string, vector, pair.

reverse

Inversează un vector (sau o porțiune):

vector<int> v = {1, 2, 3, 4, 5};

reverse(v.begin(), v.end());
// v = {5, 4, 3, 2, 1}

// Inversare parțială:
reverse(v.begin() + 1, v.begin() + 4);
// inversează pozițiile 1, 2, 3

Pe vector clasic:

reverse(v + 1, v + n + 1); // inversează v[1]..v[n]

unique

Elimină elementele duplicate consecutive (vectorul trebuie sortat):

vector<int> v = {1, 1, 2, 3, 3, 3, 4};

auto it = unique(v.begin(), v.end());
v.erase(it, v.end()); // ștergem elementele de după

// v = {1, 2, 3, 4}

Numărare elemente distincte

sort(v.begin(), v.end());
int distincte = unique(v.begin(), v.end()) - v.begin();

next_permutation

Generează următoarea permutare în ordine lexicografică:

vector<int> v = {1, 2, 3};

do {
    for (int x : v)
        cout << x << " ";
    cout << endl;
} while (next_permutation(v.begin(), v.end()));
Output:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Generează toate cele n! permutări. Vectorul trebuie sortat inițial pentru a le obține pe toate.

Atenție: pentru n > 10, n! devine enorm (10! = 3.628.800). Nu folosi pe vectori mari.

accumulate - suma elementelor

#include <numeric>

vector<int> v = {3, 7, 2, 9, 4};

int suma = accumulate(v.begin(), v.end(), 0);
cout << suma; // 25

Al treilea parametru e valoarea inițială (de obicei 0 pentru sumă).

count și count_if

vector<int> v = {3, 7, 2, 3, 4, 3};

int cnt = count(v.begin(), v.end(), 3);
cout << cnt; // 3 (de câte ori apare 3)

int pare = count_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; });
cout << pare; // 2 (câte numere pare)

fill

Umple un interval cu o valoare:

vector<int> v(10);
fill(v.begin(), v.end(), -1);
// toate elementele devin -1

Pe vector clasic:

fill(v + 1, v + n + 1, 0); // v[1]..v[n] = 0

__gcd (sau gcd din C++17)

Returnează CMMDC-ul celor 2 numere

cout << __gcd(12, 18); // 6

// C++17:
#include <numeric>
cout << gcd(12, 18);   // 6
cout << lcm(4, 6);     // 12

abs

Face valoarea absolută (în modul)

#include <cstdlib> // sau <cmath>

cout << abs(-5);   // 5
cout << abs(3);    // 3

to_string și stoi

Conversie între numere și text:

#include <string>

string s = to_string(42);   // "42"
int n = stoi("123");         // 123

Tabel rezumativ

Funcție Ce face Header Complexitate
min(a, b) Minimul <algorithm> O(1)
max(a, b) Maximul <algorithm> O(1)
swap(a, b) Interschimbare <algorithm> O(1)
reverse(begin, end) Inversare <algorithm> O(n)
unique(begin, end) Elimină duplicate consecutive <algorithm> O(n)
next_permutation Următoarea permutare <algorithm> O(n)
accumulate(begin, end, init) Suma <numeric> O(n)
count(begin, end, x) Numără x <algorithm> O(n)
fill(begin, end, val) Umple cu val <algorithm> O(n)
__gcd(a, b) CMMDC built-in O(log n)
abs(x) Valoare absolută <cstdlib> O(1)

Greșeli frecvente

1. unique fără sort

unique elimină doar duplicate consecutive. Dacă vectorul nu e sortat, nu elimină toate duplicatele.

2. unique fără erase

unique nu micșorează vectorul - doar mută duplicatele la final. Trebuie erase după.

3. accumulate cu overflow

vector<int> v(100000, 100000);
int suma = accumulate(v.begin(), v.end(), 0); // OVERFLOW!
long long suma = accumulate(v.begin(), v.end(), 0LL); // CORECT

Valoarea inițială 0LL face ca suma să fie long long.

Ce să reții

  • min, max, swap - operații de bază, O(1).
  • reverse - inversare vector, O(n).
  • unique - elimină duplicate consecutive (sortează întâi), O(n).
  • next_permutation - generează permutări, doar pentru n mic.
  • accumulate - suma, atenție la overflow.
  • fill - umple cu o valoare.
  • __gcd - CMMDC fără implementare manuală.
Cuprins Inapoi Inainte