Podrozdziały


24.2 Algorytmy i obiekty funkcyjne

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.


24.2.1 Algorytmy

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:


P194: sort.cpp     Sortowanie

      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 programie tym tworzymy wektor i sortujemy (porządkujemy) go za pomocą funkcji sort pobierającej dwa iteratory określające przedział ciągu do posortowania (linia 21). Iteratory muszą należeć do kategorii iteratorów o dostępie swobodnym, więc ten sposób sortowania nie nadaje się dla list. Nie znaczy to, że nie możemy uporządkować listy: prócz użytego w przykładzie algorytmu sort jest też podobna metoda sort dla kolekcji listowych, użyta w linii 22. Może być użyta bez argumentów — sortuje wtedy wszystkie elementy kolekcji, na rzecz której została wywołana, lub argumentami mogą być iteratory, tak jak dla funkcji o tej samej nazwie. Podobnie jest dla innych funkcji wymagających iteratorów o dostępie swobodnym: ich odpowiedniki dla kolekcji z iteratorami dwukierunkowymi są zdefiniowane jako metody odpowiednich kolekcji i zwykle mają znacznie gorsze parametry wydajnościowe (merge, remove, reverse itd.).

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:


P195: sortev.cpp     Komparatory

      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.  }

Przykładowy wydruk tego programu:
    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:


P196: predyk.cpp     Predykaty

      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.  }

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 findfind_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:


P197: szuk.cpp     Wyszukiwanie

      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


24.2.2 Obiekty funkcyjne

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:


P198: compr.cpp     Obiekty funkcyjne

      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:


P199: maniparg.cpp     Manipulatory jako obiekty funkcyjne

      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.  }

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 trzywykrzyknikisiedemgwiazdek w liniach 24-25.

T.R. Werner, 21 lutego 2016; 20:17