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:

#include <regex>

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)

regex pattern {R"((\w+)\s+(\d{1,3}))"};

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.

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;
}

Oprócz regex_match, dostępne są też funkcje regex_search i regex_replace. Zapoznać się z dokumentacją wyrażenia regularne

Statyczne tablice ++

W C++11 została wprowadzony dodatkowy kontener implementujący statyczną tablicę w pliku nagłówkowym

#include <array>

Deklaracja nowej tablicy:

//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);

Po tablicy można iterować bez problemów:

for (auto v : tab) {
  cout << "value: " << v << endl
}

Zbiory

Zbiór, czyli kolekcja niepowtarzalnych elementów. Dostępna jest po dołączeniu:

#include <set>

Przykład użycia zbioru:

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";
}

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. Dokumentacja do zbioru.

Słowo kluczowe using

Za pomocą słowa kluczowego using w C++11 można wprowadzić kilka różnych definicji.

  1. selektywny import symboli do globalnej przestrzeni nazw
    using ::std::unique_ptr;
  2. definicja nowego aliasu dla typu (odpowiednik typedef)
    #include <string>
    using Url = std::string;
     
    bool IsValid(const Url &url);
  3. import wszystkich symboli z danej przestrzeni nazw (niezalecane)
    using namespace std;

Inteligentne wskaźniki

Zapoznać się z tekstem 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

#include <memory>

Definiowanie wskaźnika i przydzielenie mu nowego obiektu Type:

unique_ptr<Type> p = make_unique<Type>();

Można też zapisać to krócej z wykorzystaniem auto:

auto p = make_unique<Type>();

Wskaźnika można używać jak zwykłego wskaźnika:

unique_ptr<Type> p = make_unique<Type>();
cout<<p->value;

Unikalny wskaźnik jest jedynym właścicielem pamięci, dlatego jeśli chcemy przypisać obiekt unique_ptr do innego musimy jawnie przenieść element:

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;
}

Wtedy funkcja, która jako parametr przyjmuje unique_ptr rząda ona tak na prawdę przekazania zarządzania nad obiektem:

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
}

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.

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

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:

Module.h
#ifndef MODULE_H
#define MODULE_H
 
#include <string>
 
namespace mymodule {
std::string ToString(int value);
}
#endif  // MODULE_H
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();  
}
}
main.cpp
#include "Module.h"
 
int main() {
   auto str = mymodule::ToString(100);
}

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.

std::pair<std::string, int> p {"abc",17};
std::tuple<std::string,double,std::string> t3 {"Mam",17.3,"lat"};

W celu poprawy czytelności kodu, można wykorzystać using np.

using Carry = bool;
using Code = char;
std::pair<Carry,Code> NextCode(Code c);

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:

  1. 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)
    std::string ToString(const Type &t);
  2. wyjątek stanowią argumenty typów prostych takich jak int, double, bool, itd.. które przekazujemy przez wartość
    std::string ToString(bool b);
  3. jeśli chcemy zwrócić z funkcji dwa lub więcej elementów można wykorzystać typy std::tuple i std::pair
    std::pair<bool, char> NextChar(char c);
  4. jeśli zachodzi potrzeba zmodyfikowania argumentu wewnątrz funkcji przekazujemy argument przez wskaźnik(klasyczny)
    void Modify(Type *t);

    Konwencja jest znacznie czytelniejsza od zastosowania niestałej referencji z punktu widzenia klienta:

    Type t; 
    Modify(&t);

    Kod przekazuje jawnie adres co sygnalizuje możliwość zmodyfikowania obiektu przez funkcję.

Ćwiczenia

  1. [2 punkty] 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:
      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);
    • Przestrzeń nazw: tinyurl
    • Importy:
      #include <utility>
      #include <string>
      #include <array>
      #include <memory>
  2. [2 plusy] 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:
      unsigned int ToMinutes(std::string time_HH_MM);
      unsigned int MinimalTimeDifference(std::vector<std::string> times);
    • Przestrzeń nazw: minimaltimedifference
    • Importy:
      #include <vector>
      #include <sstream>
      #include <regex>
      #include <cmath>
  3. [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:
      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);
    • Przestrzeń nazw: ccounter
    • Importy:
      #include <string>
      #include <memory>
      #include <map>
  4. [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:
      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);
    • Przestrzeń nazw: datastructures
    • Importy:
      #include <ostream>
      #include <string>
      #include <memory>
pl/dydaktyka/jimp2/2017/labs/pamiec2.txt · ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0