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>.
#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:
std::min < float >( 4, 3.2f );
Przykład - sortowanie z nietypowym kryterium
#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
#include <cstdlib>
#include <ctime>
int losowanie()
{
return rand() % 100;
}
bool predykat( int l, int r )
{
int l_par = l % 2, r_par = r % 2;
if( l_par != r_par )
return l_par == 0;
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):
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:
Algorytmyhttp://en.cppreference.com/w/cpp/algorithm