|
|
pl:dydaktyka:jimp2:2017:labs:pamiec-i-pliki [2017/03/03 16:18] mwp [Ale jest nadzieja - zautomatyzowane zarządzanie pamięcią część pierwsza] |
pl:dydaktyka:jimp2:2017:labs:pamiec-i-pliki [2019/06/27 15:50] |
======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// | |
| |
<WRAP center round info 60%> | |
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 [[.:wskazniki|Wskaźniki i referencje]] przygotowane zostało krótkie przypomnienie najważniejszych informacji. | |
</WRAP> | |
| |
| |
===== 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 | |
<code cpp> | |
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; | |
} | |
} | |
... | |
} | |
</code> | |
po refaktoryzacji kod mógłby wyglądać następująco: | |
<code cpp> | |
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); | |
... | |
} | |
</code> | |
| |
Zapoznać się z możliwościami automatycznej refaktoryzacji pod [[https://blog.jetbrains.com/clion/2014/12/refactorings-in-clion-be-safe-and-quick/|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:<code cpp>#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]; | |
}</code> | |
===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:<code cpp>#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; | |
}</code> | |
| |
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. | |
| |
=====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. | |
| |
Jednym z takich kontenerów jest tablica rozszerzalna [[http://en.cppreference.com/w/cpp/container/vector|vector]], zapoznać się z dokumentacją | |
uruchomić przykłady podane w dokumentacji przez **run code** i przyglądnąć się dokumentacji funkcji: | |
* push_back | |
* pop_back | |
* clear | |
Przenalizować poniższy kod: | |
<code cpp> | |
#include <iostream> | |
#include <vector> | |
| |
using std::cout; | |
using std::endl; | |
| |
void print_vector(const std::vector<int> &v) { | |
bool first = true; | |
for(auto n : v) { | |
if (!first) { | |
cout<< ", "; | |
} else { | |
first = false; | |
} | |
cout << n; | |
| |
} | |
cout<<std::endl; | |
} | |
| |
int main() | |
{ | |
// Create a vector containing integers | |
std::vector<int> v = {7, 5, 16, 8}; | |
| |
cout << "initilized with 4 numbers"<<endl; | |
print_vector(v); | |
| |
// Add two more integers to vector | |
v.push_back(25); | |
v.push_back(13); | |
cout << "after 2 more inserted"<<endl; | |
print_vector(v); | |
| |
// Iterate and print values of vector | |
for (auto it = v.begin(); it != v.end(); ++it) { | |
*it += 7; | |
} | |
| |
cout << "after 7 added to every number"<<endl; | |
print_vector(v); | |
//copy of the value inside vector | |
for (auto n : v) { | |
++n; | |
} | |
| |
cout << "BUT: after incrementation"<<endl; | |
print_vector(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; | |
print_vector(v); | |
} | |
</code> | |
[[http://coliru.stacked-crooked.com/view?id=262c6e6b2ec65eeb|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:<code cpp> | |
#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; | |
} | |
</code> | |
Przykład wczytywania pliku linia po linii:<code cpp> | |
#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; | |
} | |
</code> | |
| |
====Zapisywanie do pliku==== | |
Przykład **dopisywania** do pliku:<code cpp>#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; | |
} | |
</code> | |
| |
| |
====Otwieranie pliku w różnych trybach==== | |
Plik można otworzyć w 6 różnych trybach; kombinacje trybów też są możliwe. | |
| |
^Wartość flagi^Znaczenie^ | |
|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//. | |
<code cpp> | |
fstream file("file.txt", ios_base::in | ios_base::out | ios_base:app); | |
</code> | |
====== Ćwiczenia ====== | |
- 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). | |
- [1 plus] W sekcji [[#wskazniki_i_alokacja_pamieci|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ę iloczynami wierszy i kolumn 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! {{.:pointers2pointers.png|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: <code cpp>int **Array2D(int n_rows, int n_columns); | |
void DeleteArray2D(int **array, int n_rows, int n_columns);</code> | |
* W kroku nr 3 należy przeprowadzić refaktoryzację metody //Array2D// | |
* uruchomienie testów: ALT+SHIFT+F10 -> lab1_reverse_string_tests | |
- **[2 punkty] Napisz program, który będzie implementować algorytm szyfrujący [[http://pl.wikipedia.org/wiki/Szachownica_Polibiusza|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:**<code>./program plik-tekst.txt plik-szyfr.txt 1</code> | |
* Moduł: **polybius** | |
* Pliki z implementacją: **Polybius.h/cpp** | |
* Sygnatury metod: <code cpp>std::string PolybiusCrypt(std::string message); | |
std::string PolybiusDecrypt(std::string crypted);</code> | |
* Pliki nagłówkowe: <code cpp>#include <string></code> | |
- [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 [[http://en.cppreference.com/w/cpp/container/forward_list|forward_list]] zdolna przechowywać dowolny typ. | |
* Moduł: **simpleforwardlist** | |
* Pliki z implementacją: **ForwardList.h/cpp** | |
* Sygnatury metod: <code cpp>ForwardList *CreateNode(int value); | |
void DestroyList(ForwardList *list);</code> | |
* Sygnatury metod z kroku drugiego i trzeciego: <code cpp>ForwardList *PushFront(ForwardList *list, int value); | |
void Append(ForwardList *list, ForwardList *tail);</code> | |
- [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: <code cpp>int GreatestProduct(const std::vector<int> &numbers, int k);</code> | |
* Pliki nagłówkowe: <code cpp>#include <vector></code> | |
* Wskazówki: <code cpp>//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ść | |
</code> | |
* W kroku nr 3 należy przeprowadzić refaktoryzację metody //Array2D// | |
- **[3 punkty] [[http://projecteuler.net/index.php?section=problems&id=59|Ł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 [[http://www.talkenglish.com/vocabulary/top-2000-vocabulary.aspx|na podstawie]]** | |
* Moduł: **xorcypherbreaker** | |
* Pliki z implementacją: **XorCypherBreaker.h/cpp** | |
* Sygnatura metody: <code cpp>std::string XorCypherBreaker(const std::vector<char> &cryptogram, | |
int key_length, | |
const std::vector<string> &dictionary);</code> | |
* Pliki nagłówkowe: <code cpp>#include <string> | |
#include <vector></code> | |