Podręcznik

1. Biblioteka standardowa języka

Współcześnie już mało kto korzysta z czystego języka do pisania rzeczywistych aplikacji - niezależnie od tego jaki język wybierze. Zawsze ma do dyspozycji zestaw pomocniczych bibliotek i dodatków - które albo utworzył samodzielnie, albo utworzył jego zespół, albo - co najbardziej prawdopodobne - korzysta z kodu udostępnianego komercyjnie lub bezpłatnie - przez innych.

Dla C++ opracowano ogromną ilość bibliotek, o różnej jakości, i różnym stopniu skomplikowania. Dla mnie z całego nieprzebranego dobrobytu bibliotek najważniejsze są trzy:

• STL (ang: Standard Template Library) - to biblioteka standardowa języka. Ją głównie zajmiemy się w tym rozdziale.
• Boost - biblioteka, która została opracowana w celu uzupełnienia standardowej biblioteki C++ i rozszerzenia jej funkcjonalności. Boost dostarcza wiele różnych modułów, obejmujących obszary takie jak programowanie generyczne, metaprogramowanie, obsługa wielowątkowości, struktury danych, obsługa sygnałów i wątków, a także wiele innych.
  Najbardziej znanym elementem biblioteki Boost jest Boost.Python, który ułatwia integrację pomiędzy C++ a Pythonem. Inne istotne moduły to Boost.Asio do programowania sieciowego i asynchronicznego, Boost.Test do testowania jednostkowego, Boost.Filesystem do operacji na plikach i katalogach, Boost.Regex do obsługi wyrażeń regularnych, oraz wiele innych.
  Boost jest ceniony za wysoką jakość swojego kodu, a także za to, że wiele propozycji funkcji i rozszerzeń, które później zostały wprowadzone do standardowej biblioteki C++, pierwotnie było testowane w ramach biblioteki Boost. Patrząc na to co jest w Boost - możecie mieć obraz planowanych zmian w bibliotece standardowej.
• Qt - bibliteka zupełnie inna niż STL czy Boost. Po pierwsze - nie jest w ogóle w zakresie standardu języka - wręcz przeciwnie. Wprowadza własny etap metakompilacji, własny system budowania (z którego twórcy powoli się wycofują na rzecz cmake), własne rozszerzenia języka w formie np sygnałów i slotów, czy metadanych obiektu. Ma też wiele komponentów zastępujących / odpowiadających komponentom biblioteki standardowej, często wygodniejszych w użyciu, czasami nawet bardziej efektywnych niż ich standardowe odpowiedniki.
  Qt - podobnie jak C++ i biblioteki standardowe - jest wieloplatformowa. Bezproblemowo wykorzystacie ją do budowy aplikacji dla klasycznych PC (Windows, Linux, iOS), jak i do tworzenia aplikacji mobinych (Android).
  Dla mnie jednak najistotniejszą cechą Qt jest jej przydatność w praktycznym budowaniu aplikacji z graficznym interfejsem użytkownika. IMHO nie ma lepszego narzędzia, jeśli w C++ chcemy zaprogramować osadzony system komunikujący się z użytkownikiem przy pomocy dotykowych ekranów, zachowując przy tym możliwości komunikacji ze światem zewnętrznym zarówno klasycznie (np poprzez sieć TCP/IP), jak i korzystając ze specjalizowanych protokołów (ModBus, OPC, Protobuf) czy nawet bezpośrednio ze sprzętu (Sensors).
  
  Qt w tym podręczniku nie będziemy się specjalne zajmowali - aczkolwiek na koniec modułu zamieszczę Wam przykład wykorzystania Qt do budowy systemu opartego na pluginach.

Teraz zajmijmy się jednak STL. Jest to ogromna biblioteka - wg słów Bjarne Stroustrup-a, specyfikacja STL to 2/3 standardu ISO języka.

Zawartość biblioteki standardowej pierwotnie podzielono na trzy grupy:

• Podstawowe Komponenty: Obejmują one podstawowe aspekty języka, takie jak operacje wejścia/wyjścia (I/O), zarządzanie pamięcią, obsługa błędów, obsługa wyjątków, dynamiczna alokacja pamięci, oraz obsługa niskopoziomowych operacji.
• Struktury Danych: Ta kategoria zawiera różne struktury danych, takie jak wektory, listy, stosy, kolejki, drzewa, mapy, oraz inne. Struktury te dostarczają gotowe implementacje, które programiści mogą wykorzystać bez potrzeby ponownego implementowania podstawowych struktur za każdym razem, kiedy są potrzebne.
• Algorytmy: Zawierają gotowe algorytmy do różnych operacji na danych, takie jak sortowanie, przeszukiwanie, transformacje, oraz inne. Programiści mogą korzystać z tych algorytmów bez konieczności implementacji ich od podstaw, co sprzyja tworzeniu bardziej wydajnego i zrozumiałego kodu.

Z czasem do biblioteki dołączano dodatkowe elementy, takie jak obsługa wątków, wyrażeń regularnych, narzędzia do obliczeń numerycznych (z włączonymi dodatkowo generatorami liczb losowych), obsluga czasu, czy zaawansowane aspekty programowania szablonowego. Ze względu na ograniczony czasowo zakres tego kursu - nie będziemy omawiali wszyskiego. Skupimy się natomiast na najbardziej przydatnych lub najciekawszych elementach biblioteki: kontenerach wraz z iteratorami, podstawowych algorytmach, czy obsłudze wyjątków. Potem opiszę Wam jeszcze przykład budowania aplikacji wielowątkowej.

1.1. Kontenery

W realnym życiu w programowaniu bardzo często naszym zadaniem jest przetworzenie jakichś kolekcji - wartości czy obiektów. Poprzez przetworzenie można zarówno rozumieć ich tworzenie, jak i redukowanie, zmiany, wykonywanie operacji na każdym lub wybranym podzbiorze.

