SDA Lucrarea 5

În acest laborator se vor utiliza mulțimi cu funcții hash și arbori binari.

Șiruri de caractere în C++ - clasa std::string

Ca să putem folosi cu ușurință structurile de date definite în STL pentru a stoca șiruri de caractere, introducem clasa std::string definită în header-ul string (a nu se confunda cu cstring unde sunt definite funcțiile de manipulare de stringuri din C).

Crearea unui std::string

Pentru a instanția un obiect de tip std::string, există mai multe variante:

1. Utilizarea constructorului:

   #include <string>
   #include <cstdio>
   
   using std::string;
   
   int main() {
       string sentence("This is a sentence represented by a string object");
   
       printf("%s\n", sentence.c_str());
       return 0;
   }
   

2. Utilizarea operatorului de atribuire:

   #include <string>
   #include <cstdio>
   
   using std::string;
   
   int main() {
       string sentence = "This is a sentence represented by a string object";
   
       printf("%s\n", sentence.c_str());
       return 0;
   }
   

Citirea unui std::string

Pentru a citi dintr-un stream un șir de caractere cu funcția scanf, va fi nevoie în continuare de un array de caractere, dar acesta va fi folosit pentru apelul constructorului clasei std::string.

#include <string>
#include <cstdio>

using std::string;

int main() {
    char buffer[128];
    scanf("%[^\n]", buffer);
    string line(buffer);

    printf("This is the line from the keyboard: '%s'\n", line.c_str());
    return 0;
}

Copierea unui std::string

Un obiect de tip std::string se copiază foarte simplu, fără a fi nevoie de utilizarea funcției strcpy:

#include <string>
#include <cstdio>

using std::string;

int main() {
    string sentence = "This is a sentence represented by a string object";
    string copy = sentence;

    printf("This is the sentence: '%s' and this is the copy: '%s'\n", sentence.c_str(), copy.c_str());
    return 0;
}

Afișarea unui std::string

Pentru a afișa un șir de caractere cu funcția printf, va fi nevoie să obținem din obiectul de tip std::string de șirul de caractere în format char*. Acest lucru se realizează cu metoda c_str():

#include <string>
#include <cstdio>

using std::string;

int main() {
    string line = "This is some line!";

    printf("This is the line: '%s'\n", line.c_str());
    return 0;
}

Compararea a două obiecte de tip std::string

Compararea se poate realiza simplu, fără a utiliza funcția strcmp, ci folosind operatorii ==, !=, <, >, etc:

#include <string>
#include <cstdio>

using std::string;

int main() {
    string text1 = "Some text";
    string text2 = "Some text";

    if(text1 == text2) {
        printf("The texts are identical\n");
    } else {
        printf("The texts are NOT identical\n");
    }
    return 0;
}

Modificarea obiectelor de tip std::string

Pentru a accesa caracterele individuale dintr-un obiect de tip std::string, se poate utiliza, ca și în cazul clasei std::vector, operatorul []:

#include <string>
#include <cstdio>

using std::string;

int main() {
    string text1 = "Ana are un mar";
    text1[11] = 'c';
    text1[13] = 'l';

    printf("Textul modificat: %s\n", text1.c_str());

    return 0;
}

Mulțimea

Mulțimea este o structură de date abstractă care stochează o colecție de elemente unice în care ordinea nu contează.

Mulțimea are următoarele proprietăți:

1. Datele sunt plasate într-o ordine oarecare stabilită arbitrar de structură.
2. Numărul de elemente ce poate fi stocat de structură este nelimitat.
3. Elementele stocate în mulțime sunt de același fel.
4. Mulțimea poate conține doar elemente unice, în baza unei funcții definite de egalitate. Altfel spus, dacă două elemente sunt egale din punctul de vedere al mulțimii, ele nu pot fi ambele conținute de mulțime.

Mulțimea suportă următoarele operații de bază:

1. Interogarea numărului de elemente din mulțime.
2. Verificarea dacă mulțimea este goală.
3. Adăugarea unui element în mulțime (insert).
4. Verificarea dacă un element există în mulțime (count).
5. Eliminarea unui element din mulțime (erase).

