Menu

Algorytmy w STL

algorithms stl

Wypróbuj Nasz Instrument Do Eliminowania Problemów

Jawne badanie algorytmów i ich typów w STL.

testy jednostkowe testowanie integracyjne testowanie systemu

STL obsługuje różne algorytmy działające na kontenerach za pośrednictwem iteratorów. Ponieważ te algorytmy działają na iteratorach, a nie bezpośrednio na kontenerach, mogą być używane na iteratorach dowolnego typu.

Algorytmy STL są wbudowane, dzięki czemu oszczędzają dużo czasu i są również bardziej niezawodne. Zwiększają również możliwość ponownego wykorzystania kodu. Te algorytmy to zwykle tylko jedno wywołanie funkcji i nie musimy pisać wyczerpującego kodu, aby je zaimplementować.

=> Poszukaj całej serii szkoleń C ++ tutaj.

ALGORYTMY W STL

Czego się nauczysz:

Rodzaje algorytmów STL

STL obsługuje następujące typy algorytmów

  • Algorytmy wyszukiwania
  • Algorytmy sortowania
  • Algorytmy numeryczne
  • Algorytmy nietransformujące / modyfikujące
  • Algorytmy transformacji / modyfikacji
  • Operacje minimalne i maksymalne

Omówimy szczegółowo każdy z tych typów w kolejnych akapitach.

Algorytmy wyszukiwania i sortowania

Najważniejszym algorytmem wyszukiwania w STL jest wyszukiwanie binarne. Algorytm wyszukiwania binarnego działa na posortowanej tablicy i wyszukuje element, dzieląc tablicę na pół.

Odbywa się to poprzez porównanie szukanego elementu ze środkowym elementem tablicy, a następnie ograniczenie wyszukiwania do 1śwpół lub 2ndpołowa tablicy w zależności od tego, czy przeszukiwany element jest mniejszy, czy większy od elementu środkowego.

Wyszukiwanie binarne to najczęściej używane algorytmy wyszukiwania.

Jego ogólna składnia to:

binary_search(startaddr, endaddr, key)

Gdzie,

startaddr: adres pierwszego elementu tablicy.
endaddr: adres ostatniego elementu tablicy.
klucz: element do przeszukania.

STL dostarcza nam algorytm „sortowania”, który służy do porządkowania elementów w kontenerze w określonej kolejności.

Ogólna składnia algorytmu sortowania to:

sort(startAddr, endAddr);

Gdzie,

startAddr: adres początkowy tablicy do sortowania.
endAddr: adres końcowy tablicy do sortowania.

Wewnętrznie STL używa algorytmu Quicksort do sortowania tablicy.

Weźmy przykład, aby zademonstrować algorytm wyszukiwania i sortowania binarnego:

#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

Wynik:

Sorted Array to
0 1 2 3 4 5 6 7 8 9
W tablicy znaleziono klucz = 2
Nie znaleziono klucza = 10 w tablicy

W podanym kodzie udostępniliśmy tablicę, w której musimy przeszukać kluczowy element za pomocą wyszukiwania binarnego. Ponieważ wyszukiwanie binarne wymaga posortowanej tablicy, najpierw sortujemy tablicę za pomocą algorytmu „sort”, a następnie wywołujemy funkcję „binary_search”, podając wymagane parametry.

Najpierw wywołujemy algorytm binary_search dla klucza = 2, a następnie dla klucza = 10. W ten sposób za pomocą tylko jednego wywołania funkcji możemy wygodnie wykonać wyszukiwanie binarne w tablicy lub ją posortować.

Algorytmy numeryczne

nagłówek w STL zawiera różne funkcje, które działają na wartościach liczbowych. Funkcje te obejmują od znajdowania lcd, gcds, a nawet obliczania sumy elementów w kontenerze, takich jak tablice, wektory w danym zakresie itp.

Omówimy tutaj kilka ważnych funkcji wraz z przykładami.

(i) akumulować

Ogólna składnia funkcji sumuj jest następująca:

accumulate (first, last, sum);

Ta funkcja zwraca sumę wszystkich elementów w zakresie (pierwszy, ostatni) w zmiennej sumie. W powyższym zapisie składni, pierwszy i ostatni to adresy pierwszego i ostatniego elementu w kontenerze, a suma to wartość początkowa zmiennej sum.

(ii) suma_częściowa

Ogólna składnia funkcji suma częściowa jest następująca:

partial_sum(first, last, b)

Tutaj

pierwszy: adres początkowego elementu kontenera.
Last: adres ostatniego elementu kontenera.
B: tablica, w której będzie przechowywana częściowa suma odpowiednich elementów tablicy.

W ten sposób funkcja Parts_sum oblicza częściową sumę odpowiedniej tablicy lub elementów wektora i przechowuje je w innej tablicy.

Jeśli a reprezentuje element w zakresie (pierwszy, ostatni), a b reprezentuje element w wynikowej tablicy, to suma_częściowa będzie wynosić:

b0 = a0
b1 = a0 + a1
b2 = a0 + a1 + a2… i tak dalej.

Zobaczmy przykład demonstrujący zarówno th Funkcje te w programie:

#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: '<

Wynik:

Wynik funkcji sumowania to: 142

suma_częściowa tablicy A: 21 46 110 142

