Dynamiczne zarządzanie pamięcią i operacje na plikach

Writing in C or C++ is like running a chain saw with all the safety guards removed

Do ukończenia tego laboratorium wymagana jest znajomość wskaźników i referencji z C. Jeżeli ktoś nie czuje się w tym temacie na siłach, w laboratorium Wskaźniki i referencje przygotowane zostało krótkie przypomnienie najważniejszych informacji.

Refaktoryzacja kodu

Refaktoryzacja polega na ulepszeniu kodu bez zmiany jego zachowania. Np. zmiany nazwy funkcji w celu wyjaśnienia jej działania (zamist bool pal(std::string s) lepszą nazwą będzie bool IsPalindrome(std::string single_word_phrase)) Refaktoryzacje mogą też przyspieszyć pisanie kodu, początkowo kod można napisać w postaci jednej dłużej metody a następnie powykrawać z niego podprocedury w celu poprawy jego czytelności i modułowości

void ScheduleAppointment(const std::string &customer, const std::string &room, const std::string &when) {
   std::regex valid_customer {R"(\w+ \w+)"};
  if ( !std::regex_match(customer,valid_customer) ) {
    return;
  }
  std::regex valid_room {R"([A-Z]-\d{3})"};
  if ( !std::regex_match(room,valid_room)) {
    return;
  }
  std::regex valid_when {R"(\d{2}:\d{2})"};
  if ( !std::regex_match(when,valid_when)) {
    return;
  }
 
  Room *found_room =  nullptr;
  for (auto &r : rooms) {
    if (r.Name() == room) {
      found_room = &r;
    }
  }
  ...
}

po refaktoryzacji kod mógłby wyglądać następująco:

bool IsValid(const std::string &str, const std::regex &validator) {
   return std::regex_match(str, validator);
}
...
bool IsValidCustomer(const std::string &customer) {
   std::regex valid_customer {R"(\w+ \w+)"};
   return IsValid(customer,valid_customer);
}
 
Room FindRoom(const std::string &room) {
   for (auto &r : rooms) {
    if (r.Name() == room) {
      return r;
    }
   } 
   return {};
}
 
void ScheduleAppointment(const std::string &customer, const std::string &room, const std::string &when) {
  if ( !IsValidCustomer(customer) ) {
    return;
  }
  if ( !IsValidRoom(room)) {
    return;
  }
  if ( !IsValidWhen(when)) {
    return;
  }
 
  Room found_room = FindRoom(room);
  ...
}

Zapoznać się z możliwościami automatycznej refaktoryzacji pod linkiem do 8 min 30 s.

Dynamiczne zarządzanie pamięcią

Często zdarza się, że nie jesteśmy w stanie z góry przewidzieć ile pamięci będzie potrzebował nasz program do poprawnego działania. Na przykład w prostym kalkulatorze macierzowym nie można z góry ustalić wymiarów tablicy przechowującej macierz ani z góry ustalić ile takich tablic-macierzy będzie występować w równaniu!

Jedynym rozwiązaniem jest tworzenie nowych macierzy o ustalonych wymiarach podczas działania programu.

Wskaźniki i alokacja pamięci

Wraz z dynamiczną alokacją pamięci idą w parze wskaźniki. Pamięć zawsze alokowana jest pod jakimś adresem. A zmienne przechowujące adres i pozwalające się dostać do danych w niej przechowywanych, to właśnie wskaźniki.

Operator new

Operator new jest ekwiwalentem znanej z C funkcji malloc ale dużo potężniejszym. Wynikiem zwracanym przez operator new jest wskaźnik do zaalokowanej pamięci

Przykład dynamicznego tworzenia zmiennych:

#include <iostream>
using namespace std;
 
int main(void){
   char* ptr = new char;    //Stworzy zmienną typu char
   int* tab = new int[10];  //Stworzy tablicę typu int o rozmiarze 10
 
   // NIEPOPRAWNIE!!!
   int** tab2d = new int[10][10];
}

Operator delete

Operator delete działa podobnie jak funkcja free znana z C. Pamięć w momencie kiedy nie jest już wykorzystywana przez program powinna być zwolniona. Przykład dynamicznego tworzenia i usuwania zmiennych:

#include <iostream>
using namespace std;
 