Pentru a verifica egalitatea a două elemente vom specializa o structură equal_to care va întoarce true dacă cele două argumente sunt egale și false dacă nu. Această funcție trebuie să existe pentru orice implementare de mulțime, atunci când elementele nu sunt valori ce pot fi comparate cu operatorul implicit ==:

namespace std {
    template <class T>
    struct equal_to {
        /**
         * Functia verifica daca valorile value1 si value2 sunt egale.
         * @param value1 prima valoare de comparat.
         * @param value2 a doua valoare de comparat.
         * @return true daca cele doua valori sunt egale si false in rest.
         */
         bool equal_to(const T& value1, const T& value2) const;
    }
}

Atenție, pentru a putea fi folosită de clasele de tip mulțime din STL, această structură trebuie declarată în interiorul namespace-ului std.

Implementarea de mulțimi cu funcții hash

O funcție hash este o funcție care ia ca argument un șir de bytes de orice dimensiune și întoarce un șir de bytes 
de dimensiune fixă ce poartă numele de valoare de hash, cod hash sau pur și simplu hash.

Definiția unei funcții hash este strâns legată de definiția funcției equal_to astfel încât dacă două elemente e1 și e2 sunt considerate egale (equal_to(e1, e1) == true), atunci obligatoriu hash(e1) == hash(e2):

namespace std {
    template<class T> 
    struct hash {
        /**
         * Metoda calculeaza un hashcode pentru elementul element.
         * @param element referinta la un element de tip T pentru care se calculeaza hash-ul
         * @return hashcode-ul calculat.
         */
        std::size_t operator()(T const& element) const;
    };
}

Să definim noile elemente de sintaxă:

1. std::size_t este un tip de dată ce reprezintă o dimensiune (deci este un număr întreg fără semn), iar dimensiunea lui în biți depinde de compilator (poate fi sinonim cu uint32_t sau cu uint64_t); un cod hash este reprezentat ca o valoare de tip std::size_t
2. operator() este numele unui operator (mai precis operatorul 'paranteză rotundă') care poate fi supraîncărcat astfel încât să facă altceva decât comportamentul obișnuit (adică apel de funcție); în acest caz, se poate folosi sintaxa hash<SomeType>(someValueOfSomeType) pentru a apela metoda operator() din structura hash<T>
3. T const &element conține două elemente de noutate:
   • cuvântul cheie const face ca elementul să nu poată fi modificat de metodă (ci doar citit)
   • operatorul & se numește referință, similară cu un pointer, iar scopul lui în acest context este să permită accesarea datelor din variabila element fără a copia tot conținutul structurii pe stivă, lucru care se întâmplă cu variabilele non-referință trimise ca argument funcțiilor.
4. cuvântul cheie const de la sfârșitul metodei specifică faptul că această metodă nu poate modifica membrii clasei (în acest caz clasa nu are alți membri, deci prezența acestui cuvânt cheie este redundantă).

Clasa std::unordered_set

Clasa din STL care implementează mulțimi folosind funcții hash poartă numele de std::unordered_set și este definită în header-ul unordered_set. Mai departe vom exemplifica definirea funcțiilor de egalitate și hash pentru utilizarea unui std::unordered_set în scopul stocării unor elemente de tip struct Person:

struct Person {
    char firstName[30];
    char lastName[30];
    char idNumber[9]; // seria si numarul de buletin
    char address[255];
    char birthday[11];
    char cnp[14];
};

Pentru a implementa o funcție hash pentru variabilele de tip struct Person, avem întâi nevoie să definim operația de egalitate. O persoană își poate schimba numele, buletinul și adresa, și pot exista mai multe persoane cu aceeași dată de naștere, dar ceea ce identifică clar o persoană este codul numeric personal (CNP). Deci vom defini funcția equal să întoarcă 1 dacă cnp-urile celor două argumente de tip struct Person sunt identice:

namespace std {
    template<>
    struct equal_to<Person> {
        /**
         * Functia intoarce true daca CNP-urile celor doua persoane sunt egale.
         * @param person1 prima persoana de comparat.
         * @param person2 a doua persoana de comparat.
         * @return true daca CNP-urile celor doua persoane sunt identice.
         */
        bool operator()(const Person &person1, const Person &person2) const {
            return strcmp(person1.cnp, person2.cnp) == 0;
        }
    };

Mai departe definim funcția hash pentru o Persoană.

Pentru a putea implementa o mulțime cu funcții hash trebuie ca hash-ul maxim să fie o valoare rezonabilă pentru a putea aloca memorie cu dimensiunea valorii respective.

Din motivul de mai sus, și pentru a micșora posibilitatea unei coliziuni de hash ce va micșora performanța structurii, ieșirea funcției hash va fi un număr între 0 și 999999 obținut din ultimele 6 cifre ale CNP-ului convertite din text în număr (pentru conversie puteți folosi funcția atoi):

namespace std {
    template<>
    struct hash<Person> {
        /**
         * Functie hash pentru structurile de tip Person.
         * @param person peroana pentru care se doreste codul hash.
         * @return codul hash al persoanei person
         */
        size_t operator()(Person const & person) const {
            return (size_t) atoi(person.cnp + 7);
        }
    };
    
}

Crearea unui std::unordered_set

Pentru instanțierea unui obiect de tip std::unordered_set, se folosește constructorul fără argumente:

#include<unordered_set>
#include<cstdio>

int main() {
    std::unordered_set<int> mySet;
    printf("My set is empty: %d\n", mySet.empty());
    return 0;
}

Interogarea numărului de elemente din mulțime

Pentru interogarea numărului de elemente din mulțime sunt definite:

/**
 * Metoda intoarce numarul de elemente din multime.
 * @return numarul de elemente din multime.
 */
size_t size();

/**
 * Metoda intoarce true daca multimea e goala.
 * @return true daca multimea e goala
 */
bool empty();

Exemplu:

#include<unordered_set>
#include<cstdio>

int main() {
    std::unordered_set<float> mySet;
    mySet.insert(1);
    mySet.insert(1.1);
    mySet.insert(1);

    printf("My set has %u elements. My set is empty: %d\n", mySet.size(), mySet.empty());
    return 0;
}

Adăugarea unui element în mulțime

Pentru operația de adăugare se definește următoarea metodă:

/**
 * Metoda adauga elementul dat in multime daca acesta nu exista. Daca
 *  exista deja, functia nu are nici un efect.
 * @param element elementul ce trebuie adaugat.
 */
void insert(T element);

Exemplu:

#include<unordered_set>
#include<cstdio>

int main() {
    std::unordered_set<float> mySet;
    mySet.insert(1);
    mySet.insert(1.1);
    mySet.insert(1);

    printf("My set has %u elements. My set is empty: %d\n", mySet.size(), mySet.empty());
    return 0;
}

Eliminarea unui element din mulțime

Pentru operația de eliminare se definește următoarea metodă:

/**
 * Metoda elimina elementul dat din multime daca acesta exista. Daca
 *  nu exista, functia nu are nici un efect.
 * @param element elementul ce trebuie eliminat.
 */
void erase(T element);

Exemplu:

#include<unordered_set>
#include<cstdio>

int main() {
    std::unordered_set<float> mySet;
    mySet.insert(1);
    mySet.insert(1.1);
    mySet.insert(1);

    printf("My set has %u elements. My set is empty: %d\n", mySet.size(), mySet.empty());

    mySet.erase(1);

    printf("My set has %u elements. My set is empty: %d\n", mySet.size(), mySet.empty());

    return 0;
}

Verificarea dacă un element există în mulțime

Pentru a verifica dacă un element există în mulțime, se definește următoarea metodă:

/**
 * Metoda intoarce 1 daca elementul specificat exista in multime, 0 dacă nu.
 * @param element elementul cautat.
 * @return 1 daca elementul exista in multime, 0 daca nu.
 */
size_t count(T element);

Exemplu:

#include<unordered_set>
#include<cstdio>

int main() {
    std::unordered_set<float> mySet;
    mySet.insert(1);
    mySet.insert(1.1);
    mySet.insert(1);

    printf("Element %f is in set (0 or 1): %d\n", 1, mySet.count(1));
    printf("Element %f is in set (0 or 1): %d\n", 2, mySet.count(2));
    return 0;
}

Iterarea peste elementele mulțimii

Pentru a itera peste elementele din mulțime se folosesc iteratori:

#include<unordered_set>
#include<cstdio>

int main() {
    std::unordered_set<int> mySet;
    mySet.insert(10);
    mySet.insert(13);
    mySet.insert(-5);
    mySet.insert(-5);
    mySet.insert(0);

    for(std::unordered_set<int>::iterator it = mySet.begin(); it != mySet.end(); it++) {
        printf("%d ", *it);
    }
    printf("\n");
    return 0;
}

Implementarea de mulțimi cu arbori binari de căutare (BST)

Pentru a adăuga elementele unei mulțimi într-un arbore binar de căutare, pe tipul respectiv trebuie definită o relație de ordine. Această relație este definită deja în STL prin structurile std::less, std::greater, std::less_equal și std::greater_equal. Pentru structura de date de tip mulțime implementată cu BST, este necesară definirea doar a structurii std::less, și doar pentru clase sau structuri proprii pentru care nu există deja implementare în STL. Două elemente a și b de tip T sunt considerate egale dacă !less<T>(a, b) && !less<T>(b,a). Altfel spus, dacă nici unul nu este strict mai mic decât celălalt. Astfel, folosind operația de comparație, putem defini și egalitatea.

Definiția acestei structuri este:

namespace std {
    template<class T> 
    struct less {
        /**
         * Metoda compară cele două elemente și întoarce true dacă primul element este strict mai mic
         * decât al doilea.
         * @param first primul element de comparat.
         * @param second al doilea element de comparat.
         * @return true dacă primul element este strict mai mic decât al doilea.
         */
         bool operator() (const T& first, const T& second) const;
    };
}

Să definim noile elemente de sintaxă:

1. operator() este numele unui operator (mai precis operatorul 'paranteză rotundă') care poate fi supraîncărcat astfel încât să facă altceva decât comportamentul obișnuit (adică apel de funcție); în acest caz, se poate folosi sintaxa less<SomeType>(valueOfSomeType1, valueOfSomeType2) pentru a apela metoda operator() din structura less<T>
2. const T &first conține două elemente de noutate:
   • cuvântul cheie const face ca elementul să nu poată fi modificat de metodă (ci doar citit)
   • operatorul & se numește referință, similară cu un pointer, iar scopul lui în acest context este să permită accesarea datelor din variabila first fără a copia tot conținutul structurii pe stivă, lucru care se întâmplă cu variabilele non-referință trimise ca argument funcțiilor.
3. cuvântul cheie const de la sfârșitul metodei specifică faptul că această metodă nu poate modifica membrii clasei (în acest caz clasa nu are alți membri, deci prezența acestui cuvânt cheie este redundantă).

Clasa std::set

Mulțimile implementate cu arbori binari de căutare, în plus față proprietățile mulțimilor definite mai sus, garantează faptul că elementele sunt plasate în ordine în mulțime (Ordered Set).

Clasa din STL care implementează mulțimi folosind arbori binari de căutare poartă numele de std::set și este definită în header-ul set. Mai departe vom exemplifica definirea funcției de comparație pentru utilizarea unui std::set în scopul stocării unor elemente de tip struct Person:

struct Person {
    char firstName[30];
    char lastName[30];
    char idNumber[9]; // seria si numarul de buletin
    char address[255];
    char birthday[11];
    char cnp[14];
};

Să definim comparatorul! O persoană își poate schimba numele, buletinul și adresa, și pot exista mai multe persoane cu aceeași dată de naștere, dar ceea ce identifică clar o persoană este codul numeric personal (CNP), prin urmare vom compara două persoane folosind strict acest câmp:

namespace std {
    template<>
    struct less<Person> {
        /**
         * Functia intoarce true daca CNP-urile celor doua persoane sunt egale.
         * @param person1 prima persoana de comparat.
         * @param person2 a doua persoana de comparat.
         * @return true daca CNP-urile celor doua persoane sunt identice.
         */
        bool operator()(const Person &person1, const Person &person2) const {
            return strcmp(person1.cnp, person2.cnp) < 0;
        }
    };

Crearea unui std::set

Pentru instanțierea unui obiect de tip std::set, se folosește constructorul fără argumente:

#include<set>
#include<cstdio>

int main() {
    std::set<int> mySet;
    printf("My set is empty: %d\n", mySet.empty());
    return 0;
}

Interogarea numărului de elemente din mulțime

Pentru interogarea numărului de elemente din mulțime sunt definite:

/**
 * Metoda intoarce numarul de elemente din multime.
 * @return numarul de elemente din multime.
 */
size_t size();

/**
 * Metoda intoarce true daca multimea e goala.
 * @return true daca multimea e goala
 */
bool empty();

Exemplu:

#include<set>
#include<cstdio>

int main() {
    std::set<float> mySet;
    mySet.insert(1);
    mySet.insert(1.1);
    mySet.insert(1);

    printf("My set has %u elements. My set is empty: %d\n", mySet.size(), mySet.empty());
    return 0;
}

Adăugarea unui element în mulțime

Pentru operația de adăugare se definește următoarea metodă:

/**
 * Metoda adauga elementul dat in multime daca acesta nu exista. Daca
 *  exista deja, functia nu are nici un efect.
 * @param element elementul ce trebuie adaugat.
 */
void insert(T element);

Exemplu:

#include<set>
#include<cstdio>

int main() {
    std::set<float> mySet;
    mySet.insert(1);
    mySet.insert(1.1);
    mySet.insert(1);

    printf("My set has %u elements. My set is empty: %d\n", mySet.size(), mySet.empty());
    return 0;
}

Eliminarea unui element din mulțime

Pentru operația de eliminare se definește următoarea metodă:

/**
 * Metoda elimina elementul dat din multime daca acesta exista. Daca
 *  nu exista, functia nu are nici un efect.
 * @param element elementul ce trebuie eliminat.
 */
void erase(T element);

Exemplu:

#include<set>
#include<cstdio>

int main() {
    std::set<float> mySet;
    mySet.insert(1);
    mySet.insert(1.1);
    mySet.insert(1);

    printf("My set has %u elements. My set is empty: %d\n", mySet.size(), mySet.empty());

    mySet.erase(1);

    printf("My set has %u elements. My set is empty: %d\n", mySet.size(), mySet.empty());

    return 0;
}

Verificarea dacă un element există în mulțime

Pentru a verifica dacă un element există în mulțime, se definește următoarea metodă:

/**
 * Metoda intoarce 1 daca elementul specificat exista in multime, 0 dacă nu.
 * @param element elementul cautat.
 * @return 1 daca elementul exista in multime, 0 daca nu.
 */
size_t count(T element);

Exemplu:

#include<set>
#include<cstdio>

int main() {
    std::set<float> mySet;
    mySet.insert(1);
    mySet.insert(1.1);
    mySet.insert(1);

    printf("Element %f is in set (0 or 1): %d\n", 1, mySet.count(1));
    printf("Element %f is in set (0 or 1): %d\n", 2, mySet.count(2));
    return 0;
}

Iterarea peste elementele mulțimii

Pentru a itera peste elementele din mulțime se folosesc iteratori. Iteratorul va oferi întotdeauna elementele în ordine crescătoare, conform definiției operației std::less.

#include<set>
#include<cstdio>

int main() {
    std::set<int> mySet;
    mySet.insert(10);
    mySet.insert(13);
    mySet.insert(-5);
    mySet.insert(-5);
    mySet.insert(0);

    for(std::set<int>::iterator it = mySet.begin(); it != mySet.end(); it++) {
        printf("%d ", *it);
    }
    printf("\n");
    return 0;
}