Kontenery w C++
Większość pracy komputera polega na tworzeniu zbiorów wartości i operowaniu na nich na różne sposoby. Prostym przykładem takich działań jest wczytywanie znaków do łańcucha i ich drukowanie. Klasa, której głównym przeznaczeniem jest przechowywanie znaków, nazywa się kontenerem. Utworzenie odpowiednich kontenerów i wsparcie ich właściwymi podstawowymi operacjami jest jednym z najważniejszych elementów budowy programu.
Kontenery z biblioteki standardowej można przedstawić, posługując się przykładem prostego programu do przechowywania nazwisk i numerów telefonicznych. Jest to taki rodzaj programu, którego realizacja na różne sposoby osobom posiadającym różne rodzaje wiedzy wydaje się oczywista i łatwa.
Vector
Najbardziej przydatnym kontenerem w bibliotece standardowej jest vector. Wektor to szereg elementów określonego typu. Elementy te są przechowywane w sąsiadujących komórkach pamięci:
Wektor można zainicjować zbiorem wartości określonego typu:
{"David Hume",123456},
{"Karl Popper",234567},
{"Bertrand Arthur William Russell",345678}
};
Dostęp do elementów odbywa się poprzez indeksy:
{
for (int i = 0; i!=book.size(); ++i)
cout << book[i] << ' ';
}
Jak zawsze indeksowanie rozpoczyna się od zera, a więc book[0] to element zawierający numer Davida Hume’a. Funkcja składowa size() wektora zwraca liczbę jego elementów. Elementy wektora tworzą zakres, dzięki czemu można używać zakresowej pętli for (2.2.5):
{
for (const auto& x : book) // opis auto: 2.2.2
cout << x << ' ';
}
Definiując wektor, można określić jego początkowy rozmiar (początkową liczbę elementów):
vector v2; // rozmiar 0
vector v3(23); // rozmiar 23; początkowa wartość elementów: nullptr
vector v4(32,9.9); // rozmiar 32; początkowa wartość elementów: 9.9
Liczbę określającą rozmiar wpisuje się w nawiasie, np. (23), i domyślnie elementy są inicjowane wartością domyślną dla typu elementów wektor (np. nullptr dla wskaźników albo 0 dla liczb). Jeżeli nie chcemy domyślnej wartości, można podać własną jako drugi argument (np. 9.9 dla 32 elementów wektora v4). Początkowy rozmiar można później zmienić. Jedną z najbardziej przydatnych operacji wektora jest push_back(), która dodaje nowy element na końcu kontenera i zwiększa jego rozmiar o jeden. a przykład:
{
for (Entry e; cin>>e;)
phone_book.push_back(e);
}
Ta funkcja wczytuje pozycje książki telefonicznej (Entry) z wejścia standardowego do phone_book, aż nastąpi koniec danych wejściowych (np. koniec pliku) albo pojawi się błąd w danych wejściowych. Wektor w bibliotece standardowej jest tak skonstruowany, że jego zwiększanie poprzez wielokrotne wywoływanie funkcji push_back() jest wydajne. Wektor można kopiować w przypisaniach i inicjacjach. Na przykład:
Operacje kopiowania i przenoszenia wektora są zaimplementowane przez konstruktory i operatory przypisania, jak opisałem w podrozdziale 3.3. Przypisanie wektora powoduje skopiowanie jego elementów. Dlatego po inicjacji wektora book2 wektory book2 i phone_book zawierają własne kopie każdej pozycji książki telefonicznej. Gdy element zawiera dużą liczbę elementów, takie niewinnie wyglądające przypisania i inicjacje mogą być bardzo kosztowne. Tam, gdzie kopiowanie jest niepożądane, powinno się używać referencji lub wskaźników (7.2, 7.7) albo operacji przenoszenia (3.3.2, 17.5.2).
Elementy
Tak jak wszystkie kontenery w bibliotece standardowej vector jest kontenerem elementów typu T, tzn. vector. Praktycznie każdy typ może zostać użyty jako typ elementów. Kwalifikują się wbudowane typy liczbowe (takie jak char, int i double), typy zdefiniowane przez użytkownika (takie jak string, Entry, list czy Matrix) oraz wskaźniki (takie jak const char*, Shape* i double*). Gdy do wektora wstawiany jest nowy element, następuje skopiowanie jego wartości. Na przykład: jeśli umieści się w wektorze liczbę całkowitą o wartości 7, to element będzie miał wartość 7. Element nie jest referencją ani wskaźnikiem do jakiegoś obiektu zawierającego 7. Dzięki temu można tworzyć zgrabne kontenery o krótkim czasie dostępu. Ma to kluczowe znaczenie w przypadkach, gdy najważniejsza jest pamięć i szybkość działania.
Sprawdzanie zakresu
Wektor z biblioteki standardowej nie gwarantuje sprawdzania zakresu (31.2.2). Na przykład:
void silly(vector& book)
{
int i = book[book.size()].number; // book.size() jest poza zakresem
//...
}
Inicjacja i spowoduje zapisanie w tej zmiennej jakiejś losowej wartości zamiast zgładzenia błędu. Jest to niepożądane i błędy typu „poza zakresem” są dość powszechne. Dlatego często używam prostej adaptacji wektora ze sprawdzaniem zakresu:
class Vec : public std::vector {
public:
using vector::vector; // użycie konstruktorów z typu vector (pod nazwą Vec);
T& operator[](int i) // sprawdzanie zakresu
{ return vector::at(i); }
const T& operator[](int i) const // sprawdzanie zakresu obiektów const;
{ return vector::at(i); }
};
Vec dziedziczy wszystko z typu vector z wyjątkiem operacji indeksowania, których definicję zmienia tak, aby wykonywały sprawdzanie zakresu. Funkcja at() jest operacją indeksowania wektora zgłaszającą wyjątek typu out_of_range, jeżeli jej argument znajduje się poza zakresem wektora.
W klasie Vec dostęp do elementu spoza zakresu spowoduje zgłoszenie wyjątku, który może zostać przechwycony przez użytkownika. Na przykład:
{
try{
book[book.size()] = {"Jan",999999}; // spowoduje wyjątek
//...
}
catch (out_of_range) {
cout << "Błąd zakresu ";
}
}
Wyjątek zostanie zgłoszony i przechwycony. Jeżeli użytkownik nie przechwyci wyjątku, program zostanie zamknięty w odpowiedni sposób, zamiast kontynuować działanie albo ulec niekontrolowanej awarii. Jednym ze sposobów na zminimalizowanie ryzyka wystąpienia niemiłych niespodzianek w postaci nieprzechwyconych wyjątków jest użycie bloku try w treści funkcji main():
try{
// kod programu
}
catch (out_of_range) {
cerr << "Błąd zakresu ";
}
catch (...) {
cerr << "Wystąpił nieznany wyjątek ";
}
W kodzie tym znajdują się domyślne procedury obsługi wyjątków i jeśli wystąpi jakiś nieprzewidziany wyjątek, to dzięki tym procedurom program wydrukuje wiadomość w standardowym strumieniu błędów i diagnostyki cerr. Niektóre implementacje dostarczają wersję typu vector ze sprawdzaniem zakresu (np. włączaną za pomocą opcji kompilatora), dzięki czemu nie trzeba definiować własnego typu Vec (albo o innej nazwie).
List
W bibliotece standardowej dostępna jest implementacja listy wiązanej dwustronnie o nazwie list:
List używa się do przechowywania szeregów wartości, w których trzeba dodawać i usuwać elementy bez przesuwania pozostałych elementów. Dodawanie i usuwanie pozycji książki telefonicznej to często wykonywana czynność, więc lista może być odpowiednią strukturą do przechowywania prostej książki telefonicznej. Na przykład:
{"David Hume",123456},
{"Karl Popper",234567},
{"Bertrand Arthur William Russell",345678}
};
W listach powiązanych zwykle nie używa się indeksów w taki sposób jak w wektorach. Zamiast tego listy często się przeszukuje w celu znalezienia elementu o określonej wartości.
{
for (const auto& x : phone_book)
if (x.name==s)
return x.number;
return 0; // 0 reprezentuje „nie znaleziono numeru”
}
Szukanie s rozpoczyna się na początku listy i jest kontynuowane, aż s zostanie znalezione albo nastąpi koniec książki telefonicznej. Czasami trzeba zidentyfikować element w liście, aby np. usunąć go albo wstawić przed nim nową wartość. Do tego celu używa się iteratora. Iterator listy identyfikuje element listy i może być używany do jej przeglądania, czyli iteracji przez listę (stąd nazwa iterator). Każdy kontener w bibliotece standardowej udostępnia funkcje begin() i end() zwracające iterator odpowiednio ustawiony na pierwszy element i miejsce o jeden za ostatnim elementem. Przy użyciu iteratorów można — mniej elegancko — napisać funkcję get_number() w następujący sposób:
{
for (auto p = phone_book.begin(); p!=phone_book.end(); ++p)
if (p−>name==s)
return p−>number;
return 0; // 0 reprezentuje „nie znaleziono numeru”
}
W istocie tak właśnie jest zaimplementowana przez kompilator bardziej zwięzła i mniej podatna na błędy pętla for. Dla iteratora p *p jest wskazywanym przez niego elementem, ++p powoduje przestawienie p na następny element, a gdy p odnosi się do klasy zawierającej składową m, p->m jest równoznaczne z (*p).m.
Dodawanie i usuwanie elementów list jest łatwe:
{
phone_book.insert(p,ee); // dodaje ee przed elementem wskazywanym przez p
phone_book.erase(q); // usuwa element wskazywany przez q
}
Powyższe przykłady list można identycznie napisać przy użyciu typu vector i (co zaskakujące, jeśli ktoś dobrze nie zna architektury komputerów) mają one lepszą wydajność z małymi wektorami niż z małymi listami. Jeśli potrzebna jest tylko sekwencja elementów, to do wyboru są kontenery vector i list. Jeśli nie ma ważnych przeciwwskazań, lepiej jest użyć wektora. Wektor jest bardziej wydajny przy przeglądaniu (np. za pomocą funkcji find() i count()) oraz sortowaniu i przeszukiwaniu (np. przy użyciu funkcji sort() i binary_search()).
Map
Pisanie kodu do znajdowania nazwiska na liście par (nazwisko, numer) jest dość żmudne. Ponadto liniowe wyszukiwanie w większych listach jest dalekie od optymalnego. Dlatego w bibliotece standardowej dostępne jest drzewo poszukiwań (czerwono-czarne) o nazwie map:
Mapa czasami występuje też pod nazwami tablica asocjacyjna i słownik. Jest zaimplementowana jako zrównoważone drzewo binarne. Mapa w bibliotece standardowej jest kontenerem par wartości zoptymalizowanym pod kątem wyszukiwania. Przy tworzeniu mapy można używać takiego samego inicjatora jak w przypadku wektora i listy:
{"David Hume",123456},
{"Karl Popper",234567},
{"Bertrand Arthur William Russell",345678}
};
Mapa jest indeksowana wg wartości swojego pierwszego typu (zwanego kluczem) i zwraca odpowiednią wartość drugiego typu (zwanego wartością albo typem mapowanym). Na przykład:
{
return phone_book[s];
}
Innymi słowy, indeksowanie mapy to w istocie operacja wyszukiwania, jaką wykonywaliśmy wcześniej przy użyciu funkcji get_number(). Jeżeli klucz nie zostanie znaleziony, jest wstawiany do mapy z domyślną wartością. Wartość domyślna dla typu całkowitoliczbowego to 0. Wartość, którą akurat wybrałem, reprezentuje niepoprawny numer telefoniczny. Aby uniknąć wprowadzania niepoprawnych numerów telefonicznych do książki, można zamiast operatora [] użyć funkcji find() i insert()).
unordered_map
Złożoność obliczeniowa typu map wynosi O(log(n)), gdzie n jest liczbą elementów w kontenerze. To bardzo dobry wynik. Przykładowo: aby znaleźć element w mapie zawierającej 1 000 000 elementów, należy wykonać tylko około 20 porównań i operacji pośrednich. A jednak w wielu przypadkach da się osiągnąć jeszcze lepszy wynik poprzez zastosowanie wyszukiwania z mieszaniem zamiast porównywania przy użyciu funkcji porządkującej w rodzaju <. Kontenery mieszające dostępne w bibliotece standardowej nazywa się nieuporządkowanymi (unordered_), bo nie wymagają stosowania funkcji porządkującej:
Na przykład kontenera unordered_map z nagłówka można użyć do przechowywania naszej książki telefonicznej:
{"David Hume",123456},
{"Karl Popper",234567},
{"Bertrand Arthur William Russell",345678}
};
Kontener unordered_map można indeksować, podobnie jak map:
{
return phone_book[s];
}
Kontener unordered_map z biblioteki standardowej udostępnia domyślną funkcję mieszającą dla łańcuchów (string). W razie potrzeby można też napisać własną.
Przegląd kontenerów
W bibliotece standardowej znajduje się szeroki wybór ogólnych i bardzo przydatnych typów kontenerów, dzięki czemu dla każdego programu można znaleźć odpowiednią strukturę do przechowywania danych. Nieuporządkowane kontenery są zoptymalizowane do przeszukiwania wg klucza (często łańcuchowego). Inaczej mówiąc, są zaimplementowane przy użyciu tablic skrótów (mieszających).
Zestawienie standardowych kontenerów
vector<T> Wektor o zmiennym rozmiarze
list<T> Lista powiązana dwustronnie
forward_list<T> Lista powiązana jednostronnie
deque<T> Kolejka dwukierunkowa
set<T> Zbiór
multiset<T> Zbiór, w którym wartości mogą się powtarzać
map<K,V> Tablica asocjacyjna
multimap<K,V> Mapa, w której klucze mogą się powtarzać
unordered_map<K,V> Mapa z mieszaniem
unordered_multimap<K,V> Multimapa z mieszaniem
unordered_set<T> Zbiór z mieszaniem
unordered_multiset<T> Wielozbiór z mieszaniem
Kontenery biblioteki standardowej i ich operacje są zaprojektowane w taki sposób, aby można było się nimi posługiwać przy użyciu podobnej notacji. Ponadto wszystkie te operacje w każdym kontenerze mają takie same znaczenie. Podstawowe operacje mają zastosowanie do każdego rodzaju kontenera, w którym ich implementacja ma sens i jest opłacalna pod względem wydajnościowym. Na przykład:
- Funkcje begin() i end() zwracają iteratory do pierwszego i znajdującego się o jeden za ostatnim elementu kontenera.
- Funkcja push_back() służy do dodawania elementów na końcu kontenerów vector, forward_list, list i innych.
- Funkcja size() zwraca liczbę elementów.
Ta jednolitość pod względem notacji i semantyki sprawia, że programista może z łatwością tworzyć nowe typy kontenerów, których można używać w bardzo podobny sposób jak standardowych. Przykładem tego jest wektor ze sprawdzaniem zakresu Vector. Ponadto dzięki jednolitości interfejsów kontenerów można definiować algorytmy niezależnie od jakiegokolwiek typu kontenera. Każdy z nich ma jednak jakieś wady i zalety. Na przykład indeksowanie w wektorze jest szybkie i wydajne. Ale przy wstawianiu i usuwaniu elementów pozostałe elementy wektora są przesuwane. Lista ma dokładnie odwrotne właściwości. Należy
pamiętać, że wektor jest zazwyczaj bardziej wydajny przy przechowywaniu krótkich list niewielkich elementów (dotyczy to nawet działania funkcji insert() i erase()) niż kontener list. Zalecam używanie standardowego typu vector jako domyślnego kontenera do przechowywania sekwencji elementów. Aby zdecydować się na użycie czegoś innego, należy mieć ku temu dobry powód.
Język C++. Kompendium wiedzy. Wydanie IV, Autor: Bjarne Stroustrup, Wydawnictwo: Helion