Z drugiej strony - każda kolekcja ma mniej więcej podobny zestaw podstawowych operacji które można na niej wykonać. Można dodać / usunąć elementy, przeszukać ją, czasami zmienić kolejność czy zmienić elementy wchodzące w jej skład.

Skoro funcjonalność kontenera nie zmienia się w zależności od typu przechowywanego elementu, to w języku C++ naturalnym sposobem ich implementacji są szablony. Jednak zastosowanie szablonów wiąże się z określonymi konsekwencjami.

Po pierwsze - kontener jest właścicielem obiektów. W momencie dodawania nowego elementu do kontenera następuje jego kopiowanie, względnie przenoszenie. Zaletą takiego podejścia jest możliwość efektywnego przechowywania każdego typu danych, włączając w to typy proste, oraz brak narzutu pamięciowego.

Natomiast fakt, że kontenery przechowują jednorodne wartości sprawia nam problem gdy w kontenerze chcemy przechowywać obiekty należące do jednej hierarchii klas, ale różnych typów. W tym momencie podanie jako typu konkretyzującego szablon kontenera typu bazowego nie sprawdzi się - w momencie kopiowania zostanie utracona informacja o typie pochodnym.

Ogólnie kontenery w STL są podzielone na dwie główne grupy:

• Kontenery sekwencyjne - w których kolejność elementów jest ustalana przez korzystającego z pojemnika (klienta). Do nich należą m.inn. vector, deque czy list
• Kontenery asocjacyjne - w których klient nie ma kontroli nad kolejnością elementów. Do nich należą set, map, multiset, multimap czy ich wersje nieuporządkonane unordered_...

Zacznijmy od kontenerów sekwencyjnych.

1.2. Kontenery sekwencyjne

Wektor

Wektor jest jednym z najbardziej popularnych kontenerów biblioteki STL - zapewne poprzez fakt, iż bardzo przypomina standardową tablicę. W przypadku wektora elementy mają być przechowywane w jednym spójnym bloku pamięci - podobnie jak standardowa tablica. Rozmiar tej pamięci jest zwiększany w miarę potrzeb - co wiąże się z realokacją (kopiowaniem) całego dotychczas zajmowanego bloku. Dzięki temu wektor ma następujące cechy:

1. Zawartość wektora może być udostępniana bezpośrednio jako wskaźnik. Wystarczy pobrać adres pierwszego elementu - i wektor możemy stosować wszędzie tam, gdzie można było stosować tablice - jest to bardzo przydatne w przypadku konieczności wykorzystywania starych API
2. Wektor praktycznie nie wprowadza narzutu pamięciowego. Rozmiar wektora od rozmiaru sumy jego elementów jest większy jedynie o kilka pól - adres początku, adres pierwszego wolnego miejsca, adres końca obszaru pamięci prealokowanego
3. W wektorze mamy do czynienia z prealokacją pamięci. W praktyce oznacza to, że automatyczne rozszerzanie wektora nie zawsze wiąże się z koniecznością alokacji nowego bloku pamięci i kopiowaniem dotychczasowej zawartości. Zazwyczaj wektor wstępnie rezerwuje miejce na jakąś liczbę elementów, a potem - jak zabraknie miejsca - zwiększa swój rozmiar nie o jeden element, ale np. dwukrotnie. Możemy ręcznie sterować ilością miejsca zarezerwowaną korzystając z metody reserve - tyle że zazwyczaj nie ma takiej potrzeby.
   Wektor oferuje efektywne mechanizmy dostawiania elementów do końca - wydłużania go
4. Operacje wstawiania na początek oraz w środek wektora są czasochłonne. Jeżeli potrzebujecie dostawiać / usuwać elementy na początku i na końcu - stosujcie deque, jesli potrzebujecie częstego wstawiania / usuwania w dowolnym miejscu - lepszym wyborem jest list

Dla wektora (podobnie jak w przypadku wszystkich omawianych kontenerów STL) możemy zdefiniować własny alokator - jednak zazwyczaj nie ma takiej potrzeby. Domyślna wersja alokatora wykorzystuje standardowe new i delete - i w większości zastosowań jest wystarczająca.

Definicja wektora jest podobna do innych zmiennych, przy czym mamy do dyspozycji kilka postaci konstruktora:

// wektor o pięciu elementach inicjowany kolejnymi liczbami całkowitymi
std::vector<int> v1{1, 2, 3, 4, 5};
// wektor na liczby zmiennoprzecinkowe o długości 0
std::vector<double> v2;
// wektor w którym jest 10 pustych napisów
std::vector<std::string> v3{10};
// wektor w którym jest 3 wektory, w których w każdym jest po 4 napisy "aaa"
std::vector<std::vector<std::string>> v4{3, {4, "aaa"}};

W celu uzyskania dostępu do przechowywanych elementów najprościej jest stosować operator []:

for (size_t i=0; i<v1.size(); ++i) {
    std::cout << v1[i] << "\t";
}

Dla tych co wolą jednak być sprawdzani, przewidziano metodę at która kontrolę zakresów przeprowadza. Stosować ją można analogicznie do operatora [] - ponieważ zwraca referencję do przechowywanej wartości:

for (size_t i=0; i<v3.size(); i++) {
    v3.at(i) = std::string("a_")+std::to_string(i+1);
    std::cout << v3.at(i) << "\t";
}

To, że istnieją dwie wersje dostępu indeksowanego do elementów wektora, nie zmienia faktu, iż we współczesnym kodzie zaleca się raczej stosowanie pętli for w wersji zakresowej. Jest to zarówno bezpieczne, jak i efektywne:

for (auto& vi : v4) {
    for (auto& vii : vi) {
        std::cout << vii << "\t";
    }
std::cout << "\n";
}

Lista

