Omówienie tematu kontenerów STL-a w C++

Standard Template Library (STL) zawiera zestaw kontenerów (struktur danych), w których przechowujemy dane. Kontenerów tych używamy w połączeniu z algorytmami STL, aby rozwiązać niektóre problemy z przetwarzaniem danych. W tym artykule omówię trzy kategorie kontenerów w STL-a i krótko przedstawię ich specyfikę. 

Kategorie kontenerów w STL

Oto trzy kategorie kontenerów w STL: sekwencyjne, asocjacyjne oraz adaptery. Kontener sekwencyjny przechowuje dane w kolejności sekwencyjnej — tutaj kolejność jest bardzo ważna. Może być, na przykład, tak, że trzeba wyświetlić zestaw ocen od najniższej do najwyższej, dlatego musimy przechowywać te dane w kontenerze sekwencyjnym. 

Kontenery asocjacyjne przechowują dane związane z innymi danymi. Mam, na przykład, listę kontaktów i przechowuję tam nazwy i numery telefonów powiązane z tymi nazwami. Za przykład może również posłużyć inwentaryzacja, gdzie liczba produktów na stanie jest związana z nazwą danego produktu. Trzeci typ to adaptery. Takie kontenery są wariantami jednej z pozostałych kategorii. Dwa klasyczne przykłady to stosy i kolejki, które omówię w dalszej części artykułu.

Zanim zacznę omawiać kontenery sekwencyjne, muszę poświęcić chwilę na omówienie ich użycia w porównaniu z podstawową (w sensie bycia wbudowaną) tablicą. Przez wiele lat, nawet po pojawieniu się STL-a, programiści dalej używali tablic do przechowywania danych. 

Było tak w większości ze względu na wyższą wydajnością tablic w stosunku do kontenerów STL-a, pomimo tego, że używanie tablic powodowało problemy wynikające z braku elastyczności ze względu na rozmiar. Przewaga ta nie ma już teraz znaczenia, ponieważ STL stał się bardziej wydajny. 

Nawet taki autorytet, jak Bjarne Stroustrup, zaleca programistom wybieranie wektora (kontenera sekwencyjnego STL) zamiast podstawowej tablicy dla prawie wszystkich zastosowań.

Kontenery sekwencyjne

Kontener sekwencyjny to uporządkowany zbiór danych, w którym są one zwykle przechowywane w sąsiadujących lokalizacjach pamięci. Dostęp do danych w niektórych z tych kontenerów można uzyskać losowo, jednak nie dotyczy to wszystkich kontenerów sekwencyjnych.

Najczęściej używanym kontenerem sekwencyjnym jest klasa vector. Istnieje kilka zalet używania tej klasy w stosunku do podstawowej tablicy, a najważniejszą jest to, że może ona rosnąć i kurczyć się zgodnie z widzimisię programisty. Podstawowe tablice mają stały rozmiar i nie można ich zmienić bez wykonywania kopii lub korzystania z pamięci dynamicznej. Kolejną zaletą klasy vector jest to, że ma ona funkcję size, zwracającą liczbę elementów przechowywanych w wektorze.

Oznacza to, że możesz użyć wektora jako parametru funkcji bez konieczności zmiany jego rozmiaru jako drugiego parametru, jak ma to miejsce w przypadku podstawowych tablic. Te dwie rzeczy sprawiają, że wektor jest wybieranym kontenerem dla większości potrzeb w zakresie sekwencyjnego przechowywania danych.

Kolejnym kontenerem sekwencyjnym jest klasa deque. Działa ona jak tablica dynamiczna, w której można dodawać dane na końcu lub na początku. Oznacza to, że jeśli masz aplikację, w której dane muszą być dodawane zarówno z przodu, jak i z tyłu, to deque może Ci się przydać. Nie warto jej jednak używać, jeśli dane muszą być dodawane do środka. Wymagałoby to niestety przesuwania elementów w górę i w dół, aby zrobić miejsce dla nowych danych. 

STL również posiada klasę array. Klasa ta naśladuje podstawową tablicę, ale jest w niektórych aspektach od niej lepsza. Na przykład, ma ona funkcję size, dzięki której nie trzeba przekazywać tej informacji wraz z tablicą do funkcji tak jak w przypadku podstawowej tablicy.

Klasa list jest kontenerem sekwencyjnym, który zachowuje się, jak lista wiązana. Oznacza to, że list jest dobrym kontenerem, gdy trzeba coś wstawić lub usunąć. Zamiast przesuwania elementów, aby zrobić miejsce na wstawienia lub odzyskania miejsca po usuwaniu, wstawianie lub usuwanie polega wtedy po prostu na ponownym przypisaniu, lub usunięciu linków, które nie są już potrzebne. Klasa list jest podwójnie wiązaną listą, dzięki czemu można ją przewijać do przodu i do tyłu.

Klasa forward_list jest listą jednokierunkową, która umożliwia tylko ruch do przodu. Klasa ta nie ma większego zastosowania, ponieważ nie zapewnia funkcji klasy list, a niektóre funkcje są nieefektywne ze względu na charakter listy jednokierunkowej. Klasy tej można jednak użyć, gdy chcesz szybko przejść od początku do końca listy.

