Wstecz: 24. Biblioteka standardowa W górę: 24. Biblioteka standardowa Dalej: 24.2 Algorytmy i obiekty funkcyjne
Podstawowym udogodnieniem dostarczanym przez bibliotekę standardową są kolekcje. Kolekcja jest strukturą danych złożoną z danych pewnego typu i wyposażoną w zestaw operacji, jakie na tych danych można wykonywać. Może to być dodawanie elementów, ich usuwanie, wyszukiwanie, porównywanie, kopiowanie, porządkowanie itd. W bibliotece standardowej zaimplementowano takie podstawowe struktury danych, jak listy, stos, kolejki, kopce, tablice asocjacyjne (słowniki), zbiory; korzystając z nich użytkownik może łatwo i efektywnie tworzyć własne, bardziej złożone struktury, jak choćby różnego typu drzewa czy grafy.
Najprostsza kolekcja opisywana jest szablonem vector dołączanym poprzez włączenie nagłówka vector. Modelem wektora jest tablica elementów tego samego typu, ale o nieokreślonej zawczasu pojemności. Elementy są umieszczane w dobrze zdefiniowanym porządku i mamy do nich dostęp swobodny, to znaczy znając pozycję (indeks) elementu możemy pobrać jego wartość lub go zmienić czy usunąć bez konieczności przeglądania wszystkich elementów wektora. Elementy możemy dodawać na dowolnej pozycji, choć najefektywniejsze (w stałym, niezależnym od rozmiaru wektora, czasie) jest dodawanie na koniec. W miarę jak elementów przybywa, wektorowi przydzielana jest automatycznie większa pamięć — programista nie musi się już martwić zarządzaniem pamięcią, jej przydzielaniem i zwalnianiem. Ponieważ vector jest szablonem klasy, a nie klasą, obiekty-wektory możemy tworzyć konkretyzując wzorzec dla pewnego typu — może to być również typ wbudowany, jak int czy double. Domyślny konstruktor tworzy wektor pusty (są też inne konstruktory). Do utworzonego wektora dodajemy elementy (takiego typu, jak ten dla którego wzorzec został skonkretyzowany) za pomocą metody push_back, która dodaje kopię obiektu na końcu wektora (choć obiekty tymczasowe mogą być przenoszone, a nie kopiowane, co oczywiście może być znacznie efektywniejsze). Kopię, a zatem trzeba zadbać, aby obiekt był dobrze „kopiowalny”, a więc na przykład miał prawidłowo zdefiniowany konstruktor kopiujący (lub przenoszący, jeśli elementy przenosimy). Istnieje też metoda emplace_back pobierająca argumenty dla konstruktora obiektu i tworząca ten obiekt bezpośrednio w wektorze.
Elementy można pobierać na różne sposoby. Najprościej to zrobić
za pomocą indeksowania: robimy to dokładnie tak jak dla normalnej
tablicy (pierwszy element ma, jak zwykle, indeks zero). Taki sposób
jest bardzo efektywny, ale nie jest sprawdzane, czy użyty indeks jest
legalny (tak jak nie jest to sprawdzane w przypadku normalnych tablic).
Jeśli chcemy, aby zostało sprawdzone, czy indeks mieści się
w dozwolonym zakresie, czyli od zera do liczby o jeden mniejszej niż
aktualny rozmiar wektora, to można użyć metody
at
podając indeks jako argument. Przy tej metodzie
dostępu zgłaszany jest wyjątek
out_of_range
(z nagłówka
stdexcept), gdy indeks jest nielegalny.
Wyjątek ten możemy obsłużyć:
1. #include <vector>
2. #include <stdexcept>
3. #include <iostream>
4. #include <string>
5. using namespace std;
6.
7. int main() {
8. vector<string> vs; ➊
9.
10. vs.push_back("Ola");
11. vs.push_back("Ula");
12. vs.push_back("Ela");
13. vs.push_back("Ala");
14.
15. try {
16. for ( int i = 0; i < 5 /* BLAD */; i++ ) ➋
17. cout << vs.at(i) << " " ;
18. } catch(out_of_range) {
19. cout << "\n*** Zly indeks! *** "
20. << " wektor ma tylko " << vs.size()
21. << " elementy!" << endl;
22. }
23. cout << endl;
24.
25. cout << "Pierwszy element: " << vs.front() << endl; ➌
26. cout << "Ostatni element: " << vs.back() << endl; ➍
27.
28. vs.pop_back(); ➎
29.
30. cout << "Po pop_back: ";
31. int size = (int)vs.size(); ➏
32. for ( int i = 0; i < size; i++)
33. cout << vs[i] << " " ;
34. cout << endl;
35. }
W poniższym programie pętla przebiega 5 razy (➋), choć w wektorze są tylko cztery elementy. Podczas ostatniego obrotu zgłaszany jest zatem wyjątek (ale jest on obsłużony):
Ola Ula Ela Ala
*** Zly indeks! *** wektor ma tylko 4 elementy!
Pierwszy element: Ola
Ostatni element: Ala
Po pop_back: Ola Ula Ela
Jak widzimy (➊), obiekt
vs
jest obiektem klasy
vector<string>
powstałej z konkretyzacji szablonu
vector
dla typu
string.
Kolekcja jest zatem kolekcją elementów, z których każdy jest obiektem klasy string. Metoda size, użyta w linii ➏, zwraca, jak łatwo się domyślić, rozmiar kolekcji (nie tylko wektorów). Typem zwracanym jest pewien typ całkowity bez znaku, którego aliasem jest nazwa vector::size_type — dlatego użyliśmy rzutowania — można tu było użyć zwykłego int'a, ale narazilibyśmy się na ostrzeżenia kompilatora. Metoda pop_back (➎) usuwa ostatni element kolekcji, ale go nie zwraca. Metody front i back (➌ i ➍) zwracają, przez referencję, pierwszy i ostatni element kolekcji bez ich usuwania.
Podstawowym narzędziem do wykonywania operacji na kolekcjach są iteratory. Pozwalają one poruszać się po elementach kolekcji w sposób niezależny od ich rzeczywistego typu. Są swego rodzaju uogólnieniem wskaźników. Ich typ jest zdefiniowany w definicji wzorca szablonu kolekcji za pomocą instrukcji typedef i ma postać kol<Typ>::iterator, gdzie kol jest nazwą szablonu kolekcji, a Typ jest typem użytym do skonkretyzowania tego szablonu. Użytkownik nie musi wiedzieć, jaki naprawdę ten typ jest. Na przykład nazwą (aliasem) typu iteratora związanego z wektorem liczb typu int jest vector<int>::iterator. Kolekcja może być kolekcją elementów niemodyfikowalnych (lub chcemy ją tak traktować); dla każdej kolekcji zatem jest też zdefiniowany osobny typ const_iterator (na przykład vector<int>::const_iterator).
Iteratory mają semantykę wskaźników do elementów tablicy, to znaczy, jeśli it jest iteratorem wskazującym na pewien element kolekcji, to *it jest referencją do wskazywanego elementu (a więc l-wartością), a it->sklad jest nazwą składowej sklad wskazywanego przez iterator obiektu (jeśli taka składowa istnieje). Podobnie, po ' ++it' iterator it wskazuje na następny element kolekcji.
Istnieją w klasach kolekcyjnych dwie ważne bezargumentowe metody
zwracające iteratory: metoda
begin
i
end. Metoda
begin zwraca iterator
wskazujący na pierwszy element kolekcji. Nieco bardziej skomplikowany
jest wynik metody
end.
Nie jest to iterator wskazujący na ostatni element kolekcji, jak
by się mogło wydawać, ale na nieistniejący element „tuż za
ostatnim”.
[Biblioteka definiuje też globalne funkcje, zdefiniowane w nagłówku
iterator,
begin
i
end, które
pobierają kolekcję a zwracają te same iteratory].
Jeśli przebiegamy kolekcję za pomocą iteratora, to
osiągnięcie przez niego wartości zwracanej przez
end
oznacza, że przebiegliśmy już całą kolekcję.
Zamiast więc sprawdzać, jak zwykle w pętlach przebiegających
tablice, czy indeks jest mniejszy od wymiaru tablicy, sprawdzamy,
czy iterator wciąż nie jest równy iteratorowi zwracanemu przez
metodę
end; jeśli jest, to pętlę należy przerwać,
bo iterator wskazuje na element nieistniejący:
1. #include <vector>
2. #include <iostream>
3. #include <string>
4. using namespace std;
5.
6. int main() {
7. vector<string> vs{"Ola", "Ula", "Ela","Ala"};
8.
9. for ( vector<string>::iterator ite = vs.begin();
10. ite!= vs.end(); ++ite)
11. cout << *ite << " ";
12. cout << endl;
13.
14. // albo
15.
16. vector<string>::iterator it, kon = vs.end();
17.
18. for ( it = vs.begin(); it != kon; ++it )
19. cout << *it << " ";
20. cout << endl;
21.
22. // albo
23.
24. using SIT=vector<string>::iterator; ➊
25.
26. SIT iter, koniec = vs.end();
27.
28. for ( iter = vs.begin(); iter != koniec; ++iter )
29. cout << *iter << " ";
30. cout << endl;
31.
32. // a najlepiej
33.
34. for ( auto i = vs.begin(); i != vs.end(); ++i )
35. cout << *i << " ";
36. cout << endl;
37. }
Powyższy program ilustruje sposób konstruowania pętli z użyciem iteratorów. Jeśli w programie potrzebujemy wielu zmiennych iteratorowych danego typu, to wygodnie jest temu typowi nadać jakąś krótszą nazwę za pomocą typedef lub using, jak to zrobiliśmy w linii ➊. Tak jak mówiliśmy, ++it przesuwa iterator na następną pozycję w kolekcji, a *it oznacza element w kolekcji wskazywany przez iterator it.
Jeśli kolekcja jest niemodyfikowalna, to nie tylko możemy, ale
musimy użyć iteratora typu
const_iterator.
Z taką sytuacją
spotykamy się bardzo często, gdy przesyłamy kolekcję jako argument
funkcji, która z założenia nie powinna elementów tej kolekcji
zmieniać, a wobec tego jej parametr jest typu ustalonego:
1. #include <vector>
2. #include <iostream>
3. using namespace std;
4.
5. struct Person {
6. char name[20];
7. int year;
8. void print() const {
9. cout << name << "-" << year << endl;
10. }
11. } john = {"John",25}, mary = {"Mary",18}, sue = {"Sue",9};
12.
13.
14. void printPerson(const vector<const Person*>& list) {
15. for (auto it = list.cbegin(); it != list.cend(); it++)
16. (*it)->print();
17. }
18.
19. int main() {
20. vector<const Person*> list;
21.
22. list.push_back(&john);
23. list.push_back(&mary);
24. list.push_back(&sue);
25.
26. printPerson(list);
27. }
Zauważmy, że słowo kluczowe const pojawia się tu kilkakrotnie. W określeniu typu
vector<const Person*>oznacza, że kolekcja jest wektorem wskaźników do ustalonych elementów, a zatem, że poprzez odwołania się do obiektów klasy Person wskazywanych przez elementy kolekcji nie można zmienić tych obiektów. Z kolei pierwsze const w określeniu typu parametru funkcji printPerson oznacza, że jest to kolekcja niemodyfikowalnych elementów, czyli niemodyfikowalnych wskaźników, bo taki jest typ tych elementów. A zatem wewnątrz funkcji printPerson nie można zmienić ani adresów zapisanych we wskaźnikach będących elementami kolekcji, ani obiektów przez te wskaźniki wskazywanych. Ponieważ funkcja, poprzez typ zadeklarowanego parametru, „obiecała”, że nie zmieni obiektów wskazywanych, a wywołuje na rzecz tych obiektów metodę print, metoda ta musiała być zadeklarowana jako const. Funkcja „obiecała” też, że nie zmieni elementów kolekcji, czyli wskaźników, zatem użyty iterator musiał tu być typu const_iterator. Zauważmy, że użyliśmy tu metod cbegin i cend — są one analogiczne do begin i end, ale zwracają const_iterator.
Parametr funkcji printPerson jest typu referencyjnego. Jest to zwykle pożądane przy przesyłaniu do funkcji kolekcji — w przeciwnym przypadku kopiowane byłyby całe kolekcje, wraz ze wszystkimi elementami. Tego problemu nie było przy przesyłaniu tablic, kiedy tak naprawdę przesyłany był tylko wskaźnik do pierwszego elementu.
Prócz iteratorów
iterator
i
const_iterator
istnieje typ
iteratora odwrotnego
reverse_iterator,
za pomocą którego można przebiegać
kolekcje w odwrotnym kierunku; na przykład program
1. #include <vector>
2. #include <iostream>
3. #include <string>
4. using namespace std;
5.
6. int main() {
7. vector<string> vs{"Ola", "Ula", "Ela", "Ala"};
8.
9. for (auto r = vs.rbegin(); r != vs.rend(); ++r)
10. cout << *r << " ";
11. cout << endl;
12. }
drukuje
Ala Ela Ula Ola
Użyliśmy tu metod
rbegin
i
rend,
które zwracają właśnie iteratory odwrotne.
Istnieje też const_reverse_iterator.
Ze względu na swoją funkcjonalność iteratory dzielą się na kilka kategorii. Z różnymi kolekcjami związane są różne kategorie iteratorów.
Na przykład iterator związany z wektorem (vector) pozwala nie tylko na przesuwanie się w obu kierunkach za pomocą operatorów zwiększania i zmniejszania, ale na stosowanie arytmetyki wskaźników, to znaczy np. dodanie liczby 3 do takiego iteratora daje iterator przesunięty o trzy elementy do przodu względem wyjściowego. Podobnie, po
vector<string> vs;
// ...
auto it = vs.begin() + vs.size()/2;
iterator
it
wskazuje na środkowy element wektora. Iteratory
takie można też porównywać za pomocą operatorów relacyjnych (jak
np. '
>') czy odejmować (wynikiem jest liczba elementów
pomiędzy pozycjami w kolekcji wskazywanymi przez te iteratory).
Elementy wskazywane takimi iteratorami można odczytywać, jak i na nie
przypisywać. Tego typu iteratory to
iteratory o dostępie bezpośrednim
(ang. random access
iterator). Są one np. związane z wektorami (vector),
kolejkami dwustronnymi (deque)
i obiektami klasy
string,
które są traktowane jako kolekcje znaków.
Drugim typem iteratora jest iterator dwukierunkowy (ang. bidirectional iterator). Pozwala na poruszanie się po kolekcji w obu kierunkach za pomocą operatorów zwiększania i zmniejszania ('++' i '- -'), ale nie wspiera arytmetyki wskaźników, na przykład dodawania liczb całkowitych do iteratora. Takie iteratory można porównywać za pomocą ' ==' i ' !=', ale nie za pomocą ' <' i ' >'. Są one związane na przykład z kolekcjami listowymi (list, z nagłówka list).
Jeszcze bardziej ograniczona jest funkcjonalność iteratorów jednokierunkowych (ang. forward iterator). Są one podobne do dwukierunkowych, ale pozwalają na poruszanie się tylko w jednym kierunku: do przodu.
W końcu najbardziej ograniczone są możliwości iteratorów wejściowych i wyjściowych (ang. input i output iterator). Pozwalają one tylko na jednokrotny przebieg (ang. single pass) kolekcji w kierunku do przodu. Iteratory wejściowe pozwalają tylko na odczyt elementu wskazywanego, a wyjściowe tylko na przypisanie im wartości, ale nie odczyt. Takie iteratory związane są zwykle ze strumieniami (wejściowymi i wyjściowymi).
Iteratory są podstawowym elementem stosowanym w algorytmach i funkcjach operujących na kolekcjach. Pełnią one rolę łącznika między algorytmami (funkcjami) a strukturami danych, jakimi są kolekcje.
Na kolekcjach można wykonywać wiele operacji, choć należy
pamiętać, że nie każdą z nich można wykonać na każdej
kolekcji. Związane jest to z kwestią wydajności: niektóre
kolekcje dopuszczają mniej operacji, ale za to są one wykonywane
bardzo efektywnie. Na przykład, jak wspominaliśmy, różnica dwóch
iteratorów odnoszących się do wektora daje liczbę elementów
pomiędzy nimi — ponieważ w wektorze elementy są rozmieszczone
w pamięci jeden przy drugim i rozmiar ich jest znany, jest to operacja
bardzo szybka, sprowadzająca się do jednego odejmowania i jednego
dzielenia. Dla listy (list) nie jest to takie proste, więc
aby osiągnąć ten sam cel, należy użyć specjalnej funkcji
distance
o liniowym (a więc proporcjonalnym do rozmiaru listy) czasie
działania:
1. #include <iostream>
2. #include <vector>
3. #include <string>
4. #include <list>
5. using namespace std;
6.
7. int main() {
8. vector<string> vec;
9.
10. #if defined(__WIN32)
11. cout << "Podaj slowa (^Z konczy):\n";
12. #elif defined(__linux)
13. cout << "Podaj slowa (^D konczy):\n";
14. #else
15. #error Nieznany system
16. #endif
17.
18. string s;
19. while ( cin >> s ) vec.push_back(s);
20. cin.clear();
21.
22. list<string> lis(vec.begin(),vec.end()); ➊
23.
24. cout << "Slowo do znalezienia: ";
25. cin >> s;
26.
27. auto sit = vec.cbegin();
28. auto lit = lis.cbegin();
29.
30. // wektor
31. for ( ; sit != vec.cend(); ++sit)
32. if ( *sit == s ) break;
33. if ( sit != vec.cend() )
34. cout << "(vec) Slowo " << s << " na pozycji "
35. << sit - vec.cbegin() << endl; ➋
36. else
37. cout << "Slowo " << s << " nie wystapilo" << endl;
38.
39. // lista
40. for ( ; lit != lis.cend(); ++lit)
41. if ( *lit == s ) break;
42. if ( lit != lis.cend() )
43. cout << "(lis) Slowo " << s << " na pozycji "
44. << distance(lis.cbegin(),lit) << endl; ➌
45. else
46. cout << "Slowo " << s << " nie wystapilo" << endl;
47. }
W linii ➊ zastosowaliśmy konstruktor listy (taki sam istnieje i dla pozostałych kolekcji) przyjmujący dwa iteratory związane z inną kolekcją, w tym przypadku wektorem. Elementy od tego wskazywanego przez pierwszy iterator włącznie do wskazywanego przez drugi z iteratorów wyłącznie są kopiowane do nowo tworzonej kolekcji. Tak więc lista w naszym przypadku będzie zawierać te same elementy co wektor. Ponieważ iterator związany z wektorem należy do kategorii iteratorów o dostępie swobodnym, można (➋) użyć po prostu różnicy iteratorów do określenia pozycji — tu obliczmy ją względem pozycji zerowej, zwracanej przez begin. Dla listy (➌) użyliśmy do tego funkcji distance, ponieważ iterator związany z listami należy do kategorii dwukierunkowych i nie wspiera arytmetyki wskaźników. Przykładowy wydruk:
Podaj slowa (^D konczy):
Ala
Ela
Ula
^D
Slowo do znalezienia: Ula
(vec) Slowo Ula na pozycji 2
(lis) Slowo Ula na pozycji 2
Do przerwania wczytywania danych użyty tu został
znak końca danych, czyli Ctrl-D (pod Windows byłoby to Ctrl-Z).
Zwykła tablica może być, przynajmniej do pewnego stopnia, traktowana jak kolekcja. Wskaźniki do elementów tablicy pełnią wtedy rolę iteratorów. Na przykład po
int arr[] = {1,4,6,8,9};
vector<int> v(arr+1,arr+4);
wektor
v
będzie zawierał liczby 4, 6 i 8 bo wskaźnik
arr+1 wskazuje na liczbę 4, a wskaźnik
arr+4 na
liczbę 9, a zgodnie z tym, co mówiliśmy, przedział obejmuje element
wskazywany przez iterator pierwszy, ale już nie obejmuje elementu
wskazywanego przez iterator drugi.
Jak wspomnieliśmy, kolekcją (znaków) jest obiekt klasy string. Kilka przykładów ilustrujących tę cechę napisów w stylu C++ podaliśmy już w rozdziale o napisach .
Inną, często stosowaną operacją jest usuwanie elementów kolekcji. Służy do tego metoda erase. Jej argumentem powinien być iterator wskazujący na usuwany element albo para iteratorów; w tym drugim przypadku usuwane są elementy od wskazywanego pierwszym iteratorem włącznie do wskazywanego drugim iteratorem wyłącznie. Na przykład po
vector<Person> os;
os.push_back(Person("Jenny"));
os.push_back(Person("Jill"));
os.push_back(Person("Jane"));
os.push_back(Person("Janet"));
os.erase(os.begin()+1, os.end());
z wektora
os
usunięte zostaną wszystkie elementy
prócz pierwszego. Elementów nie należy usuwać w pętli, bo
po usunięciu pierwszego z nich stan kolekcji się zmienia —
pozostałe elementy zmieniają swoje pozycje, co może doprowadzić do
chaosu.
Podobnie można do kolekcji dodawać nowe elementy za pomocą metody insert. Argumentem wskazującym, na której pozycji (a ściślej, przed którym elementem) nowe elementy powinny się pojawić, jest oczywiście iterator. Z kolei elementy do wstawienia mogą pochodzić z innej kolekcji; ich zakres wskazywany jest parą iteratorów:
double tab[] = {2, 4, 6, 7, 8, 1.5, 5, 7};
list<double> lis(5);
lis.insert(lis.begin(),10.5);
lis.insert(lis.begin(),tab+1,tab+3);
W tym fragmencie zwróćmy uwagę na linię drugą. Tworzymy tu listę
o pięciu elementach, którym nadawane są wartości domyślne.
W naszym przypadku elementami były liczby, o wartości domyślnej 0,
ale dla obiektów użyty byłby konstruktor domyślny. Zatem powinien
on wtedy istnieć! Następnie dodajemy liczbę 10.5 na początek listy.
Pozostałe 5 elementów przesuwa się w prawo: po tej operacji lista
ma już sześć elementów. W czwartej linii na nowej początkowej
pozycji (a więc przed wstawione tam przed chwilą 10.5) wstawiamy dwie
liczby z tablicy
tab: liczby z pozycji 1 i 2, czyli liczby 4
i 6. Zatem teraz lista ma osiem elementów:
4 6 10.5 0 0 0 0 0
Dla list (również dla kolekcji typu
deque, ale nie
vector), prócz metod operujących na końcu kolekcji,
szczególnie efektywnie zaimplementowane są metody operujące na jej
początku. Analogicznie do metod
push_back,
pop_back
i
back,
o których już mówiliśmy, działają metody
push_front,
pop_front
i
front.
W miarę możności należy raczej
korzystać z funkcji operujących na końcach kolekcji, a nie np. z
funkcji
insert
czy
erase, których implementacja
jest zwykle wolniejsza.
T.R. Werner, 23 lutego 2022; 19:40