Dzisiejsze zajęcia dotyczyły będą algorytmów biblioteki STL. Zanim przejdziemy do ich opisu, podsumujmy pokrótce poznane dotychczas zagadnienia, które pozwolą nam na zrozumienie zasady ich działania:
( ).Biblioteka standardowa oferuje w nagłówkach algorithm i
numeric szeroki wachlarz różnych algorytmów. Zwięzły
przegląd algorytmów dostępnych w STL można zobaczyć np. tutaj. Celem zajęć nie jest
jednak omówienie ich wszystkich, lecz zaprezentowanie ogólnej idei ich
wykorzystania. Nadzieją autora jest, aby po wykonaniu instrukcji do
poznania działania nowego algorytmu wystarczyło czytelnikowi jedynie
szybkie zerknięcie do odpowiedniej referencji. Z tego powodu nie
będziemy też tłumaczyć szczegółów dzałania poszczególnych algorytmów,
lecz odsyłamy czytelnika do dokumentacji.
Z algorytmów STL warto korzystać z następujących 3 powodów:
Każdy algorytm STL operuje na zakresie elementów, definiowanych przez
iteratory. Zdecydowana większość przyjmuje parę iteratorów, która
definiuje zakres zgodnie z konwencją [first, last), tzn.
przedział na który wskazują jest domknięty z lewej strony i otwarty z
prawej (podobnie jak iteratory zwracane przez metody begin
i end kontenerów). Dzięki temu algorytm jest niezależny od
kontenera, na którego elementach ma operować. Zobaczmy teraz, że już
para iteratorów wystarczy, aby zrobić coś ciekawego.
Do generacji losowych wektorów w zadaniach poniżej możesz wykorzystać np. szablon funkcji makeRandomVector.
Wygeneruj wektor losowych liczb całkowitych z przedziału [0, 10] i
wyświetl go. Następnie posortuj go rosnąco używając algorytmu
std::sort. Zweryfikuj poprawność działania algorytmu
wyświetlając ponownie wektor.
Wiele algorytmów przyjmuje także dodatkowe parametry. Zobaczmy to na przykładzie.
Wygeneruj wektor losowych liczb całkowitych z przedziału [0, 10].
Policz wystąpienia liczby 7 używając algorytmu
std::count.
Czasem możemy chcieć dostroić nie tylko parametry, ale także elementy
zachowania algorytmu. Na przykład, możemy chcieć posortować zakres nie
rosnąco, lecz malejąco. Domyślnie, algorytm std::sort
porównuje elementy operatorem <. Aby sortować malejąco,
wystarczy zamienić operator < na operator
>. std::sort daje nam możliwie ogólny
interfejs: możemy podać dodatkowy argument, który definiuje dla
algorytmu operację porównania. Argument ten musi być funktorem
przyjmującym 2 argumenty sortowanego typu. Funktor to po prostu obiekt,
dla którego możemy zawołać metodę operator(). Może to być
zatem np. obiekt klasy, dla której odpowiednio przeciążony jest ten
operator, albo wskaźnik do odpowiedniej funkcji. Po szczegółową dyskusję
dotyczącą funktorów odsyłamy czytelnika do drugiego akapitu podrozdziału
pt. std::visit instrukcji nr 4.
Wygeneruj wektor losowych liczb całkowitych. Wyświetl go. Posortuj go
malejąco używając algorytmu std::sort i odpowiedniego
funktora. Zweryfikuj poprawność działania algorytmu wyświetlając
ponownie wektor.
Zobaczmy inny przykład, gdzie przydatne mogą być funktory.
Wygeneruj wektor losowych liczb całkowitych z przedziału [0, 10].
Policz wystąpienia liczb większych od 7 używając algorytmu
std::count_if.
W zadaniu 4 wykorzystaliśmy fakt, że liczba, do której porównywaliśmy
elementy wektora, była znana w czasie kompilacji (ponieważ 7 występuje
jawnie w treści zadania). W kodzie wystąpiła zatem w pewnym miejscu
linijka typu return x > 7. Co jednak, jeżeli
potrzebujemy przekazać do funktora parametry, które poznamy dopiero w
czasie wykonania programu? Przykładem takiego problemu jest zadanie 5.
Przeczytajmy teraz jego treść (ale jeszcze go nie wykonujmy). Zazwyczaj,
gdy chcemy przekazać do funkcji (lub funktora) jakieś parametry,
dołączamy je do listy argumentów. Tutaj nie mamy jednak tej opcji, gdyż
std::count_if wymaga konkrentej sygnatury funkcji
(funktora). Najprostszym (i najgorszym) sposobem rozwiązania tego
problemu jest zdefiniowanie globalnych zmiennej, której wartość
wczytujemy z konsoli, a następnie odczytujemy w ciele funkcji
(funktora). Spróbujmy teraz wykonać w ten sposób poniższe polecenie.
Napisz program, który generuje wektor losowych liczb z przedziału [0,
10], wczytuje z konsoli liczbę całkowitą a, a następnie
drukuje liczbę elementów wektora większych od a.
W języku C++ unikamy za wszelką cenę obiektów globalnych, gdyż ich
czas życia nie jest w żaden sposób ograniczony (jest równy czasowi
wykonania progrmu). Ich destruktor wołany jest więc dopiero po wyjściu z
funkcji main. Jest to mało optymalne oraz bardzo pogarsza
przejrzystość kodu (czytając kod i natrafiając nagle na jakieś dziwne
parametry globalne możemy nie rozumieć, skąd one się w ogóle biorą).
Szczęśliwie, w odróżnieniu od C, w C++ możemy korzystać z funktorów
posiadających stan (ang. stateful). Oznacza to, że możemy
zdefiniować klasę, przeciążającą operator ( ) oraz
posiadającą jakieś pola. Możemy następnie podać do algorytmu obiekt
takiej klasy, którego polom wcześniej przypisaliśmy odpowiednie
parametry. Czas jego życia jest ograniczony, a jego sens istnienia
widoczny jest na pierwszy rzut oka (nie ma więc problemu z
czytelnością).
Wykonaj zadanie 5, tym razem posługując się funktorem posiadającym
stan. Zdefiniuj klasę posiadającą pole typu całkowitego oraz
przeciążającą odpowiednio operator ( ). Stwórz obiekt tej
klasy, przypisz do jego pola wartość wczytaną z klawiatury, a następnie
podaj go do std::count_if.
Aby uniknąć konieczności definiowania nowych klas za każdym razem, gdy chcemy stworzyć relatywnie prosty funktor, od C++11 możemy używać wyrażeń lambda (zwanych także funkcjami anonimowymi, a potocznie po prostu lambdami). Wyrażenie lambda ma następującą składnię (po wszystkie szczegóły odsyłamy jak zawsze do dokumentacji):
Tworzy ono obiekt funkcyjny (funktor), którego operator nawiasów okrągłych przyjmuje argumenty wskazanego typu i wykonuje na nich operacje zdefiniowane w ciele (zupełnia jak tradycyjna funkcja!). Nawiasy kwadratowe i rolę capture omówimy za chwilę. Na razie zobaczmy prosty przykład definicji lambdy, która zwraca sinus argumentu:
auto lambda_sin = [](double x){ return sin(x); }; // lambda_sin jest funktorem
double x = M_PI / 2.;
double sin_x = lambda_sin(x); // sin_x == 1. (+/- błąd zmiennoprzecinkowy)Typ zmiennej lambda_sin jest nadawany przez kompilator,
w związku z czym musimy użyć słowa kluczowego auto. Nie
musimy jednak przypisywać lambdy do zmiennej, możemy użyć jej jako
rvalue:
Tak będziemy też najczęściej postępować w przypadku algorytmów, gdzie zazwyczaj definiujemy wyrażenie lambda bezpośrednio w liście argumentów. Korzystanie z prostych lambd obrazuje także ten kawałek kodu. Zachęcamy czytelnika do podejrzenia, jak tak naprawdę kompilator je rozwija (należy wcisnąć przycisk “Cpp Insights”, a następnie przycisk “Play”). Jak widać nie dzieje się tu nic magicznego, po prostu definiowane są za nas klasy z odpowiednimi polami i operatorami. Użycie funkcji anonimowych pozwala nam jednak oszczędzić sporo wysiłku.
Lambdy przedstawione powyżej można śmiało zastąpić tradycyjnymi
funkcjami, jedyna korzyść z ich użycia to niewielka oszczędność czasu
oraz ograniczenie widoczności nazwy funkcji pomocniczej do bieżącego
scope’u. Zobaczmy teraz, do czego służy capture lambdy (autor
nie zna dokładnego i zwięzłego ekwiwalentu tego określenia w języku
polskim, capture w kontekście regexów nazywa się czasem
kolokwialnie “grupą kapturkową”). W nawiasach kwadratowych możemy
“łapać” zmienne ze scope’u, w którym zdefiniowana została lambda. Możemy
to robić przez kopię lub referencję (a także przeniesienie, jeżeli jest
taka potrzeba). W instrukcji ograniczymy się do łapania przez referencję
całego scope’u. Dodając do definicji lambdy jeden znak -
& - zyskujemy w jej ciele dostęp do wszystkich
zmiennych, które widoczne są dla jej definicji. Na przykład:
double omega = M_PI;
double phi = M_PI / 2.;
// Błąd kompilacji - omega i phi są niewidoczne w środku lambdy
auto bad_harmonic = [](double t){ return sin(omega * t + phi); };
// OK - łapiemy referencje do omega i phi
auto good_harmonic = [&](double t){ return sin(omega * t + phi); };
// Korzystamy tak samo
double t0 = 0;
double y0 = good_harmonic(t0);Nie musimy zatem samodzielnie definiować dodatkowej klasy, tak jak w zadaniu 6!
Wykonaj ponownie zadanie 6, tym razem posługując się lambdą zamiast funktorem jawnie zdefiniowanej klasy.
Poniżej zamieszczono zadania treningowe, rozwiązanie których pomoże
poznać kilka nowych algorytmów oraz przećwiczyć pracę z szablonami
funkcji dostępnymi w nagłówkach algorithm i
numeric. Kolejność zadań dobrana została zgodnie z rosnącym
stopniem trudności (w opinii autora). Zachęcamy czytelnika do wykonania
jak największej ich liczby. Zdecydowanie wskazane jest wykonanie
przynajmniej pierwszego zadania z każdej kategorii poza ostatnią.
Napisz program, który wcztuje z klawiatury ciąg znaków
(std::string) i zwraca 1 jeżeli występują w
nim 2 te same znaki pod rząd i 0 w innym wypadku. użyj
algorytmu std::adjacent_find.
Napisz program, który wczytuje z klawiatury ciąg znaków, a następnie
zwraca 1 jeżeli podany ciąg zawiera w sobie podciąg
“piesek” lub “kotek” i 0 w innym wypadku. Użyj algorytmu
std::search.
Napisz program, który wczytuje z klawiatury ciąg znaków, a następnie
drukuje go do konsoli w odwróconej kolejności. Użyj algorytmu
std::reverse.
Stwórz 2 wektory liczb zmiennoprzecinkowych. Oblicz ich iloczyn
skalarny używając algorytmu std::inner_product.
Stwórz wektor losowych liczb całkowitych z przedziału [0, 10]. Znajdź
w nim pierwsze wystąpienie liczby 7. Posortuj elementy wektora
występujące przed znalezioną liczbą 7 (lub cały wektor, jeżeli 7 nie
występuje). Użyj std::find i std::sort.
Przykład:
Stwórz wektor losowych liczb całkowitych z przedziału [0, 10].
Następnie usuń z niego wszystkie wystąpienia liczby 3. Użyj algorytmu
std::remove oraz metody wektora erase. Spróbuj
wykonać zadanie w 1 linijce (wyjąwszy stworzenie wektora). Rozmiar
(size) wektora powinien być po operacji mniejszy o liczbę
wystąpień liczby 3.
Stwórz wektor losowych liczb całkowitych z przedziału [0, 10]. Znajdź
w nim pierwsze wystąpienie liczby 7. Przesuń elementy wektora
występujące przed znalezioną liczbą 7 na koniec wektora (zachowaj ich
kolejność). Użyj std::find i std::rotate.
Przykład:
Stwórz wektor losowych liczb zmiennoprzecinkowych z przedziału [-1,
1]. Sprawdź, czy co najmniej jedna ze stworzonych liczb jest większa niż
0.9. Użyj algorytmu std::any_of.
Stwórz wektor losowych liczb zmiennoprzecinkowych z przedziału [-1,
1]. Stwórz drugi wektor tego samego rozmiaru i wypełnij go sinusami
wartości z pierwszego wektora. Użyj algorytmu
std::transform.
Stwórz wektor losowych liczb całkowitych z przedziału [0, 10].
Przestaw jego elementy tak, aby najpierw wystąpiły wszystkie liczby
większe od 6 (poza tym wymaganiem mogą być one dowolnie przestawione).
Następnie posortuj część zakresu zawierającą elementy większe od 6. Użyj
std::partition i std::sort.
Przykład:
Napisz algorytm sorted_indices, o sygnaturze:
template < typename ConstIt, typename Comp >
std::vector< size_t > sorted_indices(ConstIt first, ConstIt last, Comp compare);który zwraca indeksy elementów podanego zakresu
[first, last) po jego posortowaniu przy użyciu funktora
porównującego compare. Algorytm nie powinien modyfikować
zakresu. Zachowanie jest analogiczne do napisania w MATLABie
[~, i] = sort(v). Innymi słowy, poniższy kod powinien się
wykonać:
std::vector<unsigned> v = { /* ... */ };
auto r = sorted_indices(v.begin(), v.end(), std::less<unsigned>{});
int a = 0;
for(size_t i = 0; i < v.size(); ++i)
{
assert(a <= v[r[i]]);
a = v[r[i]];
}Przykład:
Podpowiedzi:
[], który pozwala na
indeksowanie elementów następujących po danym iteratorze. Na
przykład:std::distance zwraca odległość między dwoma
iteratorami (np. dla begin i end będzie to
rozmiar kontenera).std::iota (z nagłówka
numeric) do generacji wektora kolejnych rosnących liczb
całkowitych (zwięźlejszy zapis niż pętla for).