Klasa list jest implementacją klasycznej, dwukierunkowej listy. Każdy element takiej listy jest pamiętany w niezależnie alokowanym bloku pamięci, wraz z dwoma adresami - następnego i poprzedniego elementu. Wiąże się z tym zestaw właściwości, które każda lista posiada:

• Przechowywanie tej samej liczby elementów w liście wymaga więcej pamięci, niż przechowywanie ich w wektorze
• Wstawianie i usuwanie elementów w dowolnym miejscu kolekcji jest tak samo efektywne - nie ma problemu z czasem potrzebnym na realokację zasobów.
• Dostęp do elementów jest sekwencyjny. By to podkreślić, twórcy biblioteki standardowej nie zdecydowali się na implementację operatora [] dla listy. Zwyczajowo - listę przeglądamy po kolei. Jeśli do elementów umieszczonych w liście brakuje Wam dostępu swobodnego - zastanówcie się, czy dobrze dobraliście kontener...
• Wstawianie / usuwanie elementów odbywa się przy pomocy iteratorów.

Sposoby inicjacji listy są podobne do sposobów inicjacji wektora. Jeśli chcemy utworzyć listę znaków, i zamieścić na niej 4 litery, to możemy zastosować listę inicjalizatora:

// lista o 4 literach
std::list l1{'a', 'b', 'd', 'e'};

Wydrukowanie zawartości tej listy:

    for (auto li : l1) {
        std::cout << li << "\t";
    }

W przypadku konieczności wstawiania / usuwania elementów z listy - mamy do dyspozycji metody insert oraz erase - tyle że one działają na iteratorach:

    // wyszukanie nieciągłości:
    auto pl = l1.front();
    for (auto it=l1.begin(); it!= l1.end(); it++) {
        if (*it-pl > 1) {
            l1.insert(it, pl+1);
        }
        pl = *it;
    }

insert wstawia element przed elementem wskazywanym przez iterator podany jako argument, erase - usuwa wskazywany element.

Kolejka

Jeśli komuś do końca ani nie odpowiada charakterystyka wektora, ani listy - ma do dyspozycji coś, co jest pomiędzy jednym a drugim rozwiązaniem - deque (ang. double ended queue - kolejka o dwóch końcach). Kolejka - czyli struktura danych gdzie efektywnie można dodawać i usuwać elementy. Przypomina to kolejkę w prawdziwym życiu, w której osoby są usuwane z przodu i dodawane z tyłu. Kolejki dwustronne to szczególny przypadek kolejek, w których operacje wstawiania i usuwania są możliwe na obu końcach.

Dane w deque są pamiętane w wielu ciągłych obszarach (ang. chunk) - ale w każdym obszarze jest więcej niż jeden element. Jak miejsce się kończy - alokowany jest nowy fragment.

Funkcjonalnie te kolejki są podobne do wektorów, ale obsługują wstawianie i usuwanie pierwszego elementu w stałym czasie. Funkcje dla deque są takie same jak w przypadku wektora, z dodatkiem operacji push i pop dla przodu (push_font, pop_front).

Osobiście - często wykorzystuję kolejkę w swoich kodach. Jest wygodniejsza niż wektor, a dodatkowy narzut powodowany przez jej fragmentaryzację zazwyczaj nie jest zauważalny. Jedyne na co trzeba zwracać uwagę - to na brak możliwości stosowania adresu pierwszego elementu tam, gdzie wymagana jest klasyczna tablica C++

1.3. Kontenery asocjacyjne

W przeciwieństwie do kontenerów sekwencyjnych - w przypadku kontenerów asocjacyjnych o kolejności elementów w kontenerze nie decyduje bezpośrednio ich umieszczanie, lecz są one przechowywane w uporządkowanej postaci. To uporządkowanie może być albo oparte o relację między elementami, albo o relację skrótów umieszczonych w kontenerze wartości - ale zawsze jest to jakaś relacja.

Zbiór

Często interesuje nas szybkie wyszukiwanie, pozwalające na sprawdzenie czy dany element już w kolekcji istnieje. Innym spotykanym przypadkiem jest potrzeba przechowywania w kontenerze tylko unikalnych wartości. Odpowiedzią na obie te potrzeby jest kontener o nazwie set

Zbiór wewnętrznie jest pamiętany jako drzewo binarne (zazwyczaj jest to drzewo znane w teorii jako drzewo czerwono/czarne). Dla takiej struktury danych mamy bardzo niski czas wyszukiwania elementu - rzędu O(log n) gdzie n to ilość elementów w kolekcji.

Inicjacja zbioru może odbywać się przy pomocy listy inicjatora podobnej do tej z wektorów, list czy kolejek. Kod do wyświetlania zawartości też będzie podobny.

    // zbiór o czterech elementach inicjowany listą
    std::set<char> s1{'a', 'b', 'd', 'e', 'a'};

    for (auto element: s1) {
        std::cout << element << "\t";
    }
    std::cout << "\n";

W powyższym kodzie uważny czytelnik zauważy jednak różnicę w stosunku do wektorów. Mimo iż podałem listę 5 elementów - po utworzeniu zbiór ma ich tylko 4. Nie można do zbioru dwa razy wstawić 'a' - dlatego jego drugie wstawienie jest ignorowane.

Podobnie działa metoda insert - wstawia do zbioru element jeśli go jeszcze w nim nie ma, i zwraca parę (iterator wskazujący na wstawiony element, true), natomiast jeśli w zbiorze już jest dany element - nie zmienia go, i zwraca parę (iterator na istniejący element, false)

    char zn = 'a' + rand() % ('h' - 'a' + 1);
    if (s1.insert(zn).second)  {
        std::cout << "Nie było jeszcze " << zn << " w zbiorze - ale już jest\n";
    } else {
        std::cout << "Duplikat " << zn  << "\n";
    }

