1. Wprowadzenie
Sukces nie jest ostateczny. Porażka nie jest śmiertelna. Tym, co się liczy, jest odwaga, by iść dalej.
Winston Churchill
Książka ta jest wynikiem mojej fascynacji komputerami i programowaniem w języku C++. Jest też rezultatem mojej ponaddwudziestoletniej przygody z nauczaniem podstaw informatyki, a w szczególności języka C++, studentów na Wydziałach Informatyki, Elektroniki i Telekomunikacji, jak również Elektrotechniki, Automatyki, Informatyki i Inżynierii Biomedycznej oraz Inżynierii Mechanicznej i Robotyki Akademii Górniczo-Hutniczej w Krakowie. Pracowałem również w kilku firmach jako programista i konsultant, stając się starszym inżynierem oprogramowania i projektantem oprogramowania. Kierowałem również zespołami programistów i służyłem moim młodszym kolegom jako nauczyciel.
Uczenie się programowania za pomocą języków komputerowych jest i powinno sprawiać frajdę, ale nauczenie się ich dobrze może być trudne. Nauczanie C++ stanowi też znacznie większe wyzwanie niż dekadę temu. Język znacznie się rozrósł i posiadł nowe fascynujące cechy, które chcielibyśmy zrozumieć i wykorzystać w celu zwiększenia naszej produktywności. W chwili, gdy piszę te słowa, najnowszą wersją języka jest C++20. W książce korzystamy z bogatej funkcjonalności C++17, jak również pokazujemy nieco nowych cech C++20. Ponadto w wielu przypadkach dobrze jest także znać przynajmniej niektóre ze starszych konstrukcji, choćby dlatego, że są one wszechobecne w wielu projektach programistycznych, bibliotekach, frameworkach itd. Dla przykładu, pewnego razu pracowałem nad projektem w C++, a dotyczącym przetwarzania strumieni wideo. Modyfikując jedną z wersji bibliotek odpowiedzialnych za wejście/wyjście JPEG, odkryłem tzw. wycieki pamięci. Choć cały projekt napisany był we współczesnym C++, musiałem znaleźć i naprawić błąd w starym kodzie napisanym w C. Znalezienie powodu zajęło mi trochę czasu, ale gdy się udało, usunięcie problemu było już tylko chwilą.
Kolejnym problemem jest to, że kod, jaki spotykamy w czasie naszej codziennej pracy, różni się od tego, czego nauczyliśmy się w trakcie zajęć. Dlaczego? Z wielu powodów. Pierwszym z nich jest pisany latami i często odziedziczony kod. Innymi słowy, znaczy to, że proces pisania ciągnie się bardzo długo. Co więcej, nawet niewielkie projekty mają tendencje do rozrastania się, by po kilku latach osiągnąć często monstrualne rozmiary. Ponadto kod piszą programiści w różnym stopniu zaawansowani w sztuce programowania, a także z różnym doświadczeniem i poczuciem humoru. Na przykład jeden z moich kolegów-programistów zaczynał każdy swój plik z kodem od wiersza. W rezultacie programiści muszą nie tylko rozumieć, utrzymywać i naprawiać błędy w rzeczywistym oprogramowaniu, ale też niekiedy czytać wiersze. Oto, co tworzy rozbieżność między ładnymi, wypolerowanymi fragmentami kodu pokazywanymi na zajęciach a tym, co niesie "samo życie". Tak więc jakie umiejętności są potrzebne, by odnieść sukces w programowaniu?
Dlaczego napisałem tę książkę, skoro istnieje tak wiele stron internetowych, list dyskusyjnych, specjalnych grup zainteresowań, przykładów kodu i dostępnych online książek poświęconych tworzeniu oprogramowania? Choć wszystko to często stanowi wspaniały i wysoce użyteczny, dostępny od ręki punkt odniesienia, niekiedy trudno jest odnaleźć miejsca lub zasoby, które prowadzą nas krok po kroku przez proces uczenia się. Jeszcze trudniej jest odnaleźć dobre przykłady, które uczą kluczowych technik programowania i są jednocześnie krótkie, praktyczne, a zarazem konkretne. Chciałbym więc podzielić się z wami efektami synergii między teoretycznymi opisami popartymi przykładowymi projektami, jakie zebrałem w trakcie moich lat pracy jako programista i wykładowca.
Spójrzmy teraz na krótki, ogólny zarys tematyki tej książki. C++ jest jednym z najbardziej wpływowych, najpowszechniej stosowanych i najbardziej fascynujących języków programowania. Stworzony został przez Bjarne'a Stroustrupa w latach 80. XX wieku. W ciągu ostatniej dekady wprowadzono w nim fundamentalne i szeroko zakrojone zmiany. Korzenie C++ tkwią w językach programowania C oraz Simula (Stroustrup B., Evolving a language 2007) (Stroustrup B., The C++ Programming Language 2013). Jak zobaczymy, podstawowe konstrukcje, takie jak instrukcje i wyrażenia, są w przypadku C oraz C++ niemal takie same. Przez lata kompilatory C++ były też w stanie sprawnie radzić sobie z kodem w C. C jest językiem, który w dużym stopniu wpłynął na naszą techniczną rewolucję, udowadniając, że jest kluczowym narzędziem w tworzeniu bardzo wpływowego systemu operacyjnego Unix, którego następcami są wszystkie inne systemy operacyjne, włączając w to Windowsa, Linuksa i Androida. Za sprawą kompatybilności z wieloma platformami oraz niewielkiemu rozmiarowi kodu wynikowego, C jest nadal używany w systemach wbudowanych, urządzeniach FPGA oraz kartach graficznych (procesorach graficznych, ang. graphics processing unit, w skrócie GPU) oraz do przyspieszenia kodu na platformach równoległych. Istnieje też mnóstwo bibliotek napisanych w C, które nadal są w użyciu, jak te zawierające efektywne algorytmy numeryczne czy te służące do przetwarzania obrazów, by wymienić tylko kilka z nich. Simula był też jednym z pierwszych języków korzystających z klas i przyczynił się do powstania metodyk programowania zorientowanego obiektowo, co stało się kamieniem węgielnym większości przedsięwzięć technologicznych. Tak więc - parafrazując - C++ odziedziczyło coś po obu tych językach: po C publicznie, a po Simuli prywatnie.
Choć istnieje wiele języków programowania, nauczenie się C++ warte jest wysiłku, szczególnie w przypadku tych osób, które planują pracę lub już są zaangażowane w jakiekolwiek przedsięwzięcia programistyczne, w szczególności te dotyczące systemów i wydajności. By zrozumieć najważniejsze cechy C++, wystarczy przeczytać tę książkę; zagłębimy się w nie później. W ramach wprowadzenia przyjrzyjmy się jednak pokrótce tym najbardziej charakterystycznym.
- Wolność dla programistów i bogactwo funkcjonalności - zarówno niskopoziomowe, jak i wysoce abstrakcyjne konstrukcje mogą być wykorzystywane w wielu kontekstach. Tak jak w przypadku szwajcarskiego scyzoryka, istnieje niebezpieczeństwo ich niepoprawnego użycia, ale wolność i bogactwo funkcjonalności prowadzą na najwyższe poziomy produktywności w wielu kontekstach i szerokich zastosowaniach. Co jednak najważniejsze - kochamy wolność.
- Wysoka wydajność - był to zawsze główny cel tego języka. Najważniejsze w tym aspekcie jest to, by móc dostosować wiele programistycznych funkcjonalności do konkretnej potrzeby bez dużego narzutu. C++ został zaprojektowany tak, by spełnić ten wymóg. Można to sparafrazować w następujący sposób: "nie płać za coś, z czego nie korzystasz". Jak zwykle pojawia się jednak cena, którą trzeba zapłacić, taka jak niezainicjalizowane zmienne czy niezwolnione zasoby. Nowe własności współczesnego C++ sprawiają jednak, że problemy te są mniej poważne, pozwalając kodowi napisanemu w C++ nadal plasować się w najwyższej lidze wydajności.
- Systemowe, nisko- i wysokopoziomowe programowanie zorientowane obiektowo (ang. object oriented programming, w skrócie OOP) na tej samej platformie - C++ jest wykorzystywane do implementacji systemów wymagających niskopoziomowego dostępu. W wielu przypadkach język ten wykorzystywany jest do konstruowania pomostów m.in. językami: np. w dziedzinie analiz numerycznych do Fortrana, a w dziedzinie programowania systemów do C lub Assemblera. Ponadto ten sam język jest wykorzystywany do implementacji wysokopoziomowych aplikacji, takich jak edytory tekstu, platformy CAD, bazy danych i gry. C++ to język silnie zorientowany obiektowo (ang. object oriented - OO) spełniający wszystkie paradygmaty tego podejścia, takie jak abstrakcja, enkapsulacja, dziedziczenie, polimorfizm, możliwość przeładowania operatorów itd. Własności te, wzmocnione przez szablony i wzorce projektowe, mocno wspierają tworzenie oprogramowania, w szczególności dla wielkich systemów.
- Silna typizacja języka - każdy obiekt scharakteryzowany jest przez swój typ. Ten silny wymóg dotyczący typu prowadzi do powstania kodu, który jest weryfikowany przez kompilator, a nie przez użytkownika w czasie wykonania, jak dzieje się w przypadku niektórych języków, które nie posiadają tej cechy. Niemniej jednak obiekty mogą zostać przekonwertowane z jednego typu na drugi dzięki wbudowanym lub stworzonym przez użytkownika operatorom konwersji. Relatywnie nowe mechanizmy dedukcji typu ze słowem kluczowym auto znacznie uprościły też użycie typów i zwyczajnie pozwoliły zaoszczędzić nam pisania.
- Obsługa wyjątków - to, jak należy obsłużyć problemy obliczeniowe w trakcie wykonania, zawsze było istotnym pytaniem. Na przykład, co powinno zadziać się w kodzie, jeśli plik z kluczowymi ustawieniami nie może zostać otwarty lub gdy doszło do dzielenia przez zero? Dobry system obsługi wyjątków z wbudowanym mechanizmem odwijania stosu w dużym stopniu ułatwia zarządzanie w takich sytuacjach.
- Wejście i wyjście (IO) - C++ był pierwszym językiem, który pobił swoją konkurencję, wprowadzając jasną, rozszerzalną i wysoce efektywną hierarchię obiektów IO i uzyskał kontrolę nad dziesiątkami stylów formatowania i flag. Cecha ta - choć nie bez pewnych ograniczeń i szczypty krytycyzmu - może zostać wykorzystana do dodania zdolności w zakresie wejście i wyjścia do zdefiniowanych przez użytkownika typów w sposób szybki i elegancki, a wszystko to za pomocą przeładowania operatorów.
- Semantyka przenoszenia - do najważniejszych celów C++ zawsze należała wydajność. Duża liczba przetwarzanych obiektów wpływa na nią negatywnie, zwłaszcza jeśli te obiekty są duże i intensywnie kopiowane. W wielu przypadkach kopiowanie obiektów nie jest jednak konieczne, ponieważ dane mogą być prosto i efektywnie podmieniane. Za wysoce efektywną semantyką przenoszenia (ang. move semantics), dostępną we współczesnym C++, kryje się właśnie mechanizm podmiany danych, co pozwoliło również podnieść jakość generowanego kodu.
- Wyrażenia lambda - ten relatywnie nowy sposób zapisu funkcji przypominających wyrażenia znacznie udoskonalił proces przekazywania wyspecjalizowanych działań lub cech do algorytmów. Wraz ze słowem kluczowym auto, wyrażenia lambda pozwoliły na tworzenie bardziej eleganckiego kodu i zwiększenie produktywności.
- Inteligentne wskaźniki - choć inteligentne wskaźniki (ang. smart pointers) znajdują się wśród dziesiątek konstrukcji programistycznych dostępnych w bibliotece standardowej (ang. Standard Library - w skrócie SL), zmieniły sposób, w jaki C++ obchodzi się z zasobami systemowymi. Przez lata wycieki pamięci (ang. memory leaks), jakie mogłyby z łatwością przydarzyć się w niedbale napisanym kodzie C lub C++, były głównym zarzutem podnoszonym przeciwko C++ w systemach, w których istotny jest wysoki poziom bezpieczeństwa, a także w przypadku programowania rozwiązań sieciowych i internetowych. Inteligentne wskaźniki w sposób robiący wrażenie zmieniły ten obraz - jeśli będziemy ich konsekwentnie używać, mogą zapobiegać wyciekom pamięci bez potrzeby stosowania mechanizmów takich jak odśmiecacze pamięci (ang. garbage collectors), które negatywnie wpływają na wydajność systemu.
- Szablony i programowanie generyczne - zauważono, że gdy powstaje kod ogromnych rozmiarów, wiele struktur i funkcji się powtarza: układ jest niemal taki sam, a zmienia się jedynie kilka typów. Szablony łagodzą problem powtarzania kodu, pozwalając nam pisać funkcje i klasy, w przypadku których konkretne typy i parametry mogą być różne, a podać je trzeba tuż przed utworzeniem instancji takiego konstruktu. Z tego powodu kod stał się bardziej generyczny, ponieważ możliwe jest zakodowanie komponentów, które mogą działać z różnymi typami - nawet tymi, które nie są znane w chwili implementacji komponentu. Dobry przykład stanowi klasa std::vector z SL, reprezentująca dynamicznie rosnącą tablicę obiektów. Jest ona w stanie przechowywać niemal każdy obiekt, który może zostać automatycznie zainicjalizowany.
- Biblioteki - biblioteka standardowa posiada dziesiątki kontenerów danych, algorytmów i podbibliotek powstałych z myślą o wyszukiwaniu z użyciem wyrażeń regularnych, programowaniu równoległym, systemie plików i pomiarze czasu. Istnieją też inne wysoce wydajne biblioteki służące do obliczeń, obróbki grafiki, programowania gier, przetwarzania i rozpoznawania obrazów, uczenia się maszyn i sztucznej inteligencji (ang. Machine Learning & Artificial Intelligence - w skrócie ML/AI), obróbki dźwięku i tworzenia innych programów narzędziowych. Dostęp do tych zasobów często jest otwarty.
- Automatyczne generowanie kodu przez kompilator - jak również tzw. metaprogramowanie, stało się możliwe dzięki niedawno powstałemu mechanizmowi wyrażeń stałych (ang. constant-expression), który pozwala na kompilowanie i wykonywanie fragmentów kodu, w wyniku czego już na tym etapie mogą być wyliczone pewne wartości, które następnie już jako gotowe są wstawiane do docelowego kodu.
- Bogaty zestaw narzędzi programistycznych - chodzi tu o kompilatory (ang. compilers), konsolidatory (ang. linkers), profilery (ang. profilers), generatory projektów (ang. project generators), narzędzia służące do wersjonowania (ang. versioning tools), repozytoria, edytory, platformy IDE (zintegrowane środowiska programistyczne, ang. Integrated Development Environment, w skrócie właśnie IDE), narzędzia służące do analizy kodu, oprogramowanie typu CAD służące do projektowania oprogramowania, i znacznie więcej dodatkowych narzędzi.
Jest to jedynie krótka charakterystyka języka C++. W wielu dyskusjach pada argument, że ceną, jaką płacimy za wszystkie te funkcjonalności, jest złożoność języka, co zarazem sprawia, że krzywa uczenia się jest relatywnie stroma. Być może to prawda, ale pamiętajmy, że nie musimy uczyć się wszystkiego naraz. Parafrazując Oprah Winfrey, poznając własności C++: "Możesz mieć wszystko. Tyle że nie wszystko od razu".
Być może słyszeliście o zasadzie 80/20, zwanej niekiedy regułą Pareto. Dla przykładu, w informatyce mówi ona, że 80% czasu pracy procesora przypada na 20% kodu lub też że 80% błędów spowodowanych jest przez 20% kodu. I tak dalej. Najważniejsze jest tu to, że większość rzeczy w życiu nie jest rozłożona równomiernie i zwykle 20% wysiłków będzie odpowiadać za 80% efektu. W odniesieniu do uczenia się C++, moje wrażenie jest takie, że do pewnego stopnia możemy tu zastosować regułę Pareto. Celem dwóch pierwszych rozdziałów tej książki jest przedstawienie koniecznych podstaw. Ile programów może napisać ktoś, kto posiadł tę wiedzę? Miejmy nadzieję, że wiele. Nie znaczy to jednak, że pozostała część tej książki nie jest ważna. Przeciwnie, wstępne części dają nam solidne podstawy, ale bardziej zaawansowane własności pozwalają nam wrzucić wyższe biegi, których potrzebujemy, by w pełni wykorzystać C++ i stać się zawodowymi projektantami i twórcami oprogramowania. Jak osiągnąć te cele? Tak jak w przypadku wielu innych dyscyplin, odpowiedź brzmi: ćwiczyć, ćwiczyć i jeszcze raz ćwiczyć! Mam nadzieję, że książka ta będzie w tym pomocna. A oto jej krótka charakterystyka.
- Celem tej książki jest zaprezentowanie fundamentów informatyki: elementarnych algorytmów i struktur danych wraz z podstawami współczesnego języka C++. Na przykład różne algorytmy wyszukiwania, mnożenia macierzy, odnajdywania miejsc zerowych funkcji i efektywnego sumowania z kompensacją zostaną przedstawione za pomocą kodu C++. Podstawowe wektorowe i łańcuchowe struktury danych, stosy, listy i drzewa również są opisane za pomocą przykładów napisanych w języku C++.
- Szczególny nacisk położony jest na uczenie się za pomocą przykładów. Dobre przykłady są kluczem do zrozumienia programowania i C++. Do najbardziej interesujących rzeczywistych przypadków dochodzi jednak w skomplikowanym kodzie produkcyjnym, który często zawiera tysiące linii i pisany był przez różne osoby przez lata pracy. Taki kod jest trudny do analizy w książce o ograniczonym rozmiarze i przeznaczonej dla studentów. Tak więc klucz stanowią nietrywialne, praktyczne przykłady kodu, które niekiedy mają swój początek w rzeczywistych projektach i zawsze są napisane tak, by ilustrowały nauczane zagadnienia.
- Co się tyczy stylu, w jakim książka została zredagowana, celem było tu wykorzystanie rysunków, podsumowań i tabel, a nie pisanie całych stron czystego tekstu, choć i tekst jest niemniej ważny do szczegółowego objaśnienia kodu. Tabele zawierające podsumowanie kluczowych zagadnień programistycznych, takich jak instrukcje C++, operatory, biblioteka systemu plików, algorytmy biblioteki standardowej itd., powinny posłużyć jako przydatne "ściągi" w codziennej pracy programistycznej.
- Nacisk położony jest na podstawowe kontenery i algorytmy biblioteki standardowej C++, które zostały opisane wraz z ich powstałymi niedawno implementacjami równoległymi.
- Szczególny nacisk położony jest na zrozumienie odpowiednich etapów tworzenia oprogramowania, zaczynając od analizy problemu przez implementację i testowanie. Ważne jest również zrozumienie oprogramowania w kontekście jego wykonania na współczesnym komputerze. Choć zawsze zaczynamy "od ogółu do szczegółu", to zagadnienia bardziej szczegółowe, takie jak organizacja kodu i danych w pamięci komputera czy wpływ architektur wielordzeniowych procesorów z warstwami pamięci podręcznej (ang. cache memory), również zostały omówione.
- Nacisk położony jest na tworzenie oprogramowania z wykorzystaniem metodologii projektowania zorientowanego obiektowo (ang. object-oriented design, w skrócie OOD) i programowania zorientowanego obiektowo.
- Wyjaśnione i wykorzystane zostały metodologia oraz kluczowe diagramy zunifikowanego języka modelowania UML (ang. Unified Modeling Language, w skrócie właśnie UML).
- Niektóre z najbardziej powszechnych i najbardziej praktycznych wzorców projektowych (ang. design patterns - w skrócie DP), takie jak handle-body i adapter, są przedstawione w ich rzeczywistych zastosowaniach.
- Nie wzbraniamy się przed przedstawianiem starszych technologii i bibliotek, które nadal można napotkać na uniwersyteckich kursach dotyczących systemów operacyjnych lub systemów wbudowanych (ang. embedded systems), a także w starszym kodzie. W tym celu w dodatku zamieszczono wydzieloną sekcję zawierającą krótkie wprowadzenie do języka programowania C oraz dyrektyw preprocesora, jak zawsze wzbogacone o przykłady.
- W osobnym rozdziale przedstawiono wprowadzenie do różnych reprezentacji numerycznych i arytmetyki komputerów. Znaleźć w nim można wstęp do dziedziny obliczeń zmiennoprzecinkowych i algorytmów numerycznych. Informacje te przydadzą się na różnych poziomach uczenia się informatyki.
- Za pomocą przykładów przedstawiony jest również tzw. ekosystem tworzenia oprogramowania. Szczególna uwaga poświęcona jest tu testowaniu oprogramowania oraz praktycznemu wykorzystaniu narzędzi do tworzenia oprogramowania.
- Rozdziały zorganizowane są w taki sposób, by stanowiły odrębną całość i można je było czytać osobno. Zostały też jednak uporządkowane w sposób ułatwiający lekturę całej książki rozdział po rozdziale.
Książka ta powstała z myślą o studentach studiów pierwszego i drugiego stopnia stawiających pierwsze kroki w dziedzinie informatyki i programowania w C++, jak również tych, którzy mają już pewne doświadczenia w programowaniu, a chcieliby poszerzyć swoje umiejętności. Najbardziej przyda się ona na zajęciach z programowania dla studentów elektroniki, informatyki i telekomunikacji oraz pokrewnych dziedzin, takich jak teleinformatyka, inżynieria mechaniczna, mechatronika, robotyka, fizyka, matematyka itd. Książka może też przydać się studentom innych kierunków oraz programistom chcącym podnieść swoje umiejętności w zakresie współczesnego języka C++. Aby wykorzystać tę książkę, trzeba spełnić kilka niewygórowanych warunków wstępnych, a mianowicie:
- Dobrze byłoby mieć za sobą podstawowe wprowadzenie do programowania.
- Przyda się też znajomość matematyki na poziomie szkoły średniej.
Z książki tej można korzystać na wiele sposobów. Jako całość najlepiej pasuje ona do trzech lub czterech semestrów powiązanych ze sobą kursów będących wprowadzeniem do programowania, programowania zorientowanego obiektowo, a w szczególności programowania w języku C++, jak również zajęć z zaawansowanych metod i technik programowania. Można ją wykorzystać w ramach zajęć z systemów operacyjnych oraz programowania systemów wbudowanych. Może też posłużyć jako dodatkowy materiał na zajęciach dotyczących rozpoznawania oraz przetwarzania obrazów. W ten sposób korzystamy z niej w Akademii Górniczo-Hutniczej w Krakowie.
Do każdego rozdziału można też podejść osobno i osobno go przeczytać. A gdy książka posłuży już jako instrukcja, dzięki zawartych w niej licznych podsumowaniach, tabelach, rysunkach i indeksach, można wykorzystać ją jako referencyjny podręcznik dla praktyków i studentów.
1.1. Struktura książki
Diagram na rysunku 1.1 przedstawia sposób organizacji tej książki oraz możliwe ścieżki jej czytania. Poniższa lista przedstawia treść rozdziałów:
Rozdział 2: "Wprowadzenie do programowania" - jest to podstawowe wprowadzenie w dziedzinę programowania. Zaczynamy od przedstawienia modelu sprzętowego, który pomoże zrozumieć, co tak naprawdę robią programy komputerowe. Następnie przejdziemy do kolejnego przedstawienia ekosystemu deweloperskiego C++, kompilatorów dostępnych w internecie oraz zintegrowanego środowiska programistycznego (IDE). Dalej znajdziemy trzy przykładowe projekty koncentrujące się na obliczeniach w pojedynczej funkcji main z bardzo ograniczonym zbiorem instrukcji i operatorów, a także wprowadzenie do wszechobecnych obiektów std::cout oraz std::cin z biblioteki standardowej, reprezentujących - odpowiednio - wyjście na ekran i wejście z klawiatury. W ostatnim przykładzie wprowadzone zostają std::vector oraz std::string, służące do reprezentacji - odpowiednio - tablic dynamicznych i ciągów tekstowych. Zbiór mechanizmów C++ wprowadzonych w tym rozdziale - choć ograniczony - pozwoli nam na napisanie całkiem sporej grupy prostych programów.
Rysunek 1.1. Struktura tej książki pokazana na diagramie stanu w języku UML. Rozdziały 2 i 3 stanowią wprowadzenie do tematu tej książki. Na poziom zaawansowany przechodzimy wraz z rozdziałami 4, 5 i 6. Dalej mamy rozdział 7 poświęcony arytmetyce komputerowej oraz rozdział 8, który traktuje o programowaniu równoległym. Do dodatku można odwołać się z poziomu każdego z wcześniejszych rozdziałów
Rozdział 3: "Podstawy C++" - rozdział ten stanowi zasadnicze wprowadzenie w podstawowe, ale jednocześnie bardzo istotne konstrukcje C++. Najpierw omawiamy wbudowane typy danych oraz metody ich inicjalizacji. Następnie ponownie przyglądamy się std::vector oraz std::string - tym razem bardziej szczegółowo. W kolejnych sekcjach poznajemy słowo kluczowe auto, wprowadzenie do algorytmów, struktur i klas biblioteki standardowej, tablice o stałej wielkości tworzone za pomocą std::array, referencje, wskaźniki, instrukcje, funkcje (włączając w to funkcje lambda), krotki (ang. tuples) i wiązania strukturalne, a także operatory. Wraz z wieloma małymi przykładami przedstawione są trzy relatywnie proste, ale kompletne projekty: reprezentacja macierzy, klasa do reprezentacji trójmianów kwadratowych oraz projekt zawierający dwie niestandardowe klasy służące do reprezentacji i wymiany walut. Celem tych przykładów, tak jak i całego rozdziału, jest nauczenie, w jaki sposób poprawnie tworzyć i korzystać z pojedynczej klasy wraz z jej danymi i funkcjami składowymi (ang. data and function members).
Rozdział 4: "Zgłębianie programowania obiektowego" - rozdział ten pozwala nam opanować średniozaawansowane i zaawansowane techniki C++. Specjalny nacisk położony jest na OOD i OOP. Po omówieniu głównych paradygmatów OOD i OOP przedstawiona jest anatomia klas wraz z zasadami dostępu. Następnie wprowadzone zostaje przeładowanie operatorów (ang. operator overloading), które od razu przećwiczymy na klasie służącej do reprezentacji liczb zespolonych. W dalszej kolejności omówione są specjalne składowe klasy (ang. special class members). Pojawiają się tematy takie jak głębokie i płytkie kopiowanie (ang. deep and shallow copy) czy korzyści, jakie daje semantyka przenoszenia. Dalej znajdujemy wprowadzenie do szablonów (ang. templates) i programowania generycznego (ang. generic programming), jak zawsze wzbogacone o liczne przykłady. Następnie analizujemy relacje między klasami. Zaprezentowane zostają hierarchie klas, a także dynamiczne i statyczne mechanizmy wirtualne (ang. dynamic and static virtual mechanisms). Analizie poddane zostają relacje "has-a" ("posiada") oraz "is-a" ("jest"); nie zabraknie też wskazówek dotyczących tego, kiedy korzystać z której.
Rozdział 5: "Zarządzanie pamięcią" - ta część poświęcona jest różnym aspektom czasu życia obiektu oraz jego zakresowi, jak również tworzeniu i pozbywaniu się obiektów oraz dostępowi do nich. Znaczna większość tego rozdziału poświęcona jest sprytnym (inteligentnym) wskaźnikom (ang. smart pointers). Przedstawione są przykłady kodu pozwalającego na skonstruowanie listy za pomocą wspólnych sprytnych wskaźników, a także wzorzec projektowy fabryka (ang. factory design pattern).
Rozdział 6: "Zaawansowane programowanie obiektowe" - rozdział ten przedstawia kilka dodatkowych, bardzo praktycznych technik i metod programistycznych. Celem jest tu przećwiczenie metod przedstawionych w poprzednich rozdziałach, a także zaznajomienie się z obiektami funkcyjnymi, dopasowywaniem ciągów z wykorzystaniem wyrażeń regularnych, implementacja maszyny stanów oraz wzorca projektowego handle-body. Omówione są zagadnienia takie jak system plików, zegar systemowy i pomiar czasu, zakresy oraz interfejs użytkownika. Zaprezentowane są również takie techniki programistyczne, jak parsowanie wyrażeń, budowanie drzewa, przechodzenie przy użyciu wzorca projektowego wizytatora (ang. visitor design pattern; wzorzec ten występuje także pod nazwą "odwiedzający"), jak również interpretowanie wyrażeń za pomocą wzorca projektowego interpretera (ang. interpreter design pattern).
Rozdział 7: "Arytmetyka komputerowa" - rozdział ten jest podzielony na dwie części, poświęcone odpowiednio liczbom stało- i zmiennoprzecinkowym. Rozpoczyna się on od bardzo podstawowych informacji dotyczących arytmetyki komputerowej, takich jak interpretacja bajtów, systemy konwersji itd. Można więc korzystać z niego w charakterze lekcji wprowadzającej następującej po rozdziale 2. Znaleźć w nim można jednak znacznie więcej niż proste obliczenia. Zagłębimy się w ważne kwestie, takie jak błędy zaokrąglenia, utrata cyfr znaczących oraz standard operacji na liczbach zmiennoprzecinkowych IEEE 754. Zbadamy również kilka zaawansowanych technik programistycznych, np. kiedy kompilator może generować kod w trakcie kompilacji albo jak obliczyć aproksymacje funkcji i jak poprawnie sumować bufory w przypadku wielkich danych.
Rozdział 8: "Podstawy programowania równoległego" - ta część stanowi wprowadzenie w dziedzinę obliczeń równoległych. Po pierwsze, wyjaśnione są tu nowe zjawiska spowodowane zbieżnym, jednoczesnym działaniem wielu rdzeni mikroprocesora, jak również jednoczesnym dostępem do wspólnych obiektów. Następnie przedstawione i przetestowane są trzy nowe komponenty oprogramowania służące do obliczeń równoległych. Najprostszy wywołuje zrównoleglone wersje algorytmów z biblioteki standardowej. C++ zawiera jednak osobną bibliotekę pozwalającą na prowadzenie obliczeń równoległych - w odniesieniu do niej zaprezentowane są zadania asynchroniczne. Ostatnim z omawianych komponentów jest biblioteka OpenMP. Za jej pomocą przetestujemy, w jaki sposób można napisać zrównoleglone sekcje, jak zrównoleglić pętle i w jaki sposób mierzyć czas wykonania z wykorzystaniem przykładów z mnożeniem macierzy.
Dodatek - w tej części przedstawione zostały różnorakie zagadnienia programistyczne. Zaczynamy od krótkiego przedstawienia preprocesora, po którym następuje zwięzłe wprowadzenie do języka C. Mimo iż do nauki języka C++ uprzednia znajomość C nie jest konieczna, pozwala ona jednak zrozumieć jego niektóre własności. Na przykład parametry funkcji main, proste tablice, unie i reprezentacje łańcuchów w wersji języka C spotykamy na co dzień. Przedstawione zostaną również inne zagadnienia, takie jak konsolidacja oraz binarna organizacja programów napisanych w C/C++, graficzne interfejsy użytkownika (ang. graphical user interface - skrót GUI) dostępne dla programów w C++, metody testowania oprogramowania oraz zestaw narzędzi programistycznych składający się z CMake, Gita i GitHuba oraz Profilera.
Jak już wspomniałem, książka ta nie musi być czytana liniowo. Rozdziały zostały zorganizowane w sposób ułatwiający ich osobny użytek. Dodatek do książki, podobnie jak wiele podsumowań i referencji, może być również wykorzystany niezależnie, w ramach prac nad projektami programistycznymi.
Dodatkowo ważne jest, by zdać sobie sprawę, że przedstawienie bardzo szczegółowych zagadnień programistycznych w sposób liniowy jest w zasadzie niemożliwe. Tak więc zrozumienie niektórych konstrukcji wykorzystanych w danym kontekście może nie być łatwe przy pierwszej lekturze, ale zostają one wyjaśnione w dalszych częściach książki.
1.2. Konwencje formatowania
Aby ułatwić poruszanie się po książce, przyjęto w niej kilka różnych sposobów formatowania. I tak:
- Wypunktowania wykorzystywane są na początku i na końcu niektórych podrozdziałów, by przedstawić wprowadzane w nich kluczowe konstrukcje i/lub technologie.
- Kod w C++ napisany jest przy użyciu koloru podkreślającego różne kategorie językowe. Jest umieszczony na jasnoniebieskim tle, a jego wiersze zostały ponumerowane, tak jak w poniższym przykładzie.
Listing 1.1. Przykład przyjętego w książce formatowania kodu C++ (z pliku main.cpp)
Wyjście w oknie terminala (zwanego także konsolą lub wierszem poleceń) jest również przedstawione na kolorowym tle, w następujący sposób:
Kod na białym tle to albo starszy kod napisany w C, tak jak ten przedstawiony w dodatku A.2, lub kod, którego wykorzystanie w C++ z jakichś powodów nie jest rekomendowane, ale który został przedstawiony jako element wyjaśnienia jakiegoś zjawiska. W ten sposób możemy łatwo odróżnić te dwa typy kodu.
Na początku każdego fragmentu kodu znajduje się nagłówek, taki jak "Listing 1.1" w powyższym przykładzie. Opisuje on intencję kryjącą się za danym fragmentem kodu oraz - jeśli kod pochodzi z jednego z projektowych plików - zawiera w nawiasie zapisaną kursywą nazwę pliku zawierającego ten kod, np. main.cpp. Dla zwiększenia czytelności długie fragmenty kodu są często dzielone na kilka krótszych. W takich przypadkach nagłówek pojawia się tylko raz, powyżej pierwszego fragmentu, a numeracja wierszy zachowuje ciągłość do końca całego bloku kodu.
- W większości listingów kodu wiersze zostały ponumerowane. Odniesienia do tych numerów linii tworzone są przy użyciu nawiasów kwadratowych []. Na przykład w listingu 1.1 standardowy nagłówek iostream dołączony jest w wierszu [1], funkcja main jest zdefiniowana w wierszach [3-8], a wiersze [5, 6] zawierają komentarze, które w języku C++ rozpoczynają się od podwójnego ukośnika //. Aby zwrócić uwagę na istotność komentarzy, oznaczone są one kolorem czerwonym.
- Kod taki jak std::cout, który reprezentuje obiekt ekranu, zapisany jest za pomocą specjalnej czcionki o stałej szerokości. Z kolei nazwy plików - takie jak iostream i main.cpp - zapisane są czcionką pochyłą.
- Przedstawionych jest wiele funkcji i obiektów należących do biblioteki standardowej. Jak widzieliśmy, można je łatwo odróżnić dzięki prefiksowi std::. Prefiks ten można jednak pominąć, jak w przypadku endl, jeśli dyrektywa using std::endl (co znaczy "end-of-line", czyli "koniec wiersza") jest umieszczona na górze kodu. Stąd w przedstawionym kodzie wykorzystane są dwie wersje - w zależności od kontekstu, ale i od ilości dostępnego miejsca.
- Istnieją dwa rodzaje podrozdziałów:
- przedstawiające nowy materiał,
- przedstawiające przykładowe projekty, zbudowane wokół samodzielnych projektów w celu przećwiczenia konkretnych technik programistycznych.
- Podrozdziały zawierające dodatkowy lub zaawansowany materiał, których natychmiastowa lektura nie jest konieczna w bieżącym kontekście przedstawionego materiału, są oznaczone za pomocą znaczka .
- Końcowe fragmenty podrozdziału zawierające ważny materiał często zawierają listę rzeczy "Do zapamiętania", np.:
Do zapamiętania
- Preferuj łatwe do odczytania nazwy dla funkcji i obiektów.
- W kodzie dodawaj znaczące komentarze kładące nacisk na istotę rozwiązania.
W celu reprezentacji algorytmów za pomocą pseudokodu wykorzystywany jest następujący format:
Algorytm 1.1. Przykładowy algorytm w pseudokodzie
Wejście:
Wartość x
Wyjście:
Kwadrat z x
1
Ustaw limit:
t ? 1e-10
2
...
- Istnieją dwa rodzaje odnośników:
- Twarde odnośniki do książek, artykułów pokonferencyjnych, artykułów w czasopismach oraz witryn internetowych, np. (Stroustrup B., The C++ Programming Language 2013; Cppreference.com 2018).
- Miękkie odnośniki (najczęściej linki do stron w sieci), umieszczone w stopce.
- Rozdziały kończą sekcje "Pytań i odpowiedzi", które zwykle poszerzają informacje na temat przedstawionych technik.
- Jeśli wzmiankowane są specjalne kombinacje klawiszy, są one oznaczone w rozpoznawalny sposób, tak jak w przypadku kombinacji Ctrl+Alt+T (która w Linuksie otwiera okno terminala).
1.3. O kodzie i projektach
Jak napomknąłem wcześniej, książka zawiera dziesiątki fragmentów przykładowego kodu. Proces uczenia się polega między innymi na własnoręcznym uruchomieniu tego kodu oraz zrozumieniu, jak on działa. Pora więc na kilka wskazówek dotyczących tego, jak korzystać z kodu:
- Cały kod dostępny jest w sieci w repozytorium GitHub (https://github.com/BogCyg/BookCpp_PL). Krótkie wprowadzenie do GitHuba znajduje się w podrozdziale A.6.2.
- Choć kod ten można łatwo skopiować, skompilować i wykonać, najlepszym sposobem na wyrobienie sobie umiejętności programistycznych jest samodzielne pisanie kodu. Może to polegać na jego prostym przepisywaniu lub - jeszcze lepiej - próbie napisania własnej wersji kodu po tym, jak już zrozumie się jego zasadniczą ideę. Gdy nam się to uda, spróbujmy go uruchomić, a jeśli nie jesteśmy czegoś pewni, sprawdźmy przykład z książki. Następnie możemy poprawić nasze rozwiązanie i spróbować ponownie.
- Najszybszym sposobem na skompilowanie kodu i sprawdzenie, co takiego robi, jest jego skopiowanie (ale jedynie kodu, a nie znaków formatowania czy numerów wierszy) do jednego z systemów pozwalających na kompilację online, o których więcej można przeczytać w podrozdziale 2.4.2. Sprawdzi się to dobrze, ale jedynie w przypadku relatywnie niewielkich projektów - platformy dostępne w sieci mają pewne ograniczenia, jeśli chodzi o działania w zakresie wejścia i wyjścia, np. zapisu do pliku.
- W przypadku większych projektów rekomendowane podejście polega na samodzielnym budowaniu projektu na swoim komputerze za pomocą własnych narzędzi programistycznych. By to zrobić, potrzebne są dwie rzeczy: w miarę aktualna wersja środowiska C++, takiego jak jakieś IDE, tak jak przedstawione zostało to w podrozdziałach 2.4 i 2.5, oraz narzędzie CMake, które zostało opisane w dodatku w podrozdziale A.6.1. Choć projekty mogą zostać zbudowane lokalnie jedynie przy użyciu IDE, CMake znacznie ułatwia ten proces, uwzględniając wiele systemów operacyjnych, platform programistycznych, narzędzi, wersji źródeł etc. Jest to również rzeczywisty standard branżowy, który dobrze jest znać. Co więcej, niektóre IDE zawierają już CMake.
- Ponieważ oprogramowanie stale ewoluuje, mogą pojawić się różnice między kodem w książce i kodem w repozytorium. Tak więc w celu wyjaśnienia technik programistycznych i własności C++, punkt odniesienia powinien stanowić kod z książki. Jednak aby zbudować aktualną wersję projektu, należy korzystać z kodu z repozytorium.
Współczesne kompilatory C++ to prawdziwe dzieła sztuki. Na przykład przed skonstruowaniem kompletnej postaci wykonywalnej współczesny kompilator może nawet dokonać prekompilacji fragmentów kodu, a te z kolei mogą następnie od razu zostać wykonane przez kompilator, aby obliczyć rezultaty osiągalne na tym etapie, które następnie można bezpośrednio umieścić w ostatecznym kodzie, tak by uniknąć obliczeń w czasie wykonania. Omówimy również, jak czerpać korzyści z tych funkcjonalności. Jeśli jednak coś jest nie tak i kod się nie skompiluje, niekiedy niełatwo jest ustalić przyczynę takiego stanu rzeczy oraz - co ważniejsze - w jaki sposób rozwiązać ten problem. Kompilator próbuje powiedzieć nam, co dokładnie jest nie tak, ale ponieważ błędy mogą pojawić się wszędzie i na różnych poziomach, komunikat o błędzie może stanowić prawdziwą zagadkę. Kompilatory nadal nie są w stanie powiedzieć nam, co dokładnie powinniśmy zrobić, by wykaraskać się z kłopotów. Być może sztuczna inteligencja da nam tu nowe możliwości. Na tę chwilę dostępne są takie funkcjonalności jak np. koncepty w C++20. Jak zawsze, nieco doświadczenia oraz kontakty z ogólnoświatową społecznością programistyczną to najważniejsze z zasobów, które mogą nam pomóc.
No więc, co powinniśmy zrobić, gdy kod się nie kompiluje? Oto kilka wskazówek dla początkujących:
- Po pierwsze, nie piszmy długich fragmentów kodu bez sprawdzania, czy się kompilują. Znacznie lepsze podejście polega na zorganizowaniu kodu - o ile to możliwe - na sposób nieco nieliniowy: np. najpierw piszemy pustą funkcję i podajemy jedynie jej parametry, a następnie kompilujemy. Po drugie, dopisujemy kilka linii - również nieliniowo, np. pustą pętlę - i sprawdzamy, czy się kompiluje. Dodajemy więcej linii, kompilujemy itd. Na każdym etapie sprawdzamy, czy pojawiły się błędy. Jeśli tak, modyfikujemy kod w taki sposób, by się kompilował.
- Gdy natrafiamy na błąd kompilacji (lub konsolidacji), powinniśmy zawsze przewinąć okno z błędami na samą górę i sprawdzić pierwszy wiersz. Pozostałe błędy często są jedynie wynikiem tego, że kompilator potknął się na tym pierwszym.
- Starannie czytajmy każdy komunikat o błędzie. Jeśli to konieczne, skopiujmy go do edytora i podzielmy na części, co ułatwi nam jego lepsze zrozumienie. Wiadomości o błędach zawierają kody, dzięki którym możemy sprawdzić informacje na temat tych błędów w Internecie. Dla przykładu, komunikat o błędzie może wyglądać następująco: "error C2628: 'MonthDays' followed by 'void' is illegal (did you forget a ';'?)". No tak, rzeczywiście brakuje średnika ; tuż po definicji struktury MonthDays. Dodanie go w tym przypadku załatwia problem. Ten przypadek był jednak dosyć prosty.
- Niekiedy przyczyną błędu jest litera, wiersz, funkcja itd. znajdujące się kilka linii przed błędnym wierszem wskazanym przez kompilator. Jeśli utkniemy na jakimś błędzie, spróbujmy zweryfikować kilka wierszy znajdujących się przed wskazanym miejscem.
- Poszukajmy wskazówek w Internecie. Witryny takie jak http://stackoverflow.com, http://codeguru.com itp. zawierają wiele praktycznych porad udzielonych przez wytrawnych programistów. Zawsze jednak sprawdzajmy datę danego posta - w sieci znajduje się też mnóstwo informacji nie pierwszej świeżości!
- Jeśli fragment kodu uporczywie się nie kompiluje i nie mamy pojęcia, co jest grane, dezaktywujmy go na jakiś czas. Można to zrobić, ujmując go w komentarz, czyli umieszczając // na początku wiersza lub zamykając go w obrębie instrukcji #if 0 tymczasowo_dezaktywowany_kod #endif. Jeśli reszta się kompiluje, spróbujmy zawęzić dezaktywowany obszar i sprawdźmy ponownie.
- Kod można napisać na wiele sposobów. Istnieje np. wiele rodzajów pętli, a instrukcja switch-case może zostać napisana przy użyciu if-else itd. Nie porzucajmy jednak kodu, który się nie kompiluje, nim nie znajdziemy i nie zrozumiemy, dlaczego tak się dzieje. Może to zająć trochę czasu, ale w ten sposób nauczymy się czegoś i unikniemy straty czasu w przyszłości, gdy napotkamy podobny problem. Jedynie gdy już zrozumiemy, co zrobiliśmy źle, powinniśmy rozważyć użycie innej lub lepszej konstrukcji językowej.
- I rzecz ostatnia, ale nie mniej ważna: prośmy o konsultację inne osoby na uczelni lub w miejscu pracy albo pytajmy naszych nauczycieli - wysyłajmy im e-maile, prośmy o radę itd. Zawsze dobrze jest rozmawiać.
2. Wprowadzenie do programowania
Aby stworzyć program komputerowy mający wykonywać dane zadanie, musimy wyspecyfikować działania, jakie komputer musi dla nas wykonać. Wiedza ta bierze się z analizy problemu, która niekiedy stanowi najtrudniejszy etap procesu tworzenia oprogramowania. Gdy wiadomo już, o jakie działania chodzi, trzeba zapisać je w takiej postaci, którą komputer - to znaczy procesor - potrafi zrozumieć. Choć każdy procesor mówi w swoim własnym języku, zwanym assembly czy też językiem albo kodem maszynowym, jest on zbyt prymitywny, by ludzie mogli w nim efektywnie kodować. Zamiast niego powstało w tym celu wiele wysokopoziomowych języków komputerowych. C++ jest jednym z nich. Jest on dobrze znany, dysponuje najlepszymi możliwymi narzędziami i bibliotekami oraz znaczącym wsparciem ze strony zgromadzonej wokół niego społeczności posiadającej lata doświadczeń w programowaniu w tym języku.
C++ posiada setki własności, które można na różne sposoby wykorzystać, aby przełożyć nasze oczekiwania na ich optymalną reprezentację zrozumiałą dla komputera. Poznawanie własności C++ jest interesującym przedsięwzięciem, ale bywa też czasochłonne. Skupimy się więc na wybranych obszarach C++, ale takich, które pozwolą nam na napisanie bardzo wielu programów.
Rozdział ten stanowi wprowadzenie do programowania w C++. Na początek omówimy ekosystemy sprzętu i oprogramowania. Ściślej mówiąc, przedstawimy modele obliczeniowe stanowiące podstawę umożliwiającą zrozumienie, w jaki sposób działa oprogramowanie i na czym polega proces jego tworzenia.
2.1. Model sprzętowy
Komputery to wysoce zintegrowane, ale i skomplikowane systemy, składające się z dziesiątek chipów, z których każdy składa się z tysięcy tranzystorów itd. Modelowanie - czyli tworzenie modeli - to proces upraszczania rzeczywistości w celu uwydatnienia niektórych z jej najważniejszych własności, koniecznych do wyjaśnienia fragmentu tej rzeczywistości. Rysunek 2.1 przedstawia model obliczeniowy systemu komputerowego wyposażonego w wielordzeniowy procesor, pamięć główną, chipset, a także pewną liczbę podłączonych do niego urządzeń zewnętrznych, takich jak klawiatura, monitor, dyski czy urządzenia sieciowe.
Centralna część składa się z procesora posiadającego pewną liczbę rdzeni, które same w sobie stanowią niezależne jednostki obliczeniowe. Najważniejszym modułem zewnętrznym jest pamięć główna, która mieści zarówno kod, jak i dane. Taki sposób ich zorganizowania naśladuje powszechnie uznaną architekturę von Neumanna.
Poza procesorem głównym, obliczeń mogą też dokonywać rdzenie procesora graficznego (GPU), który również wyposażony jest w swoją własną pamięć. Choć nie będziemy bezpośrednio odnosić się do tej platformy w naszych programistycznych ćwiczeniach, dobrze wiedzieć, że jej rodzimymi językami programowania są C oraz C++.
Rysunek 2.1. Model systemu komputerowego. Centralny element składa się z procesora wyposażonego w określoną liczbę rdzeni będących niezależnymi jednostkami obliczeniowymi. Procesor wspomagany jest zwykle przez chipset systemowy, który pełni rolę pośrednika między procesorem a różnymi modułami zewnętrznymi. Najważniejszym z nich jest pamięć główna, która zawiera kod i dane. Obok procesora głównego i jego rdzeni, obliczeń można też dokonywać na rdzeniach procesora graficznego (GPU)
Rysunek 2.2. przedstawia model wielordzeniowego procesora wyposażonego w różne typy pamięci. Wielordzeniowy procesor wyposażony jest w szereg pamięci podręcznych będących częścią układu. Posiada również dołączony moduł zewnętrznej pamięci głównej. Wyjaśnimy teraz funkcjonowanie tych komponentów sprzętowych z perspektywy obliczeniowej.
Jednostka arytmetyczno-logiczna (ang. arithmetic logic unit, w skrócie ALU) stanowi serce każdego rdzenia i odpowiada za wykonanie podstawowych, niskopoziomowych operacji. Te mają postać zakodowanych w postaci binarnej poleceń przechowywanych w pamięci, które po zdekodowaniu mówią ALU, co należy zrobić - np. z wartościami przechowywanymi w innych obszarach pamięci. Polecenia te są w zakodowanej postaci, zwanej językiem maszynowym, i nie są łatwe do odczytania przez człowieka. Mogą być reprezentowane w równoważnym języku assembly, który człowiek jest w stanie zrozumieć, a nawet - w rzadkich przypadkach - wykorzystać do napisania oprogramowania. Każdy procesor posiada jednak swój własny język maszynowy, tak więc pisanie w języku assembly jest uciążliwe, podatne na błędy i w dużym stopniu zależne od sprzętu. Na szczęście w dzisiejszych czasach możemy uniknąć tych niedogodności dzięki wsparciu ze strony wysokopoziomowych języków takich jak C++. Dużo łatwiej zrozumieć je ludziom, a dodatkowo są one niezależne od procesorów i systemów operacyjnych. Dodatkowo kod napisany za ich pomocą może łatwo zostać przetłumaczony na niemal każdą znaną reprezentację maszynową za pomocą kompilatora.
Jak widać na rysunku 2.2, ALU ma zwykle dostęp do wybranych rejestrów rdzenia. W zależności od procesora jest to kilka lokalizacji w wewnętrznej pamięci rdzenia, które mogą przechowywać tylko bardzo ograniczoną liczbę słów komputerowych, w większości przeznaczonych dla operacji ALU. Poza tymi uniwersalnymi rejestrami istnieją też dwa specjalne: PC (ang. program counter, czyli licznik programu), wskazujący aktualną pozycję wykonywanego kodu, oraz SP (ang. stack pointer, czyli wskaźnik stosu), wskazujący obszar pamięci zewnętrznej zwany stosem, który zawiera adresy procedur, a niekiedy parametry wywołania (zob. podrozdział 3.14.3). Rysunek 2.2 pokazuje również dwie specyficzne flagi: flagę zero (Z) oraz flagę przeniesienia (C). W praktyce są to dwie spośród wielu flag, zwykle zakodowanych jako określone bity w jednym z rejestrów kontrolnych. Wyróżniliśmy je, ponieważ pomagają zrozumieć pewne operacje numeryczne omawiane w rozdziale 7.
Rysunek 2.2. Model wielordzeniowego procesora z różnymi typami pamięci. Jednostka arytmetyczno-logiczna (ALU) wykonuje niskopoziomowe operacje maszynowe. Najbliższy obszar pamięci składa się z rejestrów. Poza rejestrami uniwersalnymi istnieją dwa specyficzne: PC (ang. program counter, czyli licznik programu wskazujący bieżącą pozycję wykonywanego kodu) oraz SP (ang. stack pointer, czyli wskaźnik stosu, który wskazuje na obszar pamięci nazywany stosem, który zawiera adresy powrotne do procedur oraz ich niektóre parametry). L1, L2 i L3 to pamięci podręczne posiadające różne rozmiary i czasy dostępu (1c oznacza pojedynczy cykl procesora). Rdzenie mogą działać niezależnie, współdzieląc jedynie część pamięci wyższego poziomu. Procesor połączony jest z zewnętrzną pamięcią główną, która przechowuje zarówno kod, jak i dane (architektura von Neumanna)
L1, L2 i L3 to bloki pamięci nazywane pamięciami podręcznymi. Mają one różne rozmiary i różny czas dostępu. Ich charakterystyczną cechą jest to, że im dalej od ALU znajduje się taka pamięć, tym większa jej pojemność, ale i dłuższy czas dostępu. Na samym końcu tego specyficznego trójkąta pojemności i prędkości jest pamięć główna: jej pojemność jest o kilka rzędów wielkości większa niż pamięci podręcznych, ale ma też najdłuższy czas dostępu. Jest tak z powodu technologii sprzętowych użytych do jej wytworzenia. Rejestry oraz pamięci podręczne to pamięć wewnętrzna procesora (rdzeni). Jednak to zewnętrzna pamięć główna w architekturze von Neumanna[1] zawiera cały skompilowany kod wykonywalny programu oraz większość jego danych. Ściślej mówiąc, jest to pamięć operacyjna, która - inaczej niż w przypadku przestrzeni dyskowej - może zostać bezpośrednio zaadresowana przez procesor w celu wykonania programu. Z programistycznego punktu widzenia ważne jest, by zdawać sobie sprawę, że aby uzyskać dostęp do dowolnej komórki pamięci operacyjnej, procesor i chipset muszą obsłużyć dwie poniższe wyspecjalizowane szyny sygnałowe.
- Szyna adresowa - wszystkie sygnały tej szyny określają lokalizację komórki pamięci, do której mamy uzyskać dostęp. Z przyczyn historycznych najmniejszą komórką możliwą do zaadresowania jest bajt, czyli 8 bitów danych. Adresy logiczne odpowiadają wskaźnikom w C/C++.
- Szyna danych - ta dwukierunkowa szyna odpowiada za obsługę danych, które mają zostać odczytane z pamięci lub do niej zapisane.
Trzeba zaznaczyć, że ten płaski model pamięci w znacznym stopniu upraszcza to, co tak naprawdę dzieje się ze sprzętem. W skrócie, w przypadku wielu współczesnych architektur szyny danych posiadają szerokość 32 lub 64 bitów. Te równe wielokrotności bajtów określają to, co nazywane jest słowem komputerowym (ang. computer word). Jak już wspomniałem, chociaż adresy logiczne mogą odnosić się do pojedynczego bajtu, z powodu szerokości szyny danych dostęp do pamięci związany jest z operacjami na słowach. Z tego powodu niższe bity adresowe nie muszą być ustawione bezpośrednio na szynie. Wraz z mechanizmem stronicowania pamięci oraz TLB (ang. translation lookaside buffers) sprawia to, że fizyczna liczba linii we wspólnej architekturze znajduje się zwykle gdzieś w przedziale od 40 do 52. Niemniej jednak taki płaski model stanowi uczciwy kompromis między różnorodnością architektur sprzętowych oraz tym, jak to wygląda z perspektywy oprogramowania. Dla przykładu, wykorzystując to podejście, umiejscowienie obiektu oraz inicjalizacja w przestrzeni pamięci zostały wyjaśnione jak na rysunku 3.1.
Z kolei szybszej pamięci podręcznej nie można bezpośrednio zaadresować z poziomu programu w C++. Nie ma takiej potrzeby, ponieważ pamięć podręczna przechowuje jedynie kopie danych z pamięci głównej, by umożliwić szybszy dostęp do nich. Niemniej jednak można ją efektywnie wykorzystać przy wykonywaniu programów napisanych w C++ dzięki odpowiedniemu umiejscowieniu danych w pamięci operacyjnej. Odniesiemy się do tych kwestii w rozdziale 8, gdy będziemy omawiać dostęp do pamięci i zrównoleglone operacje rdzeni.
Po tym krótkim wprowadzeniu do współczesnych architektur komputerowych zauważyć trzeba, że starsze i prostsze architektury procesora były zwykle oparte na niewyszukanym ALU i kilku rejestrach; nie posiadały też rdzeni ani pamięci podręcznych. Wszystkie te funkcjonalności pozwalają nam na wykonanie programów w C++ nawet w sposób wielowątkowy. Stąd proste procesory połączone z pamięcią zewnętrzną stanowią jeszcze bardziej minimalistyczny, ale nadal bardzo użyteczny model obliczeniowy. Podejścia takie są nadal wykorzystywane w przypadku niektórych platform wbudowanych za sprawą ich niższego kosztu, a nierzadko także niższej konsumpcji energii. Tę ostatnią kwestię również należy uwzględnić, projektując oprogramowanie.
W tym wprowadzeniu jedynie dotknęliśmy zagadnienia architektury oprogramowania czy obliczeniowego modelu programistycznego. Niemniej jednak rozważania te pomogą zrozumieć techniki programowania omawiane w kolejnych rozdziałach tej książki. W ramach dalszej lektury warto zapoznać się z pozycjami Pattersona i Hannessy'a (2018) oraz Bryanta i O'Hallarona (2015).
2.2. Ekosystem tworzenia oprogramowania
Z jednej strony oprogramowanie sprawia, że komputery działają. Z drugiej strony komputery wykorzystywane są do tworzenia oprogramowania. Dychotomię tę można dostrzec na rysunku 2.3: przedstawia on ekosystem tworzenia oprogramowania, którego elementy stanowić będą tematy dalszych rozdziałów tej książki. Scharakteryzujmy krótko każdy z nich.
Pierwsze kroki pokazane na rysunku 2.3 to projektowanie oprogramowania i kodowanie. Choć na tym diagramie są to początkowe stadia, niedługo odkryjemy, że stanowią one zwieńczenie bardzo istotnej - może nawet najistotniejszej - konceptualnej fazy tworzenia oprogramowania. Gdy prace nad częścią kodu zostają zakończone, trzeba je przełożyć na reprezentację zrozumiałą dla procesora, co omówiliśmy w poprzednim podrozdziale. Ten proces przekładu z języka C++ dokonywany jest przez program powszechnie zwany kompilatorem. Ramię w ramię z systemami operacyjnymi, kompilatory są bardzo złożonymi i wyrafinowanymi programami, co jeszcze nieraz będziemy mieli możliwość obserwować. W przypadku środowiska C++ komponenty oprogramowania mogą być tworzone niezależnie, a by zbudować ostateczny program, fragmenty te muszą zostać ze sobą połączone. Za realizację tego zadania odpowiada konsolidator. Gdy zakończy się ono sukcesem, dostajemy komponent kodu, który może zostać wykonany przez komputer.
Nadal zostało nam jednak kilka kroków, nim będziemy mogli powiedzieć, że nasza praca dobiegła końca. Tak naprawdę rozpoczynają się nowe etapy prac nad oprogramowaniem: testowanie kodu oraz debugowanie. Ponieważ nawet krótkie programy mogą implementować skomplikowane koncepcje, nie powinniśmy mieć złudzeń, że napiszemy poprawną wersję już za pierwszym podejściem. Dlatego też powinniśmy
Rysunek 2.3. Ekosystem tworzenia oprogramowania. Aby wykonać program napisany w C++, musi on zostać przetłumaczony przez kompilator na reprezentację maszynową. Jako że program może posiadać części i korzystać z uprzednio stworzonych bibliotek, wszystkie one muszą zostać połączone w jedną postać wykonywalną. Odpowiada za to konsolidator. Są to etapy budowy oprogramowania. Dalej, postać wykonywalna musi zostać odpowiednio przetestowana i zdebugowana w celu usunięcia usterek. Działanie aktualnej wersji następnie może zostać zoptymalizowane dzięki uruchomieniu profilera. Jego rolą jest pomiar wydajności komponentów oprogramowania w celu wykrycia "gorących miejsc", czyli tych fragmentów kodu, które pochłaniają najwięcej czasu wykonania. Cały proces tworzenia oprogramowania może być kontynuowany w celu zbudowania następnej, lepszej wersji. W trakcie tego procesu nie możemy zapominać o ochronie i kontroli wersji naszego oprogramowania. Można to łatwo osiągnąć, korzystając z kontroli źródeł oraz platformy umożliwiającej wersjonowanie. Gdy oprogramowanie jest już gotowe, może zostać wdrożone na konkretnej platformie sprzętowej
dopisać oprogramowanie, które kontroluje to, co robią inne programy. Może to np. polegać na napisaniu testów jednostkowych, które również omówimy. Gdy problemy z programem zostaną dostrzeżone, możemy wykonać go krok po kroku za pomocą debuggera. Jest to trzeci program w naszym zestawie narzędzi programistycznych. Poza tym, że pozwala nam na wykonanie kodu wiersz po wierszu, umożliwia też dodawanie punktów wstrzymania (ang. breakpoint), sprawdzanie wartości zmiennych, zaglądanie w określony obszar pamięci i strukturę stosu, a jeśli zajdzie taka potrzeba - nawet przeglądanie rejestrów procesora. Debugowanie jest najlepszym sposobem na nauczenie się tego, co robi kod. Tak więc szeroko korzystajmy z debuggerów, pracując nad przykładami kodu przedstawionymi w niniejszej książce.
Oprogramowanie może być różnie skonfigurowane i mieć różne wersje. Choć w grę wchodzi wiele konfiguracji, zwykle wyróżnia się dwa tryby:
- Tryb debugowania (ang. debug) - wersja oprogramowania, która zwykle nie jest zoptymalizowania i jest wykorzystywana do wewnętrznych testów i uruchamiania.
- Tryb wdrożenia (ang. release) - stabilna wersja oprogramowania, która przeszła intensywne testy, jest w pełni gotowa do działania, zoptymalizowana i przeznaczona do dystrybucji wśród użytkowników.
Załóżmy, że udało nam się otrzymać stabilną wersję naszego oprogramowania i możemy przystąpić do prawdziwych obliczeń. W wielu przypadkach wydajność może jednak nie być satysfakcjonująca z powodu długich czasów wykonania czy tego, że oprogramowanie utknęło w martwym punkcie. Można to skorygować za pomocą profilera. Jego rolą jest pomiar wydajności komponentów służących do budowy oprogramowania i wykrycie "gorących" fragmentów kodu, odpowiedzialnych za spowolnienia. Takie miejsca odnalezione w kodzie - konsumujące większość czasu wykonania - mogą zostać zoptymalizowane poprzez użycie innych algorytmów lub refaktoryzację (czyli ponowne zaprojektowanie i implementację), jeśli to możliwe - do postaci zrównoleglonej. Następnie możemy powtórzyć cały proces tworzenia oprogramowania w celu zbudowania jego kolejnej, ulepszonej wersji.
W trakcie cyklu tworzenia naszego oprogramowania nie możemy zapominać o ochronie i kontroli jego wersji. Jest to możliwe dzięki wykorzystaniu jednej z platform pozwalających na kontrolę źródeł i wersjonowanie, omówionych w dodatku w podrozdziale A.6.2.
Gdy oprogramowanie jest już gotowe, można je wdrożyć na konkretnej platformie sprzętowej. Stopień zależności między oprogramowaniem a sprzętem (ang. software-hardware, w skrócie S/H) jest funkcją własności oprogramowania. Znaczy to, że jedne programy można z łatwością uruchomić na niemal każdej platformie sprzętowej, podczas gdy inne wymagają znacznych mocy obliczeniowych lub np. dostrojenia pod konkretne wyświetlacze. Stąd też, jeśli jest to wskazane, takie funkcjonalności trzeba wziąć pod uwagę w trakcie kolejnych kroków tworzenia oprogramowania.
Tak więc proces tworzenia oprogramowania często przypomina spiralę: te same zadania są powtarzane raz za razem, aż osiągniemy zadowalające rozwiązanie. Innymi słowy, możemy działać w cyklach o coraz większej i większej średnicy. Tym samym wchodzimy w spiralny model tworzenia oprogramowania, stanowiący uznaną strategię wykorzystywaną przez wiele firm. Jeśli podejście takie zostanie właściwie zorganizowane, w praktyce może okazać się wysoce skuteczne. W kolejnym podrozdziale przyjrzymy się bliżej kolejnym etapom tworzenia oprogramowania.
I rzecz ostatnia, ale wcale nie najmniej ważna. Zauważmy, że ekosystem programowania przedstawiony na rysunku 2.3 uwzględnia tylko jedną osobę, zaś tworzenie i rozwój oprogramowania wymagają zwykle pracy zespołowej. Czynnik ludzki, który często bywa przeoczany w książkach dotyczących programowania, może mieć znaczny wpływ na sukces lub porażkę każdego projektu. Choć ta istotna kwestia znajduje się poza zakresem niniejszej książki, efektywne działanie obejmuje również współpracę i sposób organizacji projektu (McConnell 2004). Do pewnego stopnia jest to wspierane przez modułową strukturę projektów w C++ oraz narzędzia odpowiadające za wersjonowanie i utrzymanie oprogramowania, takie jak Git i GitHub przedstawione na rysunku 2.3.
2.3. Etapy tworzenia oprogramowania
Tak jak dom, most czy samochód można zaprojektować na więcej niż jeden sposób, tak i na kilka sposobów można to zrobić w przypadku oprogramowania. We wszystkich tych przypadkach ostatecznym kryterium sukcesu lub porażki jest jednak wydajność finalnego produktu. Tak jak w przypadku innych nauk inżynierskich, bazując na latach doświadczeń i tysiącach projektów, można wskazać pewne wspólne zasady, które mogą pomóc w uniknięciu częstych pułapek w przyszłych projektach. Takie kroki tworzenia oprogramowania zostały zobrazowane na rysunku 2.4. Przyjrzymy się bliżej każdemu z nich.
Rysunek 2.4. Diagram czynności UML przedstawiający kroki procesu tworzenia oprogramowania
W niniejszej książce skupiamy się przede wszystkim na poprawnej implementacji C++. Nie może być jednak mowy o dobrej implementacji, gdy wadliwy jest już sam projekt. Z kolei nawet dobry projekt i implementacja nie gwarantują też pomyślnego rozwiązania, jeśli oprogramowanie nie przeszło intensywnych testów. Tak więc choć zajmujemy się głównie C++, zwrócimy również uwagę na inne kroki tworzenia oprogramowania. Opiszemy teraz krótko każdy z nich w kolejności pokazanej na rysunku 2.4:
1. Specyfikacja wymagań (ang. requirements specification) - jest to proces definiowania najważniejszych zadań, jakie mają być realizowane, a także funkcjonalności oraz zastosowań produktu. Wymaga on współpracy różnych stron, takich jak użytkownicy końcowi, architekci systemu, menedżerowie itd. Na tym etapie kluczowe jest również adekwatne określenie możliwych kosztów i przewidywanego harmonogramu (Dick et al. 2017).
2. Analiza problemu (ang. problem analysis) - bazuje na poprzednim kroku. Jest to proces ustanawiania najważniejszych relacji w obrębie systemu, rozpoznawania reguł rządzących krytycznymi procesami, identyfikacji najtrudniejszych komponentów i zarysowania najważniejszych stadiów kluczowych algorytmów, ze szczególnym uwzględnieniem tych najbardziej problematycznych. W niektórych przypadkach może to być najkosztowniejszy i najbardziej żmudny etap, angażujący ekspertów z innych obszarów.
3. Projektowanie rozwiązań (ang. solution design) - opiera się na poprzednich krokach. Proces ten polega na wyspecyfikowaniu architektury całego systemu, rozważeniu jego wszystkich komponentów oraz ich interfejsów. Jego element stanowi specyfikacja narzędzi i strategii implementacyjnych. Często proces ten polega na przygotowaniu wykresów Gantta obrazujących wzajemne powiązania pomiędzy etapami implementacji systemu, zasobami ludzkimi, terminami oraz kamieniami milowymi.
4. Implementacja (ang. implementation) - proces tworzenia oprogramowania bazujący na poprzednich krokach. Głównym produktem tego etapu jest kod źródłowy. Powstaje też postać wykonywalna, jak zostało to pokazane na rysunku 2.3.
5. Testowanie i debugowanie (ang. testing & debugging) - połączony proces wykrywania i naprawy wadliwego oprogramowania. Testy powinny być dobrze zaprojektowane przy użyciu formalnych metodologii, takich jak tworzenie oprogramowania sterowane testami (ang. test driven development, w skrócie TDD) czy testy jednostkowe (zob. dodatek A.7). Problemy pojawiają się jednak, gdy przyczyną niedziałającej poprawnie implementacji są wady samego projektu lub innych wyższych poziomów procesu tworzenia oprogramowania. Tak więc rola omówionych kroków projektowych jest najważniejsza.
6. Wdrożenie systemu (ang. system deployment) - proces integracji i instalacji systemu w celu zapewnienia jego odpowiedniego działania na specjalnie skonfigurowanej platformie sprzętowej. Wymaga to zwykle dopasowania do określonych komponentów sprzętowych, które np. nie są obecne na wybranej platformie lub mają różne parametry (Somerville 2016).
7. Utrzymanie systemu (ang. system maintenance) - praktyki zapewniające nieprzerwane działanie systemu, pozwalające na jego ewolucję i niezakłócone wprowadzanie zmian.
Z pewnością te etapy tworzenia oprogramowania nie są jedyną możliwą ścieżką, jaką można podążać w tej wysoce wymagającej dziedzinie inżynierii. Jest to po prostu jeden z możliwych modeli. Strategie projektowe opracowane w innych dziedzinach, takich jak elektronika czy architektura, również mogą być pomocne przy projektowaniu oprogramowania. Co ciekawe, postulat wspólnych wzorców projektowych - które dla nas stanowią dobrze ugruntowane komponenty oprogramowania posiadające określone charakterystyki - po raz pierwszy pojawił się w odniesieniu do konstrukcji budynków (Alexander 1977). Poprzednie kroki powinny również znajdować odzwierciedlenie w dokumentacji projektowej, której struktura mogłaby stanowić temat znacznie dłuższych rozważań. Nie trzeba dodawać, że taka dokumentacja powinna tak precyzyjnie, jak to tylko możliwe, i tak zwięźle, jak to możliwe, opisywać wszystkie kroki konieczne do rozwiązania danego problemu. W przypadku naszych projektów będziemy mieć do czynienia przede wszystkim z dokumentacją kodu. W tym zakresie zasada kodu, który sam się dokumentuje dzięki dobrej strukturze i dobrym komentarzom, dowiodła swojej przydatności w wielu praktycznych zastosowaniach. Dokumentacja taka zwięźle przekazuje najważniejsze koncepcje i - co najważniejsze - powinna być aktualna. Powrócimy do tej kwestii w dalszych podrozdziałach.
Na koniec należy zaznaczyć, że proces tworzenia oprogramowania pokazany na rysunku 2.4 jest jedynie jednym z możliwych procesów i nie odzwierciedla wszystkich ważnych aspektów tworzenia oprogramowania, takich jak czynnik ludzki. Nie ma gwarancji, że projekt, który przejdzie przez wszystkie te etapy, odniesie sukces. Jednak jako heurystyczne odkrycie, nietrzymanie się żadnej strategii projektowej - zwłaszcza jeśli bierzemy się za tworzenie złożonych systemów - stanowi znakomity przepis na katastrofę. Istnieje wiele bardziej wyczerpujących strategii realizacji projektów IT, by wymienić jedynie PRINCE2, Scrum czy Agile. Dalsze zgłębienie tej tematyki z pewnością warte jest wysiłku; można tu zajrzeć np. do Hinde 2018, Cohn 2019 czy Sommerville 2016.
2.4. Reprezentacja i uruchamianie algorytmów
W tym podrozdziale zaimplementujemy wreszcie program w C++. Poprosi on użytkownika o wprowadzenie liczby i sprawdziwszy, czy liczba ta jest nieujemna, wyświetli jej pierwiastek kwadratowy. To znaczy, że jeśli wprowadzona zostanie liczba 16, wyświetlone zostanie 4 itd. Zanim jednak przejdziemy do kodu C++, który jest jedną z form reprezentacji algorytmów, pochylmy się nad tym, czym jest algorytm i w jaki sposób można go wyrazić.
W tym podrozdziale nauczymy się:
- Czym jest algorytm i w jaki sposób go reprezentować.
- Czym jest zunifikowany język modelowania UML i co można przedstawić za pomocą diagramów czynności UML (ang. UML activity diagrams).
- Jak napisać w C++ prosty program obliczający pierwiastek kwadratowy wprowadzonej wartości liczbowej.
- W jaki sposób skompilować i wykonać prosty kod w C++, korzystając z platform dostępnych online.
- W jaki sposób napisać plik źródłowy C++, skompilować go i uruchomić jego postać wykonywalną w środowisku Linuksa.
2.4.1. Reprezentowanie algorytmów
Algorytm opisuje kroki, jakie należy wykonać. Algorytmy często spotyka się nie tylko w informatyce, ale i w życiu codziennym. Na przykład instrukcja pożarowa znajdująca się w każdym biurze opisuje kroki, jakie należy podjąć w wypadku pożaru. Wybranie programu w zmywarce również określa kroki, jakie maszyna wykona w celu umycia naszych drogocennych szklanek itd.
Wiele zależy od poziomu abstrakcji, na którym operujemy. Pojęcie abstrakcji jest w informatyce często spotykane: jeśli chodzi o reprezentowanie algorytmów, mówi nam po prostu, jaki stopień szczegółowości jest konieczny. W niektórych przypadkach, szczególnie jeśli chcemy wyświetlić całą postać algorytmu, preferowany jest bardziej ogólny, zgrubny poziom, na którym można wykorzystać obraz, a mówiąc precyzyjniej, diagram wykorzystujący symbole o powszechnie ustalonym znaczeniu. Takie diagramy wykorzystywane są w wielu dziedzinach, np. w inżynierii elektrycznej czy architekturze. W informatyce mamy to szczęście, że dysponujemy powszechnym systemem diagramów powstałym pod parasolem UML (zob. http://uml.org oraz www.visual-paradigm.com). UML to znacznie więcej niż prosta kolekcja wspólnych symboli - jest to platforma wspomagająca cały proces tworzenia oprogramowania pokazany na rysunku 2.4. Będziemy do niego wielokrotnie wracać. Teraz jednak przedstawmy diagram czynności UML reprezentujący kroki wymagane przez nasz własny program, pokazany na rysunku 2.5.
Rysunek 2.5. Diagram czynności UML przedstawiający algorytm służący do obliczania pierwiastka kwadratowego z wartości x wprowadzonej z klawiatury. Wszystkie działania mogą zostać wyrażone przez dwa symbole: czynności (procedury) i bloki decyzyjne
Zasadniczo istnieją dwa typy symboli widoczne na rysunku 2.5. Czynności to zaokrąglone prostokąty, a bloki decyzyjne mają kształt rombów. Linie zakończone strzałkami pokazują przepływ sterowania. Dlatego też takie diagramy są niekiedy nazywane diagramami przepływu (ang. flow charts). W przypadku prostych diagramów główny przepływ ma zwykle miejsce z góry na dół. Zauważmy jednak, że przepływ może zostać łatwo przekierowany, tworząc pętle wykonania. Choć proste i jasne, końcowe symbole przypominają nam o bardzo ważnym problemie w projektowaniu algorytmów: problemie stopu. Mówiąc wprost, znaczy on, że dobrze zaprojektowany algorytm powinien posiadać dobrze określone warunki stopu, czyli nie powinien po wieczność wisieć w nieokreślonym stanie. Tym niemniej niektóre programy, takie jak systemy operacyjne, działają w nieskończonej pętli. Nigdy jednak nie powinny znaleźć się w nieokreślonym stanie lub wykonywać nieprecyzyjnej akcji.
Warto zauważyć, że na rysunku 2.5 cały program można objąć jednym spojrzeniem. Jednocześnie jednak kroki wyrażają pewne ogólne działania, takie jak "Oblicz sqrt(x)", bez zagłębiania się w szczegóły. To właśnie nazywamy poziomem zgrubnym lub - bardziej ogólnie - podejściem od ogółu do szczegółu (ang. top-down approach). Z drugiej strony, zagłębiając się w szczegóły, wchodzimy na coraz bardziej i bardziej ziarniste poziomy, czyli "podążamy w głąb" projektu. Zwykle wymaga to użycia większej liczby symboli. Aby uniknąć zaśmiecenia, są one zwykle przedstawiane na osobnych diagramach. W niektórych projektach możliwe jest też zastosowania podejścia od szczegółu do ogółu. Jak pokazuje praktyka, takie podejście jest jednak znacznie mniej przydatne w naszej dziedzinie i skutkuje zwykle tym, że wysokopoziomowe komponenty projektu nie współgrają dobrze ze sobą.
W jeszcze inny sposób algorytm można przedstawić w postaci pseudokodu. Jest to mieszanina prostych poleceń komputerowych przeplecionych bardziej ogólnymi instrukcjami, zwykle zapisanymi w postaci możliwych do odczytania przez człowieka poleceń lub krótkich zdań. Algorytm 2.1 przedstawia to podejście.
Algorytm 2.1. Algorytm obliczający pierwiastek kwadratowy wartości rzeczywistej, wyrażony w pseudokodzie (mieszaninie poleceń programistycznych i tych możliwych do zrozumienia przez człowieka)
Wejście:
Wartość x będąca liczbą rzeczywistą
Wyjście:
Pierwiastek kwadratowy z x
1
jeżeli x ? 0
2
Wyświetl sqrt( x )
3
w innym przypadku
4
Wyświetl komunikat błędu
Ostateczna reprezentacja przybiera postać komputerowego kodu, takiego jak ten pokazany na listingu 2.1. Można ją przełożyć na format możliwy do wykonania przez komputer i uruchomić.
Kod z listingu 2.1 robi to, co zostało pokazane na rysunku 2.5 i w algorytmie 2.1.
2.4.2. Korzystanie z kompilatorów dostępnych w Internecie
Nim wyjaśnimy każdą linię kodu z listingu 2.1, możemy go skompilować, a następnie uruchomić jako program za pomocą jednej z dostępnych w Internecie platform wyposażonych w kompilator C++, tak jak zostało to pokazane na rysunku 2.6[2]. Pisząc, możemy
Listing 2.1. Funkcja main służąca do obliczania pierwiastka kwadratowego wprowadzonej wartości (z pliku main.cpp).
Rysunek 2.6. Środowisko dostępnego na stronie http://ideone.com kompilatora C++ uruchomione w przeglądarce Mozilla Firefox wraz z kodem z listingu 2.1 (a). Kod źródłowy został skopiowany do okna edytora. Poniżej znajduje się okno wejścia symulujące std::cin. Po kliknięciu przycisku "Run" kod źródłowy jest kompilowany i wykonywany. Wyniki są pokazane w (b)
jednak popełnić błąd i w takim przypadku kod się nie skompiluje, a platforma wyświetli komunikat błędu z kompilatora. By móc naprawić błąd, należy uważnie przeczytać komunikat i sprawdzić, na czym polega problem. Niekiedy jednak dokładna lokalizacja błędu może być trudna do określenia, a faktyczna usterka może znajdować się kilka linii powyżej miejsca wskazanego przez kompilator. Powinniśmy więc sprawdzić również wcześniejsze wiersze, a dokładną analizę zacząć od pierwszego wystąpienia słowa "error".
Kompilatory dostępne w Internecie są bardzo przydatne, gdy trzeba przetestować krótkie fragmenty kodu, często prezentowane również w tej książce. Jednak w przypadku większych projektów składających się z wielu plików, dla zbudowania wersji wykonywalnych, często będziemy się posługiwać IDE.
2.4.3. Struktura programu w C++
Aby zrozumieć role różnych komponentów kodu, uproszczona wersja programu napisanego w C++ została wyekstrahowana z listingu 2.1 i pokazana oraz wyjaśniona na rysunku 2.7. Szczegółowy opis kodu z listingu 2.1 zostanie zaprezentowany w następnym podrozdziale. Program składa się z szeregu instrukcji oddzielonych średnikami ;. Pominięcie tego końcowego symbolu jest jednym z najczęstszych błędów popełnianych na wczesnych etapach przygody z programowaniem. Zauważmy jednak, że średnika nie ma na końcu bloku funkcji main, która biegnie dalej wewnątrz obszaru wyznaczonego przez nawiasy klamrowe {}.
Rysunek 2.7. Struktura uproszczonego programu w C++, składającego się z funkcji main. Pliki nagłówka zawierające definicje innych komponentów zostają wprowadzone przez dyrektywę #include. Każda instrukcja, taka jak definicja double x {0.0}, jest zakończona średnikiem ;. Średnika nie ma jednak na końcu bloku funkcji wyznaczonego przez nawiasy {}. Obiekt std::cin reprezentuje klawiaturę, podczas gdy std::cout ekran dla wyjścia. Wewnątrz main mogą być wywoływane inne funkcje dające jakieś rezultaty, np. std::sqrt( x ) obliczająca pierwiastek kwadratowy z wartości x.
2.4.4. Analiza kodu
Wróćmy do kodu przedstawionego na listingu 2.1. Pierwszy wiersz [1] zawiera prosty komentarz, czyli tekst, którego jedynym celem jest dostarczenie dodatkowych informacji programistom. W C++ komentarze rozpoczynają się od dwóch ukośników // i kończą się wraz z końcem bieżącego wiersza. Zobaczymy więcej takich symboli składających się z wielokrotności pojedynczych znaków - są one niezbędne ze względu na ograniczoność zbioru symboli specjalnych na komputerowej klawiaturze. Wiersze [3, 4] zawierają dwie dyrektywy #include - po każdej z nich następuje nazwa pliku ujęta w nawiasy <>. Są to dyrektywy preprocesora omówione w dodatku A.1, które w rzeczywistości kopiują i wklejają zawartość wskazanego pliku w bieżące miejsce. Robi się tak, chcąc wprowadzić komponenty programistyczne napisane już przez innych programistów, które możemy łatwo wykorzystać, nie kłopocząc się ich samodzielną implementacją. Przykłady stanowią obiekt std::cout oraz funkcja std::sqrt, które wykorzystamy w kolejnych wierszach. Na szczęście całe to kopiowanie i wklejanie dokonywane jest w niewidoczny sposób w momencie rozpoczęcia kompilacji, więc nie widzimy bałaganu w naszym kodzie.
W naszym przykładzie funkcja main jest zdefiniowana w wierszu [6], a jej ciało - zbiór linii kodu - zawarte jest pomiędzy nawiasami klamrowymi w wierszach [7-17]. int na początku main znaczy, że powinna ona zwracać wartość całkowitą, ale w tym przypadku nie ma to znaczenia.
Pierwszy obiekt - zmienna o nazwie x - zostaje zdefiniowana i zainicjalizowana w wierszu [8]. Jest ona typu double. Typ ten jest wykorzystywany do reprezentowania liczb zmiennoprzecinkowych, czyli w przybliżeniu liczb rzeczywistych, co jest omawiane w podrozdziale 7.4. Nawiasy klamrowe { 0.0 } oznaczają, że zmienna x została zainicjalizowana wartością 0, co w dziedzinie liczb zmiennooprzecinkowych jest precyzyjnie wyrażane w postaci stałej 0.0.
Wiersz [10] poleca komputerowi, aby wyświetlił tekst "Enter x=" na ekranie, to jest w jakimś oknie. Udaje się to osiągnąć za pomocą obiektu std::cout reprezentującego strumień wyjściowy (ekran) oraz operatora << (raz jeszcze dwa znaki wzięte razem otrzymują nowe znaczenie). Operator ten, w swej domyślnej wersji, oznacza przesunięcie bitowe w lewo liczby całkowitej. Zobaczymy jednak, że w C++ operatorom można przypisywać inne znaczenia zależnie od kontekstu, w jakim działają. Jest to całkiem przydatna własność.
Odwrotna akcja została zakodowana w wierszu [11]: komputer będzie czekać na użytkownika, by ten wprowadził wartość x. Zostaje to zrealizowane za pomocą - odpowiednio - obiektu std::cin i operatora >>. W rezultacie tuż po tym, jak użytkownik wciśnie klawisz Enter , x zmieni swoją zawartość na to, co tylko zostało wprowadzone z klawiatury.
Nie wszystkie wartości x mogą jednak zostać wykorzystane do obliczenia pierwiastka kwadratowego. Stąd też w wierszu [13] warunek x >= 0.0 (to znaczy, czy x jest większe lub równe 0.0) zostaje sprawdzony za pomocą instrukcji if-else (podrozdział 3.13.2.1). Są tu dwie możliwości: albo warunek ten jest spełniony, a wtedy wykonany zostaje kod z wiersza [14]; albo też jest on fałszywy i wykonany zostanie alternatywny wiersz [16], następujący tuż po else w linii [15].
Wiersz [14] zasługuje na krótkie wyjaśnienie. Jest on nieco bardziej skomplikowany niż wiersz [10], jako że poza tekstem wyświetla też serię obiektów. Wszystkie one odseparowane są operatorem <<. std::sqrt( x ) stanowi wywołanie funkcji o nazwie sqrt zawartej w bibliotece standardowej[3] - stąd prefiks std:: oraz #include <cmath> - z x w charakterze jej parametru. Innymi słowy, wiedząc już, że x jest nieujemne, wywołujemy gotową funkcję, która oblicza dla nas pierwiastek kwadratowy. Pojawia się pytanie, co by się stało, gdyby x było ujemne? To zależy, ale na pewno nic dobrego. Sytuacja taka jest znana jako niezdefiniowane zachowanie (ang. undefined behavior, w skrócie UB) i należy jej unikać.
Ostatnim obiektem przesłanym na ekran w linii [14] jest std::endl. Poleca ona komputerowi, aby (i) umieścił kursor w nowym wierszu oraz (ii) wyczyścił wyjście, co skutkować będzie przekazaniem wszystkich symboli na ekran. Pierwszą akcję - przejście do nowego wiersza - można również wykonać, dodając \n do stałej tekstowej, tak jak pokazano to w wierszach [14, 16].
Wyjaśnijmy też wreszcie znaczenie wszechobecnego operatora ustalenia zakresu :: (dwóch dwukropków, czyli czterokropka). Jest on wykorzystywany do uzyskiwania dostępu do składowych przestrzeni nazw, takich jak dane i funkcje, klasy oraz struktury, co omówione jest w dalszych częściach niniejszej książki. Jego składnia pokazana jest na rysunku 2.8.
Na przykład std::cout w poprzednim fragmencie kodu oznacza obiekt cout z przestrzeni nazw std. Ten ostatni element oznacza przestrzeń nazw biblioteki standardowej.
Rysunek 2.8. Składnia operatora zakresu :: pozwalającego na uzyskanie dostępu do składowych przestrzeni nazw, struktur i klas
2.4.5. () Budowa linuksowej postaci wykonywalnej
W tym podrozdziale pokażemy, jak zbudować aplikację, wprowadzając kilka poleceń do systemu operacyjnego Linux[4]. Nie powinno zaskakiwać, że ogół działań, jakie należy wykonać, również został ujęty w postaci następującego algorytmu.
- Otwórz okno terminala (w Linuksie możesz wykorzystać skrót klawiaturowy Ctrl+Alt+T ).
- Uruchom polecenie ls -l, aby wylistować pliki i katalogi. Poniżej znaleźć można przykładowy rezultat wykonania tego polecenia.
boxy@PARSEC:~$ ls -l
total 0
drwxrwxrwx 1 boxy boxy 512 Aug 16 18:32 Desktop
drwxr-xr-x 1 boxy boxy 512 Aug 16 18:32 Videos
- Za pomocą polecenia mkdir utwórz nowy katalog, np. Projects i wylistuj jego zawartość.
boxy@PARSEC:~$ mkdir Projects
boxy@PARSEC:~$ ls -l
total 0
drwxrwxrwx 1 boxy boxy 512 Aug 16 18:32 Desktop
drwxrwxrwx 1 boxy boxy 512 Aug 30 19:51 Projects
drwxr-xr-x 1 boxy boxy 512 Aug 16 18:32 Videos
- Przejdź do katalogu Projects wywołując cd Pro* (aby zaoszczędzić sobie pisania, korzystamy ze specjalnego znaku grep *, który zastępuje zero lub więcej znaków):
boxy@PARSEC:~$ cd Pro*
boxy@PARSEC:~/Projects$ ls -l
total 0
- Wpisz teraz - lub wklej - kod z listingu 2.1. Aby to zrobić, można wywołać jeden z zainstalowanych edytorów tekstu, takich jak GNU nano lub emacs. Aby stworzyć plik sq.cpp, można też jednak skorzystać z prostego polecenia cat. Po wpisaniu cat > sq.cpp trzeba po prostu wkleić kod ze schowka (lub go wpisać) w następujący sposób:
boxy@PARSEC:~/Projects$ cat > sq.cpp
// To jest komentarz C++ w programie do obliczania pierwiastka kwadratowego z jakiejś wartości
#include <cmath> // Nagłówek dla std::sqrt
#include <iostream> // Nagłówek dla std::cout, std::cin, std::endl
int main() // Program w C++ składa się z funkcji main()
{
double x { 0.0 }; // Zdefiniuj i zainicjalizuj zmienną x
std::cout << "Enter x="; // Wyświetl komunikat
std::cin >> x; // Wprowadź z klawiatury wartość x
if( x >= 0.0 ) // Sprawdź, czy x jest nieujemne
std::cout << "\nSqrt(" << x << ") = " << std::sqrt( x ) << std::endl;
else
std::cout << "\nWrong value - cannot compute Sqrt\n";
}
^Z
[1]+ Stopped cat > sq.cpp
Aby wskazać, że chcemy przerwać przekierowywanie tego, co wpisujemy lub wklejamy do sq.cpp, wciskamy kombinację klawiszy Ctrl+Z , aby zamknąć potok przekierowania.
- Teraz jesteśmy już gotowi do skompilowania naszego programu i możemy w następujący sposób wywołać kompilator GNU gcc:
boxy@PARSEC:~/Projects$ g++ sq.cpp -o sq
By zmusić gcc do skorzystania z kompilatora C++, a nie C, przywołane zostaje polecenie g++. Jego drugim argumentem jest plik źródłowy sq.cpp, po którym pojawia się opcja -o oraz nazwa postaci wykonywalnej (sq). Nim to zrobimy, powinniśmy się jednak upewnić, że g++ jest już zainstalowane.
- Listujemy nasze pliki za pomocą ls -l:
boxy@PARSEC:~/Projects$ ls -l
total 20
-rwxrwxrwx 1 boxy boxy 13248 Sep 3 18:14 sq
-rw-rw-rw- 1 boxy boxy 611 Sep 3 18:10 sq.cpp
Widzimy, że poza naszym plikiem źródłowym sq.cpp pojawił się nowy plik sq posiadający włączony atrybut wykonywalności. Gratulacje! Znaczy to, że pomyślnie utworzyliśmy postać wykonywalną.
- Uruchom program i sprawdź, jak działa:
boxy@PARSEC:~/Projects$ ./sq
Enter x=123.45
Sqrt(123.45) = 11.1108
boxy@PARSEC:~/Projects$
- Jeśli popełniliśmy błąd, pisząc na klawiaturze, lub chcielibyśmy po prostu popracować jeszcze nad zmodyfikowaniem źródła, przyda nam się jakiś edytor tekstu. Możemy go otworzyć, wpisując np.:
boxy@PARSEC:~/Projects$ nano sq.cpp
Po wprowadzeniu zmian i zapisaniu pliku sq.cpp należy powtórzyć powyższy proces kompilacji.
Z pewnością trochę praktyki w zarządzaniu środowiskiem Linuksa jest konieczne. Pomóc mogą obszerne zasoby internetowe (takie jak www.linux.org czy https://askubuntu.com przeznaczone dla użytkowników Ubuntu), ale i wiele książek (Dalheimer i Welsh 2006). Jeszcze bardziej fascynujące jest jednak programowanie w Linuksie. W ostatnich latach zyskało ono jeszcze więcej uwagi, głównie za sprawą systemów wbudowanych wykorzystujących środowisko Linux. Istnieje mnóstwo świetnych źródeł dotyczących programowania w Linuksie, wśród których szczególnie warta polecenia jest znakomita książka "Linux Programming Interface" autorstwa Michaela Kerriska (Kerrisk 2010). Jako że system operacyjny Linux jest napisany w C, przykłady programowania w środowisku Linuksa również są w C. W ich zrozumieniu pomocna będzie lektura dodatku A.2. Linux jest również doskonałym środowiskiem dla współczesnego C++, co również znajdzie odzwierciedlenie w niniejszej książce.
Choć Linux jest znakomitym systemem operacyjnym z setkami przydatnych funkcjonalności i programów, niekiedy dobrze jest mieć Linuksa i Windowsa współistniejące na tym samym komputerze. Windows 10 posiada funkcje ułatwiające programowanie dla Linuksa. Po pierwsze, dystrybucje Linuksa, takie jak Ubuntu czy Debian, można ściągnąć i zainstalować przy użyciu Windows Store, pozwalając na uruchomienie podsystemu Windows dla Linuksa (ang. Windows Subsystem for Linux, w skrócie WSL) w taki sam sposób, jak każdej innej aplikacji pod Windowsem, otrzymując jednocześnie pełen zestaw usług linuksowych. Po drugie, w Microsoft Visual od wersji 2019 (MV'19) dostępna jest linuksowa wtyczka deweloperska[5].
Środowisko MV'19 jest również naszą główną platformą programistyczną[6]. Tak więc o ile nie zostanie zaznaczone inaczej, większość projektów zaprezentowanych w tej książce - czyli cała platforma ze wszystkimi plikami i ustawieniami pozwalającymi stworzyć kompletny program - została w pierwszym rzędzie opracowana i przetestowana za pomocą MV'19 w Windows 10. Projekty zostały jednak wygenerowane automatycznie przy użyciu programu CMake. W dużym stopniu ułatwia to utrzymanie aktualnych projektów w środowiskach wielu systemów operacyjnych i wielu różnych platform kompilujących, jak jest to opisane w dodatku A.6.1. Organizacja projektów w C++ oraz role, jakie pełnią różne pliki, są omówione w podrozdziale 3.15.
Podsumowując, w tym podrozdziale dowiedzieliśmy się następujących rzeczy:
- Czym jest algorytm i w jaki sposób przedstawić go za pomocą diagramu czynności UML, pseudokodu oraz kodu C++.
- W jaki sposób zaimplementować funkcję main stanowiącą wejście do każdego programu w C++.
- Jak zdefiniować i zainicjalizować zmienną typu double mającą reprezentować liczby rzeczywiste.
- Jak wykorzystać obiekty std::cin oraz std::cout dla - odpowiednio - wejścia i wyjścia.
- Jak wykorzystać instrukcję if-else w celu sprawdzenia wartości zmiennej i - w zależności od jego rezultatu - wykonania określonej ścieżki kodu.
- Jak edytować plik źródłowy C++, skompilować go i uruchomić w środowisku online oraz w środowisku systemu Linux.
2.5. Przykładowy projekt - kalkulator procentu składanego
W tym przykładzie stworzymy prosty program ułatwiający inwestycje finansowe. Załóżmy, że mamy 1000 $ (nasz początkowy kapitał) i chcemy bezpiecznie zainwestować tę kwotę w banku na 3% rocznie. Łatwo określić, że po roku zyskamy 1000 $ - 3% = 30 $, a nasz kapitał zwiększy się do 1030 $. Co się stanie, jeśli zrobimy jeszcze raz to samo? Teraz nasz kapitał wynosi 1030 $, więc po roku zyskamy 1030 $ - 3% = 30,90 $. Tym razem zrobiliśmy nieco więcej niż w pierwszym roku, ponieważ nasz kapitał był odrobinę wyższy. Napiszmy program w C++, który będzie robić za nas te obliczenia. Jak zaznaczyliśmy w podrozdziale 2.3, są to nasze wymagania. Nim napiszemy choćby jedną linię kodu, zgodnie z rysunkiem 2.4 powinniśmy jednak przeznaczyć nieco czasu na analizę problemu. W tym przypadku zaczniemy od napisania kilku prostych równań, które pokierują naszą implementacją.
2.5.1. Analiza procentu składanego
Przyjmując, że kapitał początkowy oznaczymy jako C0, oprocentowanie jako r, a liczbę okresów rozliczeniowych jako t, odsetki obliczane są w następujący sposób:
(2.1)
Stąd nowy kapitał po upływie t wynosi C1, co stanowi sumę C0 i I1. Następnie C1 można ponownie zainwestować itd. Cały ten proces można rozpisać w następujący sposób:
(2.2)
gdzie r oznacza stopę procentową w złożonym okresie t. Banki podają jednak zwykle wartość r w odniesieniu do rocznego okresu, czyli 12 miesięcy, podczas gdy w roku możemy mieć do czynienia z wieloma okresami kapitalizacji. Stąd musimy podejść do tego bardziej ziarniście i za naszą podstawową jednostkę przyjąć okres kapitalizacji. Innymi słowy, nasz indeks i będzie zliczać pełne okresy kapitalizacji w łącznym czasie trwania inwestycji. Przypuśćmy, że inwestujemy na 24 miesiące, a okres kapitalizacji wynosi 4 miesiące. W tym czasie będziemy mieć 6 okresów kapitalizacji. Jak to policzyliśmy? 24/4 = 6. Ogólnie rzecz biorąc, liczba okresów kapitalizacji i = m/t, gdzie m oznacza ogólny czas inwestycji wyrażony w miesiącach. Z kolei w każdym okresie kapitalizacji oprocentowanie wynosi r/12 - t. Na przykład, jeśli r wynosi 3%, a t ponownie wynosi 4 miesiące, oprocentowanie w tym okresie wynosi 0,03/12 - 4 = 0,01. Stąd też dostajemy następujące równanie, które posłuży nam za podstawę naszej implementacji:
(2.3)
gdzie
C0 to kapitał początkowy.
Ci to ostateczny kapitał po upływie m miesięcy inwestycji (tj. i = m/t okresów kapitalizacji).
r to roczna stopa procentowa (wyrażona jako ułamek, więc jeśli dostaniemy ją w postaci procentowej, musimy podzielić ją przez 100).
t oznacza okres kapitalizacji w miesiącach (np. dla kapitalizacji kwartalnej t wynosi 3 miesiące).
m to całkowity czas trwania inwestycji w miesiącach.
Spójrzmy, jak to działa w praktyce. Przypuśćmy, że mamy do zainwestowania 2500 $, roczna stopa oprocentowania wynosi 3,4%, a zarówno czas trwania inwestycji, jak i okres kapitalizacji wynoszą 6 miesięcy. Jaki będzie nasz zysk? Jeśli wprowadzimy wszystkie dane do równania 2.3, dostaniemy C1 = 2500 $ - (1 + 0,034/12 - 6)(6/6) ? 2542,50 $. Stąd zysk wyniesie C1 - C0 = 42,50 $. Niestety, w niektórych krajach ten zysk jest opodatkowany, więc nasza inwestycja będzie nieco mniej lukratywna.
2.5.2. Implementacja kalkulatora procentu składanego
Jesteśmy niemal gotowi, aby przejść do implementacji. Musimy tylko dowiedzieć się jeszcze, w jaki sposób zapisywać równania takie jak (2.3) w C++. Pisanie wyrażeń jest mniej więcej podobne do pisania równań w matematyce. Musimy jednak pamiętać o dwóch przeszkodach. Po pierwsze, dla zachowania klarowności i uwzględnienia różnych terminali wyrażenia muszą pasować do wiersza lub wierszy czystego tekstu. Innymi słowy, indeksy górne i dolne nie wchodzą w grę. Drugim ograniczeniem jest liczba symboli, za pomocą których można reprezentować operatory. Stąd też, aby utworzyć niektóre operatory w C++, symbole znane z terminala zostaną ze sobą sklejone: +=, &&, :: itd. Kompletną tabelę operatorów C++ można znaleźć w podrozdziale 3.19.
A oto jako zapisujemy równanie (2.3) jako wyrażenie C++:
C_i = C_0 * std::pow( 1.0 + r / 12.0 * t, m / t );
Po pierwsze, wszystkie symbole takie jak C_i, r, t itd. muszą zostać zdefiniowane - to znaczy muszą posiadać jakiś typ. W naszym przypadku wbudowane typy float lub double powinny zostać wybrane do reprezentowania ułamków. Zmienne muszą też zostać zainicjalizowane. Po drugie, w C++ nie ma operatora potęgowania. Musimy więc wywołać funkcję std::pow z biblioteki matematycznej C++. Przyjmuje ona dwa argumenty, a następnie zwraca jako rezultat pierwszy argument podniesiony do potęgi równej drugiemu argumentowi. Funkcja ta przychodzi wraz z gotową do użycia biblioteką, ale musimy dać znać kompilatorowi, że zamierzamy jej użyć. Na koniec zauważmy też, że w przypadku stałych wartości zamiast 1 napisaliśmy 1.0, a zamiast 12 napisaliśmy 12.0. Zrobiliśmy tak, by wykorzystać format zmiennoprzecinkowy i uniknąć konwersji z reprezentacji właściwej dla liczb całkowitych.
Teraz jesteśmy już gotowi do rozpoczęcia implementacji. Rezultat wygląda tak jak poniższy kod, który został podzielony na części, by ułatwić jego odczytanie.
Listing 2.2. Funkcja main z aplikacji CompInterest (z pliku main.cpp)
1
#include <cmath> // Aby wykorzystać funkcję pow
2
#include <iostream> // Aby wykorzystać std::cout i std::cin
3
4
// Wprowadź nazwy obiektów wejścia i wyjścia z przestrzeni nazw std
5
using std::cout, std::cin, std::endl;
6
7
8
// Ten program oblicza procent składany
9
int main()
10
{
11
// ----------------------------------------------------
12
cout << "Enter the initial amount to invest: " << endl;
13
double C_0 {}; // Kwota początkowa
14
cin >> C_0;
15
16
if(C_0 <= 0.0 )
17
{
18
cout << "Wrong value, exiting..." << endl;
19
return -1;
20
}
W wierszach [1] oraz [2] dołączone zostają dwa pliki nagłówkowe z bibliotek C++. Dzięki temu będziemy mogli wykorzystać wspomnianą już funkcję std::pow, jak również obiekty std::cout oraz std::cin reprezentujące - odpowiednio - ekran wyjścia oraz urządzenie wejściowe w postaci klawiatury. Aby uniknąć powtarzania raz za razem prefiksu std::, w wierszu [5] za pomocą dyrektywy using wprowadzone zostają nazwy obiektów wejścia-wyjścia z przestrzeni nazw std (zob. podrozdział 3.5).
W wierszu [9] zaczynamy definiowanie funkcji main. Od programów napisanych w C++ wymaga się, by zawierały dokładnie jedną definicję main. Dalsze szczegóły dotyczące różnych form main są przedstawione w dodatku A.2.2.
W wierszu [12] wyświetlamy na ekranie tekst, korzystając z obiektu cout, operatora << oraz stałej tekstowej zawartej w cudzysłowie. (Zobaczymy, że działanie operatora takiego jak << może być różne w zależności od typów obiektów, na jakich działa). endl oznacza przeniesienie kursora do kolejnej linii i zaktualizowanie ekranu[7].
W wierszu [13] tworzona jest zmienna o nazwie C_0 mająca przechowywać początkową kwotę. Nazwy zmiennych są bardzo istotne i mogą przekazywać użyteczne informacje. Tak więc ta zmienna mogłaby nazywać się np. kwota_poczatkowa. Jednak gdy implementujemy równania takie jak równanie (2.3), lepiej jest trzymać się nazw elementów równania, a równania matematyczne są zwykle zapisywane przy użyciu pojedynczych liter i indeksów dolnych. Zmienna (obiekt) C_0 może przechowywać dowolną nieujemną wartość, włączając w to ułamki. Z tego powodu na jej typ wybrany został double. C_0 zostaje utworzone i w tym samym wierszu natychmiast zainicjalizowane do wartości 0.0 poprzez wpisanie {}.
Następnie w wierszu [14] czekamy, aż użytkownik wprowadzi liczbę rzeczywistą będącą wartością kapitału początkowego. Potem sprawdzamy tę wartość w wierszu [16]. Jeśli jest niepoprawna, program wypisuje komunikat i w linii [19] zwracany jest kod błędu -1. Sprawdzanie poprawności wartości jest jednym z ważnych, ale często pomijanych działań, które muszą być uwzględniane w rzeczywistym kodzie - zawsze starajmy się trzymać bezpiecznych rozwiązań. Symbol || w linii [26] jest operatorem logicznego OR (tabela 3.15). W C++ istnieją bardziej zaawansowane mechanizmy radzenia sobie z błędami niż zwracanie kodu błędu. Są one omówione w podrozdziale 3.13.2.5.
Ten proces wyświetlania, definiowania zmiennych, czekania i sprawdzania poprawności danych wprowadzonych przez użytkownika jest powtarzany kilka razy. Pokazuje to poniższy kod, który w tym momencie powinien już być jasny:
21
22
// -------------------------------------------
23
cout << "Enter the annual rate [% per 12 months]: " << endl;
24
double r {};
25
cin >> r;
26
if ( r <= 0.0 || r >= 100.0 ) // operator || oznacza logiczne LUB
27
{
28
cout << "Wrong value, exiting..." << endl;
29
return -1;
30
}
31
32
// -------------------------------------------
33
cout << "Compound frequency is a period in months between computing interest" << endl;
34
cout << "(e.g. if 2 times a year, enter 6)" << endl;
35
cout << "If you don't know, enter 12 for a yearly compound frequency." << endl;
36
cout << "Enter the compound frequency [months 1-72]: " << endl;
37
double t {};
38
cin >> t;
39
if ( t <= 0.0 || t > 72.0 )
40
{
41
cout << "Wrong value, exiting..." << endl;
42
return -1;
43
}
44
45
// ---------------------------------------------------
46
cout << "Enter the investment time [months 1-100]: " << endl;
47
double m {};
48
cin >> m;
49
if ( m <= 0.0 || m >= 100 )
50
{
51
cout << "Wrong value, exiting..." << endl;
52
return -1;
53
}
54
Wczytawszy wszystkie dane, zaczynamy nasze obliczenia i definiujemy dwie stałe w wierszach - odpowiednio - [58] i [59]. Ich nazwy niosą informację o ich roli. Dodanie słowa kluczowego const przed double sprawia, że obiekt jest tylko do odczytu. Pominięcie w tym miejscu const nie zmieniłoby obliczeń, ale mogłoby zaszkodzić odporności kodu na ewentualne błędy. Tak więc jeśli wartość powinna pozostać stała, powinniśmy zadeklarować ją jako const.
55
// ------------------------------
56
// Wykonaj obliczenia
57
58
const double kMontsPerYear = 12.0;
59
const double kPercentageDiv = 100.0;
60
61
double i = m / t; // Okresy kapitalizacji
62
63
double C_i =C_0 * std::pow( (1.0 + ( r/kPercentageDiv ) / kMontsPerYear*t ), i);
64
65
cout << "Your balance before tax, after " << m;
66
cout << " months of investment is: " << C_i << endl;
67
68
// Oblicz dochód netto
69
double income = C_i - C_0;
70
cout << "Your income is " << income << endl;
71
const double kIncomeTax = 19.0; // 19%
72
cout << "After " << kIncomeTax << "% tax deduction you get: ";
73
cout << ( 1.0 - kIncomeTax / kPercentageDiv ) * income << endl;
74
75
return 0;
76
}
Uwzględniając całkowitą liczbę miesięcy trwania inwestycji równą m i okres kapitalizacji odsetek wynoszący t również wyrażony w miesiącach, w wierszu [61] wyliczana jest liczba i okresów kapitalizacji. Następnie w wierszu [63] obliczana jest ostateczna suma, dokładnie tak jak w równaniu (2.3). W wierszach [65-66] na ekranie wyświetlane są obliczone wartości. I wreszcie, w wierszach [69-73] obliczany i wyświetlany jest nasz dochód i oraz dochód po odjęciu należnego podatku.
2.5.3. Budowanie i uruchamianie oprogramowania
Możemy z łatwością odpalić poprzedni kod na jednej z dostępnych online platform kompilujących C++, tak jak wspomniano w podrozdziale 2.4.2. Zbudowanie aplikacji, która może zostać uruchomiona jak każdy inny program, w naszym systemie jest jednak w tym wypadku wygodniejszą opcją. Aby zbudować aplikację CompInterest dla Linuksa, możemy powtórzyć kroki przedstawione w podrozdziale 2.4.5. Z racji tego, że kod z listingu 2.2 korzysta jedynie ze standardowych mechanizmów C++, ten komponent oprogramowania jest raczej ogólny. Stąd mógłby zadziałać na dowolnej platformie, gdybyśmy dysponowali narzędziami pozwalającymi tworzyć i utrzymywać projekty wieloplatformowe. Dla każdego środowiska tworzenia oprogramowania możemy ręcznie stworzyć stosowny projekt i zbudować aplikację. Biorąc jednak pod uwagę liczbę takich platform i systemów operacyjnych, taki sposób postępowania byłby żmudny. Zamiast tego możemy wykorzystać generator projektów CMake. Dzięki niemu nie tylko ten, ale i wszystkie inne przyszłe projekty będzie można wygenerować automatycznie w taki sposób, by pasowały do różnych platform deweloperskich i różnych systemów operacyjnych. Wszystko, co musimy zrobić, to zainstalować to darmowe narzędzie i napisać plik CMakeList.txt zawierający polecenia mówiące CMake, jak postępować. (Zostały one opisane w dodatku A.6.1). Na szczęście pasujący plik CMakeList.txt został dołączony do przykładowego projektu i można go pobrać wraz z innymi zasobami z repozytorium GitHub (https://github.com/BogCyg/BookCpp_PL). Zarazem tak się szczęśliwie składa, że wszystkie nasze projekty korzystają z niemal identycznego pliku CMakeList.txt.
Gdy mamy już zbudowaną aplikację CompInterest, aby ją przetestować, załóżmy, że mamy 1000 $, roczna stopa oprocentowania wynosi 2,7%, a my chcemy zainwestować nasz kapitał na 4 miesiące. Po uruchomieniu CompInterest możemy łatwo obliczyć nasze odsetki w następujący sposób:
Enter the initial amount to invest:
1000
Enter the annual rate [% per 12 months]:
2.7
Compound frequency is a period in months between computing interest
(e.g. if 2 times a year, enter 6)
If you don't know, enter 12 for a yearly compound frequency.
Enter the compound frequency [months 1-72]:
4
Enter the investment time [months 1-100]:
4
Your balance before tax, after 4 months of investment is: 1009
Your income is 9
After 19% tax deduction you get: 7.29
Poprzednia funkcja main może działać jako prosty szablon dla podobnych programów, które wczytują dane, wykonują proste obliczenia i na wyjściu wyświetlają wyniki. Ten projekt może być również wykorzystany jako punkt wyjścia do zbudowania aplikacji posiadającej graficzny interfejs użytkownika dla platformy mobilnej lub jako komponent webowy. Później omówimy niektóre z tych pomysłów.
W tym podrozdziale:
- Nauczyliśmy się, jak definiować i inicjalizować liczby całkowite za pomocą int, wartości ułamkowe za pomocą double i stałe łańcuchy znaków za pomocą "".
- Poznaliśmy powszechnie spotykane operatory arytmetyczne +, -, *, / i nauczyliśmy się zapisywać proste wyrażenia.
- Nauczyliśmy się, w jaki sposób wypisywać tekst oraz zmienne na ekranie za pomocą wbudowanego obiektu cout oraz operatora <<, a także jak wprowadzać te wartości przy użyciu obiektu cin i operatora >>.
2.6. Przykładowy projekt - zliczanie wystąpień znaków w tekście
Widzieliśmy już, jak reprezentować proste algorytmy i w jaki sposób budować je i uruchamiać na platformie dostępnej online, jak również jak tworzyć ich postać wykonywalną. Poznaliśmy również kilka użytecznych własności C++, takich jak funkcja main, tworzenie i inicjalizacja zmiennych, obiekty wejścia i wyjścia, jak również instrukcje warunkowe if-else. W tym miejscu poszerzymy tę listę, dodając do niej instrukcję for pozwalającą na implementację pętli oraz kontenery do przechowywania obiektów tego samego typu. W przykładzie z tej sekcji pokażemy, jak obliczyć histogram wystąpień liter a-z w zdaniu.
2.6.1. Analiza problemu i implementacja
Załóżmy, że chcemy obliczyć histogram wystąpień liter a-z w danym zdaniu. Jak zabrać się za ten problem? Zacznijmy od prostego przykładu i przeanalizujmy proces budowania takiego histogramu na bazie słowa Alcatraz, tak jak zostało to pokazane na rysunku 2.9.
Rysunek 2.9. Tworzenie histogramu znaków: analiza przypadku użycia. Każdy pojemnik zawiera liczbę wystąpień danej litery
Histogram to struktura danych składająca się z N pojemników, z których każdy zawiera liczbę wystąpień powiązanego z tym pojemnikiem zdarzenia. Każdy pojemnik odpowiada w naszym przykładzie określonej literze lub jakiemuś innemu zdarzeniu w ogólności. Tak więc histogramy powszechnie stosuje się do mierzenia liczebności wystąpień jakichś zdarzeń. Można je też wykorzystać do pomiaru prawdopodobieństwa - im wyższa liczebność, tym wyższe prawdopodobieństwo. Początkowo wszystkie liczebności w histogramie zostają ustawione na 0. Następnie przechodzimy przez mierzony tekst, a wystąpienie danej litery zwiększa odpowiadający jej pojemnik o 1. Tak więc w naszym przykładzie pojemnik odpowiadający literze a oznaczony zostaje liczbą 3, ponieważ w słowie Alcatraz mamy 3 wystąpienia litery a itd. (małe i wielkie litery są traktowane jednakowo). Poniższy kod C++ wykonuje te akcje.
Listing 2.3. Funkcja main CharHistogram (w CppBookCode, plik letter_histogram.cpp)
1
#include <iostream>
2
#include <string>
3
#include <vector>
4
5
// Wylistowanie ich w tym miejscu pozwala pominąć std::
6
using std::cout, std::cin, std::endl;
7
using std::string, std::vector;
8
9
10
int main()
11
{
12
// Utwórz slot dla każdej litery, od 'a' do 'z'
13
// Początkowo dla każdej z nich ustaw licznik na 0
14
vector histogram( 'z' - 'a' + 1, 0 );
15
16
string in_str;
17
18
cin >> in_str;
19
in_str = "AGH University of Science and Technology";
20
21
for( auto c : in_str ) // c przyjmuje kolejne litery z in_str
22
if( std::isalpha( c ) ) // isalpha( c ) zwraca true, jeśli c jest alfanumeryczne
23
++ histogram[ std::tolower( c ) - 'a' ]; // ++ dodaje 1 do pozycji litery
24
25
cout << endl;
26
27
for( auto c { 'a' }; c <= 'z'; ++ c ) // c przyjmuje kody od 'a' do 'z'
28
cout << c << " "; // Wypisz wszystkie znaki od 'a' do 'z'
29
30
cout << endl;
31
32
for( auto h : histogram ) // h przyjmuje kolejne wartości histogramu
33
cout << h << " "; // Wypisz wartości histogramu
34
}
2.6.2. Uruchomienie kodu C++ za pomocą kompilatora dostępnego w Internecie
Zanim wyjaśnimy, jak działa ten kod, zobaczmy, co robi. W jaki sposób możemy go uruchomić? Najprostszy sposób polega na otwarciu jednej ze stron internetowych z kompilatorem C++, takich jak Coliru, przeklejenie kodu i kliknięcie przycisku "Compile, link and run...". Spójrzmy na zrzut ekranu na rysunku 2.10. Zważywszy na przykłady z wcześniejszych podrozdziałów, zbudowanie samodzielnej aplikacji również nie powinno stanowić problemu.
Rysunek 2.10. Środowisko online kompilatora Coliru (http://coliru.stacked-crooked.com) uruchomione w przeglądarce Mozilla Firefox, wraz ze skopiowanym i wklejonym do okienka edytora kodem listingu 2.3. W lewym dolnym rogu znajdziemy wiersz poleceń pozwalający na zbudowanie i uruchomienie programu. W prawym dolnym rogu znajdują się przyciski wywołujące określone działania
Po uruchomieniu otrzymujemy następujący wynik:
a b c d e f g h i j k l m n o p q r s t u v w x y z
2 0 3 1 4 1 2 2 3 0 0 1 0 4 3 0 0 1 2 2 1 1 0 0 2 0
Znaczy to, że każda litera jest powiązana z liczebnością swoich wystąpień w zdaniu wejściowym.
2.6.3. Kod histogramu - wyjaśnienie
Podzielmy teraz kod z listingu 2.3 i wyjaśnijmy, co robi, wiersz po wierszu. W wierszach [1-3] wywołane jest #include <nazwa_pliku>, gdzie nazwa_pliku odpowiada jakiemuś plikowi nagłówka. Jak wspomniano wcześniej, nagłówki zawierają napisany wcześniej kod, który możemy wykorzystać, aby uprosić swoje programistyczne życie. Określenie, jaki nagłówek wybrać dla danego komponentu języka, jest niekiedy trudne - najprościej jest sprawdzić to w Internecie. Tu dołączamy iostream dla obiektów std::cout i std::cin, które reprezentują - odpowiednio - ekran i klawiaturę. Następnie wprowadzony zostaje plik string, co pozwala wykorzystać klasę std::string do przechowywania zwykłego tekstu. Na koniec, tak jak zostało to pokazane na rysunku 2.9, dołączony zostaje plik vector zawierający definicję klasy std::vector pozwalającej na przechowanie histogramu.
1
#include <iostream>
2
#include <string>
3
#include <vector>
4
Wiersze [6-7] zawierają dyrektywy using. Są one opcjonalne, ale pozwalają nam zaoszczędzić sobie pisania na klawiaturze, ponieważ zamiast std::cout możemy pominąć prefiks std:: i ograniczyć się do zwięźlejszego cout:
5
// Wylistowanie ich w tym miejscu pozwala pominąć std::
6
using std::cout, std::cin, std::endl;
7
using std::string, std::vector;
Sam program zaczyna się w wierszu [10]. Program w C++ składa się z funkcji main i wszystkich funkcji wywoływanych z wewnątrz niej. Funkcja jest ograniczona przez nawiasy klamrowe, takie jak { w wierszu [11] i } w wierszu [34]. main w wierszu [10] zwraca obiekt typu int, ale nie korzystamy tu z tej możliwości (więcej o main można dowiedzieć się z dodatku A.2.2.).
8
9
10
int main()
11
{
Teraz znajdujemy się wewnątrz main. W wierszu [14] obiekt histogram typu vector zostaje zdefiniowany i zainicjalizowany przy użyciu dwóch parametrów (obie formy - std::vector i vector - są w tym kontekście w porządku). Pierwszy z nich to 'z' - 'a' + 1. Jako że 'z' i 'a' to liczbowe wartości kodowe ostatniej i pierwszej litery angielskiego alfabetu, odjęcie tej drugiej od tej pierwszej i dodanie 1 daje łącznie 26 liter. Nieco później zobaczymy, jak w jednolity sposób radzić sobie z małymi i wielkimi literami. Dzięki temu powstaje struktura składająca się z 26 liczników, co zostało pokazane na rysunku 2.9. Drugi parametr inicjalizujący dla histogram to 0 - ustawia on początkową wartość liczników na 0. vector jest bardzo użyteczną strukturą danych, która może zawierać wiele obiektów, ale o tym samym typie.
W wierszu [16] tworzony jest obiekt string o nazwie in_str (raz jeszcze możemy pominąć prefiks std::). Jest to również rodzaj wektora, ale wyspecjalizowany w przechowywaniu i przetwarzaniu znaków (tekstu):
12
// Utwórz slot dla każdej litery, od 'a' do 'z'
13
// Początkowo dla każdej z nich ustaw licznik na 0
14
vector histogram( 'z' - 'a' + 1, 0 );
15
16
string in_str;
17
Obiekt in_str jest początkowo pusty, ale nie trwa to długo. W wierszu [18] czekamy, aż użytkownik wprowadzi w oknie terminala zdanie i wciśnie klawisz Enter. Byłoby to wystarczające, ale jako że uruchamiamy ten program w kompilatorze online, który nie przyjmuje danych wejściowych wprowadzanych przez użytkownika, w wierszu [19] zakodowaliśmy do in_str na stałe pewien przykładowy tekst:
18
cin >> in_str;
19
in_str = "AGH University of Science and Technology";
Teraz czas przejść do działania. Musimy mieć dostęp do wszystkich liter w obiekcie in_str i inkrementować histogram na pozycjach pojemników odpowiadających poszczególnym literom. Tak więc jeśli literą jest 'a', indeks powinien wynosić 0, jeśli 'b', indeks wynosi 1, jeśli 'z' - 25 itd. Zauważmy, że dla N elementów indeksy biegną od 0 do N - 1. Aby uzyskać dostęp do każdej litery, w wierszu [21] utworzona jest pętla for. W niej auto c znaczy, że c przyjmować będzie wartość kolejnych liter ze zmiennej in_str, która znajduje się po drugiej stronie dwukropka :. Dzięki auto nie musimy zawracać sobie głowy typem c - zostanie on automatycznie wywnioskowany przez kompilator na podstawie typu liter przechowywanych w in_str.
Wiersz [23] działa pod nadzorem najbliższej pętli for. Tak więc dla każdej litery c odnajdujemy odpowiadający jej indeks w wektorze histogramu, odejmując kod 'a'. Następnie ten wpis jest zwiększany o 1 poprzez wywołanie operatora ++. Aby wszystkie małe i wielkie litery były traktowane tak samo, każda literowa wartość zmiennej c jest konwertowana na małą dzięki wywołaniu funkcji std::tolower (tu musimy explicite posłużyć się prefiksem std::, ponieważ std::tolower nie zostało wylistowane za pomocą using). Aby zresetować pozycję znaku zachęty w wyjściowym oknie do początku kolejnej linii, w wierszu [25] obiekt endl jest przesyłany do obiektu ekranu cout.
20
21
for( auto c : in_str ) // c przyjmuje kolejne litery z in_str
22
if(std::isalpha( c ) ) // isalpha( c ) zwraca true, jeśli c jest alfanumeryczne
23
++ histogram[ std::tolower( c ) - 'a' ];// ++ dodaje 1 do pozycji litery
24
25
cout << endl;
26
Wiersze [27-28] prezentują kolejną pętlę for. Jej celem jest wypisanie wszystkich liter na ekranie. Tym razem for składa się jednak z trzech pól oddzielonych średnikiem ;. Jej pierwsza część - auto k { 'a' } - wykonywana jest tylko raz. Tworzy ona obiekt k o początkowej wartości 'a'. Druga część - warunek k <= 'z' - jest sprawdzany w każdym przebiegu; jeśli jest spełniony, wykonywany jest wiersz [28], który po prostu wypisuje literę reprezentowaną przez k, a następnie spację. Następnie wykonywana jest trzecia część pętli for. W naszym przykładzie jest to wyrażenie ++ k, które przesuwa k o 1, czyli do kolejnego kodu literowego. Następnie pętla powtarza się od miejsca, w którym sprawdzany jest warunek. Jeśli jednak w którymkolwiek przebiegu warunek nie zostanie spełniony, tzn. jego sprawdzenie da wartość false, pętla zostanie przerwana i wykonana zostanie linia kodu znajdująca się tuż po pętli. Jeśli w każdym przebiegu pętli musi zostać wykonana więcej niż jedna instrukcja, instrukcje można pogrupować w bloki za pomocą nawiasów klamrowych {}.
27
for( auto k { 'a' }; k <= 'z'; ++ k ) // c przyjmuje kody od 'a' do 'z'
28
cout << k << " "; // Wypisz wszystkie znaki od 'a' do 'z'
29
I wreszcie, pętla w wierszach [32-33] wyświetla obliczone wartości histogramu. Raz jeszcze wykorzystana zostaje pierwsza postać pętli for, więc w każdym przebiegu h przyjmuje wartość kolejnych elementów przechowywanych w obiekcie histogram.
30
cout << endl;
31
32
for( auto h : histogram ) // h przyjmuje kolejne wartości histogramu
33
cout << h << " "; // Wypisz wartości histogramu
34
}
I to tyle. Jak dalej możemy wykorzystać ten kod? Można go skopiować, zmienić coś i się nim pobawić. Czytajmy dalej, jako że wszystkie użyte tu konstrukty zostaną wyjaśnione w kolejnych rozdziałach. W tym podrozdziale nauczyliśmy się następujących elementów programowania w języku C++:
- Jak zaimplementować prosty program w C++.
- Do czego wykorzystywana jest funkcja int main().
- Jakie pliki nagłówkowe należy dołączyć za pomocą dyrektywy #include i dlaczego.
- Jakie dyrektywy using należy umieścić na początku programu.
- Jak zdefiniować prostą tablicę elementów za pomocą std::vector.
- Jak wprowadzić tekst z klawiatury i jak przechować go w obiekcie std::string.
- Jak zautomatyzować dedukcję typu obiektu za pomocą słowa kluczowego auto.
- Jak na dwa sposoby zaimplementować pętlę za pomocą instrukcji for.
- Jak sprawdzić warunki logiczne za pomocą wyrażenia if.
- W jaki sposób wywołać predefinowane funkcje umożliwiające manipulację tekstem, takie jak std::isalpha i std::tolower.
W następnych rozdziałach doszlifujemy te techniki na kolejnych przykładach.
2.7. Podsumowanie
Do zapamiętania
- Przeanalizuj problem, nim przystąpisz do projektowania.
- Stwórz odpowiedni projekt, nim przystąpisz do implementacji. Preferuj podejście od ogółu do szczegółu.
- Zrozum działanie sprzętu i pamiętaj o jego ograniczeniach. Poznaj również swoje narzędzia służące do tworzenia oprogramowania.
- Możesz wykorzystać projekty z tego rozdziału w charakterze ogólnego planu dla prostych aplikacji w C++.
- Wszędzie tam, gdzie to możliwe, korzystaj z obiektów z biblioteki standardowej.
- Dbaj o to, by obiekty znajdowały się w dobrze określonym stanie.
- Dokumentuj swój kod za pomocą zwięzłych, wymownych komentarzy.
- Zrozum, jak działa każda linijka twojego kodu.
- Stale ulepszaj swoje umiejętności programistyczne. Czytaj książki i blogi. Zdobywaj wiedzę na temat środowiska programistycznego.
Pytania i ćwiczenia
1. Największy wspólny dzielnik (ang. greatest common divisor, w skrócie GCD) dwóch dodatnich liczb całkowitych a i b jest największą liczbą całkowitą, która dzieli każdą z nich bez reszty. Problem ten można rozwiązać dzięki algorytmowi Euklidesa (https://pl.wikipedia.org/wiki/Algorytm_Euklidesa):
Algorytm 2.2. Algorytm Euklidesa pozwalający odnaleźć największy wspólny dzielnik dwóch liczb
Wejście:
Dwie dodatnie liczby całkowite: a,b
Wyjście:
GCD( a, b )
1
while b != 0 (przebiegaj pętlę, dopóki b jest różne od 0)
2
tmp ? b (skopiuj b do tymczasowej zmiennej tmp)
3
b ? a % b (skopiuj resztę z dzielenia a przez b do b)
4
a ? tmp (skopiuj wartość tmp do a)
5
Return: a (zwróć a zawierające największy wspólny dzielnik)
a. Na kartce oblicz jakiś przykład, dajmy na to, przyjmując, że a = 255, a b = 221.
b. Zaimplementuj algorytm 2.2. Wskazówka: aby zaimplementować pętlę, wykorzystaj instrukcję while (b != 0) lub for ( ; b !=0 ; ) {zapętl_instrukcje_z_wierszy 2-4 }.
c. Zweryfikuj działanie swojego programu, ustawiając inne wartości a i b.
2. Przeanalizuj poniższy algorytm równego podziału służący do obliczenia przybliżonego pierwiastka kwadratowego jakiejś wartości całkowitej.
a. Napisz implementację algorytmu 2.3.
b. Porównaj zwrócone wartości z tymi, jakie daje kod z listingu 2.1.
Algorytm 2.3. Algorytm równego podziału służący do obliczania przybliżenia pierwiastka kwadratowego z liczby całkowitej
Wejście:
Wartość x będąca liczbą całkowitą
Wyjście:
Przybliżenie pierwiastka kwadratowego z x
1
lower_bnd ? 1
upper_bnd ? x / 2 (dla x > 4 pierwiastek nie może być większy)
2
while upper_bnd >= lower_bnd (biegnie tak długo, jak długo warunek jest spełniony)
3
mid_val ? (lower_bnd + upper_bnd ) / 2 (oblicz wartość środkową)
4
if mid_val * mid_val > x (sprawdź, która połowa)
5
upper_bnd ? mid_val - 1 (obniż górną granicę)
6
else
7
lower_bnd ? mid_val + 1 (przesuń dolną granicę)
8
Return: (lower_bnd + upper_bnd ) / 2 (zwróć wartość środkową)
3. Algorytm równego podziału posiada też inne zastosowania. Jest pomocny w zadaniach związanych z przeszukiwaniem po wartościach monotonicznych (https://pl.wikipedia.org/wiki/Metoda_równego_podziału). Skorzystaj z algorytmu równego podziału, by odnaleźć pierwiastek funkcji (tj. jej punkt zerowy).
4. Mogą pojawić się problemy przy wprowadzaniu wartości z wykorzystaniem obiektu std::cin. Na przykład w linii [14] listingu 2.2 oczekiwana jest wartość liczbowa, ale użytkownik może np. wprowadzić abc. Aby zapobiec takim błędom, status operacji wczytywania może być sprawdzany tak jak w poniższym fragmencie kodu:
if( ! ( cin >> C_0 ) )
{
cout << "Błąd w trakcie wprowadzania wartości.\n" << endl;
return -1;
}
Działa to, ponieważ wyrażenie cin >> C_0 zostaje przekonwertowane na typ bool przyjmujący wartości true lub false zależnie od tego, czy operacja - odpowiednio - powiodła się czy nie. Następnie operator ! neguje ten wynik, tak więc jeśli zwrócone zostało false, wykonany zostaje kod wewnątrz if i program się kończy.
Korzystając z tego sposobu, zaktualizuj wiersze odpowiedzialne za wczytywanie wartości w listingach 2.2 oraz 2.3.
5. Przeprowadź refaktoryzację kodu źródłowego CharHistogram z listingu 2.3 tak, aby wyświetlał histogram w postaci pionowych słupków składających się z symboli *, a nie liczbę wystąpień.
6. Wielomian drugiego rzędu można wyrazić następująco:
(2.4)
gdzie a, b i c oznaczają współczynniki rzeczywiste. Pytanie brzmi, czy istnieją takie wartości x, które spełniają to równanie. Jeśli istnieją, nazywane są pierwiastkami wielomianu drugiego stopnia. Przypomnijmy, że aby odpowiedzieć na to pytanie, wystarczy obliczyć d - współczynnik delta - w następujący sposób:
(2.5)
Jeśli d ? 0, możemy obliczyć rozwiązanie równania (2.4) (jego pierwiastki) w następujący sposób:
(2.6)
W innym przypadku pierwiastki nie istnieją. Napisz program w C++, który prosi użytkownika o podanie trzech współczynników a, b i c, określa, czy pierwiastki istnieją i - o ile to możliwe - oblicza je. W pierwszej kolejności przepisz poprzednie równania na odpowiadające im wyrażenia w C++, a następnie je zaadaptuj.
7. Zaimplementuj grę "Sekretna komnata" - jej plansza o rozmiarach 10 × 10 wygląda następująco.
Możemy przesuwać gracza 'P' w górę, w dół, w lewo lub w prawo, ale tylko o jedną pozycję naraz (np. wciskając klawisze 'U', 'D', 'L' i 'R'). Wygrana następuje, gdy uda się graczem 'P' nastąpić na skarb 'T'. Jeśli jednak gracz nastąpi na którąś z pułapek 'X' - przegrywamy. Co więcej, w każdej turze 'X' może losowo zmienić swoje położenie o jedną pozycję. Uważajmy też, by nie wyjść poza planszę.
8. Oblicz sumę dwóch dodatnich wartości całkowitych. Suma, którą należy obliczyć, jest jednak podana jako łańcuch znaków, np. "123 + 37", "78+ 99" itd. Napisz program, który wykonuje następujące kroki:
- Prosi użytkownika o wprowadzenie łańcucha znaków.
- Eliminuje z niego dodatkowe spacje.
- Wydobywa dwa podłańcuchy reprezentujące dwa argumenty, takie jak "123" i "37".
- Wylicza wartości tych dwóch ciągów w postaci liczb całkowitych, tak że "123" zostaje przekształcone na wartość 123 itd.
- Wypisuje sumę tych dwóch wartości.
Możesz też wzbogacić swoje rozwiązanie o obsługę możliwych błędów.
9. Istnieje wiele sposobów na porównywanie tekstów. Prosty sposób polega na porównaniu dwóch histogramów składających się na nie liter. Dwa histogramy tej samej długości można porównać, sumując kwadraty różnic odpowiadających sobie wartości pojemników.
- Rozszerz program z listingu 2.3 w taki sposób, by obliczał i porównywał histogramy dwóch tekstów.
- Przetestuj swoją procedurę, porównując kilka paragrafów.
- Wyniki będą lepsze, jeśli histogramy zostaną znormalizowane przed ich porównaniem.
Po normalizacji suma wszystkich pojemników w histogramie wynosi 1.0. Aby znormalizować histogram, podziel wartość każdego z jego pojemników przez łączną sumę wszystkich pojemników w tym histogramie. Wskazówka: utwórz wektor histogramu, aby przechować wartości zmiennoprzecinkowe, np. w wierszu [14] listingu 2.3 zmień wartość inicjalizującą z 0 na 0.0.
