Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Autor: pekfos
Kurs C++

Wprowadzenie do standardowych algorytmów

[lekcja] Rozdział 49. Trochę więcej o iteratorach, ich różnych rodzajach, oraz po co one w ogóle są.

Wstęp

Iterator to coś co potrafi iterować po czymś. Trudno o bardziej szczegółową definicję, przez to że iterator to bardziej koncept, niż faktyczny twór języka. Dostępne operacje czynią iteratorem, bardziej niż cokolwiek innego. Wskaźnik jest iteratorem, bo można na nim przeprowadzić operacje wymagane dla iteratora, ale iterator ogólnie nie jest wskaźnikiem (koty to zwierzęta, ale zwierzęta to niekoniecznie tylko koty).

Różne rodzaje iteratorów

InputIterator i OutputIterator to najbiedniejsze typy iteratorów jakie są. Można je inkrementować, ale już nie dekrementować. Można wykonać na nich dereferencję. Tu się zaczynają między nimi różnice: Do obiektu wskazywanego z iteratora wyjściowego można zapisać wartość raz (nie musi się dać drugi raz), a odczyt z niego nie musi być możliwy. Z obiektu wskazywanego przez iterator wejściowy można tylko czytać. Inkrementacja przesuwa iterator na następny element w sekwencji. Ewentualne kopie iteratora po inkrementacji nie muszą zachowywać ważności, więc są to iteratory do przejścia po sekwencji tylko raz.
Iterator wejściowy można dodatkowo porównać z innym, ale tylko operatorami == i !=. Iterator wyjściowy nie musi umożliwiać żadnych porównań.

ForwardIterator to najbiedniejszy w operacje iterator, jaki możemy w praktyce dostać z kontenerów (a przynajmniej tych standardowych). ForwardIterator spełnia wymagania stawiane dla InputIterator, oraz dla OutputIterator, jeśli możemy przez ten iterator modyfikować zawartość sekwencji danych. Dodatkowym wymaganiem jest spełnianie tzw multipass guarantee, które znaczy tyle, że możemy dowolnie kopiować iteratory, przechodzić po sekwencji dowolnie wiele razy i dowolnie mieszając iteratory i nie będzie to wpływało na wynik ich dereferencji, lub porównań między iteratorami. Mając iterator spełniający takie wymagania, można już implementować bardziej  złożone algorytmy niż wyszukiwanie maksimum, czy inne rzeczy które da się zrobić w jednym przebiegu.

BidirectionalIterator - to samo co ForwardIterator, ale umożliwia również dekrementację iteratora.

RandomAccessIterator - to samo co BidirectionalIterator, ale daje możliwość arytmetyki. Umożliwia, poprzez dodanie stałej, skok z jednego miejsca w sekwencji w drugie w czasie stałym. Można je odejmować do siebie określając dystans między nimi, można je porządkować operatorami <, <= itp, można je potraktować operatorem indeksowania []. W gruncie rzeczy taki iterator ma zachowanie wskaźnika, przy czym nie musi być wskaźnikiem.

Standardowe algorytmy

Po co cała ta klasyfikacja iteratorów? Bo różne kontenery mają różne możliwości. Omówiliśmy std::vector<> który udostępnia iterator dostępu swobodnego, bo sama struktura danych - zwykła tablica - jest dostępu swobodnego. Gdybyśmy mieli zwykłą listę jednokierunkową, dostępu swobodnego by nie było, można by go najwyżej zasymulować w czasie liniowym. Dla takiej struktury danych naturalnym rozwiązaniem jest ForwardIterator. Powiedzmy że chcemy, używając konceptu iteratora, zaimplementować wyświetlenie wszystkich elementów kontenera. Jeśli sprowadzimy wszystkie kontenery dla własnej wygody do poziomu RandomAccessIterator i użyjemy typowego for z indeksem, to przejście po wektorze będzie miało czas liniowy, a po liście będzie miało czas kwadratowy. Zamiast tego powinniśmy użyć poziomu ForwardIterator i osiągniemy czas liniowy niezależnie od tego czy to wektor, czy lista. Należy użyć iteratora o najmniejszych możliwościach dla kompatybilności i ewentualnie skorzystać z lepszego (jeśli został podany) dla optymalizacji. Tak działają standardowe algorytmy, zdefiniowane w nagłówkach <algorithm> i <numeric>.
C/C++
#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <iterator>
#include <cstdlib>
#include <ctime>

