Wstecz: 24.1 Kolekcje i iteratory W górę: 24. Biblioteka standardowa Dalej: 24.3 Przykłady
Biblioteka standardowa dostarcza ponad sto algorytmów, czyli szablonów funkcji operujących na kolekcjach. Argumentami tych funkcji nie są kolekcje jako takie, a iteratory.
Jako argumenty wielu algorytmów występują też funkcje albo, jeszcze częściej, obiekty funkcyjne.
Omówimy pokrótce kilka algorytmów dostarczanych przez bibliotekę standardową. Nie będzie to przegląd pełny, ale pozwoli zorientować się Czytelnikowi, w jaki sposób algorytmy stosować. Większość algorytmów udostępniana jest poprzez włączenie pliku nagłówkowego algorithm.
Do bardziej popularnych i użytecznych należą algorytmy sortujące.
Użycie ich jest proste:
1. #include <iostream>
2. #include <vector>
3. #include <list>
4. #include <string>
5. #include <algorithm>
6. #include <iterator>
7. using namespace std;
8.
9. int main() {
10. vector<string> vec{"Paris", "London", "Warsaw",
11. "Berlin", "Lisbon", "Oslo"};
12. auto ini = vec.begin(), fin = vec.end();
13.
14. list<string> lis(vec.size()-2); ➊
15. copy(ini+1, fin-1, lis.begin()); ➋
16.
17. sort(ini,fin); ➌
18. lis.sort(); ➍
19.
20. copy(ini, fin, ➎
21. ostream_iterator<string>(cout, " "));
22. cout << endl;
23.
24. copy(lis.begin(),lis.end(),
25. ostream_iterator<string>(cout, " "));
26. cout << endl;
27. }
W programie tworzymy wektor napisów.
Następnie tworzymy listę (➊) o początkowej wielkości
o dwa mniejszej niż rozmiar wektora. Algorytm
Algorytm
copy
(➋) pobiera zakres (w postaci
pary iteratorów) z kolekcji źródłowej i iterator z kolekcji
docelowej wskazujący, od którego miejsca elementy mają być nadpisywane.
Zauważmy, że algorytm nie tworzy nowych elementów docelowego
kontenera, tylko nadpisuje istniejące. Dlatego właśnie tworząc
listę musieliśmy zadbać o to, by miała ona wystarczający rozmiar.
Następnie sortujemy wektor algorytmem
sort
(➌) —
jak zwykle, zakres elementów do posortowania przekazujemy
jako parę iteratorów. Funkcja
sort
oczekuje
iteratorów dostępu swobodnego. Dlatego nie można jej użyć
do posortowania listy — dla list jednak istnieje metoda
sort
(patrz ➍).
Podobny mechanizm działa również dla innych algorytmów
wymagających iteratorów swobodnego dostępu — kolekcje
dostarczające tylko dwukierunkowych iteratorów mają zamiast nich
odpowiadające im metody
(np.
merge,
remove,
reverse
itd.).
Zwróćmy jeszcze uwagę na linię ➎. Tu również używamy funkcji copy. Kopiujemy elementy z jednej kolekcji, określone za pomocą iteratorów, do drugiej, określonej przez jeden iterator, tak jak poprzednio, przy kopiowaniu wektora do listy. Tym razem iterator będący trzecim argumentem jest nieco dziwny. Jest to iterator utworzony z szablonu ostream_iterator (z nagłówka iterator) przez konkretyzację dla typu string. Argumentami konstruktora tej konkretyzacji jest strumień wyjściowy, w naszym przypadku cout, oraz napis, który będzie pełnił rolę separatora pomiędzy elementami, w naszym przykładzie znak odstępu. W ten sposób strumień wyjściowy jest traktowany jak kolekcja elementów, które mają być wypisane. Iterator związany z tą kolekcją jest typu wyjściowego (output iterator), a więc jest jednokierunkowy, jednoprzebiegowy (one pass) i nie dopuszcza odczytu elementów. Wydruk programu to:
Berlin Lisbon London Oslo Paris Warsaw
Berlin Lisbon London Warsaw
Jak widzieliśmy, funkcja
copy
kopiuje elementy
z jednej kolekcji do drugiej nadpisując już istniejące
elementy. Dlatego w programie powyżej (linia ➊) musieliśmy
utworzyć listę od razu odpowiedniego rozmiaru. To nie zawsze jest
takie proste — często nie wiemy z góry ile elementów trzeba
będzie skopiować. W takich sytuacjach możemy użyć specjalnej
funkcji
back_inserter,
która zwraca obiekt zachowujący się jak iterator wyjściowy, ale
który dodaje nowe elementy do kolekcji (wywołując
push_back). Na przykład w poniższym przykładzie
kopiujemy elementy z jednego wektora do drugiego (początkowo
pustego), ale tylko takie, które spełniają predykat przesłany
jako ostatni argument do funkcji
copy_if:
1. #include <algorithm> // copy
2. #include <iostream>
3. #include <iterator> // inserters
4. #include <vector>
5.
6. int main() {
7. std::vector<int> v{1, 2, 3, 4, 5, 6, 7};
8. std::vector<int> emp;
9. std::copy_if(v.begin(), v.end(),
10. std::back_inserter(emp),
11. [](auto n){ return n%2 != 0; });
12. std::copy(emp.begin(), emp.end(),
13. std::ostream_iterator<int>(std::cout, "\n"));
14. }
(istnieją też funkcje front_inserter i inserter).
Przekazywanie funkcji do algorytmów jest bardzo częste.
Na przykład funkcje sortujące mogą mieć dodatkowy argument określający
jak elementy mają być porównywane (domyślnie są porównywane
za pomocą operatora <). Powinien to być wskaźnik do funkcji,
lambda lub obiekt funkcyjny (cokolwiek, co zachowuje się
jak funkcja) pełniącej rolę komparatora,
czyli funkcji pobierającej dwa argumenty typu takiego, jakiego są
elementy kolekcji i zwracającej wartość logiczną (bool)
odpowiadającą na pytanie czy pierwszy argument jest
ściśle mniejszy od drugiego?
Na przykład w poniższym programie funkcja
compar
(➊) uznaje każdą liczbę nieparzystą za mniejszą od
dowolnej liczby parzystej a liczby o tej samej parzystości
porządkuje w sposób naturalny (rosnąco). Ten komparator użyty jest
w linii ➍ jako wskaźnik funkcyjny.
Definiujemy też prostą strukturę
Evens
(➋)
z przeciążonym operatorem wywołania: obiekty tej klasy mogą
również służyć jako komparatory (➎) — w tym przypadku
liczby parzyste są uważane za mniejsze od nieparzystych,
a dla liczb o tej samej parzystości porządek będzie odwrócony
(malejący).
W końcu w linii ➏ jako komparatora użyliśmy lambdy
(porządkującej liczby malejąco, bez względu na parzystość).
Funkcja (szablon)
printVec
(➌) służy do wypisywania
wektorów.
1. #include <iostream>
2. #include <vector>
3. #include <algorithm>
4. #include <iterator>
5.
6. bool compar(int a, int b) { ➊
7. return (a+b)%2 != 0 ? a%2 != 0 : a < b;
8. }
9.
10. struct Evens { ➋
11. bool operator()(int a, int b) {
12. return (a+b)%2 != 0 ? a%2 == 0 : b < a;
13. }
14. };
15.
16. template <typename T>
17. void printVec(const std::vector<T>& vec) { ➌
18. copy(vec.cbegin(), vec.cend(),
19. std::ostream_iterator<T>(std::cout, " "));
20. std::cout << '\n';
21. }
22.
23. int main() {
24. std::vector<int> vec{2, 5, 2, 9, 1, 5, 7, 4};
25. printVec(vec);
26.
27. sort(vec.begin(), vec.end(), compar); ➍
28. printVec(vec);
29.
30. sort(vec.begin(), vec.end(), Evens{}); ➎
31. printVec(vec);
32.
33. sort(vec.begin(), vec.end(),
34. [](int a, int b) {return b < a;}); ➏
35. printVec(vec);
36.
37. }
Program drukuje
2 5 2 9 1 5 7 4
1 5 5 7 9 2 2 4
4 2 2 9 7 5 5 1
9 7 5 5 4 2 2 1
Ogólnie, funkcje zwracające wartość logiczną nazywamy
predykatami. Są one używane przez bardzo
wiele algorytmów, nie tylko sortujących. Na przykład funkcja
(a właściwie, jak pamiętamy, wzorzec funkcji)
count_if
zlicza liczbę tych elementów kolekcji, określonej za pomocą dwóch
iteratorów, dla których predykat wywołany z elementem kolekcji jako
jedynym argumentem zwraca
true. W poniższym programie predykat
parzysta
został użyty (linia 21) do zliczenia liczby
elementów parzystych wektora:
1. #include <iostream>
2. #include <vector>
3. #include <algorithm>
4. #include <iterator>
5. using namespace std;
6.
7. bool parzysta(int a) {
8. return (a&1) == 0;
9. }
10.
11. int main() {
12. vector<int> vec;
13. int d;
14. while ( cin >> d ) vec.push_back(d);
15. cin.clear();
16.
17. cout << "W ciagu liczb ";
18. copy(vec.begin(),vec.end(),
19. ostream_iterator<int>(cout, " "));
20. cout << "\njest "
21. << count_if(vec.begin(), vec.end(), parzysta)
22. << " liczb parzystych\n";
23. }
Wydruk tego programu:
2 4 -2 7 5 4 31 4 5 -4
^D
W ciagu liczb 2 4 -2 7 5 4 31 4 5 -4
jest 6 liczb parzystych
Bardzo obszerna jest klasa algorytmów wyszukujących. Podstawowe
funkcje (szablony) to
find
i
find_if.
Funkcja
find
poszukuje w kolekcji pierwszego elementu równego
obiektowi przesłanemu jako argument, natomiast
find_if
poszukuje pierwszego elementu, dla którego spełniony jest pewien
predykat, to znaczy pierwszego elementu kolekcji dla którego
funkcja definiująca ten predykat zwróci
true. Kolekcja, jak
zwykle, zadana jest parą iteratorów. W razie sukcesu obie funkcje
zwracają iterator do znalezionego elementu. Jeśli wyszukiwanie
zakończyło się porażką, zwracany jest iterator
end().
Przykład na obie te funkcje znajdziemy w następującym programie:
1. #include <vector>
2. #include <iostream>
3. #include <string>
4. #include <cctype> // tolower
5. #include <algorithm>
6. #include <iterator>
7. using namespace std;
8.
9. bool czy_na_A(string& s) {
10. return s[0] == 'A';
11. }
12.
13. void mala(string& imie) {
14. imie[0] = tolower(imie[0]);
15. }
16.
17. int main() {
18. vector<string> vs;
19.
20. vs.push_back("Magda"); vs.push_back("Anna");
21. vs.push_back("Monika"); vs.push_back("Agata");
22. vs.push_back("Ala"); vs.push_back("Urszula");
23.
24. vector<string>::iterator k;
25.
26. k = find(vs.begin(), vs.end(), "Anna");
27. if ( k != vs.end() )
28. cout << *k << " znaleziona\n";
29. else
30. cout << "Anna nie znaleziona\n";
31.
32. k = find(vs.begin(), vs.end(), "Basia");
33. if ( k != vs.end() )
34. cout << *k << " znaleziona\n";
35. else
36. cout << "Basia nie znaleziona\n";
37.
38.
39. cout << "\nZ imion\n";
40. copy(vs.begin(),vs.end(),
41. ostream_iterator<string>(cout," "));
42. cout << "\nnastepujace zaczynaja sie na \'A\':\n";
43. k = vs.begin();
44. while ( k < vs.end() ) {
45. k = find_if(k, vs.end(), czy_na_A);
46. if ( k != vs.end() ) cout << *k++ << " ";
47. }
48. cout << endl;
49.
50. for_each(vs.begin(),vs.end(),mala);
51. cout << "\nPo zamianie na male:\n";
52. copy(vs.begin(),vs.end(),
53. ostream_iterator<string>(cout," "));
54. cout << endl;
55. }
W liniach 26 i 32 użyta jest funkcja find, po czym sprawdzane jest, czy otrzymany iterator nie jest równy vs.end(), co oznaczałoby porażkę wyszukiwania.
Następnie z wektora imion wyszukiwane są w pętli (linie 44-47) imiona zaczynające się na literę 'A'. W tym celu korzystamy z funkcji find_if i predykatu czy_na_A (zdefiniowanego w liniach 9-11).
W linii 50 korzystamy z funkcji for_each. Jest to przykład algorytmu modyfikującego kolekcję, w odróżnieniu od algorytmów wyszukujących, które są algorytmami niemodyfikującymi. Działanie jego polega na wywołaniu dla każdego elementu kolekcji ze wskazanego przedziału pewnej określonej przez użytkownika funkcji (lub obiektu funkcyjnego). Argument przekazywany jest przez referencję, tak, aby możliwa była modyfikacja jego oryginału. Wartość zwracana funkcji, jeśli istnieje, jest ignorowana. W naszym przypadku funkcją tą jest funkcja mala, która w przekazanym przez referencję napisie zmienia pierwszą literę na małą. Wydruk programu jest następujący:
Anna znaleziona
Basia nie znaleziona
Z imion
Magda Anna Monika Agata Ala Urszula
nastepujace zaczynaja sie na 'A':
Anna Agata Ala
Po zamianie na male:
magda anna monika agata ala urszula
Jak widzieliśmy, ważną rolę odgrywają w algorytmach funkcje. W rzeczywistości nie muszą to być funkcje: wystarczy, że jest to „coś, co da się wywołać”. Jak pamiętamy z rozdziału o przeciążeniu operatora wywołania, jeśli w klasie przeciążony został operator wywołania, to nazwa obiektu tej klasy z podanymi argumentami w nawiasach powoduje wywołanie metody operator(). Obiekt staje się zatem obiektem wywoływalnym (ang. callable object). Takie właśnie obiekty mogą pełnić rolę obiektów funkcyjnych — można je wstawić tam, gdzie może wystąpić funkcja. Obiekty funkcyjne mają z punktu widzenia algorytmów tę przewagę nad funkcjami, że tworząc je można, na przykład poprzez konstruktor, przekazać do nich dodatkową informację prócz samych tylko argumentów wywołania, których liczba i typ są określone przez algorytm. Obiekty funkcyjne zapewniają zatem większą elastyczność algorytmów. Są też często efektywniejsze od zwykłych funkcji, bo metoda operator() może być rozwinięta, podczas gdy przekazywanie zwykłej funkcji przez wskaźnik nie pozwala kompilatorowi na jej rozwinięcie.
Przyjrzyjmy się następującemu programowi:
1. #include <iostream>
2. #include <cmath> // sqrt
3. #include <vector>
4. #include <algorithm> // sort, copy
5. #include <iterator>
6. using namespace std;
7.
8. struct Komp {
9. enum Sposoby {
10. wg_sumy_cyfr,
11. wg_ilosci_dzielnikow,
12. wg_wartosci,
13. wg_wart_odwrotnie
14. };
15.
16. Komp(Sposoby sposob): sposob(sposob) { }
17.
18. int operator()(int n1, int n2);
19.
20. class BrakKomparatora { };
21.
22. private:
23. Sposoby sposob;
24.
25. static int suma_cyfr(int n);
26. static int ilosc_dzi(int n);
27. };
28.
29. int Komp::operator()(int n1, int n2) {
30. switch (sposob) {
31. case wg_sumy_cyfr:
32. return suma_cyfr(n1) < suma_cyfr(n2);
33. case wg_ilosci_dzielnikow:
34. return ilosc_dzi(n1) < ilosc_dzi(n2);
35. case wg_wartosci:
36. return n1 < n2;
37. case wg_wart_odwrotnie:
38. return n2 < n1;
39. default:
40. throw BrakKomparatora();
41. // nigdy się nie zdarzy
42. }
43. }
44.
45. int Komp::suma_cyfr(int n) {
46. // suma cyfr liczby całkowitej n (licząc
47. // wszystkie cyfry ze znakiem dodatnim)
48. n = n >= 0 ? n : -n;
49. int s = 0;
50. while (n) { s += n%10; n /= 10; }
51. return s;
52. }
53.
54. int Komp::ilosc_dzi(int n) {
55. // ilość dodatnich dzielnikow liczby całkowitej
56. // n (wliczając jedynkę i samą liczbę n)
57. n = n > 0 ? n : -n;
58. if ( n < 3 ) return n;
59. int sr = (int) sqrt(n+0.5);
60. int ilosc = (sr*sr == n ? 1 : 2);
61. for (int i = 2; i <= sr; ++i) if (n%i == 0) ilosc += 2;
62. return ilosc;
63. }
64.
65. int main() {
66. int tab[] = {7, 4, 8, 12, 13, 119, 16, 6};
67. vector<int> v(tab,tab+sizeof(tab)/sizeof(int));
68. v.push_back(64);
69.
70. // sortujemy różnymi sposobami i wyświetlamy wyniki
71.
72. cout << "Sortujemy wg. sumy cyfr\n";
73. sort(v.begin(),v.end(),Komp(Komp::wg_sumy_cyfr));
74. copy(v.begin(),v.end(),ostream_iterator<int>(cout," "));
75.
76. cout << "\nSortujemy wg. ilosci dzielnikow\n";
77. sort(v.begin(),v.end(),Komp(Komp::wg_ilosci_dzielnikow));
78. copy(v.begin(),v.end(),ostream_iterator<int>(cout," "));
79.
80.
81. cout << "\nSortujemy wg. wartosci\n";
82. sort(v.begin(),v.end(),Komp(Komp::wg_wartosci));
83. copy(v.begin(),v.end(),ostream_iterator<int>(cout," "));
84.
85. cout << "\nSortujemy wg. wartosci odwrotnie\n";
86. sort(v.begin(),v.end(),Komp(Komp::wg_wart_odwrotnie));
87. copy(v.begin(),v.end(),ostream_iterator<int>(cout," "));
88.
89. cout << endl;
90. }
Program sortuje wektor na wiele różnych sposobów. Komparator jest tym razem nie funkcją, ale obiektem klasy Komp. W klasie tej przeciążony jest operator operator() (linie 18 i 29-43). Jedyny konstruktor klasy wymaga argumentu typu wyliczeniowego, który określa następnie sposób sortowania. Odpowiedni element wyliczenia jest zapamiętywany w składowej sposob obiektu.
W funkcji main wywołujemy sort i jako wartość trzeciego argumentu podajemy utworzony „na miejscu” anonimowy obiekt klasy Komp. W samym obiekcie zapamiętane jest zatem kryterium sortowania, które określiliśmy argumentem przesłanym do konstruktora. W trakcie sortowania obiekt będzie wielokrotnie wywoływany przez algorytm z elementami kolekcji jako argumentami: dzięki temu jednak, że jest to obiekt, może przechowywać dodatkową informację w swoich składowych. W naszym przypadku jest to składowa sposob, dzięki której przy każdym wywołaniu wybrana zostaje odpowiednia gałąź instrukcji switch (linia 30). Wydruk z programu:
Sortujemy wg. sumy cyfr
12 4 13 6 7 16 8 64 119
Sortujemy wg. ilosci dzielnikow
13 7 4 6 8 119 16 12 64
Sortujemy wg. wartosci
4 6 7 8 12 13 16 64 119
Sortujemy wg. wartosci odwrotnie
119 64 16 13 12 8 7 6 4
Obiekty funkcyjne stosuje się również do tworzenia manipulatorów.
W rozdziale o manipulatorach
mówiliśmy o manipulatorach z argumentami: jest szereg takich
manipulatorów zdefiniowanych w bibliotece dołączanej poprzez
nagłówek
iomanip, ale jak tworzyć własne takie manipulatory?
Przyjrzyjmy się przykładowi:
1. #include <iostream>
2. #include <string>
3. using namespace std;
4.
5. struct maniparg {
6. string str;
7. maniparg(int ile, char c) : str(ile,c) { }
8. ostream& operator()(ostream& s) const {
9. return s << str;
10. }
11. };
12.
13. ostream& operator<<(ostream& s, const maniparg& manip) {
14. return manip(s);
15. }
16.
17. int main() {
18. cout << maniparg(7,'*') << "To jest maniparg"
19. << maniparg(3,'!') << maniparg(7,'*') << endl;
20.
21. maniparg trzywykrzykniki(3,'!');
22. maniparg siedemgwiazdek (7,'*');
23.
24. cout << siedemgwiazdek << "To jest maniparg"
25. << trzywykrzykniki << siedemgwiazdek << endl;
26. }
Tworzymy klasę maniparg i dla niej przeciążamy w zwykły sposób operator wstawiania do strumienia '<<' (linie 13-15). Funkcja przeciążająca zadziała, według normalnych zasad, gdy po prawej stronie operatora '<<' pojawi się konkretny obiekt klasy maniparg. Przesłanymi argumentami będą strumień i sam obiekt. Z kolei funkcja przeciążająca operator '<<' wywołuje przesłany obiekt (linia 14), czyli funkcję operator() z klasy maniparg (zdefiniowaną w liniach 8-10). Funkcja ta została skonstruowana w ten sposób, że otrzymuje poprzez argument obiekt strumienia i wypisuje do niego napis skonstruowany z ile znaków c (przesłanych do konstruktora obiektu). Zwraca referencję do tegoż strumienia, tak że i funkcja przeciążająca operator '<<' również zwraca ten strumień, tak jak to jest wymagane. Po co ta konstrukcja?
Otóż tworząc obiekt klasy maniparg możemy przekazać do niego poprzez konstruktor i zapamiętać w jego składowych dowolną ilość informacji. W naszym przypadku przekazujemy tam znak i liczbę całkowitą określającą, ile razy ten znak ma być wstawiony do strumienia. Na podstawie tej informacji tworzona jest składowa str, czyli napis zawierający znak powtórzony odpowiednią liczbę razy. Z tej składowej korzysta metoda operator() wywoływana z funkcji przeciążającej operator '<<'. Widzimy to w linii 18, w której tworzymy obiekt klasy maniparg przekazując poprzez argumenty konstruktora znak gwiazdki i liczbę 7. Ponieważ obiekt klasy maniparg pojawił się po prawej stronie operatora '<<', wywoływana jest funkcja zdefiniowana w liniach 13-15 i przekazywany jest do niej ten obiekt. Jest on wywoływany, przekazując z kolei strumień poprzez argument. Metoda operator() ma zatem komplet informacji: strumień i dane ze składowej obiektu, które do tego strumienia mają być wpisane. Program drukuje
*******To jest maniparg!!!*******
*******To jest maniparg!!!*******
Zauważmy, że równie dobrze możemy utworzyć zawczasu obiekty klasy
maniparg
nadając im nazwy, a potem używać ich wielokrotnie,
jak robimy to z obiektami
trzywykrzykniki
i
siedemgwiazdek
w liniach 24-25.
T.R. Werner, 23 lutego 2022; 19:40