======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>