[LABORATOR DE PROGRAMARE C++]
Aritoni Ovidiu
Algoritmi STL
1. Prezentare general
2. Clasificare:
Algoritmi nechirurgicali ;
Algoritmi chirurgicali ;
Algoritmi de sortare;
Algoritmi generali;
3. Algoritmi nechirurgicali (Non-mutating algorithms)
Aceti algoritmi dup cum le spune i numele sunt algoritmi care nu modific variabilele sau
structurile de date pe care le manipuleaz.
n continuare este prezentat o list de astfel de algoritmi, i cteva exemple.
for_each()
- Efectueaz o operaie pentru fiecare element
count() - Returneaza numarul de elemente
count_if() - Returneaza numarul de elemente care se potrivesc cu un criteriu
min_element()- Returneaza elemental cu valoarea ce mai mica
max_element()- Returneaza elemental cu valoarea ce mai mare
find()
- Cauta primul element cu o valoare trecuta
find_if() - Cauta primul element care se potriveste cu un criteriu
search_n()
- Cauta primele n elemente consecutive cu anumite proprietati
search() - Cauta prima aparitie a unui subrang
find_end()
- Cauta ultima aparitie a unui subrang
find_first_of() - Cauta primul element din mai multe posibile
adjacent_find()-Cauta 2 elemente adiacente care sunt egale(dupa un criteriu)
equal()
- Verifica daca 2 ranguri sunt egale
mismatch()
- Returneaza primul element din 2 secvente care difera
3.1 Count()
Count() gaseste numrul de elemente n [prima, ultima), care sunt egale cu o valuare. Mai exact, prima
versiune de count() returneaz numrul de iteratori i n [prima, ultima), astfel nct * i == valoare. Cea
de-a doua versiune a count() adaug la n numrul de iteratori i n [prima, ultima), astfel nct * i ==
valoare.
Exemplu:
int main() {
[LABORATOR DE PROGRAMARE C++]
Aritoni Ovidiu
int A[] = { 2, 0, 4, 6, 0, 3, 1, -7 };
const int N = sizeof(A) / sizeof(int);
cout << "Number of zeros: "
<< count(A, A + N, 0)
<< endl;
3.2 Equal
Exemplu
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool mypredicate (int i, int j) {
return (i==j);
}
int main () {
int myints[] = {34,14,62,56,123};
vector<int> myvector (myints,myints+5);
if (equal ([Link](), [Link](), myints))
cout << "The contents of both sequences are equal." << endl;
else
cout << "The contents of both sequences differ." << endl;
myvector[3]=81;
if (equal ([Link](), [Link](), myints, mypredicate))
cout << "The contents of both sequences are equal." << endl;
else
cout << "The contents of both sequences differ." << endl;
return 0;
}
3.3 Find
Exemplu
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main()
{
const string delArr[] = {" ", "\t", "(", ")", "[", "]", "{", "}",
";", "<", ">", "=", "+", "-", "*", "&"};
vector<string> delimiters(delArr,delArr +
sizeof(delArr)/sizeof(delArr[0]));
[LABORATOR DE PROGRAMARE C++]
Aritoni Ovidiu
string str = "&";
vector<string>::iterator it =find([Link](), [Link](), str);
if (it != [Link]())
{
cout << "Found delimiter" << endl;
}
else
{
cout << "No dice" << endl;
}
return 0;
}
4. Algoritmi chirurgicali (Mutating algorithms)
Spre deosebire de prima categorie de algoritmi acetia pot modifica structura intern a datelor pe care
le manipuleaz.
n continuare este prezentat o list de astfel de algoritmi, i cteva studii de caz.
copy()
- Copiaza un rang incepand cu primul element
copy_n() - Copiaza elemente de la un rang la altul
copy _backward() -Copiaza un rang incepand de la ultimul element
transform()
- Modifica(si copiaza) elemente
merge() - Uneste 2 ranguri
swap_ranges()- Schimba elementele a 2 ranguri
fill()
- Schimba valuarea fiecarui element cu o valuare data
fill_n()
- Schimba n elemente cu o valuare data
remove()
- sterge dintr-un rang toate elementele care au valoarea egala cu o valuare data
rotate()
- Intershimba elementele intr-un rang
reverse()
- Inverseaza un rang
replace()
- Schimba valuarea fiecarui element dintr-un rang cu o valuare data
4.1 Rotate( )
Rotate roteste elementele ntr-un rang. Adica elementul din mijloc, este mutat pe prima pozitie,
elementul indicat de mijloc + 1 este mutat n poziia primul + 1, i aa mai departe. Un mod de a gndi
la aceast operaie este c schimba cele 2 ranguri: [prima,mijloc) i [mijloc, ultima). Formal, pentru
fiecare n a.i 0 <= n <ultima - prima, elementul * (prima + n) este alocat * (prima + (n + (ultima
-mijloc))% (ultima - prima)).
Rotate returneaz primul + (ultima - mijloc).
Exemplu
char alpha[] = "abcdefghijklmnopqrstuvwxyz";
rotate(alpha, alpha + 13, alpha + 26);
printf("%s\n", alpha);
// The output is nopqrstuvwxyzabcdefghijklm
4.2 Copy
[LABORATOR DE PROGRAMARE C++]
Aritoni Ovidiu
Exemplu
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main () {
int myints[]={140,20,76,40,50,60,70};
vector<int> myvector;
vector<int>::iterator it;
[Link](7);
copy ( myints, myints+7, [Link]() );
cout << "myvector contains:";
for (it=[Link](); it!=[Link](); ++it)
cout << " " << *it;
cout << endl;
}
return 0;
4.3 Swap
Exemplu
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main () {
int x=10, y=20;
swap(x,y);
// x:10 y:20
// x:20 y:10
vector<int> first (4,x), second (6,y);
swap(first,second);
// first:4x20 second:6x10
// first:6x10 second:4x20
cout << "first contains:";
for (vector<int>::iterator it=[Link](); it!=[Link](); ++it)
cout << " " << *it;
cout << endl;
}
return 0;
5. Algoritmi de sortare
sort()
- Sorteaza toate elementele
[LABORATOR DE PROGRAMARE C++]
Aritoni Ovidiu
stable_sort() - Sorteaza in timp ce mentine ordinea elementelor egale
partial_sort()- Sorteaza pana cand primele n elemente sunt correct sortate
partial_sort_copy() Copiaza elementele sortate
nth_element()-Sorteaza conform pozitie n
partition() - Schimba pozitia elementelor astfel incat elementele care se potrivesc cu un
criteriu sunt puse la inceput
make_heap() - Converts a range into a heap
push_heap() - Adds an element to a heap
pop_heap() - Removes an element from a heap
sort_heap() - Sorts the heap (it is no longer a heap after the call)
5.1 Merge( )
Merge combin dou ranguri sortate [first1, last1) i [first2, last2) ntr-un singur rang sortat. Adica,
merge copiaza elementele de la [first1, last1) i [first2, last2) n [rezultat, rezultat + (last1 - first1) +
(last2 - first2)), astfel nct rangul rezultat este n ordine strict crescatoare.
Exemplu:
int main()
{
int A1[] = {
int A2[] = {
const int N1
const int N2
1, 3, 5, 7 };
2, 4, 6, 8 };
= sizeof(A1) / sizeof(int);
= sizeof(A2) / sizeof(int);
merge(A1, A1 + N1, A2, A2 + N2,
ostream_iterator<int>(cout, " "));
// The output is "1 2 3 4 5 6 7 8"
}
5.2 Sort ( )
Exemplu
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool myfunction (int i,int j) { return (i<j); }
struct myclass {
bool operator() (int i,int j) { return (i<j);}
} myobject;
int main () {
int myints[] = {32,71,12,45,26,80,53,33};
vector<int> myvector (myints, myints+8);
[LABORATOR DE PROGRAMARE C++]
Aritoni Ovidiu
vector<int>::iterator it;
// using default comparison (operator <):
sort ([Link](), [Link]()+4);
// using function as comp
sort ([Link]()+4, [Link](), myfunction);
// using object as comp
sort ([Link](), [Link](), myobject);
// print out content:
cout << "myvector contains:";
for (it=[Link](); it!=[Link](); ++it)
cout << " " << *it;
cout << endl;
return 0;
}
6. Algoritmi Generali
accumulate()
- Calculeaza suma, produsul
inner_product()
- Combina toate elementele a 2 ranguri
adjacent_difference()- Combina fiecare element cu predecesorul sau
partial_sum() C
- Combina fiecare elemente cu toti predecesorii sai
6.1 Accumulate()
Acumulate este o generalizare a sumei: calculeaza-o suma (sau alte cteva operatii binare) elementelor
n intervalul [prima, ultima).
Exemplu
int main()
{
int A[] = {1, 2, 3, 4, 5};
const int N = sizeof(A) / sizeof(int);
cout <<
<<
<<
cout <<
<<
<<
"The sum of all
accumulate(A, A
endl;
"The product of
accumulate(A, A
endl;
elements in A is "
+ N, 0)
all elements in A is "
+ N, 1, multiplies<int>())
6.2 Power
Exemplu
[LABORATOR DE PROGRAMARE C++]
Aritoni Ovidiu
int main() {
cout << "2 ** 30 = " << power(2, 30) << endl;
}
6.3 Adjacent Difference
Exemplu
#include
#include
#include
#include
#include
<iostream>
<numeric>
<functional>
<vector>
<iterator>
#if _MSC_VER > 1020
// if VC++ version is > 4.2
using namespace std; // std c++ libs implemented in std
#endif
typedef vector < int, allocator < int > > IntegerArray;
typedef ostream_iterator < int, char, char_traits<char> > IntOstreamIt;
void main ()
{
IntegerArray rgIA;
rgIA.push_back(5661); // San Francisco to Berlin
rgIA.push_back(7456); // to Cairo
rgIA.push_back(10995); // to Calcutta
rgIA.push_back(17019); // to Cape Town
rgIA.push_back(24394); // to Hong Kong
rgIA.push_back(30376); // to London
rgIA.push_back(35758); // to Los Angeles
copy([Link](),[Link](),itOstream);
cout << endl;
IntegerArray rgDifferences(7);
IntegerArray::iterator itDifferences = [Link]();
adjacent_difference([Link](),[Link](),itDifferences);
cout << "The adjacent differences are: ";
copy([Link]()+1,[Link](),itOstream);
cout << endl;
IntegerArray rgGT(6);
IntegerArray::iterator itGT = [Link]();
adjacent_difference([Link]()+1,
[LABORATOR DE PROGRAMARE C++]
Aritoni Ovidiu
[Link](),
itGT,
less<int>());
cout << "Which adjacent distances are greater:" << endl
<< "(If you have [a,b,c], then you have [1,0] if a>b and b<=c)"
<< endl;
copy([Link]()+1,[Link](),itOstream);
cout << endl;