int losowanie()
{
    return rand() % 100;
}

int modyfikacja( int x )
{
    return 2 * x + 1;
}

int main()
{
    srand( time( nullptr ) );
   
    std::vector < int > wektor;
    std::generate_n( std::back_inserter( wektor ), 10, losowanie );
    std::copy( wektor.begin(), wektor.end(), std::ostream_iterator < int >( std::cout, ", " ) );
    std::cout << '\n';
    std::transform( wektor.begin(), wektor.end(), wektor.begin(), modyfikacja );
    std::copy( wektor.begin(), wektor.end(), std::ostream_iterator < int >( std::cout, ", " ) );
    std::cout << '\n';
    std::sort( wektor.begin(), wektor.end() );
    std::copy( wektor.begin(), wektor.end(), std::ostream_iterator < int >( std::cout, ", " ) );
    std::cout << '\n';
    std::cout << "Suma : " << std::accumulate( wektor.begin(), wektor.end(), 0 ) << '\n';
}
97, 4, 38, 37, 2, 46, 1, 27, 21, 21,
195, 9, 77, 75, 5, 93, 3, 55, 43, 43,
3, 5, 9, 43, 43, 55, 75, 77, 93, 195,
Suma : 598
Po kolei:
std::generate_n() generuje N wartości i zapisuje je poprzez iterator zgodny z OutputIterator, podany w pierwszym argumencie. Wartości są generowane z użyciem czegoś wywoływalnego, podanego w 3. argumencie. std::back_inserter() tworzy iterator wyjściowy, który w momencie zapisu pod niego wartości, dodaje tą wartość do kontenera, z użyciem metody push_back(). Działa dla każdego kontenera, który ma taką metodę.
std::copy() kopiuje elementy (duh!) z sekwencji określonej parą iteratorów zgodnych z InputIterator (argumenty 1 i 2) i zapisuje w miejsce podane w trzecim argumencie, iteratorem zgodnym z OutputIterator. std::ostream_iterator() tworzy iterator wyjściowy, który przyjmuje wartości typu podanego w ostrych nawiasach i wypisuje je do strumienia podanego jako pierwszy argument, oddzielając wartości napisem podanym jako drugi argument.
std::transform() to coś, co w programowaniu funkcyjnym nazywa się mapowaniem: dla każdego elementu z sekwencji (argumenty 1 i 2, InputIterator), wykonuje operację (argument 4) i zapisuje wynik do sekwencji określonej iteratorem OutputIterator w argumencie numer 3. W tym wypadku wyniki są zapisywane do tego samego kontenera, nadpisując oryginalne wartości.
std::sort() sortuje elementy z zakresu określonego parą iteratorów RandomAccessIterator. W tym wypadku elementy są sortowane rosnąco, gdzie porównanie odbywa się operatorem <. Jako trzeci argument można podać inne kryterium sortowania - coś wywoływalnego, przyjmującego parę elementów i zwracającego wartość konwertowalną do bool.
std::accumulate() to operacja redukcji z programowania funkcyjnego. Sekwencja elementów (argumenty 1, 2, InputIterator) jest redukowana do jednego, domyślnie operacją dodawania, wartość początkowa jest podana jako 3 argument. Jako 4. argument można podać inną operację.

min, max, swap

Jeśli któreś 'algorytmy' powinieneś znać na pamięć, to właśnie te małe ułatwiacze życia. std::min() zwraca minimum z dwóch wartości, std::max() zwraca maksimum, std::swap() zamienia 2 elementy miejscami. Dla std::swap(), oba argumenty muszą być tego samego typu, w przypadku minimum i maksimum już niekoniecznie. Może to jednak powodować czasem błąd kompilacji przez niejednoznaczność zapisu (jakiś trzeba przyjąć typ dla wyniku), wtedy warto jawnie podać oczekiwany typ:
C/C++
//std::min(4, 3.2f); // Blad
std::min < float >( 4, 3.2f ); // OK