Jak pokazano w powyższym programie, najpierw obliczamy sumę elementów za pomocą funkcji akumuluj, a następnie wywołujemy funkcję suma_częściowa, aby obliczyć częściową sumę odpowiednich elementów tablicy.

Inne algorytmy obsługiwane przez STL i nagłówek:

  • odrobina: Wypełnia zakres kolejnymi przyrostami wartości początkowej.
  • zmniejszyć: Podobnie jak akumulować, z wyjątkiem awarii.
  • produkt_wewnętrzny: Oblicza iloczyn skalarny dwóch zakresów elementów.
  • adjacent_difference: Oblicza różnice między sąsiednimi elementami w zakresie.
  • inclusive_scan: Podobnie jak suma_częściowa, zawiera i-ty element wejściowy w i-tej sumie.
  • exclusive_scan: Podobnie jak suma_częściowa, wyklucza i-ty element wejściowy z i-tej sumy.

Algorytmy niemodyfikujące

Algorytmy niemodyfikujące lub nietransformujące to takie, które nie zmieniają zawartości kontenera, w którym działają. STL obsługuje wiele algorytmów niemodyfikujących.

Poniżej wymieniliśmy niektóre z nich:

  • liczyć: Zwraca liczbę wartości w podanym zakresie.
  • równy: Porównuje elementy w dwóch zakresach i zwraca wartość logiczną.
  • niezgodność: Zwraca parę iteratorów, gdy porównywane są dwa iteratory i występuje niezgodność.
  • Szukaj: Wyszukuje podaną sekwencję w podanym zakresie.
  • search_n: Wyszukuje w podanym zakresie sekwencję wartości licznika.

Opiszmy więcej na temat funkcji „liczenia” i „równości” !!

count (first, last, value) zwraca, ile razy „wartość” pojawia się w zakresie (pierwszy, ostatni).

#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= '<

Wynik:

Ile razy „5” pojawia się w tablicy = 4

Jak widać w tym kodzie, definiujemy wartość tablicy, a następnie wywołujemy funkcję count, podając zakres wartości i wartości 5. Funkcja zwraca, ile razy (liczba) wartość 5 pojawiła się w zakresie.

Weźmy przykład, aby zademonstrować funkcję „równości”.

equal (first1, last1, first2) porównuje elementy z zakresu (first1, last1) z pierwszym elementem wskazywanym przez first2 i zwraca wartość true, jeśli wszystkie elementy są równe, w przeciwnym razie false.

najlepsze miejsca do oglądania anime online za darmo
#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'; }

Wynik:

Elementy w dwóch zakresach nie są równe.

W powyższym kodzie definiujemy dwie tablice liczb całkowitych i porównujemy odpowiadające im elementy za pomocą funkcji „equal”. Ponieważ elementy tablicy nie są takie same, equal zwraca false.

Modyfikowanie algorytmów

Algorytmy modyfikujące modyfikują lub przekształcają zawartość kontenerów podczas ich wykonywania.

Najpopularniejsze i szeroko stosowane algorytmy modyfikujące to „swap” i „reverse”, które odpowiednio zamieniają dwie wartości i odwracają elementy w kontenerze.

Zobaczmy przykłady tych funkcji:

#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<

Wynik:

Wektor 1: 2 4 6 8 10

Wektor 2: 1 1 2 3 5

Odwrócony wektor 1:10 8 6 4 2

Odwrócony wektor 2: 5 3 2 1 1

Jak widać, w programie zdefiniowano dwa wektory. Najpierw używając funkcji swap zamieniamy zawartość vector1 i vector2. Następnie odwracamy zawartość każdego wektora za pomocą funkcji odwrotnej.

Program wyprowadza Vector 1 i Vector 2 po zamianie ich zawartości, a także po odwróceniu zawartości.

Operacje minimalne i maksymalne

Ta kategoria składa się z funkcji min i max, które wyszukują odpowiednio minimalne i maksymalne wartości z podanych dwóch wartości.

Ogólna składnia tych funkcji jest następująca:

max(objecta, objectb); min(objecta, objectb);

Możemy również podać trzeci parametr, aby podać „funkcję porównania” lub kryteria, które zostaną użyte do znalezienia wartości min./maks. Jeśli tego nie podano, funkcja max używa operatora „>” do porównania, podczas gdy funkcja min używa operatora „<’ operator for comparison.

Pokażmy te funkcje za pomocą programu.

#include #include using namespace std; int main() { int x=4, y=5; cout<<'Max of 4 and 5 : '; cout << max(x,y); cout<

Wynik:

Maksymalnie 4 i 5: 5

Min z 4 i 5: 4

Max String: mniejszy ciąg

Min String: dłuższy ciąg

Powyższy program jest oczywisty, ponieważ używamy funkcji min i max najpierw na liczbach, a następnie na łańcuchach. Ponieważ nie udostępniliśmy opcjonalnej funkcji „porównaj_funkcja”, funkcje min / maks działały odpowiednio na operatorach „”.

Wniosek

W ten sposób doszliśmy do końca tego samouczka dotyczącego głównych algorytmów używanych w STL.

W naszych kolejnych samouczkach szczegółowo omówimy iteratory wraz z typowymi funkcjami używanymi w STL niezależnie od kontenerów.

=> Przeczytaj serię szkoleń Easy C ++.

rekomendowane lektury

^