algorithms stl
Un estudi explícit dels algorismes i els seus tipus a STL.
com obrir el fitxer swf a Chrome
STL admet diversos algoritmes que actuen sobre els contenidors mitjançant iteradors. Com que aquests algorismes actuen sobre els iteradors i no directament sobre els contenidors, es poden utilitzar en qualsevol tipus d'iteradors.
Els algoritmes STL estan incorporats i, per tant, estalvien molt de temps i també són més fiables. També milloren la reutilització del codi. Aquests algoritmes solen ser només una trucada de funció i no cal escriure un codi exhaustiu per implementar-los.
=> Cerqueu aquí tota la sèrie de formació C ++.
Què aprendreu:
Tipus d’algorismes STL
STL admet els següents tipus d’algoritmes
- Algorismes de cerca
- Algorismes d'ordenació
- Algorismes numèrics
- Algoritmes no transformadors / modificadors
- Transformar / modificar algoritmes
- Operacions mínima i màxima
Analitzarem detalladament cadascun d’aquests tipus als paràgrafs següents.
Algorismes de cerca i ordenació
L’algorisme de cerca destacat a STL és una cerca binària. L’algorisme de cerca binària funciona en una matriu ordenada i busca l’element dividint la matriu en meitats.
Això es fa primer comparant l’element que es vol cercar amb l’element central de la matriu i, tot seguit, limitant la cerca a 1cla meitat o 2ndla meitat de la matriu en funció de si l'element a cercar és inferior o superior a l'element mitjà.
La cerca binària és l’algorisme de cerca més utilitzat.
La seva sintaxi general és:
binary_search(startaddr, endaddr, key)
On,
startaddr: adreça del primer element de la matriu.
endaddr: adreça de l'últim element de la matriu.
clau: l'element a cercar.
STL ens proporciona un algorisme de 'Classificació' que s'utilitza per disposar els elements d'un contenidor en un ordre concret.
La sintaxi general de l'algorisme d'ordenació és:
sort(startAddr, endAddr);
On,
startAddr: adreça inicial de la matriu a ordenar.
endAddr: adreça final de la matriu a ordenar.
Internament STL utilitza l'algorisme Quicksort per ordenar la matriu.
Prenguem un exemple per demostrar l'algorisme de cerca i classificació binària:
#include #include using namespace std; int main() { int testAry[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 }; int arysize = sizeof(testAry) / sizeof(testAry[0]); sort(testAry, testAry + arysize); cout<<'
Sorted Array is
'; for(int i=0;i Sortida:
Matriu ordenada és
0 1 2 3 4 5 6 7 8 9
Clau = 2 trobada a la matriu
Clau = 10 no trobada a la matriu
Al codi donat, hem proporcionat una matriu en què hem de cercar un element clau mitjançant la cerca binària. Com que la cerca binària requereix una matriu ordenada, primer ordenem la matriu mitjançant l'algorisme 'ordenar' i després fem una trucada de funció a 'recerca_binar' proporcionant els paràmetres necessaris.
En primer lloc, anomenem l'algorisme binary_search per key = 2 i després per key = 10. D'aquesta manera, amb una sola trucada de funció, podem fer una cerca binària en una matriu o ordenar-la convenientment.
Algoritmes numèrics
La capçalera a STL conté diverses funcions que operen en valors numèrics. Aquestes funcions van des de trobar lcds, gcds fins i tot calcular la suma dels elements d'un contenidor com ara matrius, vectors en un interval determinat, etc.
Aquí discutirem algunes funcions importants amb exemples.
(i) acumular
La sintaxi general de la funció acumula és:
accumulate (first, last, sum);
Aquesta funció retorna la suma de tots els elements dins d’un interval [primer, darrer] d’una suma variable. A la notació de sintaxi anterior, primer i darrer són les adreces del primer i últim element d’un contenidor i suma és el valor inicial de la variable suma.
(ii) suma_partial
La sintaxi general de la funció partial_sum és:
partial_sum(first, last, b)
Aquí
primer: adreça de l’element inicial del contenidor.
Darrer: adreça de l’últim element del contenidor.
B: matriu en què s’emmagatzemarà la suma parcial dels elements de matriu corresponents.
Així, la funció partial_sum calcula la suma parcial de la matriu corresponent o dels elements vectorials i els emmagatzema en una matriu diferent.
Si a representa l'element de l'interval [primer, darrer] ib representa l'element de la matriu resultant, la suma_partial serà:
b0 = a0
b1 = a0 + a1
b2 = a0 + a1 + a2 ... i així successivament.
Vegem un exemple per demostrar-ho Aquestes funcions en un programa:
#include #include using namespace std; int main() { int A[] = {21,25,64,32}; int sum = 0; int b[4]; cout<<'
Result of accumulate function is: '< Sortida:
El resultat de la funció acumula és: 142
partial_sum de la matriu A: 21 46 110 142
Com es mostra al programa anterior, primer calculem la suma dels elements mitjançant la funció acumula i després anomenem la funció suma_partal per calcular la suma parcial dels elements de matriu corresponents.
Altres algorismes suportats per STL i capçalera:
- iota: Emplena un interval amb increments successius del valor inicial.
- reduir: Semblant a acumular, excepte fora de funcionament.
- producte_interior: Calcula el producte interior de dues gammes d'elements.
- diferència_adjacent: Calcula les diferències entre elements adjacents en un interval.
- exploració_inclusiva: Semblant a partial_sum, inclou l'element d'entrada i en la suma i.
- scan_exclusive: De manera similar a partial_sum, s’exclou l’ítem element d’entrada de la suma ith.
Algorismes no modificadors
Els algoritmes que no modifiquen o no transformen són els que no canvien el contingut del contenidor on operen. STL admet molts algorismes que no modifiquen.
A continuació, en detallem alguns:
- comptar: Retorna el nombre de valors de l'interval donat.
- igual: Compara els elements en dos intervals i retorna un valor booleà.
- desajust: Retorna un parell d'iteradors quan es comparen dos iteradors i es produeix un desajustament.
- cerca: Cerca una seqüència determinada en un interval determinat.
- cerca_n: Cerca en un interval determinat una seqüència del valor de recompte.
Expliquem més sobre funcions de 'comptar' i 'iguals' !!
count (first, last, value) retorna el nombre de vegades que apareix el 'valor' a l'interval [first, last].
#include #include using namespace std; int main () { int values[] = {5,1,6,9,10,1,12,5,5,5,1,8,9,7,46}; int count_5 = count(values, values+15, 5); cout<<'The number of times '5' appears in array= '< Sortida:
El nombre de vegades que apareix '5' en una matriu = 4
Com veieu en aquest codi, definim un valor de matriu i, a continuació, cridem a la funció de recompte proporcionant l'interval de valor i el valor de 5. La funció retorna el nombre de vegades (recompte) que apareix el valor 5 a l'interval.
Prenem un exemple per demostrar la funció 'igual'.
igual (primer1, darrer1, primer2) compara els elements del rang [primer1, darrer1] amb el primer element assenyalat per primer2 i retorna cert si tots els elements són iguals en cas contrari fals.
#include #include using namespace std; int main() { int inputs1[] = { 1,2,3,4,5,6,7,8}; int inputs2[] = { -1,2,1,2,3,4,6,7,8,9}; if (equal( inputs1 , inputs1+8 , inputs2 )==1) cout<<'Elements in Two ranges are equal'; else cout<<'Elements in two ranges are not equal'; }
Sortida:
Els elements de dos intervals no són iguals.
Al codi anterior, definim dues matrius senceres i comparem els seus elements corresponents mitjançant la funció 'igual'. Com que els elements de la matriu no són els mateixos, l'igual retorna fals.
Algorismes de modificació
Els algorismes de modificació modifiquen o transformen el contingut dels contenidors quan s’executen.
Els algoritmes de modificació més populars i àmpliament utilitzats inclouen 'swap' i 'reverse' que intercanvien dos valors i inverteixen els elements del contenidor respectivament.
Vegem els exemples d’aquestes funcions:
#include #include #include #include using namespace std; int main () { vector vec1 = {1,1,2,3,5}; vector vec2 = {2,4,6,8,10}; swap(vec1,vec2); cout<<'Vector 1 : '; for (auto it = vec1.begin(); it < vec1.end(); ++it) cout << *it << ' '; cout< Sortida:
Vector 1: 2 4 6 8 10
Vector 2: 1 1 2 3 5
Vector invertit 1: 10 8 6 4 2
Vector invertit 2: 5 3 2 1 1
Com es veu, tenim dos vectors definits al programa. Primer utilitzant la funció d’intercanvi, intercanviem el contingut de vector1 i vector2. A continuació, invertim el contingut de cada vector mitjançant la funció inversa.
El programa emet els vectors 1 i 2 després d’intercanviar-ne el contingut i també després d’invertir-los.
Operacions mínimes i màximes
Aquesta categoria consta de funcions mínimes i màximes que descobreixen els valors mínim i màxim respectivament dels dos valors donats.
La sintaxi general d’aquestes funcions és:
max(objecta, objectb); min(objecta, objectb);
També podem proporcionar un tercer paràmetre per proporcionar 'compare_function' o els criteris que s'utilitzarien per trobar el valor mínim / màxim. Si no s'ofereix, la funció max utilitza l'operador '>' per a la comparació, mentre que la funció min utilitza '<’ operator for comparison.
Demostrem aquestes funcions mitjançant un programa.
#include #include using namespace std; int main() { int x=4, y=5; cout<<'Max of 4 and 5 : '; cout << max(x,y); cout< Sortida:
Màxim de 4 i 5: 5
Mínim de 4 i 5: 4
Cadena màxima: cadena més petita
Cadena mínima: cadena més llarga
El programa anterior s’explica per si mateix ja que primer fem servir funcions mínimes i màximes als números i després a les cadenes. Com que no vam proporcionar 'compare_function' opcional, les funcions mínima / màxima van actuar sobre els operadors '' respectivament.
Conclusió
Amb això, hem arribat al final d’aquest tutorial sobre els principals algorismes utilitzats a STL.
com és una clau de seguretat de xarxa
En els nostres tutorials posteriors, parlarem detalladament dels iteradors juntament amb les funcions habituals utilitzades en STL, independentment dels contenidors.
=> Llegiu la sèrie de formació Easy C ++.
Lectura recomanada