C++ i kontenery danych – omówienie

Opublikowano 25 marca, 20205 lutego, 2024 przez Mateusz Rzeczyca

W poprzednim wpisie z C++ zostały wprowadzone typy danych i została omówiona podstawowa semantyka języka. W dzisiejszym omówię niezwykłe elementy jakimi są kontenery danych. Potrafią niesamowicie uprościć pracę programiście, są proste w obsłudze i każdy szanujący się developer z nich korzysta na bieżąco. Bardzo polecam nauczyć się wspomnianego materiału, ponieważ czy w pracy, czy w pobocznych projektach będziesz korzystał z nich codziennie.

Table of Contents

Biblioteka standardowa

Myślę, że możemy zacząć od wprowadzenia biblioteki standardowej std, która definiuje dwa typy jednostek:

podstawowe funkcje językowe (są to na przykład typy wbudowane jak int, char oraz pętle)
komponenty biblioteki standardowej (kontenery danych, operacje wejścia / wyjścia czy wielowątkowość)

To właśnie w std znajduje się wszystko co potrzebne programiście języka C++. Co niektóre rzeczy są implementowane na wzór biblioteki boost, która posiadała pewne jednostki szybciej i zostało uznane, że C++ potrzebuje takich komponentów w bibliotece standardowej. Język Stroustrupa rozpoczął swój nowy rozdział wraz z aktualizacją C++11, była ona niezwykle ważna. Nie zagłębiajmy się jednak w historię tego języka, gdyż nie jest to tematem wpisu. Przejdźmy do kontenerów.

Kontenery danych

Struktury danych, takie jak tablice, wektory czy słynne łańcuchy znaków są wspomnianymi kontenerami danych. Ich zadaniem jest magazynowanie danych w sposób zorganizowany, pozwalający programiście prostą obsługę elementów. C++ definiuje takie kontenery jak:

std::pair i std::tuple, które są różnorodne, czyli mogą składować elementy różnych typów. Wszystkie pozostałe są jednorodne, ponieważ ich składowe muszą być tego samego typu. Wspomniane dwa typy pozwalają magazynować obiekty (std::pair tylko dwa, std::tuple wiele).
std::array, std::vector , std::list i std::forward_list, które są jednostkami składującymi sekwencje elementów tego samego typu. Warto tutaj wspomnieć, że std::array, std::vector oraz std::tuple są alokowane ciągle / stale.
std::map i std::unordered_map magazynujące pary klucz – wartość.
std::bitset i std::vector<bool> odpowiadające za bity (liczby w formacie binarnym / zero jedynkowym).

Oczywiście jest ich wiele innych, jednak tutaj przedstawione kontenery pozwalają na proste wprowadzenie do zarządzania elementami w C++. Gdy dobrze opanujesz ukazane typy biblioteki standardowej będziesz miał ogromne podstawy do zrozumienia pozostałych. To już jednak pozostawiam Tobie.

std::pair

Żeby móc uruchomić powyższy kod musisz dołączyć bibliotekę utility, w której znajduje się std::pair. Tworzymy parę typów int, int i korzystamy z metody to tworzenie par, inicjalizujemy parę wartościami 10 i 25. Tworzymy wyrażenie lambda, które pobiera istniejący obiekt std::pair oraz za parametr przyjmuje sobie liczbę całkowitą. Zauważ, że poprzez pair.first zwracamy się do 10, pair.second wskazuje na 25. Dodam, że nie wiem czemu w kodzie powyżej [&pair] zmienia się na [&pair].

std::pair<int, int> pair = std::make_pair(10, 25);

auto multiply_pair = [&pair](int x)
{
    return pair.first * pair.second + x; // 10 * 25 + 50
};

std::cout << multiply_pair(50) << '\n';

std::tuple

Na początku definiujemy obiekt element typu std::tuple, którego celem jest składowanie trzech zmiennych int. Korzystamy z kreatora samodzielnie dedukującego typy argumentów. Następnie tworzone jest kolejne wyrażenie lambda, którego celem jest pomnożenie dwóch pierwszych elementów obiektu std::tuple oraz przyjęcie argumentu będącego łańcuchem znaków i wyświetlenie go po operacji mnożenia.

std::tuple<int, int, int> element = std::make_tuple(10, 15, 97);

auto multiply_tuple = [&element](std::string done)
{ 
    int result = std::get<0>(element) * std::get<1>(element);
    std::cout << done << std::endl;
    return result;
};

std::cout << multiply_tuple("Done") << "\n";

Teraz odrobinę trudniejszy przykład. Tworzymy ponownie ten sam obiekt oraz obiekty A, B i C typów kolejno int, std::string i char. Kolejne wyrażenie lambda, które pobiera element i za argument przyjmuje typ std::tuple z łańcuchem znaków na pierwszym miejscu oraz liczbą całkowitą na drugim. Tam wykonujemy operacje mnożenia, tworzymy nowy łańcuch i pobieramy znak w kodzie ASCII. Zwracamy również obiekt std::tuple z nowo wyliczonymi wartościami. Nowością tym razem jest std::tie, którego cel to rozdzielenie zwracanych wartości typu tuple. Zauważ, że wyrażenie lambda zwraca trzy jednostki, które zostają rozdzielone kolejno na A, B i C. Następnym przykładem jest skorzystanie z std::ignore, które pokrótce mówi, zignoruj tern argument, nie chcemy otrzymać wartości w tym miejscu.

std::tuple<int, int, int> element = std::make_tuple(10, 15, 97);
int A;
std::string B;
char C;

auto three_results = [&element](std::tuple<std::string, int> tuple)
{
    int number = std::get<1>(tuple) + std::get<1>(element);
    std::string text = "Mati " + std::get<0>(tuple) + " awesome!";
    char character = static_cast<char>(std::get<2>(element));

    return std::make_tuple(number, text, character);
};

