Folosirea bibliotecii STL în rezolvarea unor probleme de concurs

Dumitrescu Ovidiu, Dumitrescu Mihaela ,CN Mircea cel Bătrân -Rm.Vâlcea

I. Despre STLStandard Template Library (STL) este o bibliotecă generică, ce

furnizează soluţii pentru manipularea colecţiilor de date, precum şi algoritmi eficienţi care acţionează asupra acestor date.STL, este o biblioteca formata din clase container, algoritmi si iteratori. Toate componentele STL sunt şabloane de clase sau şabloane de functii. Biblioteca STL este parte integranta a C++ Standard Library. Aceasta din urma, la randul ei, extinde limbajul C++.

STL (Standard Template Library) privit foarte simplu, din punctul de vedere al concurentului, este o colecţie de structuri de date şi algoritmi aplicaţi asupra acestora. La concursurile de nivelul Olimpiadei Nationale de Informatică, STL-ul se poate folosi si este de un real folos pentru elevii care au aprofundat limbajul C++ şi stăpânesc aceste biblioteci. Sfătuim concurenţii să studieze cu atenţie şi algoritmii clasici de sortare rapidă, de generare de permutări, de căutare binară,etc şi să nu se bazeze în concursuri doar pe aceste cunostinţe avansate de STL. De multe ori la concursuri se dau probleme asemănatoare algoritmilor clasici in care folosirea acestor biblioteci nu mai poate fi facută iar cunoştinţele acumulate în eleborarea algoritmilor clasici le vor fi de un real folos. Folosirea STL în concursuri trebuie să reprezinte doar un instrument ajutător menit să salveze timp şi memorie. Pentru scopurile în care vom folosi noi STL-ul nu este nevoie de cunoştinţe avansate de programare orientatã obiect. STL-ul se bazeazã pe câteva template-uri (şabloane) care fac aplicabili toţi algoritmii pentru orice tip de structuri de date. Pentru a vã arãta importanţa STL-ului trebuie precizat de la început faptul cã aceastã librãrie este standard. Toate exemplele au fost testate cu MinGW. Datoritã faptului cã librãria este relativ nouã, ea nu este disponibilã în Borland C++ 3.1.

40II. Aplicaţii C++ în care folosim biblioteca STL

Un prim exemplu de aplicaţie în care “puterea STL-ului” este evidentă poate fi considerată problema generării de permutări. Există diverse metode de rezolvare a problemei de mai jos, însă fiecare dintre ele necesită un timp de ordinul O(n!). Putem genera permutările prin metoda ordinii lexicografice crescătoare, prin definiţia recursivă a permutărilor sau folosind reprezentarea acestora prin vectorii de inversiune. Algoritmul “next_permutation” din STL are complexitate O(last-first)/2 interschimbări şi are următoarele prototipuri:

1

template <class BidIt>bool next_permutation(BidIt first, BidIt last);

template <class BidIt, class BinPred> bool next_permutation(BidIt first, BidIt last, BinPred pr);

Efectul constă în transformarea secvenţei definită de intervalul [first, last] în permutarea următoare în ordine lexicografică. Pentru compararea elementelor, prima funcţie utilizează operator<, iar cealaltă predicatul binar pr. Algoritmul “next_permutation” returnează true, dacă o permutare următoare există. Dacă nu există, atunci transformă secvenţa în cea mai mică permutare, in ordine lexicografică, şi returnează false.Generare de permutariSa se genereze toate permutarile multimii {1, 2, ...N}, in ordine lexicografica.

Date de intrare:In fisierul de intrare permutari.in se gaseste pe prima linie numarul natural N.

Date de iesire:In fisierul de iesire permutari.out se vor afisa permutarile multimii, fiecare pe cate o

linie.

Restrictii:

1 ≤ N ≤ 8

Exemplu:

permutari.in permutari.out

3 1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

Sursa in C++ cu folosirea bibliotecii STL este urmatoarea:#include <stdio.h>#include <algorithm>using namespace std;int main(){ int i,v[100],n; freopen("permutari.in","r",stdin); freopen("permutari.out","w",stdout);

2

scanf("%d",&n); for (i=1;i<=n;i++) {v[i]=i;printf("%d ",v[i]);}printf("\n"); while (next_permutation(v+1, v+1+n)) /*next_permutation va returna false dupa afisarea celor n! permutari*/ {for (i=1;i<=n;i++) printf("%d ",v[i]);printf("\n"); } return 0;}Un alt exemplu de folosire a STL-ului în rezolvarea unor probleme este dat în exemplul de mai jos în care se foloseşte un algoritm de căutare binară precedat de un algoritm de sortare. STL-ul propune algoritmi de sortare puternic optimizaţi în ordonarea elementelor într-un interval. Nu întotdeauna avem nevoie de o sortare completă. De exemplu dacă dorim să identificăm doar primele zece elemente ordonate crescător, dintre cele n din container, utilizăm unul dintre algoritmii de sortare parţială din STL. În asemenea situaţii, este preferabilă utilizarea acestora, întrucât oferă o performanţă mai bună. Algoritmul “sort”, are următoarele prototipuri:template <class RanIt>

void sort(RanIt first, RanIt last) Sortează elementele din intervalul [first,last) şi are o complexitate de O(N*log N) comparaţii, unde N==last-first.Algoritmul “upper_bound” face parte din clasa algoritmilor de căutare binară şi are următoarele prototipuri:template <class FwdIt, class T>

FwdIt upper_bound(FwdIt first, FwdIt last, const T& val);template <class FwdIt, class T, class BinPred>

FwdIt upper_bound(FwdIt first, first, FwdIt last, const T& val, BinPred pr); Acest prototip găseşte cea mai îndepărtată poziţie în care val poate fi inserat, astfel încât să nu strice relaţia de ordine. Returnează cel mai îndepărtat iterator i din intervalul [first, last], astfel încât, pentru fiecare iterator j din intervalul [first, i), au loc următoarele condiţii corespunzătore: !(val < *j) sau pr(val, *j) == false. Complexitatea este O(log(last-first)+1 .

În aplicaţia de mai sus am prezentat doar trei algoritmi STL : “next_permutation”,” sort” şi ”upper_bound”. Am dorit să arătăm cât de eficiente sunt aceste tehnici STL în rezolvarea acestor probleme. Sperăm ca prin această expunere să vă facem curioşi să studiaţi întreaga bibliotecă STL pentru rezolvarea anumitor probleme de concurs. O bibliotecă ne devine utilă din momentul în care ştim să folosim instrumentele pe care le pune la dispoziţie. Pentru programatori (iar pe olimpicii noştri îi putem numi deja “programatori”), răspunsul la întrebarea “cum este construit ?” un anumit instrument de lucru este mai puţin important decât deprinderea de a folosi în mod efectiv acest instrument în rezolvarea sarcinilor concrete.

3

4