int main(void){
   char* ptr = new char;    //Stworzy zmienną typu char
   int* tab = new int[10];  //Stworzy tablicę typu int o rozmiarze 10
 
   // Tutaj znajdują się operacje na zmiennych
 
   delete ptr;
   delete [] tab;
 
   // NIEPOPRAWNIE!!
   // Jeśli tab2d jest poprawnie zaalokowaną tablica dwuwymiarową
   // nie można zwolnić pamięci w następujący sposób
   delete [][] tab2d;
}

Niestety należy pamiętać o tym by zwolnić pamięć przydzieloną inaczej uzyskujemy wyciek pamięci i program w trakcie działania zaczyna zużywać coraz więcej pamięci operacyjnej mimo, że już jej i tak nigdy nie użyje! Sprawa też nie jest taka prosta, bo nie zawsze wiadomo, czy pewne elementy nie są już na pewno przez nikogo używane.

Brak wartości

W C++11 nie używamy już makra NULL zostało dodane specjalne słowo kluczowe reprezentujące pusty wskaźnik nullptr

int *v = nullptr;
delete v;

Ale jest nadzieja - zautomatyzowane zarządzanie pamięcią część pierwsza

Jedną z możliwości automatycznego zarządzania pamięcią jest oddelegowanie tego zadania do kontenerów zdefiniowanych w bibliotece standardowej, które automatycznie zwolnią pamięć jeśli przestanie ona być używana.

Vector

Jednym z takich kontenerów jest tablica rozszerzalna vector, zapoznać się z dokumentacją uruchomić przykłady podane w dokumentacji przez run code i przyglądnąć się dokumentacji funkcji:

  • emplace_back
  • pop_back
  • clear

Przenalizować poniższy kod:

#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
void PrintVector(const vector<int> &v) {
    bool first = true;
    for(auto n : v) {
        if (!first) {
            cout<< ", ";
        } else {
            first = false;
        }
        cout << n;
 
    }
    cout<<endl;
}
 
int main()
{
    // Create a vector containing integers
    vector<int> v = {7, 5, 16, 8};
 
    cout << "initilized with 4 numbers"<<endl;
    PrintVector(v);
 
    // Add two more integers to vector
    v.emplace_back(25);
    v.emplace_back(13);
    cout << "after 2 more inserted"<<endl;
    PrintVector(v);
 
    //copy of the value inside vector
    for (auto n : v) {
        ++n;
    }
 
    cout << "BUT: after incrementation"<<endl;
    PrintVector(v);
 
    //reference to the value inside vector, therefore one can change the value
    for (auto &n : v) {
        ++n;
    }
    cout << "and again... can you spot the difference?"<<endl;
    PrintVector(v);
}

Run code

Map

Tablica asocjacyjna, która pozwala zaadresować dowolny element innym typem, niekoniecznie tylko liczbą naturalną.

#include <iostream>
#include <map>
 
using std::cout;
using std::endl;
using std::map;
 
void PrintMap(const map<char,int> &v) {
    bool first = true;
    for(const auto &n : v) {
        if (!first) {
            cout<< ", ";
        } else {
            first = false;
        }
        cout << n.first << " -> " << n.second;
 
    }
    cout<<endl;
}
 
int main()
{
    // Create a vector containing integers
    map<char, int> v = {{'a',17}, {'c',-2}, {'g',67}, {'z',13}};
 
    cout << "initilized with 4 numbers"<<endl;
    PrintMap(v);
 
    // Add two more integers to vector
    v.emplace('h',25);
    v.emplace('$',13);
    cout << "after 2 more inserted"<<endl;
    PrintMap(v);
 
    //copy of the value inside vector
    for (const auto &n : v) {
        //Compilation error
        //++n.second;
    }
 
    cout << "BUT: after incrementation"<<endl;
    PrintMap(v);
 
    //reference to the value inside vector, therefore one can change the value
    for (auto &n : v) {
        ++n.second;
    }
    cout << "and again... can you spot the difference?"<<endl;
    PrintMap(v);
}

Run code

Operacje na plikach

Operacje na plikach wykonywane są w C++ przy użyciu strumieni - analogicznie jak operacja czytania z klawiatury i wypisywania na ekran.

Należy pamiętać o tym, że każdy plik, który został otwarty, powinien zostać również zamknięty, kiedy korzystanie z niego nie jest już potrzebne.

Biblioteka fstream

Obiekty strumieni służące do odczytu i zapisu do pliku znajdują się w pliku nagłówkowym <fstream>. Biblioteka ta zawiera dwa obiekty strumieni analogiczne do obiektów cin i cout:

  • ifstream - służący do odczytu z pliku (input-file-stream)
  • ofstream - służący do zapisu do pliku (output-file-stream).