Tą cechę zbioru można uzyskać do poszukiwania unikalnych wartości w innych kontenerach. Wystarczy w takim wypadku skopiować zawartość przeszukiwanego kontenera do zbioru:

    std::vector<int> v1;
    for (int i=0; i < 100; i++)
        v1.emplace_back(rand()%50);
    std::set<int> s2{v1.begin(), v1.end()};
    std::cout << "W wektorze jest " << v1.size() << " elementów, z czegp " << s2.size() << " unikalnych\n";

Jeśli chcemy sprawdzić czy jakiś element jest w zbiorze - korzystamy z metody find:

    if (auto search = s2.find(2); search != s2.end())
        std::cout << "Znaleziono " << (*search) << '\n';
    else
        std::cout << "Nie znaleziono\n";

Ostania istotna cecha set jest powiązana ze sposobem pamiętania elementów. Skoro są one uporządkowane - to pośrednio wynika z tego, iż wartości elementu nie można zmienić. Więc poniższy kod nie zadziała:

    for (auto& element : s2) {
        element += 2;
    }

Słownik

Jeśli przechowywane dane mają postać listy par, z których jeden z elementów możemy traktować jako klucz, a drugi jako wartość skojarzoną z tym kluczem - to mówimy o słowniku. Wyobraźmy sobie problem przechowywania oceny studenta. Możemy wtedy stwierdzić że kluczem jest identyfikator studenta (dla uproszczenia w przykładzie założymy że jest to tekst zawierający nazwisko i imię), a wartością - ocena. Teoretycznie zatem moglibyśmy przygotować strukturę np taką: 

struct SStudentOcena {
   std::string nazwa; 
   double ocena; 
};

i takch studentów przechowywać po prostu w wektorze / kolejce / na liście:

std::vector<SStudentOcena> studenci; 

Potem - jak chcę się odwołać do poszczególnego studenta - to muszę go znaleźć na liście. Problem pojawia się, jak podstawową operacją wykonywaną przez użytkownika jest zmiana / wystawienie oceny poszczególnym studentom. Wtedy powtarzamy nieoptymalne przeszukiwania. Nieoptymalne - bo studenci mogą być umieszczeni w wektorze w kolejności przypadkowej, więc typowa implementacja algorytmu wyszukiwania będzie liniowa - idąc od pierwszego do ostatniego elementu wektora biorę kolejne nazwiska, sprawdzam czy jest to nazwisko którego szukam - i jeśli tak, to mam sukces...

W praktyce jednak w przypadku podobnym do omawianego raczej nie stosuje się losowego ułożenia osób, lecz listy alfabetyczne, i algorytmy wyszukiwania oparte na podziale szukanego zbioru na połowy bazując na relacji większości między poszukiwanym, a środkowym elementem. W STL zaimplementowano to w sposób jeszcze bardziej wyrafinowany. Zauważcie, że takie pary można pamiętać w strukturze podobnej do zbioru - jedynie trzeba zapewnić by do każdego elementu zbioru (klucza) można było "dokleić" ekstra dane (wartość). Taki kontener w STL nazywa się słownikiem (map). W języku polskim wykorzytuje się także określnie tablica asocjacyjna lub po prostu mapa.

Klasa map z biblioteki standardowej jest kontenerem zoptymalizowanym pod kątem przeszukiwania i wstawiania par wartości, z czego klucz musi być unikalny i nie może być zmieniany.

Kolejność elementów w słowniku jest definiowana przez standard języka. Zakłada się, że poszczególne elementy są zawsze ułożnone w kolejności od najmniejszego do największego klucza - wartość nie ma wpływu na położenie. 

Słowniki także można inicjować na wiele sposobów. Naturalnym jest inicjacja poprzez listę inicjacyjną. Dodatkowo - jeśli odwołujemy się do klucza który nie istnieje w danym słowniku - zostanie on do niego dołączony.  Mamy także możliwości kopiowania i przenoszenia innych słowników. Odwoływanie się do elementów mapy odbywa się przez operator indeksowania - gdzie indeksem jest klucz. Przykładowe zastosowanie mapy do pamiętania ocen możecie zobaczyć na poniższym kodzie: 

#include "iostream"
#include "map"

void printStandard17(std::map<std::string, double>& slownik) {
    // odwołanie do zbioru wykorzystując C++17
    for (const auto& [klucz, wartosc] : slownik) {
        std::cout << klucz << " : " << wartosc << std::endl;
    }
}

void printStandard11(std::map<std::string, double>& slownik) {
    // odwołanie starszą, lepiej znaną wersją pętli for C++11
    for (const auto& element : slownik) {
        std::cout << element.first << " : " << element.second << std::endl;
    }
}

int main() {
    // utworzenie i inicjacja 3 wpisami
    std::map<std::string, double> dzienniczek {
            {"Skrzetuski Jan", 4.0},
            {"Wołodyjowski Michał", 3.5},
            {"Kurcewiczówna Helena", 5.0}
    };

    // wydruk
    printStandard17(dzienniczek);

    // dodanie do słownika nowego elementu
    dzienniczek["Zagłoba Onufry"] = 3.0;
    // zmiana istniejącego wspisu
    dzienniczek["Wołodyjowski Michał"] += 0,5;

    // sprawdzenie czy w mapie nie ma określonego klucza
    if (dzienniczek.find("Podbipięta Longin") == dzienniczek.end()) {
        dzienniczek["Podbipięta Longin"] = 3.0;
    }

    // usunięcie klucza z mapy
    dzienniczek.erase("Skrzetuski Jan");

    std::cout << "\nPo zmianach:\n";
    printStandard11(dzienniczek);
    return 0;
}

Inne kontenery asocjacyjne

Oprócz wspomnianego zbioru i słownika mamy jeszcze kilka rzadziej stosowanych kontenerów tego typu:

• multiset - przechowuje posortowane elementy - podobnie jak zbiór. Jednak w przeciwieństwie do zbioru - pozwala na powtarzanie się wartości
• multimap  - podobnie jak słownik przechowuje pary klucz / wartość, przy czym pozwala na powtarzanie się klucza (jednemu kluczowi można przypisać więcej niż jedną wartość
• unordered_set i unordered_map - są to odpowiedniki zbioru i słownika, w których nie układa się elementów korzystając z operatora relacji, lecz wykorzystuje się do tego funkcję skrótu (ang. hash). Wykorzystanie funkcji skrótu pozwala nam na dodatkowe przyspieszenie wyszukiwania w niektórych przypadkach. Dodatkowo - od typu klucza nie wymaga się istnienia funkcji porządkującej (np operatora <) w przypadku tych wersji kontenerów.

2. Współbieżność

Współczesne procesory praktycznie zawsze są wyposażone w więcej niż jedną jednostkę wykonawczą. W takim wypadku – by w pełni wykorzystać moc takiego procesora, przygotowuje się dla niego aplikacje, które mają więcej niż jeden tok wykonania. Takie toki wykonania nazywa się wątkami. Pamiętajcie:

• Każda uruchomiona instancja programu to proces
• Każdy proces ma co najmniej jeden wątek
• Każdy wątek musi być przypisany do jakiegoś procesu

W ogromnym skrócie – różnica pomiędzy wątkiem a procesem polega głównie na dostępie do pamięci. Każdy proces ma przydzielany własny obszar pamięci na stosie i na stercie, który nie jest dostępny dla innych procesów. W przypadku wątków sytuacja jest inna – każdy wątek posiada własny stos, lecz stertę współdzieli z innymi wątkami w ramach tego samego procesu. Skoro współdzieli – to zawsze może pojawić się sytuacja, w której dwa wątki próbują zapisać coś do tego samego obszaru pamięci. Konsekwencje tego – jak się zapewne domyślacie – są tragiczne ... dla programu oczywiście ;>

Język C, oraz C++ w pierwszych wersjach nie wspierały bezpośrednio mechanizmów programowania współbieżnego. Jedyne co mogliśmy - to korzystać z API systemu operacyjnego, i wykonywać współbieżne zadania bez użycia blokad i mechanizmów komunikacji wspieranych przez język.

Od wersji C++11 standardu wprowadzono model pamięci, wątki, mutex-y, zmienne typu conditional variables i inne niskopoziomowe mechanizmy współbieżności. Standard C++14 rozszerza jeszcze tą listę o nowe mechanizmy blokowania, w C++17 wprowadzono mechanizmy umożliwiające równoległe wykonanie wybranych alogrytmów STL.

Następna duża zmiana została wprowadzona wraz ze standardem C++20 - gdzie pojawiły się atomowe inteligentne wskaźniki, obiekty typu future i premise, pakiety zadań, i kilka innych konstrukcji pozwalających na bardziej wysokopoziomową obsługę wielowątkowości znaną z innych języków jak choćby JS czy C#

My w tym podręczniku ograniczymy się jednak do zagadnień niskopoziomowych.

Wątki w C++

To, co na najniższym poziomie podlega zrównoleglaniu - to podprogram, w C++ reprezentowany przez funkcję. Zwyczajowo taką funkcję przeznaczoną do wykonania w innym wątku nazywa się zadaniem.

Sama funkcja może być reprezentowana bezpośrednio (nie ma jakiś specjalnych wymagań odnośnie jej sygnatury, poza faktem, iż nie powinna zwracać bezpośrednio wartości), można też wykorzystać obiekt funkcyjny (funktor). Aby natomiast wykonać ją w niezależnym toku - równolegle z innymi funkcjami w systemie, wykorzystujemy obiekt typu std::thread. Utworzenie tego obiektu pozwala na uruchomienie funkcji lub funktora równolegle do toku funkcji / metody w której został pierwotnie utworzony. Formalnie nie ma wymogu czekania na zakończenie wykonania równolegle utworzonej funkcji - niemniej jednak często chcemy wiedzieć kiedy utworzone wątki się zakończą. By wykryć ten moment wykorzystuje się metodę join.

void fKlasyczna();

class fFunktor {
public:
    void operator()();
};

int main() {
    std::thread watekA{fKlasyczna};
    std::thread watekB{fFunktor()};
    // od tego momentu wątki wykonują się równolegle.

    // jak chcemy na nie poczekać:
    watekA.join();
    watekB.join();

    std::cout << "Zakończono wykonanie obu wątków";

    return 0;
}

Powyższy kod nie pokazuje jeszcze problemów związanych ze współbieżnością - wątki nie korzystają ze wspólnych zasobów (a przynajmniej tego w nich nie widać).

Wystarczy jednak uzupełnić go o dodatkowe elementy związane choćby z drukowaniem na standardowym wyjściu korzystając z cout - który nie jest w pełni zabezpieczony przed wielodostępem. Jedyne co mamy gwarantowane - to fakt że pojedyncza operacja zapisu nie będzie przerwana (jest operacją atomową). Natomiast jeśli zmodyfikujemy powyższy przykład dodając implementację metod:

#include "iostream"
#include "thread"

void fKlasyczna() {
    for (int i{0}; i<100; ++i) {
        std::cout << "Ala " << "ma " << "kota " << "\n";
    }
}

class fFunktor {
public:
    void operator()() {
        for (int i{0}; i<100; ++i) {
            std::cout << "Mateusz " << "uprawia " << "fiołki " << "\n";
        }

    }
};

int main() {
    std::thread watekA{fKlasyczna};
    std::thread watekB{fFunktor()};
    watekA.join();
    watekB.join();
    std::cout << "Zakończono wykonanie obu wątków";
    return 0;
}

Uruchamiając ten kod możecie się dowiedzieć, że Mateusz uprawia kota ... Programując współbieżnie pamiętajcie o tym, by zadania wykonywane równolegle były od siebie kompletnie rozdzielone. A jeśli już muszą się wymienić jakimiś informacjami - to niech to odbywa się pod kontrolą.

Zazwyczaj wywołujemy funkcję w niezależnym wątku w pewnym celu - żeby coś zrobiła, co też zazwyczaj wymaga podania jej pewnych parametrów (argumentów). W przypadku std::thread funkcja przekazana jako argument w konstrukotrze sama może przyjąć dowolną listę argumentów, przekazywanych zarówno poprzez wartość, jak i referencję.

Programując wspólbieżnie staramy się nie przekazywać argumentów przez referencję. W przypadku przekazania przez referencję - nie mamy gwarancji, że przekazane dane są do wyłącznej dyspozycji funkcji (bo ma ona ich kopię) - i inny równolegle wykonywany wątek może także je zmienić. Dlatego też preferuje się przekazywanie przez wartość.

Przygotujmy więc program, który wykorzysta wiele wątków do czegoś innego niż proste uruchamianie funcji. Będziemy chcieli zrobić aplikację, która równolegle w kilku wątkach zsumuje wiersze w dwuwymiarowym wektorze. Przy czym najpierw kod wykonamy sekwencyjnie, potem równolegle, a na koniec porównamy czas w jakim te zadania zostały wykonane.

#include "iostream"
#include "deque"
#include "random"
#include "algorithm"
#include "thread"


/** Metoda wypełnia tablicę przekazaną jej jako parametr liczbami losowymi.
 * Tablica jest wypełniana liczbami losowymi z zakresu 1..100 */
void fillRandmCollection(std::deque<std::deque<double>>& array) {
    std::random_device random_device;
    std::mt19937 random_engine(random_device());
    std::uniform_int_distribution<int> distribution_1_100(1, 100);

    for (auto& row : array) {
        for (auto& elem : row) {
            elem = distribution_1_100(random_engine);
        }
    }
}

/** Metoda sumuje pojedynczy wiersz */
void sortFunction(std::deque<double> array, double *result) {
    *result = 0;
    // celowo robimy przeciągnięte w czasie sumowanie
    for (auto item : array) {
        *result += item;
        std::this_thread::sleep_for(std::chrono::nanoseconds (50));
    }
}

int main() {
    // tablica do posortowania
    std::deque<std::deque<double>> toBeSorted(10, std::deque<double>(10000, 0) );
    // tablica na sumy częściowe
    std::vector<double> results{10, 0.0};
    // losowanie tablicy
    fillRandmCollection(toBeSorted);

    // sumowanie  w jednym wątku
    std::cout << "Sumuję w jednym wątku ... " << std::flush;
    auto tstart = std::chrono::high_resolution_clock::now();
    for (int i=0; i<toBeSorted.size(); ++i) {
        sortFunction(toBeSorted[i], &results[i]);
    }
    auto tstop = std::chrono::high_resolution_clock::now();
    std::cout << " koniec, trwało " << std::chrono::duration_cast<std::chrono::milliseconds>(tstop-tstart).count()/1000.0 << " s\n";

    // sumowanie w wielu wątkach
    std::deque<std::thread> threads;
    std::cout << "Sumuję w wielu wątkach ... " << std::flush;
    tstart = std::chrono::high_resolution_clock::now();
    for (int i=0; i<toBeSorted.size(); ++i) {
        threads.emplace_back(sortFunction, toBeSorted[i], &results[i]);
    }
    for (auto& thread : threads) {
        thread.join();
    }
    tstop = std::chrono::high_resolution_clock::now();
    std::cout << " koniec, trwało " << std::chrono::duration_cast<std::chrono::milliseconds>(tstop-tstart).count()/1000.0 << " s\n";

    return 0;
}

W kodzie powyżej mamy małe oszustwo - sumowanie jest sztucznie przedłużane. Jeśli z tego przedłużania zrezygnujecie - może się okazać, że czas wykonana obu wersji jest podobny. No cóż - pamiętajcie że uruchomienie wątku, a potem końcowa synchronizacja (oczekiwanie na ukończenie) - trwa ... czasem dłużej niż czas który jest potrzebny do wykonania zadania. Nie zawsze wielowątkowość jest najlepszym rozwiązaniem.

2.1. Przekazywanie argumentów i odbieranie wyników

W powyższym przykładzie - parametry do zadania były przekazywane przez wartość - i jest to zalecana metoda. Podobnie w zasadzie był odebrany wynik - przekazaliśmy przez wartość adres w pamięci gdzie należy go umieścić.

W przypadku dużych zbiorów danych przekazywanie przez wartość nie zawsze jednak będzie optymalnym rozwiązaniem. W tym przykladzie z sumowaniem - w klasycznym (nie równoległym) kodzie staralibyśmy się przekazać tablicę do zsumowania przez referencję, by uniknąć jej niepotrzebnego kopiowania. Jeśli jednak zmienimy deklarację funkcji do postaci:

void sortFunction(std::deque<double>& array, double *result)

kod przestanie się kompilować. W przypadku nie stałych referencji C++ wymaga jawnego wywołania std::ref na liście parametrów konstruktora std::thread.

W przypadku odbierania wyniku jest podobnie - jeśli typ argumentu result miałby być referecją do double a nie wskaźnikiem - to powinniśmy przekazać go poprzez std::ref()

Czasem także wynik jest odbierany bezpośrednio w argumencie przekazującym dane wejściowe - jeśli np. naszym zadaniem jest sortowanie wektora. Popatrzmy więc jak nasz przykład mógłby wyglądać jeśli zmienimy sumowanie na sortowanie:

#include "iostream"
#include "sstream"
#include "deque"
#include "random"
#include "algorithm"
#include "thread"

/** Metoda wypełnia tablicę przekazaną jej jako parametr liczbami losowymi.
 * Tablica jest wypełniana liczbami losowymi z zakresu 1..100 */
void fillRandmCollection(std::deque<std::deque<double>>& array) {
    std::random_device random_device;
    std::mt19937 random_engine(random_device());
    std::uniform_int_distribution<int> distribution_1_100(1, 100);

    for (auto& row : array) {
        for (auto& elem : row) {
            elem = distribution_1_100(random_engine);
        }
    }
}

/** Metoda sortuje pojedynczy wiersz */
void sortFunction(std::deque<double>& array) {
    std::sort(array.begin(), array.end(), [](double a, double b) {
        // zasypiamy na chwilę - by sztucznie wydłużyć jej działanie
        std::this_thread::sleep_for(std::chrono::nanoseconds (50));
        return a > b;
    });
}

int main() {
    // tablica do posortowania
    std::deque<std::deque<double>> toBeSorted(10, std::deque<double>(1000, 0) );

    // losowanie tablicy
    fillRandmCollection(toBeSorted);

    // sortowanie  w jednym wątku
    std::cout << "Sortuję w jednym wątku ... " << std::flush;
    auto tstart = std::chrono::high_resolution_clock::now();
    for (int i=0; i<toBeSorted.size(); ++i) {
        sortFunction(toBeSorted[i]);
    }
    auto tstop = std::chrono::high_resolution_clock::now();
    std::cout << " koniec, trwało " << std::chrono::duration_cast<std::chrono::milliseconds>(tstop-tstart).count()/1000.0 << " s\n";

    // sortowanie w wielu wątkach
    fillRandmCollection(toBeSorted);
    std::deque<std::thread> threads;
    std::cout << "Sortuję w wielu wątkach ... " << std::flush;
    tstart = std::chrono::high_resolution_clock::now();
    for (int i=0; i<toBeSorted.size(); ++i) {
        threads.emplace_back(sortFunction, std::ref(toBeSorted[i]));
    }
    for (auto& thread : threads) {
        thread.join();
    }
    tstop = std::chrono::high_resolution_clock::now();
    std::cout << " koniec, trwało " << std::chrono::duration_cast<std::chrono::milliseconds>(tstop-tstart).count()/1000.0 << " s\n";

    return 0;
}

2.2. Blokowanie zasobów

No dobrze - a jakbym chciał wyświetlać postęp sortowania? Dodajmy kod który co N porównań pozwoli na wyświetlenie aktualnej wartości:

...
const int N{1000};
...
/** Metoda sortuje pojedynczy wiersz, drukując co N porównań informację o postępie */
void sortFunction(std::deque<double>& array, const std::string visPrefix) {
    auto callCount{0};
    std::sort(array.begin(), array.end(), [&callCount,  &visPrefix](double a, double b) {
        if (++callCount % N == 0) {
            std::cout << visPrefix << ": " <<  callCount << "\n";
        }
        return a > b;
    });
    std::cout << visPrefix << " skończony po " << callCount << " porównaniach\n" << std::flush;
}

int main() {
    ...
    // sortowanie  w jednym wątku
    for (int i=0; i<toBeSorted.size(); ++i) {
        sortFunction(toBeSorted[i], std::string("Wątek ")+std::to_string(i+1));
    }
    ...
    // sortowanie w wielu wątkach
    for (int i=0; i<toBeSorted.size(); ++i) {
        threads.emplace_back(sortFunction, std::ref(toBeSorted[i]), std::string("Wątek ")+std::to_string(i+1));
    }
    ...
    return 0;
}

Po wprowadzeniu zmian - znów mamy bałagan na konsoli ... mniejszy lub większy - to zależy od Waszego procesora, ale mamy ... Musimy się zabiezpieczyć jakoś przed wielodostępem do strumienia wyjściowego. Podobnie - jeśli oprócz sortowania chcielibyśmy np sumować wszystkie elementy do jednej zmiennej.

Do cełów blokowania zasobów wykorzystuje się tzw. mutex-y (ang. mutual exclusion). Ogólnie - ochronie powinny podlegać wszystkie zasoby które nie są zabezpieczone wewnętrznie przed wielodostępem. A zabezpieczone mogą być na różne sposoby. Zacznijmy od wprowadzenia operacji atomowych

Jeśli taka operacja będzie wykonywać zmianę jakiejś zmiennej - to oznacza że możemy ją bezpiecznie zmieniać z równolegle wykonywanych wątków. W C++ mamy wsparcie dla operacji atomowych w bibliotece standardowej. Jest tam zamieszczony szablon std::atomic który przekształca typ podany tam jako parametr na typ atomowy. Taki typ możemy bezpiecznie zmieniać w różnych wątkach:

#include "atomic"
#include "iostream"
#include "thread"
#include "vector"

std::atomic<int> acnt{0};
int cnt{0};

void f()
{
    for (int n = 0; n < 10000; ++n) {
        ++acnt;
        ++cnt;
    }
}

int main()
{
    std::vector<std::thread> pool;
    for (int n = 0; n < 10; ++n) {
        pool.emplace_back(f);
    }
    for (auto& thr : pool) {
        thr.join();
    }

    std::cout << "Licznik bezpieczny " << acnt << '\n';
    std::cout << "Licznik bez zabezpieczeń " << cnt << '\n';
    return 0;
}

Podejście z bezpośrednim wykorzystaniem szablonu atomic jest zalecane dla typów prostych. Dla skomplikowanych klas lepiej jest zapewnić własną kontrolę dostępu.

Zauważcie, że mając do dyspozycji operacje atomowe - mogę mieć zmienną, dzięki której oznaczam że korzystam z zasobu, i nikt inny nie powinien. Oczywiście tego kodu nie muszę robić sam - już jest dla mnie przygotowany, właśnie w formie mutex-ów. Sam mutex jest tworem, w którym najważniejsze są metody lock i unlock.

• Blokowanie (lock): Wątek wywołujący lock staje się właścicielem blokady. Jeśli inny wątek już posiada blokadę, to wątek wywołujący lock zostanie zablokowany (zostanie wstrzymany tok jego wykonania) do momentu, gdy blokada będzie dostępna.

  
      #include "mutex"
  
      std::mutex myMutex;
  
      // ...
  
      myMutex.lock();  // Blokowanie mutex
      // ... chroniony kod ...
      myMutex.unlock();  // Odblokowywanie mutex
      ```
          

• Odblokowywanie (unlock): Wątek wywołujący unlock zwalnia blokadę, umożliwiając innym wątkom dostęp do chronionego zasobu.

Współpraca z std::mutex może również odbywać się za pomocą bardziej bezpiecznych konstrukcji. Są klasy unique_lock, scoped_lock czy shared_lock które automatycznie zarządzają blokadą i eliminują potrzebę ręcznego wywoływania metod lock i unlock. To pomaga w unikaniu błędów związanych z niedbalstwem w zwalnianiu blokad po zakończeniu operacji chronionej przez mutex.

• std::unique_lock: reprezentuje blokadę, która może być zarówno zablokowana, jak i odblokowana ręcznie. Dodatkowo - pozwala na ręczne zarządzanie blokadą, co jest przydatne w bardziej zaawansowanych scenariuszach, i może być kopiowany. Natomiast jego wadą jest brak możliwości obsługi równoległej wielu blokad w jednym obiekcie. Przykład użycia std::unique_lock:

  
  {
      std::mutex myMutex;
      std::unique_lock<std::mutex> myLock(myMutex);
      // ... kod chroniony blokadą ...
  }
  // myLock jest automatycznie zwalniana po opuszczeniu zakresu
          

• std::scoped_lock to wygodna klasa, która umożliwia blokowanie wielu mutexów jednocześnie w sposób bezpieczny dla nich (eliminuje ryzyko zakleszczenia). Zapewnia automatyczne zarządzanie zajmowaniem i zwalnianiem wszyskich na raz. Natomiast nie daje nam możliwości ręcznego zwalniania, i nie może być kopiowana. Wykorzystuje się ją analogicznie do unique_lock
• std::shared_lock to współpracująca z std::unique_lock klasa, która pozwala na rozróżnienie typ dostępu. Zauważcie, że w przypadku odczytu wielodostęp nie jest problemem - tak więc blokowanie zasobu do odczytu nie ma większego sensu. Natomiast w momencie wystąpienia zapisu - nie powinny trwać ani żadne inne zapisy, ani jakiekolwiek odczyty. Dlatego też jeśli chcemy różnicować dostęp w zależności od tego czy będziemy zasób modyfikowali czy nie - to wykorzystujemy unique_lock przy próbach zapisu, oraz shared_lock przy odczytach. Resztę zrobi za nas kompilator.

Wróćmy zatem do naszego przykładu - zmodyfikujemy przykład, każdorazowo blokując standardowy strumień wyjściowy na czas wykonywania przez dany wątek zapisów.

#include "iostream"
#include "sstream"
#include "deque"
#include "random"
#include "algorithm"
#include "thread"
#include "mutex"

const int N{1000};

std::mutex consoleMx;

/** Metoda wypełnia tablicę przekazaną jej jako parametr liczbami losowymi.
 * Tablica jest wypełniana liczbami losowymi z zakresu 1..100 */
void fillRandmCollection(std::deque<std::deque<double>>& array) {
    std::random_device random_device;
    std::mt19937 random_engine(random_device());
    std::uniform_int_distribution<int> distribution_1_100(1, 100);

    for (auto& row : array) {
        for (auto& elem : row) {
            elem = distribution_1_100(random_engine);
        }
    }
}

/** Metoda sortuje pojedynczy wiersz, drukując co N porównań informację o postępie */
void sortFunction(std::deque<double>& array, const std::string visPrefix) {
    auto callCount{0};
    std::sort(array.begin(), array.end(), [&callCount,  &visPrefix](double a, double b) {
        if (++callCount % N == 0) {
            std::scoped_lock lck{consoleMx};
            std::cout << visPrefix << ": " <<  callCount << "\n";
        }
        return a > b;
    });
    std::scoped_lock lck{consoleMx};
    std::cout << visPrefix << " skończony po " << callCount << " porównaniach\n" << std::flush;
}

int main() {
    // tablica do posortowania
    std::deque<std::deque<double>> toBeSorted(10, std::deque<double>(1000, 0) );

    // losowanie tablicy
    fillRandmCollection(toBeSorted);

    // sortowanie  w jednym wątku
    std::cout << "Sortuję w jednym wątku ... " << std::flush;
    auto tstart = std::chrono::high_resolution_clock::now();
    for (int i=0; i<toBeSorted.size(); ++i) {
        sortFunction(toBeSorted[i], std::string("Wątek ")+std::to_string(i+1));
    }
    auto tstop = std::chrono::high_resolution_clock::now();
    std::cout << " koniec, trwało " << std::chrono::duration_cast<std::chrono::milliseconds>(tstop-tstart).count()/1000.0 << " s\n";

    // sortowanie w wielu wątkach
    fillRandmCollection(toBeSorted);
    std::deque<std::thread> threads;
    std::cout << "Sortuję w wielu wątkach ... " << std::flush;
    tstart = std::chrono::high_resolution_clock::now();
    for (int i=0; i<toBeSorted.size(); ++i) {
        threads.emplace_back(sortFunction, std::ref(toBeSorted[i]), std::string("Wątek ")+std::to_string(i+1));
    }
    for (auto& thread : threads) {
        thread.join();
    }
    tstop = std::chrono::high_resolution_clock::now();
    std::cout << " koniec, trwało " << std::chrono::duration_cast<std::chrono::milliseconds>(tstop-tstart).count()/1000.0 << " s\n";

    return 0;
}

Powyższy kod wreszcie działa zgodnie z oczekiwaniami.