Wstecz: 24.1 Kolekcje i iteratory W górę: 24. Biblioteka standardowa Dalej: 24.3 Przykłady
Biblioteka standardowa dostarcza ok. 80 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;
11. string s;
12. while ( cin >> s ) vec.push_back(s);
13. cin.clear();
14.
15. vector<string>::iterator ini = vec.begin(),
16. fin = vec.end();
17.
18. list<string> lis(vec.size()-2);
19. copy(ini+1,fin-1,lis.begin());
20.
21. sort(ini,fin);
22. lis.sort();
23.
24. copy(ini,fin,ostream_iterator<string>(cout, " "));
25. cout << endl;
26.
27. copy(lis.begin(),lis.end(),
28. ostream_iterator<string>(cout, " "));
29. cout << endl;
30. }
W linii 19 zastosowana została z kolei inna ważna funkcja, funkcja copy. Kopiuje ona elementy z jednej kolekcji do drugiej. Pierwsze dwa argumenty określają przedział z kolekcji źródłowej (jak zwykle łącznie z elementem wskazywanym przez pierwszy iterator, a bez elementu wskazywanego przez drugi). Trzecim argumentem jest iterator w kolekcji docelowej wskazujący, od której pozycji elementy mają być wkopiowywane. Nowe elementy nie są tworzone, dlatego musieliśmy zadbać, aby lista miała odpowiednią liczbę elementów jeszcze przed operacją kopiowania (linia 18). W naszym przykładzie przekopiowaliśmy do listy wszystkie elementy wektora prócz pierwszego i ostatniego.
Zwróćmy jeszcze uwagę na linię 24 (i analogiczną linię 27). 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. Konstrukcja użyta w liniach 24 i 27 jest zwarta i efektywna; można ją oczywiście stosować tylko, jeśli obiekty, które wstawiamy do strumienia wyjściowego, są tego samego typu — w naszym przypadku był to typ string. Przykładowy wydruk programu to:
Ola
Ala
Ula
Ela
Magda
Monika
^D
Ala Ela Magda Monika Ola Ula
Ala Ela Magda Ula
gdzie, jak poprzednio, wczytywanie zostało przerwane po słowie
'Monika' przez naciśnięcie Ctrl-D (w systemie Windows byłoby to
Ctrl-Z).
Funkcje sortujące mogą mieć dodatkowy argument wskazujący funkcję
(lub obiekt funkcyjny, o czym więcej w następnym podrozdziale), jaka
ma być użyta przy porównywaniu elementów. Powinien to być
komparator, czyli funkcja
pobierająca dwa argumenty typu takiego, jakiego są elementy kolekcji
i zwracająca 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ę parzystą za mniejszą od
dowolnej liczby nieparzystej zwracając w takim, i tylko w takim,
przypadku wartość
true:
1. #include <iostream>
2. #include <vector>
3. #include <string>
4. #include <algorithm>
5. #include <iterator>
6. using namespace std;
7.
8. bool compar(int a, int b) {
9. return (a%2 == 0) && (b%2 != 0);
10. }
11.
12. int main() {
13. vector<int> vec;
14. int d;
15. while ( cin >> d ) vec.push_back(d);
16. cin.clear();
17.
18. sort(vec.begin(), vec.end(), compar);
19.
20. copy(vec.begin(),vec.end(),
21. ostream_iterator<int>(cout, " "));
22. cout << endl;
23. }
3 4 6 8 2 4
2 4 5 3 1 9
^D
4 6 8 2 4 2 4 3 5 3 1 9
gdzie wczytywanie danych zostało przerwane po wprowadzeniu liczby 9.
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 22) do zliczenia liczby
elementów parzystych wektora:
1. #include <iostream>
2. #include <vector>
3. #include <string>
4. #include <algorithm>
5. #include <iterator>
6. using namespace std;
7.
8. bool parzysta(int a) {
9. return (a&1) == 0;
10. }
11.
12. int main() {
13. vector<int> vec;
14. int d;
15. while ( cin >> d ) vec.push_back(d);
16. cin.clear();
17.
18. cout << "W ciagu liczb ";
19. copy(vec.begin(),vec.end(),
20. ostream_iterator<int>(cout, " "));
21. cout << "\njest "
22. << count_if(vec.begin(),vec.end(),parzysta)
23. << " liczb parzystych\n";
24. }
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. }
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. }
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) {
9. return s << str;
10. }
11. };
12.
13. ostream& operator<<(ostream& s, 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. }
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, 21 lutego 2016; 20:17