std::tie(A, B, C) = three_results(std::make_tuple("is", 5));
std::cout << A << "\n" << B << "\n" << C << "\n";
std::tie(A, std::ignore, C) = three_results(std::make_tuple("IGNORE IT", 10));

// text doesn't change! It is ignored!
std::cout << A << "\n" << B << "\n" << C << "\n";

Oczywiście nie zapomnij dołączyć pliku nagłówkowego <tuple>.

std::vector

Inicjalizujemy std::vector, który ma składować jednostki o typie int, tworzymy iterator, który ma obsłużyć początek wektora (ve.begin() wskazuje na początku na 1) oraz korzystając z słowa kluczowego auto tworzymy drugi iterator wskazujący na ostatni element wektora. Następnie liczymy odległość między tymi iteratorami przy pomocy metody std::distance. Do wektora możemy zwracać zarówno poprzez nawiasy kwadratowe jak w zwykłych tablicach i poprzez metodę at(). Później są zilustrowane przykłady poruszania się po iteratorach korzystając z std::advance. Ponadto są pokazane metody std::next (która zwraca n-ty iterator) oraz std::prev (robi to samo co std::advance, tylko w tył).

std::vector<int> ve = {1, 2, 3, 4, 5, 6, 7, 8, 9, 11};
std::vector<int>::iterator first = ve.begin();
auto last = ve.end();

int index_first = std::distance(ve.begin(), first); // index = 0 - 0 = 0
int index_last = std::distance(ve.begin(), last); // index = 10 - 0 = 10

std::cout << "Index: ";
std::cout << index_first << " " << index_last << "\n";

// in C++ array starts from 0 so ve[index_last = 10] will return garbage 
// because of that we have to remember about decrementing it by 1
std::cout << "ve[index]: ";
std::cout << ve[index_first] << " " << ve.at(index_last - 1) << "\n";

std::advance(first, 2); // moves iterator by 2 positions forward
index_first = std::distance(ve.begin(), first); // index = 2 - 0
std::advance(last, -2); // moves iterator by 2 positions back
index_last = std::distance(ve.begin(), last); // index = 8 - 0

std::cout << "Index: ";
std::cout << index_first << " " << index_last << "\n" << "ve[index]: "
     << ve[index_first] << " " << ve[index_last] <<"\n";

std::vector<int>::iterator next = std::next(first, 2); // moves iterator by 2 positions forward
index_first = std::distance(ve.begin(), next); // index = 4 - 0
auto prev = std::prev(last, 2); // moves iterator by 2 positions back
index_last = std::distance(ve.begin(), prev); // index = 6 - 0

std::cout << "Index: ";
std::cout << index_first << " " << index_last << "\n" << "ve[index]: "
     << ve[index_first] << " " << ve[index_last] <<"\n";

std::array, std::list i pozostałe „tablice i listy” działają całkiem podobnie, Polecam samodzielnie się doczytać na ich temat i je zaimplementować. Warto jednak omówić kluczowe różnice między nimi:

std::vector jest implementacją tablicy dynamicznej, przechowywanej w stercie, która rośnie i kurczy się automatycznie po dodaniu lub usunięciu elementów.
std::array jest tablicą o rozmiarze statycznym, przechowywaną wewnątrz samego obiektu, co oznacza, że jeśli utworzysz instancję klasy na stosie, sama tablica będzie na stosie (rozmiar tablicy musi być znany w czasie kompilacji).
std::list przechowuje elementy w nieciągłych lokacjach pamięci oraz wykorzystuje podwójne połączenie listy (można iść elementami do przodu i do tyłu).

Żeby skorzystać z wspomnianych kontenerów należy dołączyć pliki nagłówkowe <vector>, <array> lub <list>.

std::map

Obiekt składuje pary klucz – wartość. W tym przypadku kluczem jest std::string, a wartością int. Następnie iterujemy po wszystkich elementach std::map (dzięki zapisowi [key, value] mamy dostęp bezpośrednio do zmiennych).

std::map<std::string, int> map;
map.insert( {"KEY", 17} );
map.insert( {"SECOND", 18} );

for(auto const& [key, value] : map)
    std::cout << "Value for " << key << " is " << value << "\n";

std::unordered_map jest całkiem podobna, jednak różni się w porównaniu do std::map przez rzeczy takie jak:

wewnętrzna implementacja – std::map działa na podstawie binarnego drzewa poszukiwań (ang. binary search tree), natomiast std::unordered_map magazynuje dane w tablicy mieszającej (ang. hash table)
złożoność obliczeniowa – O(n*log(n)) dla std::map (wynika to z założeń BST) oraz dla drugiego kontenera O(n).

Obowiązkowo należy dołączyć nagłówki <map> lub <unordered map>.

std::bitset

Poniżej mamy po prostu trzy przypadki utworzenia łańcuchów bitowych.

std::bitset<8> b1; // [0,0,0,0,0,0,0,0]
std::bitset<8> b2(42); // [0,0,1,0,1,0,1,0]
std::string bit_string = "110010";
std::bitset<8> b3(bit_string); // [0,0,1,1,0,0,1,0]

Klasa zdefiniowana w pliku nagłówkowym <bitset>.

Podsumowanie

W dzisiejszym wpisie udało się nam zrozumieć podstawowe komponenty pracy każdego programisty jakimi są kontenery danych. Zauważyłem, że najczęściej stosowaną strukturą jest std::vector, więc polecam przyłożyć się do tej jednostki oraz oczywiście samodzielnie przekonać się co robi dany kod.

Linki referencyjne:

cppreference

A Tour of C++

map vs unordered_map | When to choose one over another?

std::vector versus std::array in C++