Czytanie z pliku

Przykład wczytywania pliku wyraz po wyrazie:

#include <iostream>
#include <fstream>
using namespace std;
 
int main(void){
  ifstream myfile("file.txt");
  char word[64];
 
  if(!myfile)
    cout << "Nie można otworzyć pliku!" << endl;
 
  while(myfile >> word)
    cout << word;
 
  myfile.close();
  return 0;
}

Przykład wczytywania pliku linia po linii:

#include <iostream>
#include <fstream>
using namespace std;
 
int main(void){
  ifstream myfile("file.txt");
  char line[256];
 
  if(!myfile)
    cout << "Nie można otworzyć pliku!" << endl;
 
  while(!myfile.eof()){
    myfile.getline(line,256);
    cout << line;
  }
 
  myfile.close();
  return 0;
}

Zapisywanie do pliku

Przykład dopisywania do pliku:

#include <iostream>
#include <fstream>
using namespace std;
 
int main () {
 
  // Aby zrozumieć zapis: ios_base::in | ios_base::app
  // Zobacz kolejny podrozdział
  ofstream myfile ("file.txt", ios_base::in | ios_base::app);
 
  if(!myfile)
    cout << "Nie można otworzyć pliku!" << endl;
 
  myfile << "Tekst zapisany w pliku" << endl;
 
  myfile.close();
 
  return 0;
}

Otwieranie pliku w różnych trybach

Plik można otworzyć w 6 różnych trybach; kombinacje trybów też są możliwe.

Wartość flagiZnaczenie
ios_base::app(append) Ustawia wskaźnik pozycji strumienia na samym końcu strumienia. Służy do dopisywania do pliku.
ios_base::ate(at end) Ustawia wskaźnik pozycji strumienia na samym końcu pliku.
ios_base::binary(binary) Traktuje strumień jako strumień binarny a nie tekstowy
ios_base::in(input) Umożliwia zapis do pliku
ios_base::out(output) Umożliwia odczyt z liku
ios_base::trunc(truncate) Jeśli otwierany pli posiadał jakąś zawartość, jest ona pomijana i wskaźnik pozycji w strumieniu jest ustawiany na początku pliku.

Otwieranie strumienia ifstream z opcją ios_base::out mija się z celem. Do strumieni, które mają służyć zarówno zapisowi jak i odczytowi, stosuje się ogólną postać strumienia o nazwie fstream.

  fstream file("file.txt", ios_base::in | ios_base::out | ios_base:app);