To by było na tyle, jeśli chodzi o kontenery sekwencyjne. 

Kontenery asocjacyjne

Kontener asocjacyjny to taki, który automatycznie sortuje swoje elementy na podstawie pewnego kryterium. Dane przechowywane w kontenerach asocjacyjnych mogą być wartościami dowolnego typu lub parami klucz-wartości dowolnego typu. W przypadku kontenerów z kluczem klucz jest mapowany bezpośrednio do wartości.

Pierwszym kontenerem asocjacyjnym, który omówię, jest klasa set. Set jest kontenerem unikalnych i posortowanych wartości według ich wagi. Zbiory są zazwyczaj uporządkowane według operatora <, co oznacza, że normalnym porządkiem sortowania jest sortowanie rosnące. Próby umieszczenia duplikatów w klasie set zakończą się niepowodzeniem.

Istnieje jeszcze klasa multiset, która zezwala na duplikaty i ma takie samo porządkowanie, jak klasa set.

Klasa map to kontener asocjacyjny, który przechowuje dane w parach klucz-wartość. Kluczem do mapy może być dowolny typ danych, a wartość z nim powiązana również może być dowolna. Instancje klasy map są często nazywane tablicami asocjacyjnymi, ponieważ mapa zachowuje się tak jak tablica z indeksem, który nie musi być liczbą całkowitą. Gdy nazwa mapy jest „indeksowana” kluczem, to zwraca wartość zapisaną za pomocą klucza. Ważną cechą mapy jest to, że duplikaty kluczy są niedozwolone.

Jeśli potrzebujesz kontenera, który zawiera duplikaty kluczy, to użyj klasy multimap. Klasa ta może być używana jako słownik, ponieważ dzięki niemu jedno słowo ma wiele znaczeń. Klasa multimap może mieć ten sam klucz, który będzie powiązany z wieloma wartościami. To tyle, jeśli chodzi o kontenery asocjacyjne. Klasy set oraz map są używane najczęściej, chyba że konieczne jest przechowywanie danych, które nie są unikalne.

Adaptery

Kontener jest adapterem, jeśli dostosowuje ogólny typ kontenera do określonego celu. Klasy kontenerów adaptera to stack, queue i priority_queue. Klasa stack implementuje specjalny kontener, który umożliwia dostęp last-in, first-out (LIFO).

Jest to wymuszane przez interfejs klasy, który ma ograniczoną liczbę funkcji składowych. Nowa wartość danych jest dodawana do stosu za pomocą funkcji push. Dane są usuwane ze stosu za pomocą funkcji pop. Najwyższa wartość stosu jest wyświetlana przy użyciu funkcji top. Jest to jedyny element stosu, który można wyświetlić.

Oprócz kilku innych funkcji pomocniczych to są to jedyne operacje, które można wykonać na stosie. Stosy mają wiele zastosowań w informatyce, np. operacje określania zasięgu w interpretatorach i kompilatorach, a także w innych obszarach, takich jak implementacja arytmetyki odwróconej notacji polskiej.

Klasa queue implementuje kontener, który naśladuje działanie bufora danych lub kolejki w sklepie. Kolejki zezwalają na dostęp first-in, first-out (FIFO). Nowe dane są umieszczane w kolejce za pomocą funkcji push. Front kolejki jest sprawdzany za pomocą funkcji front, a tył jest badany za pomocą funkcji back. Funkcja pop usuwa daną wartość z kolejki. Kolejki mają zastosowania w informatyce (bufory danych) i symulacjach, w których należy modelować zachowanie podobne do kolejki w sklepie.

Klasa priority_queue jest podobna do klasy queue, ale elementy są umieszczane w kolejce priorytetowej na podstawie kryteriów sortowania, które podaje się, gdy kolejka priorytetowa jest zadeklarowana. Jeśli nie podano kryteriów sortowania, to wykorzystuje się operator mniejszości.

Dane są umieszczane w kolejce priorytetowej za pomocą funkcji push, a usuwane za pomocą funkcji pop. Podejrzenie zawartości jest możliwe tylko poprzez funkcję top (która pokaże pierwszy element). Klasycznym przykładem kolejki priorytetowej jest linia na oddziale ratunkowym w szpitalu. Pacjentów ustawia się w kolejce w zależności od powagi ich sytuacji, aby Ci najbardziej chorzy mieli pierwszeństwo. 

Podsumowanie

Nie każda klasyczna struktura danych jest implementowana przez STL. Dostarczane kontenery będą jednak pokrywać większość napotkanych przez Ciebie zastosowań.

Chociaż mogłeś zaimplementować niektóre lub większość tych kontenerów podczas studiów, to zaleca się jednak używanie wersji z STL w każdym programie C++, ponieważ jest ona gwarancją większej wydajności niż cokolwiek, co zbudujesz samemu.

Oryginał tekstu w języku angielskim możesz przeczytać tutaj.