Przykład - sortowanie z nietypowym kryterium

C/C++
#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
#include <cstdlib>
#include <ctime>

int losowanie()
{
    return rand() % 100;
}

// Malejąco, najpierw parzyste, potem nieparzyste
bool predykat( int l, int r )
{
    // Parzystość
    int l_par = l % 2, r_par = r % 2;
   
    if( l_par != r_par )
    // L ma poprzedzać R, jeśli jest parzyste, a R nie (wynika z if)
         return l_par == 0;
   
    // L ma poprzedać R, jeśli jest większe (sortowanie rosnąco)
    return l > r;
}

int main()
{
    srand( time( nullptr ) );
   
    std::vector < int > wektor;
    std::generate_n( std::back_inserter( wektor ), 10, losowanie );
    std::sort( wektor.begin(), wektor.end(), predykat );
    std::copy( wektor.begin(), wektor.end(), std::ostream_iterator < int >( std::cout, ", " ) );
}
74, 68, 66, 62, 4, 97, 73, 41, 3, 1,
Predykat sortowania przyjmuje dwa argumenty i zwraca informację, czy pierwszy argument powinien być przed drugim w posortowanej sekwencji. Ten przykładowy predykat porządkuje liczby tak, by po posortowaniu, najpierw były wszystkie parzyste liczby, a potem dopiero nieparzyste. Każda z tych dwóch partycji ma być posortowana malejąco. Jeśli testowane liczby mają różną parzystość, wynik porównania jest przesądzony. Jeśli obie liczby są parzyste/nieparzyste, wynik porównania jest obliczany na podstawie ich całych wartości.
Aby odwrócić kolejność sortowania nie można po prostu zanegować predykatu. Domyślnie liczby są sortowane rosnąco, porównaniem L < R, aby posortować je malejąco, należy zapisać na przykład L > R, a nie !(L < R). Negacja "mniejsze niż" to "większe równe", a nie "większe niż". Sortowanie (jak większość standardowych algorytmów) wymaga predykatu, który spełnia strict weak ordering, a więc dla predykatu P(L, R):
  • Dla dowolnego X, P(X, X) jest fałszywe ("X nie powinno być przed X")
  • Dla A i B, !P(A, B) && !P(B, A) implikuje, że A i B są sobie "równe" (nie muszą być całkiem równe, np jeśli sortujemy struktury po wartości jednej ze składowych - wartość tej składowej może i jest równa, ale wartości reszty pól są różne)
  • Relacja P(L, R) oraz wyżej opisana relacja równości, nazwijmy ją E(L, R), są relacjami przechodnimi, a wiec:
    P(A, B) && P(B, C) implikuje P(A, C) ("jeśli A ma być przed B i B ma być przed C, to A ma być przed C")
    E(A, B) && E(B, C) implikuje E(A, C) ("jeśli A jest równe B i B jest równe C, to A jest równe C")
Sekwencja jest posortowana, jeśli nie ma takiej pary A i B, gdzie A jest po B i spełnione jest P(A, B), czyli A powinno być przed B. Jeśli predykat nie spełnia wymagań, sekwencja nie musi spełniać tego warunku po sortowaniu, a w skrajnym przypadku sortowanie może spowodować błąd aplikacji.
Elementy sekwencji, które są sobie równe, w sensie relacji E, po posortowaniu będą znajdować się w nieokreślonej kolejności. Jeśli pożądane jest zachowanie dla tych elementów oryginalnej kolejności względem siebie, należy użyć stabilnego sortowania, np std::stable_sort().

Zadanie domowe

Rzuć okiem na poniższe strony i rozeznaj się trochę po dostępnych gotowych implementacjach algorytmów:
» standard C++Algorytmy
http://en.cppreference.com/w​/cpp/algorithm
Poprzedni dokument Następny dokument
Kontener std::vector<> Kontenery asocjacyjne std::set<> i std::map<>