Ćwiczenia

  1. Zrefaktoryzować kod metod factorial, reverse i is_palindrome tak, żeby nawiązywały do konwencji, że nazwa funkcji jest pisana jako NazwaFunkcjiCamelCase, skorzystać z narzędzia do refaktoryzacji wbudowanego w CLion: najechać na metodę kursorem wybrać z menu Refactor→Rename… (SHIFT+F6).
  2. [1 plus] W sekcji Wskaźniki i alokacja pamięci zostało powiedziane, że nie można utworzyć tablicy wielowymiarowej prostym poleceniem int * *tab = new int[10][10]. Przeanalizuj rysunek poniżej i zastanów się dlaczego tak jest. Następnie napisz program który będzie pobierał od użytkownika wymiary tablicy i dynamicznie alokował pamięć dla niej. Napisz funkcję która będzie uzupełniała tablicę kolejnymi liczbami całkowitymi (tak jak na rysunku) i osobną funkcję do wyświetlania tablicy. Czy można do tego wykorzystać funkcje napisane na poprzednich laboratoriach nie modyfikując ich? Pamiętaj o poprawnym zwolnieniu pamięci! Tablica wskaźników. Zadanie zostało podzielone na kroki: (step1,step2,…). Ukończenie pierwszego i drugiego kroku jest wymagane do zaliczenia ćwiczenia.
    • Moduł: array2d
    • Pliki z implementacją: Array2D.h/cpp
    • Sygnatura metody:
      int **Array2D(int n_rows, int n_columns);
      void DeleteArray2D(int **array, int n_rows, int n_columns);
    • W kroku nr 3 należy przeprowadzić refaktoryzację metody Array2D
    • uruchomienie testów: ALT+SHIFT+F10 → lab1_reverse_string_tests
  3. [2 punkty] Napisz program, który będzie implementować algorytm szyfrujący Polibiusza. Program powinien przyjmować trzy parametry: nazwę pliku wejściowego, nazwę pliku wyjściowego oraz 1 w przypadku gdy plik wejściowy ma zostać zaszyfrowany lub 0, gdy ma zostać odszyfrowany. Wynik szyfrowania/deszyfrowania powinien znaleźć się w pliku wyjściowym podanym jako parametr.
    Przykład uruchomienia programu:
    ./program plik-tekst.txt plik-szyfr.txt 1
    • Moduł: polybius
    • Pliki z implementacją: Polybius.h/cpp
    • Sygnatury metod:
      std::string PolybiusCrypt(std::string message);
      std::string PolybiusDecrypt(std::string crypted);
    • Pliki nagłówkowe:
      #include <string>
  4. [2 plusy] Wykorzystując strukturę danych (struct) znaną jeszcze z języka C, należy zaimplementować listę jednokierunkową zdolną przechowywać liczby całkowite w swoich węzłach. UWAGA: jest to ćwiczenie tylko techniczne, w standardowej bibliotece istnieje forward_list zdolna przechowywać dowolny typ.
    • Moduł: simpleforwardlist
    • Pliki z implementacją: SimpleForwardList.h/cpp
    • Sygnatury metod:
      ForwardList *CreateNode(int value);
      void DestroyList(ForwardList *list);
    • Sygnatury metod z kroku drugiego i trzeciego:
      ForwardList *PushFront(ForwardList *list, int value);
      void Append(ForwardList *list, ForwardList *tail);
  5. [2 plusy + 2 punkty] Napisz program, który jest w stanie wyliczyć największy iloczyn k liczb z podanych n liczb na wejściu. Uwaga - Program ma mieć złożoność obliczeniową maksymalnie O(n k) - innymi słowy, przegląda tablicę tylko raz - od początku do końca i zwraca wynik (dla każdej napotkanej liczby może jednak wykonać k operacji) ! Do zaliczenia zadania wystarczy, że program przejdzie pierwszy etap, tzn. k jest ustalone na 2 (maksymalny iloczyn dokładnie dwóch liczb) i wszystkie podane liczby są nieujemne. Kolejne etapy komplikują problem, są za dodatkowe punkty.
    • Moduł: greatestproduct
    • Pliki z implementacją: GreatestProduct.h/cpp
    • Sygnatura metody:
      int GreatestProduct(const std::vector<int> &numbers, int k);
    • Pliki nagłówkowe:
      #include <vector>
    • Wskazówki:
      //po obiekcie vector można iterować w pętli for
      for (int v : numbers) {
        //zmienna v przyjuje kolejne wartości elementów zawartych w tablicy
      } 
      std::vector<int> another_vector; //utworzenie nowej tablicy rozszerzalnej
      another_vector.push_back(17); //wstawienie na sam koniec nowego elementu (pamięć jest przydzielana automatycznie!)
      if (anotehr_vector.size() > 0) //vector można odpytać o wielkość
    • W kroku nr 3 należy przeprowadzić refaktoryzację metody Array2D
  6. [3 punkty] Łamanie hasła (lub wersja interaktywna z kilkoma test cases: https://www.hackerrank.com/contests/projecteuler/challenges/euler059. W przypadku testów zostanie podany kryptogram (zaszyfrowana wiadomość), w postaci tablicy znaków (std::vector<char>), długość klucza (w prostszej wersji można założyć, że będzie równa 3) i słownik zawierający około 100 najpopularniejszych wyrazów języka angielskiego na podstawie
    • Moduł: xorcypherbreaker
    • Pliki z implementacją: XorCypherBreaker.h/cpp
    • Sygnatura metody:
      std::string XorCypherBreaker(const std::vector<char> &cryptogram,
                           int key_length,
                           const std::vector<string> &dictionary);
    • Pliki nagłówkowe:
      #include <string>
      #include <vector>
    • Wskazówki:
      #include <algorithm>
      using std::find;
      using std::vector;
      using std::string;
       
      vector<string> dictionary {"the","of"};
       
      //THERE ARE BETTER WAYS TO LOOK FOR A WORD BUT IT WORKS
      if (find(dictionary.begin(),dictionary.end(),"of") != dictionary.end()) {
         //FOUND!
      }
pl/dydaktyka/jimp2/2017/labs/pamiec-i-pliki.txt · ostatnio zmienione: 2017/07/17 08:08 (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