[[
✎ pl:dydaktyka:jimp2:2017:labs:pamiec2
]]
aiWiki
Pokaż stronę
Ostatnie zmiany
Indeks
Zaloguj
Ta strona jest tylko do odczytu. Możesz wyświetlić źródła tej strony ale nie możesz ich zmienić.
======Dynamiczne zarządzanie pamięcią 2====== ===== Wyrażenia regularne ===== Biblioteka wyrażeń regularnych została dołączona do standaradu C%%++%%11 i jest dostępna w pliku nagłówkowym: <code cpp>#include <regex></code> Utworzenie nowego wyrażenia regularnego jest jeszcze prostsze z surowymi łańcuchami znaków (w których nie interpretuje się ukośnika jako znaku specjalnego) <code cpp> regex pattern {R"((\w+)\s+(\d{1,3}))"}; </code> Powyższe wyrażenie regularne dopasuje się do wyrazu składającego się z co najmniej jednej litery **\w**, po którym następuje odstęp złożony z co najmniej jednego białego znaku **\s** i wreszcie ciągu składającego się z od 1 do 3 cyfr **\d**. Dodatkowo zostały zastosowane grupy przechwytujące (kolejne grupy to kolejne nawiasy okrągłe), dzięki którym można się odnieść do fragmentów dopasowania. <code cpp> regex pattern {R"((\w+)\s+(\d{1,3}))"}; string line {"Adam 789"}; smatch matches; if (regex_match(line, matches, pattern)) { cout<<"udało się dopasować do linii: "<<line<<endl; cout<<"zerowa grupa przechwytująca to całe dopasowanie: "<<matches[0]<<endl; cout<<"pierwsza grupa przechwytująca to napis: "<<matches[1]<<endl; cout<<"druga grupa przechwytująca to liczba: "<<matches[2]<<endl; } </code> Oprócz **regex_match**, dostępne są też funkcje **regex_search** i **regex_replace**. Zapoznać się z dokumentacją [[http://en.cppreference.com/w/cpp/regex|wyrażenia regularne]] ===== Statyczne tablice ++ ===== W C%%++%%11 została wprowadzony dodatkowy kontener implementujący statyczną tablicę w pliku nagłówkowym <code cpp>#include <array></code> Deklaracja nowej tablicy: <code cpp> //inicjalizacja tablicy intów o rozmiarze 3 za pomocą zadanych wartości: array<int, 3> tab {1,2,3}; //alternatywnie jednorodna inicjalizacja tablicy boolów o romiarze 10: array<bool, 10> flags; flags.fill(false); </code> Po tablicy można iterować bez problemów: <code cpp> for (auto v : tab) { cout << "value: " << v << endl } </code> ===== Zbiory ===== Zbiór, czyli kolekcja niepowtarzalnych elementów. Dostępna jest po dołączeniu: <code cpp>#include <set></code> Przykład użycia zbioru: <code cpp> set<int> s {4,5,6,7}; if (s.find(5) != s.end()) { cout<<"5 jest elementem zbioru"<<endl; } if (s.find(17) != s.end()) { cout<<"17 jest elementem zbioru"<<endl; } else { cout<<"17 nie jest w zbiorze"; } </code> W przypadku użycia zbioru, sprawdzenie, czy element znajduje się w zbiorze ma złożoność logarytmiczną w przeciwieństwie do liniowej złożoności wyszukiwania w tablicy. [[http://en.cppreference.com/w/cpp/container/set|Dokumentacja do zbioru]]. =====Słowo kluczowe using===== Za pomocą słowa kluczowego using w C%%++%%11 można wprowadzić kilka różnych definicji. - selektywny import symboli do globalnej przestrzeni nazw <code cpp> using ::std::unique_ptr; </code> - definicja nowego aliasu dla typu (odpowiednik **typedef**) <code cpp>#include <string> using Url = std::string; bool IsValid(const Url &url); </code> - import wszystkich symboli z danej przestrzeni nazw (niezalecane) <code cpp> using namespace std; </code> ===== Inteligentne wskaźniki ===== Zapoznać się z tekstem [[http://umich.edu/~eecs381/handouts/C++11_smart_ptrs.pdf|Smart Pointers]]. Inteligentne wskaźniki automatycznie zarządzają dostępem do powierzonej im pamięci i gdy pamięć nie jest już używana zostaje automatycznie zwolniona. Opisane poniżej funkcjonalności weszły w standardzie C++14. ==== unique_ptr ==== Najprostszy z inteligentnych wskaźników. Jedyny właściciel pamięci, gdy zmienna traci zakres pamięć jest automatycznie zwolniona. Definicja znajduje się w pliku nagłówkowym <code cpp>#include <memory></code> Definiowanie wskaźnika i przydzielenie mu nowego obiektu Type: <code cpp>unique_ptr<Type> p = make_unique<Type>();</code> Można też zapisać to krócej z wykorzystaniem auto: <code cpp>auto p = make_unique<Type>();</code> Wskaźnika można używać jak zwykłego wskaźnika: <code cpp>unique_ptr<Type> p = make_unique<Type>(); cout<<p->value;</code> Unikalny wskaźnik jest jedynym właścicielem pamięci, dlatego jeśli chcemy przypisać obiekt unique_ptr do innego musimy jawnie przenieść element: <code cpp> unique_ptr<int> origin = make_unique<int>(3); //Błąd kompilacji: unique_ptr<int> new_owner = origin; //Przeniesienie odpowiedzialności: unique_ptr<int> real_new_owner = move(origin); if (oring == nullptr) { cout<<"W tym momencie utworzony obiekt o wartości 3 już nie należy do origin"<<endl; } </code> Wtedy funkcja, która jako parametr przyjmuje unique_ptr rząda ona tak na prawdę przekazania zarządzania nad obiektem: <code cpp> unique_ptr<int> GiveMeItForASec(unique_ptr<int> p) { ++(*p); return p; } void foo() { auto ptr = make_unique<int>(99); //BLAD KOMPILACJI: auto new_ptr = GiveMeItForASec(ptr); //OK auto new_ptr = GiveMeItForASec(move(ptr)); //TERAZ ptr nie zawiera nic } </code> Wciąż jednak można pozostawić właściciela w spokoju i przekazać unique_ptr przez stałą referencję lub wskaźnik (druga opcja brzmi dziwnie, ale ujednolica konwencję, patrz niżej). ==== shared_ptr ==== Innym typem wskaźnika jest współdzielony wskaźnik, którego można współdzielić z innymi obiektami tego typu i pamięć zostanie zwolniona w momencie, gdy ostatni wskaźnik przestanie istnieć. Jest to możliwe, dzięki zliczaniu ilości odwołań do wskazanego fragmentu pamięci, które się odbywa automatycznie. <code cpp> shared_ptr<int> p = make_shared<int>(78); //poniższa linia jest poprawna shared_ptr<int> another = p; //W tym momencie oba wskaźniki pokazują na ten sam obszar pamięci, a wewnętrzny licznik odwołań wynosi 2 </code> Minusem wykorzystania współdzielonych wskaźników inteligentnych jest większe zużycie pamięci (gdzieś musi być przechowany licznik odwołań), dlatego z tych wskaźników zaleca się korzystać w ostateczności jeśli zależy nam na minimalizowaniu zużycia pamięci. Z drugiej strony jeśli nie zależy nam na pamięci, a z jakiegoś dziwnego powodu wciąż chcemy pisać aplikację w C%%++%% 8-), wykorzystanie shared_ptr w większości przypadków powinno rozwiązać problemy z wyciekami pamięci. ==== weak_ptr ==== Ten wskaźnik jest dodany w celu rozwiązania problemu cyklicznych odwołań współdzielonych wskaźników wzajemnie na siebie (wtedy licznik odwołań nigdy nie spadnie do zera i pamięć nigdy nie zostaje zwolniona). Dokładniejszy opis w tekście podanym w literaturze. ===== Przestrzenie nazw ===== Przestrzenie nazw porządkują definicje symboli i pozwalają wykluczyć konflikty pojęć z różnych kontekstów przypadkowo tak samo nazywające się. Symbole to nazwy metod, nazwy zmiennych globalnych, nazwy struktur i klas, nazwy typów, itp... Definicja nowej przestrzeni nazw może wyglądać następująco: <file cpp Module.h> #ifndef MODULE_H #define MODULE_H #include <string> namespace mymodule { std::string ToString(int value); } #endif // MODULE_H </file> <file cpp Module.cpp> #include <string> #include <sstream> #include "Module.h" namespace mymodule { using ::std::string; using ::std::stringstream; string ToString(int value) { stringstream ss; ss<<value; return ss.str(); } } </file> <file cpp main.cpp> #include "Module.h" int main() { auto str = mymodule::ToString(100); } </file> ===== Typ pary i krotki ===== Typ pary i krotki stanowi w C%%++%%11 odpowiednik anonimowej struktury, którą można użyć w dowolnym miejscu kodu, bez potrzeby jej definiowania. Np.<code cpp> std::pair<std::string, int> p {"abc",17}; std::tuple<std::string,double,std::string> t3 {"Mam",17.3,"lat"}; </code> W celu poprawy czytelności kodu, można wykorzystać **using** np.<code cpp> using Carry = bool; using Code = char; std::pair<Carry,Code> NextCode(Code c);</code> ===== Przekazywanie argumentów do funkcji ===== Argumenty do funkcji można przekazywać w C%%++%% na wiele różnych sposobów, natomiast należy brać pod uwagę czytelność zarówno kodu klienta (wywołujący metodę), jak i kod implementujący metodę. Stąd na laboratoriach będziemy korzystać z następującej konwencji: - argumenty o typie **Type** do funkcji przekazujemy przez **const Type &** w celu uniknięcia potencjalnego kopiowania pamięci (referencja), ale zabezpieczamy się przed modyfikacją argumentu w metodzie (cost) <code cpp>std::string ToString(const Type &t);</code> - wyjątek stanowią argumenty typów prostych takich jak int, double, bool, itd.. które przekazujemy przez wartość <code cpp>std::string ToString(bool b);</code> - jeśli chcemy zwrócić z funkcji dwa lub więcej elementów można wykorzystać typy **std::tuple** i **std::pair** <code cpp>std::pair<bool, char> NextChar(char c);</code> - jeśli zachodzi potrzeba zmodyfikowania argumentu wewnątrz funkcji przekazujemy argument przez wskaźnik(klasyczny) <code cpp>void Modify(Type *t);</code> Konwencja jest znacznie czytelniejsza od zastosowania niestałej referencji z punktu widzenia klienta:<code cpp>Type t; Modify(&t);</code> Kod przekazuje jawnie adres co sygnalizuje możliwość zmodyfikowania obiektu przez funkcję. ====== Ćwiczenia ====== - **[2 punkty] [[https://leetcode.com/problems/encode-and-decode-tinyurl/#/description|LeetCode]] Przygotwać bibliotekę wspomagającą tworzenie skróconych adresów URL. W tym celu może pomóc Zdefniowanie metody generotora, która jest testowana w pierwszym kroku testów. Na podstawie aktualnego stanu generatora (tablica 6 znaków) wyznacza następny stan. Tablicę stanu można dalej przechowywać w strukturze TinyUrlCodec** * Moduł: **tinyurl** * Pliki z implementacją: **TinyUrl.h/cpp** * Używana struktura danych: **TinyUrlCodec** * Sygnatury metod: <code cpp>std::unique_ptr<TinyUrlCodec> Init(); void NextHash(std::arrray<char, 6> *state); std::string Encode(const std::string &url, std::unique_ptr<TinyUrlCodec> *codec); std::string Decode(const std::unique_ptr<TinyUrlCodec> &codec, const std::string &hash);</code> * Przestrzeń nazw: **tinyurl** * Importy: <code cpp>#include <utility> #include <string> #include <array> #include <memory></code> - [2 plusy] [[https://leetcode.com/problems/minimum-time-difference/#/description|LeetCode]] Przygotować metodę, która wyliczy różnicę czasu pomiędzy czasami w formacie HH:MM lub H:MM w minutach. Z pośród wielu godzin należy znaleźć najmniejszą różnicę między dwoma godzinami. * Moduł: **minimaltimedifference** * Pliki z implementacją: **MinimalTimeDifference.h/cpp** * Sygnatury metod: <code cpp>unsigned int ToMinutes(std::string time_HH_MM); unsigned int MinimalTimeDifference(std::vector<std::string> times);</code> * Przestrzeń nazw: **minimaltimedifference** * Importy: <code cpp>#include <vector> #include <sstream> #include <regex> #include <cmath></code> - [2 plusy] Przygotować bibliotekę udostępniającą stukturę **Counter** umożliwiającą zliczanie obiektów i metody ją wspierające. Motoda Init ma za zadanie stworznie obiektu i ewentualne jego zaincjalizowanie, metoda Inc ma za zadanie zwiększenie licznika obiektu o 1, metoda Counts ma zwrócić aktulany licznik obiektów, jeśli nigdy nie był inkremetowany licznik dla tego klucza, powinno zostać zwrócone 0 i wreszcie metoda SetCountsTo ma za zadanie ustawienie licznika na zadaną wartość. * Moduł: **ccounter** * Pliki z implementacją: **CCounter.h/cpp** * Używana struktura danych: **Counter** * Sygnatury metod: <code cpp>std::unique_ptr<Counter> Init(); void Inc(std::string key, std::unique_ptr<Counter>* counter); int Counts(const std::unique_ptr<Counter> &counter, std::string key); void SetCountsTo(std::string key, int value, std::unique_ptr<Counter> *counter);</code> * Przestrzeń nazw: **ccounter** * Importy: <code cpp>#include <string> #include <memory> #include <map></code> - **[3 punkty] Napisz bibliotekę wspierającą budowę drzew binarnych z wykorzystaniem wskaźników inteligentnych. ** * Moduł: **smarttree** * Pliki z implementacją: **SmartTree.h/cpp** * Używana struktura danych: **SmartTree** * Sygnatury metod: <code cpp>std::unique_ptr <SmartTree> CreateLeaf(int value); std::unique_ptr <SmartTree> InsertLeftChild(std::unique_ptr<SmartTree> tree, std::unique_ptr<SmartTree> left_subtree); std::unique_ptr <SmartTree> InsertRightChild(std::unique_ptr<SmartTree> tree, std::unique_ptr<SmartTree> right_subtree); void PrintTreeInOrder(const std::unique_ptr<SmartTree> &unique_ptr, std::ostream *out); std::string DumpTree(const std::unique_ptr<SmartTree> &tree); std::unique_ptr <SmartTree> RestoreTree(const std::string &tree);</code> * Przestrzeń nazw: **datastructures** * Importy: <code cpp>#include <ostream> #include <string> #include <memory></code>
pl/dydaktyka/jimp2/2017/labs/pamiec2.txt
· ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)
Pokaż stronę
Poprzednie wersje
Menadżer multimediów
Do góry