Versiunea curentă din 14 mai 2017 19:58

În acest laborator se vor implementa structuri de date asociative (map) cu arbori binari și funcții hash.

Structura de date asociativă - Map

Structura de date asociativă (map) este o structură de date abstractă care stochează perechi de elemente cheie-valoare, 
într-o ordine arbitrară stabilită de structură, astfel încât nu pot exista două perechi cu aceeași cheie în map.

În esență, un map este o mulțime (set) de chei care sunt întotdeauna stocate împreună cu o valoare.

Map-ul are următoarele proprietăți:

Datele sunt plasate într-o ordine oarecare stabilită arbitrar de structură.
Numărul de elemente ce poate fi stocat de structură este nelimitat.
Elementele stocate în map sunt de același fel.
Tipul de date al cheii și tipul de date al valorii pot fi diferite.
Map-ul poate conține doar chei unice, în baza unei funcții definite de egalitate. Altfel spus, dacă două chei sunt egale din punctul de vedere al map-ului, ele nu pot fi ambele prezente în perechi cheie-valoare în map.

Map-ul suportă următoarele operații de bază:

Interogarea numărului de elemente din map.
Verificarea dacă map-ul este gol.
Adăugarea perechi cheie-valoare (insert) - dacă cheia există deja în map, aceasta nu se înlocuiește.
Verificarea dacă o cheie există în map (count).
Căutarea unei valori după o cheie dată (at);
Eliminarea unei chei din map (erase).

Implementarea de structuri asociative cu funcții hash

Definirea funcțiilor hash și a proprietăților lor s-a făcut în laboratorul 5 (SDA Lucrarea 5#Implementarea de mulțimi cu funcții hash).

Tipul de date și funcțiile de bază

În continuare vom prezenta un exemplu de map de la CNP (cheia) la elemente de tip Person (valoarea), implementată cu funcții hash. În primul rând vom defini structura ce memorează datele legate de o persoană:

struct Person {
    std::string firstName;
    std::string lastName;
    std::string idNumber; // seria si numarul de buletin
    std::string address;
    std::string birthday;
    std::string cnp;
};

Funcțiile de hash și de egalitate pentru clasa std::string sunt deja implementate în STL. Dacă totuși aveți nevoie de a folosi niste funcții proprii, acestea se scriu în același fel ca cele pentru mulțimi împlementate cu funcții hash (vezi SDA Lucrarea 5).

Clasa `std::unordered_map`

Pentru stocarea datelor necesare map-ului, În STL se definește clasa std::unordered_map în header-ul unordered_map. Aceasta este o clasă de tip template care se parametrizează cu două tipuri de date: tipul pentru cheie și tipul pentru valoare:

#include <unordered_map>
#include <string>

int main() {
    std::unorder_map<std::string, Person> myMap; // un map de la string la Person
    return 0;
}

Crearea unui `std::unordered_map`

Pentru crearea unui std::unordered_map, se definește următorul constructor:

/**
 * Constructorul creeaza un map nou și inițializează structurile de date interne.
 */
unordered_map();

Exemplu:

#include <unordered_map>
#include <string>

int main() {
    std::unorder_map<std::string, Person> myMap;
    Person person;
    myMap["190010112345"] = person;
    return 0;
}

Interogarea numărului de elemente din map

Pentru interogarea numărului de elemente din map se definesc:

/**
 * Metoda intoarce numarul de elemente din map.
 * @return numarul de elemente din map.
 */
uint64_t size();

/**
 * Metoda intoarce true dacă map-ul nu conține nici un element.
 * @return true dacă map-ul este gol, false în rest.
 */
bool empty();

Exemplu:

#include <unordered_map>
#include <string>
#include <cstdio>

int main() {
    std::unorder_map<std::string, Person> myMap;
    Person person;
    myMap["190010112345"] = person;
    printf("Map-ul contine %lu elemente.\n", myMap.size());
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
    return 0;
}

Adăugarea unei perechi cheie-valoare în map

Pentru operația de adăugare se definesc următoarele metode:

/**
 * Metoda adauga perechea data in map daca cheia nu exista. 
 * @param keyValuePair o pereche cheie-valoare
 * @return o pereche iterator-bool, unde iteratorul identifică perechea 
 *   introdusă în map, sau cea existentă cu aceeași cheie, iar bool spune daca
 *   perechea a fost introdusa sau nu (pentru ca exista deja).
 */
pair<iterator, bool> insert(pair<K, V> keyValuePair);

/**
 * Metoda ia ca argument o cheie și intoarce o referinta (LVALUE) la 
 *  valoarea asociată. Dacă cheia nu există în map, se adaugă cu o valoare
 *  neutră.
 * @param key cheia ce se dorește adăugată (sau interogată).
 * @return o referință la valoarea asociată cheii.
 */
V & operator[](K key);

Exemplu:

#include <unordered_map>
#include <string>
#include <cstdio>
 
int main() {
    std::unorder_map<std::string, Person> myMap;
    Person person;
    myMap.insert({"191010112345", person});
    myMap["190010112345"] = person;
    printf("Map-ul contine %lu elemente.\n", myMap.size());
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
    return 0;
}

Eliminarea unei chei din map

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

/**
 * Metoda elimina cheia data din map daca acesta exista. Daca
 *  nu exista, functia nu are nici un efect.
 * @param key cheia ce trebuie eliminata.
 */
void erase(K key);

/**
 * Metoda sterge toate elementele din map.
 */
void clear();

Exemplu:

#include <unordered_map>
#include <string>
#include <cstdio>
 
int main() {
    std::unorder_map<std::string, Person> myMap;
    Person person;
    myMap.insert({"191010112345", person});
    myMap["190010112345"] = person;
    myMap.erase("098764321987");
    printf("Map-ul contine %lu elemente.\n", myMap.size());
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
    myMap.erase("191010112345");
    printf("Map-ul contine %lu elemente.\n", myMap.size());
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
    myMap.clear();
    printf("Map-ul contine %lu elemente.\n", myMap.size());
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");

    return 0;
}

Verificarea dacă o cheie există în map

Pentru a verifica dacă o cheie există în map, se definește următoarea funcție:

/**
 * Functia intoarce 1 daca cheia specificata exista in map, 0 in rest.
 * @param key cheia cautata.
 * @return 1 daca cheia exista in map, 0 daca nu.
 */
uint64_t count(K key);

Exemplu:

#include <unordered_map>
#include <string>
#include <cstdio>
 
int main() {
    std::unorder_map<std::string, Person> myMap;
    Person person;
    myMap.insert({"191010112345", person});
    myMap["190010112345"] = person;
    myMap.erase("098764321987");
    printf("Map-ul contine %lu elemente.\n", myMap.size());
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
    myMap.erase("191010112345");
    printf("Cheia 123 apare in map: %d\n", myMap.count("123"));
    printf("Cheia 190010112345 apare in map: %d\n", myMap.count("190010112345"));
    printf("Map-ul contine %lu elemente.\n", myMap.size());
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
    myMap.clear();
    printf("Map-ul contine %lu elemente.\n", myMap.size());
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
 
    return 0;
}

Căutarea unei valori după cheie

Pentru a căuta o valoare după cheie, se definește următoarele metode:

/**
 * Metoda intoarce a referinta la valoarea asociată cheii key.
 * @param key cheia cautata.
 * @return valoarea asociată cheii, dacă aceasta există, 
 *  sau se generează o eroare daca cheia nu exista in map.
 */
V& at(K key);

/**
 * Operatorul intoarce o referinta la valoarea asociată cheii key.
 * @param key cheia cautata.
 * @return valoarea asociată cheii, dacă aceasta există, 
 *  sau o valoare neutra daca nu există (care se si adauga in map).
 */

V& operator[](K key);

Exemplu:

#include <unordered_map>
#include <string>
#include <cstdio>
 
int main() {
    std::unorder_map<std::string, Person> myMap;
    Person person;
    person.firstName = "Ghita";
    myMap.insert({"191010112345", person});
    printf("Numele persoanei cu cheia 191010112345 este: %s\n", myMap.at("191010112345").fullName.c_str());
    printf("Numele persoanei cu cheia 191010112345 este: %s\n", myMap["191010112345"].fullName.c_str());
    return 0;
}

Implementarea de structuri asociative cu arbori binari de căutare

Definirea arborilor binari de căutare și a proprietăților lor s-au făcut în laboratorul 5 (SDA Lucrarea 5#Implementarea de mulțimi cu arbori binari de căutare (BST)).

Clasa `std::map`

Pentru stocarea datelor necesare map-ului, În STL se definește clasa std::map în header-ul map. Aceasta este o clasă de tip template care se parametrizează cu două tipuri de date: tipul pentru cheie și tipul pentru valoare:

#include <map>
#include <string>

int main() {
    std::map<std::string, Person> myMap; // un map de la string la Person
    return 0;
}

Crearea unui `std::map`

Pentru crearea unui std::map, se definește următorul constructor:

/**
 * Constructorul creeaza un map nou și inițializează structurile de date interne.
 */
map();

Exemplu:

#include <map>
#include <string>

int main() {
    std::map<std::string, Person> myMap;
    Person person;
    myMap["190010112345"] = person;
    return 0;
}

Interogarea numărului de elemente din map

Pentru interogarea numărului de elemente din map se definesc:

/**
 * Metoda intoarce numarul de elemente din map.
 * @return numarul de elemente din map.
 */
uint64_t size();

/**
 * Metoda intoarce true dacă map-ul nu conține nici un element.
 * @return true dacă map-ul este gol, false în rest.
 */
bool empty();

Exemplu:

#include <map>
#include <string>
#include <cstdio>

int main() {
    std::map<std::string, Person> myMap;
    Person person;
    myMap["190010112345"] = person;
    printf("Map-ul contine %lu elemente.\n", myMap.size());
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
    return 0;
}

Adăugarea unei perechi cheie-valoare în map

Pentru operația de adăugare se definesc următoarele metode:

/**
 * Metoda adauga perechea data in map daca cheia nu exista. 
 * @param keyValuePair o pereche cheie-valoare
 * @return o pereche iterator-bool, unde iteratorul identifică perechea 
 *   introdusă în map, sau cea existentă cu aceeași cheie, iar bool spune daca
 *   perechea a fost introdusa sau nu (pentru ca exista deja).
 */
pair<iterator, bool> insert(pair<K, V> keyValuePair);

/**
 * Metoda ia ca argument o cheie și intoarce o referinta (LVALUE) la 
 *  valoarea asociată. Dacă cheia nu există în map, se adaugă cu o valoare
 *  neutră.
 * @param key cheia ce se dorește adăugată (sau interogată).
 * @return o referință la valoarea asociată cheii.
 */
V & operator[](K key);

Exemplu:

#include <map>
#include <string>
#include <cstdio>
 
int main() {
    std::map<std::string, Person> myMap;
    Person person;
    myMap.insert({"191010112345", person});
    myMap["190010112345"] = person;
    printf("Map-ul contine %lu elemente.\n", myMap.size());
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
    return 0;
}

Eliminarea unei chei din map

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

/**
 * Metoda elimina cheia data din map daca acesta exista. Daca
 *  nu exista, functia nu are nici un efect.
 * @param key cheia ce trebuie eliminata.
 */
void erase(K key);

/**
 * Metoda sterge toate elementele din map.
 */
void clear();

Exemplu:

#include <map>
#include <string>
#include <cstdio>
 
int main() {
    std::map<std::string, Person> myMap;
    Person person;
    myMap.insert({"191010112345", person});
    myMap["190010112345"] = person;
    myMap.erase("098764321987");
    printf("Map-ul contine %lu elemente.\n", myMap.size());
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
    myMap.erase("191010112345");
    printf("Map-ul contine %lu elemente.\n", myMap.size());
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
    myMap.clear();
    printf("Map-ul contine %lu elemente.\n", myMap.size());
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");

    return 0;
}

Verificarea dacă o cheie există în map

Pentru a verifica dacă o cheie există în map, se definește următoarea funcție:

/**
 * Functia intoarce 1 daca cheia specificata exista in map, 0 in rest.
 * @param key cheia cautata.
 * @return 1 daca cheia exista in map, 0 daca nu.
 */
uint64_t count(K key);

Exemplu:

#include <map>
#include <string>
#include <cstdio>
 
int main() {
    std::map<std::string, Person> myMap;
    Person person;
    myMap.insert({"191010112345", person});
    myMap["190010112345"] = person;
    myMap.erase("098764321987");
    printf("Map-ul contine %lu elemente.\n", myMap.size());
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
    myMap.erase("191010112345");
    printf("Cheia 123 apare in map: %d\n", myMap.count("123"));
    printf("Cheia 190010112345 apare in map: %d\n", myMap.count("190010112345"));
    printf("Map-ul contine %lu elemente.\n", myMap.size());
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
    myMap.clear();
    printf("Map-ul contine %lu elemente.\n", myMap.size());
    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
 
    return 0;
}

Căutarea unei valori după cheie

Pentru a căuta o valoare după cheie, se definesc următoarele metode:

/**
 * Metoda intoarce a referinta la valoarea asociată cheii key.
 * @param key cheia cautata.
 * @return valoarea asociată cheii, dacă aceasta există, 
 *  sau se generează o eroare daca cheia nu exista in map.
 */
V& at(K key);

/**
 * Operatorul intoarce o referinta la valoarea asociată cheii key.
 * @param key cheia cautata.
 * @return valoarea asociată cheii, dacă aceasta există, 
 *  sau o valoare neutra daca nu există (care se si adauga in map).
 */

V& operator[](K key);

Exemplu:

#include <map>
#include <string>
#include <cstdio>
 
int main() {
    std::map<std::string, Person> myMap;
    Person person;
    person.firstName = "Ghita";
    myMap.insert({"191010112345", person});
    printf("Numele persoanei cu cheia 191010112345 este: %s\n", myMap.at("191010112345").fullName.c_str());
    printf("Numele persoanei cu cheia 191010112345 este: %s\n", myMap["191010112345"].fullName.c_str());
    return 0;
}

SDA Lucrarea 6: Diferență între versiuni

Versiunea curentă din 14 mai 2017 19:58

Cuprins

Structura de date asociativă - Map

Implementarea de structuri asociative cu funcții hash

Tipul de date și funcțiile de bază

Clasa `std::unordered_map`

Crearea unui `std::unordered_map`

Interogarea numărului de elemente din map

Adăugarea unei perechi cheie-valoare în map

Eliminarea unei chei din map

Verificarea dacă o cheie există în map

Căutarea unei valori după cheie

Implementarea de structuri asociative cu arbori binari de căutare

Clasa `std::map`

Crearea unui `std::map`

Interogarea numărului de elemente din map

Adăugarea unei perechi cheie-valoare în map

Eliminarea unei chei din map

Verificarea dacă o cheie există în map

Căutarea unei valori după cheie

Meniu de navigare

Page actions

Page actions

Unelte personale

Navigare

Căutare

Unelte

@@ Linia 6: / Linia 6: @@
   într-o ordine arbitrară stabilită de structură, astfel încât nu pot exista două perechi cu aceeași cheie în map.
-În esență, un ''map'' este o mulțime (set) de chei care este întotdeauna stocată împreună cu o valoare.
+În esență, un ''map'' este o mulțime (set) de chei care sunt întotdeauna stocate împreună cu o valoare.
 [[Fișier:map.png]]
@@ Linia 20: / Linia 20: @@
 # Interogarea numărului de elemente din map.
 # Verificarea dacă map-ul este gol.
-# Adăugarea perechi cheie-valoare (''put'') - dacă cheia există deja în map, perechea respectivă este înlocuită de noua valoare.
+# Adăugarea perechi cheie-valoare (''insert'') - dacă cheia există deja în map, aceasta nu se înlocuiește.
-# Verificarea dacă o cheie există în map (''hasKey'').
+# Verificarea dacă o cheie există în map (''count'').
-# Căutarea unei valori după o cheie dată (''get'');
+# Căutarea unei valori după o cheie dată (''at'');
-# Eliminarea unei chei din map (''remove'').
+# Eliminarea unei chei din map (''erase'').
-<!--
-== 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
+== Implementarea de structuri asociative cu funcții hash  ==
-  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 <code>equals</code> astfel încât dacă două elemente e1 și e2 sunt considerate egale (<code>equals(e1, e1) == 1</code>), atunci obligatoriu <code>hash(e1) == hash(e2)</code>.
+Definirea funcțiilor hash și a proprietăților lor s-a făcut în laboratorul 5 ([[SDA Lucrarea 5#Implementarea de mulțimi cu funcții hash]]).
 === Tipul de date și funcțiile de bază ===
-În continuare vom prezenta un exemplu de mulțime pentru elemente de tip "persoană" implementată cu funcții hash. În primul rând vom defini structura ce memorează datele legate de o persoană:
+În continuare vom prezenta un exemplu de map de la CNP (cheia) la elemente de tip <code>Person</code> (valoarea), implementată cu funcții hash. În primul rând vom defini structura ce memorează datele legate de o persoană:
-<syntaxhighlight lang="C">
+<syntaxhighlight lang="cpp">
 struct Person {
-     char firstName[30];
+     std::string firstName;
-     char lastName[30];
+     std::string lastName;
-     char idNumber[9]; // seria si numarul de buletin
+     std::string idNumber; // seria si numarul de buletin
-     char address[255];
+     std::string address;
-     char birthday[11];
+     std::string birthday;
-     char cnp[14];
+     std::string cnp;
 };
 </syntaxhighlight>
-Pentru a implementa o funcție hash pentru variabilele de tip <code>struct Person</code>, 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 <code>equals</code> să întoarcă 1 dacă cnp-urile celor două argumente de tip <code>struct Person</code> sunt identice:
+Funcțiile de hash și de egalitate pentru clasa <code>std::string</code> sunt deja implementate în STL. Dacă totuși aveți nevoie de a folosi niste funcții proprii, acestea se scriu în același fel ca cele pentru mulțimi împlementate cu funcții hash (vezi [[SDA Lucrarea 5]]).
-<syntaxhighlight lang="C">
+=== Clasa <code>std::unordered_map</code> ===
-/**
- * Functia intoarce 1 daca CNP-urile celor doua persoane sunt egale.
+Pentru stocarea datelor necesare map-ului, În STL se definește clasa <code>std::unordered_map</code> în header-ul <code>unordered_map</code>. Aceasta este o clasă de tip template care se parametrizează cu două tipuri de date: tipul pentru cheie și tipul pentru valoare:
- * @param person1 prima persoana de comparat.
- * @param person2 a doua persoana de comparat.
- * @return 1 daca CNP-urile celor doua persoane sunt identice.
- */
-char equals(struct Person person1, struct Person person2);
-</syntaxhighlight>
-Mai departe definim funcția hash pentru o Persoană.
+<syntaxhighlight lang="cpp">
+#include <unordered_map>
+#include <string>
- 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.
+int main() {
+    std::unorder_map<std::string, Person> myMap; // un map de la string la Person
+    return 0;
+}
+</syntaxhighlight>
-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 [http://www.cplusplus.com/reference/cstdlib/atoi/ atoi]):
+=== Crearea unui <code>std::unordered_map</code>===
-<syntaxhighlight lang="C">
+Pentru crearea unui <code>std::unordered_map</code>, se definește următorul constructor:
+<syntaxhighlight lang="cpp">
 /**
-  * Functie hash pentru structurile de tip Person.
+  * Constructorul creeaza un map nou și inițializează structurile de date interne.
- * @param person peroana pentru care se doreste codul hash.
- * @return codul hash al persoanei person
   */
-unsigned hash(struct Person person);
+unordered_map();
 </syntaxhighlight>
-În continuare vom utiliza pentru implementarea unui Hash Set o structură de date de tip secvență împlementată cu liste (LinkedList) și vom folosi funcțiile deja definite de la laboratoarele anterioare:
+Exemplu:
-* [[Fișier:linkedList.h]]
+<syntaxhighlight lang="cpp" highlight="5">
-* [[Fișier:linkedList.c]]
+#include <unordered_map>
+#include <string>
-=== Structura <code>HashSet</code> ===
+int main() {
+    std::unorder_map<std::string, Person> myMap;
+    Person person;
+    myMap["190010112345"] = person;
+    return 0;
+}
+</syntaxhighlight>
-Pentru stocarea datelor necesare mulțimii, definim următoarea structură:
+=== Interogarea numărului de elemente din map ===
-<syntaxhighlight lang="C">
+Pentru interogarea numărului de elemente din map se definesc:
-#define MAX_HASH 1000000
+<syntaxhighlight lang="cpp">
-struct HashSet {
+/**
-    struct LinkedList array[MAX_HASH]; // un vector de liste, una pentru fiecare valoare posibila de hash
+ * Metoda intoarce numarul de elemente din map.
-    unsigned size; // numarul de elemente din multime
+ * @return numarul de elemente din map.
-};
+ */
-</syntaxhighlight>
+uint64_t size();
-=== Crearea unui <code>HashSet</code>===
-Pentru crearea unui <code>HashSet</code>, se definește următoarea funcție:
-<syntaxhighlight lang="C">
 /**
-  * Functia creeaza un hashSet nou si intoarce adresa de memorie alocata.
+  * Metoda intoarce true dacă map-ul nu conține nici un element.
-  * @return un pointer la o structura de tip HashSet.
+  * @return true dacă map-ul este gol, false în rest.
   */
-struct HashSet * createHashSet();
+bool empty();
 </syntaxhighlight>
-Pentru crearea unui <code>HashSet</code> se urmează următorii pași:
+Exemplu:
-# Se alocă memorie pentru un element de tip <code>struct HashSet</code> folosind funcția corectă pentru reseta memoria la alocare (scrierea ei cu 0).
+<syntaxhighlight lang="cpp" highlight="9,10">
-# Se inițializează <code>size</code> cu 0.
+#include <unordered_map>
-# Se întoarce adresa elementului de tip <code>struct HashSet</code>.
+#include <string>
+#include <cstdio>
-* Complexitate în '''timp''': O(1)
+int main() {
-* Complexitate în '''spațiu''': O(MAX_HASH)
+    std::unorder_map<std::string, Person> myMap;
+    Person person;
+    myMap["190010112345"] = person;
+    printf("Map-ul contine %lu elemente.\n", myMap.size());
+    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
+    return 0;
+}
+</syntaxhighlight>
-=== Interogarea numărului de elemente din mulțime ===
+=== Adăugarea unei perechi cheie-valoare în map ===
-Pentru interogarea numărului de elemente din mulțime definim:
+Pentru operația de adăugare se definesc următoarele metode:
-<syntaxhighlight lang="C">
+<syntaxhighlight lang="cpp">
 /**
-  * Functia intoarce numarul de elemente din multime.
+  * Metoda adauga perechea data in map daca cheia nu exista.
-  * @param set multimea a carei dimensiuni este ceruta.
+  * @param keyValuePair o pereche cheie-valoare
-  * @return numarul de elemente din multime.
+  * @return o pereche iterator-bool, unde iteratorul identifică perechea
+ *   introdusă în map, sau cea existentă cu aceeași cheie, iar bool spune daca
+ *   perechea a fost introdusa sau nu (pentru ca exista deja).
   */
-unsigned hashSetSize(struct HashSet * set);
+pair<iterator, bool> insert(pair<K, V> keyValuePair);
-</syntaxhighlight>
-Funcția va întoarce valoarea din câmpul <code>size</code> din structură.
-* Complexitate în '''timp''': O(1)
-* Complexitate în '''spațiu''': O(1)
-Pentru a afla dacă mulțimea este goală definim:
-<syntaxhighlight lang="C">
 /**
-  * Functia intoarce 1 dacă mulțimea nu conține nici un element.
+  * Metoda ia ca argument o cheie și intoarce o referinta (LVALUE) la
-  * @param set multimea de interes.
+ *  valoarea asociată. Dacă cheia nu există în map, se adaugă cu o valoare
-  * @return 1 dacă mulțimea este goală, 0 în rest.
+ *  neutră.
+  * @param key cheia ce se dorește adăugată (sau interogată).
+  * @return o referință la valoarea asociată cheii.
   */
-char hashSetIsEmpty(struct HashSet * set);
+V & operator[](K key);
 </syntaxhighlight>
-Funcția va întoarce 1 dacă valoarea din câmpul <code>size</code> este 0.
+Exemplu:
+<syntaxhighlight lang="cpp" highlight="8-9">
+#include <unordered_map>
+#include <string>
+#include <cstdio>
+int main() {
+    std::unorder_map<std::string, Person> myMap;
+    Person person;
+    myMap.insert({"191010112345", person});
+    myMap["190010112345"] = person;
+    printf("Map-ul contine %lu elemente.\n", myMap.size());
+    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
+    return 0;
+}
+</syntaxhighlight>
-* Complexitate în '''timp''': O(1)
+=== Eliminarea unei chei din map ===
-* Complexitate în '''spațiu''': O(1)
-=== Adăugarea unui element în mulțime ===
+Pentru operația de eliminare se definește următoarea metodă:
-Pentru operația de adăugare se definește următoarea funcție:
+<syntaxhighlight lang="cpp">
-<syntaxhighlight lang="C">
 /**
-  * Functia adauga elementul dat in multime daca acesta nu exista. Daca
+  * Metoda elimina cheia data din map daca acesta exista. Daca
-  *  exista deja, functia nu are nici un efect.
+  *  nu exista, functia nu are nici un efect.
-  * @param set multimea in care trebuie adaugat elementul.
+  * @param key cheia ce trebuie eliminata.
- * @param person elementul ce trebuie adaugta.
   */
-void hashSetPut(struct HashSet * set, struct Person person);
+void erase(K key);
-</syntaxhighlight>
-Adăugarea se realizează în felul următor:
-# Se aplică funcția hash pe variabila <code>person</code>.
-# Folosind valoarea obținută se accesează lista de pe poziția hash-ului din <code>array</code>.
-# Se folosește funcția <code>linkedListSearch</code> pentru a verifica dacă <code>person</code> există în listă (funcția <code>linkedListSearch</code> trebuie re-implementată pentru a se folosi de funcția <code>equals</code> pentru compararea elementelor).
-# Dacă valoarea întoarsă este -1 atunci <code>person</code> se adaugă în listă și <code>size</code> se incrementează cu 1.
-* Complexitate în '''timp''': O(1) best case (fără coliziuni), O(1) average case pentru număr mai mic de 1000000 de persoane, O(n) worst case (același hash pentru poate persoanele).
-* Complexitate în '''spațiu''': O(1)
-<div class="regula"><span style="color: red; font-weight: bold">Atenție:</span> Deoarece vectorul <code>array</code> conține variabile de tip <code>struct LinkedList</code> și nu pointeri, pentru a folosi funcțiile definite în '''linkedList.h''' e necesară obținerea adresei variabilei de tip <code>struct LinkedList</code> folosind operatorul &.</div>
-=== Eliminarea unui element din mulțime ===
-Pentru operația de eliminare se definește următoarea funcție:
-<syntaxhighlight lang="C">
 /**
-  * Functia elimina elementul dat din multime daca acesta exista. Daca
+  * Metoda sterge toate elementele din map.
- *  nu exista, functia nu are nici un efect.
- * @param set multimea din care trebuie eliminat elementul.
- * @param person elementul ce trebuie eliminat.
   */
-void hashSetRemove(struct HashSet * set, struct Person person);
+void clear();
 </syntaxhighlight>
-Eliminarea se realizează în felul următor:
+Exemplu:
-# Se aplică funcția hash pe variabila <code>person</code>.
+<syntaxhighlight lang="cpp" highlight="10,13,16">
-# Folosind valoarea obținută se accesează lista de pe poziția hash-ului din <code>array</code>.
+#include <unordered_map>
-# Se folosește funcția <code>linkedListSearch</code> pentru a verifica dacă <code>person</code> există în listă.
+#include <string>
-# Dacă valoarea întoarsă este diferită de -1 atunci se folosește funcția <code>linkedListDelete</code> pentru a șterge elementul de pe poziția respectivă și size se decrementează cu 1.
+#include <cstdio>
+int main() {
+    std::unorder_map<std::string, Person> myMap;
+    Person person;
+    myMap.insert({"191010112345", person});
+    myMap["190010112345"] = person;
+    myMap.erase("098764321987");
+    printf("Map-ul contine %lu elemente.\n", myMap.size());
+    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
+    myMap.erase("191010112345");
+    printf("Map-ul contine %lu elemente.\n", myMap.size());
+    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
+    myMap.clear();
+    printf("Map-ul contine %lu elemente.\n", myMap.size());
+    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
-* Complexitate în '''timp''': O(1) best case (fără coliziuni), O(1) average case pentru număr mai mic de 1000000 de persoane, O(n) worst case (același hash pentru poate persoanele).
+    return 0;
-* Complexitate în '''spațiu''': O(1)
+}
+</syntaxhighlight>
-=== Verificarea dacă un element există în mulțime ===
+=== Verificarea dacă o cheie există în map ===
-Pentru a verifica dacă un element există în mulțime, se definește următoarea funcție:
+Pentru a verifica dacă o cheie există în map, se definește următoarea funcție:
-<syntaxhighlight lang="C">
+<syntaxhighlight lang="cpp">
 /**
-  * Functia intoarce 1 daca elementul specificat exista in multime.
+  * Functia intoarce 1 daca cheia specificata exista in map, 0 in rest.
- * @param set multimea in care se cauta elementul.
+  * @param key cheia cautata.
-  * @param person elementul cautat.
+  * @return 1 daca cheia exista in map, 0 daca nu.
-  * @return 1 daca elementul exista in multime, 0 daca nu.
   */
-char hashSetContains(struct HashSet * set, struct Person person);
+uint64_t count(K key);
 </syntaxhighlight>
-Verificarea unui element dacă este sau nu în mulțime se realizează în felul următor:
+Exemplu:
-# Se aplică funcția hash pe variabila <code>person</code>.
+<syntaxhighlight lang="cpp" highlight="14,15">
-# Folosind valoarea obținută se accesează lista de pe poziția hash-ului din <code>array</code>.
+#include <unordered_map>
-# Se folosește funcția <code>linkedListSearch</code> pentru a verifica dacă <code>person</code> există în listă.
+#include <string>
-# Dacă valoarea întoarsă este diferită de -1 atunci se întoarce 1, altfel se întoarce 0.
+#include <cstdio>
+int main() {
+    std::unorder_map<std::string, Person> myMap;
+    Person person;
+    myMap.insert({"191010112345", person});
+    myMap["190010112345"] = person;
+    myMap.erase("098764321987");
+    printf("Map-ul contine %lu elemente.\n", myMap.size());
+    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
+    myMap.erase("191010112345");
+    printf("Cheia 123 apare in map: %d\n", myMap.count("123"));
+    printf("Cheia 190010112345 apare in map: %d\n", myMap.count("190010112345"));
+    printf("Map-ul contine %lu elemente.\n", myMap.size());
+    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
+    myMap.clear();
+    printf("Map-ul contine %lu elemente.\n", myMap.size());
+    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
+    return 0;
+}
+</syntaxhighlight>
-* Complexitate în '''timp''': O(1) best case (fără coliziuni), O(1) average case pentru număr mai mic de 1000000 de persoane, O(n) worst case (același hash pentru poate persoanele).
+=== Căutarea unei valori după cheie ===
-* Complexitate în '''spațiu''': O(1)
-=== Ștergerea unui <code>HashSet</code>===
+Pentru a căuta o valoare după cheie, se definește următoarele metode:
-Pentru dezalocarea unui <code>HashSet</code>, se definește următoarea funcție:
 <syntaxhighlight lang="C">
 /**
-  * Functia sterge hash set-ul specificat.
+  * Metoda intoarce a referinta la valoarea asociată cheii key.
-  * @param set hash set-ul ce trebuie sters.
+  * @param key cheia cautata.
+ * @return valoarea asociată cheii, dacă aceasta există,
+ *  sau se generează o eroare daca cheia nu exista in map.
   */
-void deleteHashSet(struct HashSet * set);
+V& at(K key);
-</syntaxhighlight>
-Pentru ștergerea unui <code>HashSet</code> se urmează următorii pași:
-# Se iterează peste tot <code>array</code>-ul, ștergându-se toate nodurile din toate listele.
-# Se șterge memoria alocată pentru structura de tip <code>HashSet</code>.
-* Complexitate în '''timp''': O(MAX_HASH)
-* Complexitate în '''spațiu''': O(1)
--->
-== Implementarea map-urilor cu arbori binari de căutare (Binary Search Trees - BST) ==
- Pentru a putea plasa elemente într-un map implementat cu arbori binari de căutare, pe mulțimea cheilor
- trebuie să existe definită o relație de ordine.
- Map-urile implementate cu arbori binari de căutare, în plus față proprietățile map-urilor definite mai sus, garantează
- faptul că elementele sunt plasate în ordinea cheilor în structură (Ordered Map).
-Din acest motiv trebuie definită o funcție care să compare două chei. Vom numi această funcție <code>compare</code> și se ca comporta similar cu funcția <code>strcmp</code>: va întoarce o valoare pozitivă dacă primul element e mai mare, o valoare negativă dacă al doilea element e mai mare și 0 dacă elementele sunt egale:
-<syntaxhighlight lang="c">
 /**
-  * Compara value1 cu value2 si intoarce o valoare corespunzătoare.
+  * Operatorul intoarce o referinta la valoarea asociată cheii key.
-  * @param value1 prima valoare de comparat.
+  * @param key cheia cautata.
- * @param value2 a doua valoare de comparat.
+  * @return valoarea asociată cheii, dacă aceasta există,
-  * @return o valoare pozitivă dacă primul element e mai mare, o
+  *  sau o valoare neutra daca nu există (care se si adauga in map).
-  *  valoare negativă dacă al doilea element e mai mare și 0 dacă
- *  elementele sunt egale.
   */
-int compare(K value1, K value2);
+V& operator[](K key);
 </syntaxhighlight>
-=== Tipul de date și funcțiile de bază ===
+Exemplu:
+<syntaxhighlight lang="cpp" highlight="10,11">
-În continuare vom prezenta un exemplu de map pentru elemente de tip "server" implementată cu arbori binari de căutare. În primul rând vom defini structura ce memorează datele legate de un server:
+#include <unordered_map>
-<syntaxhighlight lang="c">
+#include <string>
-struct Server {
+#include <cstdio>
-    /* Numele server-ului in retea - sir de caractere */
-    char hostname[30];
+int main() {
+     std::unorder_map<std::string, Person> myMap;
-    /* Adresa IP a server-ului o secvență de 4 valori numerice între 0 și 255 (ex: 192.168.1.10) */
+     Person person;
-    unsigned char ipv4[4];
+     person.firstName = "Ghita";
+     myMap.insert({"191010112345", person});
-     /* Adresa hardware pentru adaptorul de retea - o secventa de 6 bytes, in hexa (ex: 60:57:18:6e:a8:e8). */
+     printf("Numele persoanei cu cheia 191010112345 este: %s\n", myMap.at("191010112345").fullName.c_str());
-     char hardwareAddress[6];
+     printf("Numele persoanei cu cheia 191010112345 este: %s\n", myMap["191010112345"].fullName.c_str());
+     return 0;
-     /* Tipul procesorului - sir de caractere. */
+}
-    char cpuType[10];
-     /* Frecventa procesorului in Gigahertz. */
-    float cpuFrequencyGhz;
-     /* Cantitatea de memorie RAM, in Gigabytes. */
-    float ramMemoryGigaBytes;
-     /* Capacitatea discului, in Terabytes. */
-     float diskCapacityTeraBytes;
-};
 </syntaxhighlight>
-Vom folosi pe post de cheie în map hostname-ul server-ului, prin urmare definim:
-* tipul de date al cheii este '''char *''';
-* tipul de date al valorii este '''struct Server''';
-Pentru a implementa un map de servere folosind BST, avem întâi nevoie să definim funcția de comparare a două chei:
+== Implementarea de structuri asociative cu arbori binari de căutare  ==
-<syntaxhighlight lang="c">
-/**
- * Compara name1 cu name2 si intoarce o valoare corespunzătoare.
- * @param name1 primul nume de comparat.
-  * @param name2 al doilea nume de comparat.
- * @return o valoare pozitivă dacă primul nume este mai mare, o
- *  valoare negativă dacă al doilea nume este mai mare și 0 dacă
- *  numele sunt egale.
- */
-int compare(char * name1, char * name2);
-</syntaxhighlight>
-=== Structurile <code>TreeMap</code>, <code>TreeNode</code> și <code>Pair</code> ===
+Definirea arborilor binari de căutare și a proprietăților lor s-au făcut în laboratorul 5 ([[SDA Lucrarea 5#Implementarea de mulțimi cu arbori binari de căutare (BST)]]).
-Pentru stocarea datelor necesare pentru map, definim următoarele structuri:
+=== Clasa <code>std::map</code> ===
-<syntaxhighlight lang="C">
+Pentru stocarea datelor necesare map-ului, În STL se definește clasa <code>std::map</code> în header-ul <code>map</code>. Aceasta este o clasă de tip template care se parametrizează cu două tipuri de date: tipul pentru cheie și tipul pentru valoare:
-struct Pair {
-    char * key;
-    struct Server value;
-};
-struct TreeNode {
+<syntaxhighlight lang="cpp">
-    struct TreeNode * parent;
+#include <map>
-    struct TreeNode * left;
+#include <string>
-    struct TreeNode * right;
-    struct Pair pair;
-};
-struct TreeMap {
+int main() {
-     struct TreeNode * root;
+     std::map<std::string, Person> myMap; // un map de la string la Person
-     unsigned size;
+     return 0;
-};
+}
 </syntaxhighlight>
-=== Crearea unui <code>TreeMap</code> ===
+=== Crearea unui <code>std::map</code>===
-Pentru a crea un <code>TreeMap</code>, definim următoarea funcție:
+Pentru crearea unui <code>std::map</code>, se definește următorul constructor:
+<syntaxhighlight lang="cpp">
-<syntaxhighlight lang="C">
 /**
-  * Functia aloca memorie si intoarce un pointer la un nou TreeMap.
+  * Constructorul creeaza un map nou și inițializează structurile de date interne.
- * @return adresa noului TreeMap.
   */
-struct TreeMap * createTreeMap();
+map();
 </syntaxhighlight>
-Funcția trebuie să realizeze următorii pași:
+Exemplu:
-# Se alocă memorie pentru un nou <code>struct TreeMap</code> ce trebuie inițializată automat cu 0.
+<syntaxhighlight lang="cpp" highlight="5">
-# Se întoarce adresa alocată.
+#include <map>
+#include <string>
-* Complexitate în '''timp''': O(1)
+int main() {
-* Complexitate în '''spațiu''': O(1)
+    std::map<std::string, Person> myMap;
+    Person person;
+    myMap["190010112345"] = person;
+    return 0;
+}
+</syntaxhighlight>
 === Interogarea numărului de elemente din map ===
-Pentru interogarea numărului de elemente din map definim:
+Pentru interogarea numărului de elemente din map se definesc:
-<syntaxhighlight lang="C">
+<syntaxhighlight lang="cpp">
 /**
-  * Functia intoarce numarul de elemente din map.
+  * Metoda intoarce numarul de elemente din map.
- * @param map map-ul pentru care se cere dimensiunea.
   * @return numarul de elemente din map.
   */
-unsigned treeMapSize(struct TreeMap * map);
+uint64_t size();
-</syntaxhighlight>
-Funcția va întoarce valoarea din câmpul <code>size</code> din structură.
-* Complexitate în '''timp''': O(1)
-* Complexitate în '''spațiu''': O(1)
-Pentru a afla dacă map-ul este gol definim:
-<syntaxhighlight lang="C">
 /**
-  * Functia intoarce 1 dacă map-ul nu conține nici un element.
+  * Metoda intoarce true dacă map-ul nu conține nici un element.
- * @param map map-ul de interes.
+  * @return true dacă map-ul este gol, false în rest.
-  * @return 1 dacă map-ul este gol, 0 în rest.
   */
-char treeMapIsEmpty(struct TreeMap * map);
+bool empty();
 </syntaxhighlight>
-Funcția va întoarce 1 dacă valoarea din câmpul <code>size</code> este 0.
+Exemplu:
+<syntaxhighlight lang="cpp" highlight="9,10">
+#include <map>
+#include <string>
+#include <cstdio>
-* Complexitate în '''timp''': O(1)
+int main() {
-* Complexitate în '''spațiu''': O(1)
+    std::map<std::string, Person> myMap;
+    Person person;
+    myMap["190010112345"] = person;
+    printf("Map-ul contine %lu elemente.\n", myMap.size());
+    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
+    return 0;
+}
+</syntaxhighlight>
-=== Adăugarea unui element în map ===
+=== Adăugarea unei perechi cheie-valoare în map ===
-Pentru operația de adăugare se definește următoarea funcție:
+Pentru operația de adăugare se definesc următoarele metode:
-<syntaxhighlight lang="C">
+<syntaxhighlight lang="cpp">
 /**
-  * Functia adauga elementul dat in map. Daca
+  * Metoda adauga perechea data in map daca cheia nu exista.
- *  cheia exista deja, perechea existenta este suprascrisa.
+  * @param keyValuePair o pereche cheie-valoare
-  * @param map map-ul in care trebuie adaugat elementul.
+  * @return o pereche iterator-bool, unde iteratorul identifică perechea
-  * @param key cheia din map (numele server-ului)
+ *   introdusă în map, sau cea existentă cu aceeași cheie, iar bool spune daca
-  * @param value server-ul ce trebuie adaugat.
+  *   perechea a fost introdusa sau nu (pentru ca exista deja).
   */
-void treeMapPut(struct TreeMap * map, char * key, struct Server value);
+pair<iterator, bool> insert(pair<K, V> keyValuePair);
-</syntaxhighlight>
-Adăugarea se realizează în felul următor:
-# Dacă dimensiunea mulțimii este 0, se alocă memorie pentru un nod nou <code>newNode</code> în care:
-#* <code>pair.key</code> va lua valoarea lui <code>key</code>
-#* <code>pair.value</code> va lua valoarea lui <code>value</code>
-#* <code>parent</code>, <code>left</code> și <code>right</code> vor lua valoarea <code>NULL</code>.
-# Câmpul <code>root</code> ia valoarea <code>newNode</code>, <code>size</code> se incrementează și funcția se încheie.
-# Altfel, se definește o variabilă de tip nod numită <code>tmpNode</code> care se inițializează cu valoarea câmpului <code>root</code>.
-# Într-o buclă infinită se realizează următorii pași:
-## Dacă rezultatul funcției <code>compare</code> cu argumentele <code>tmpNode->pair.key</code> și <code>key</code> este 0 (elementele sunt egale), <code>tmpNode->pair.key</code> ia valoarea <code>key</code>, <code>tmpNode->pair.value</code> ia valoarea <code>value</code> și funcția se încheie.
-## Dacă rezultatul funcției <code>compare</code> cu argumentele <code>tmpNode->pair.key</code> și <code>key</code> este mai mare ca 0 și <code>tmpNode->left</code> este diferit de <code>NULL</code>, atunci <code>tmpNode</code> ia valoarea <code>tmpNode->left</code>.
-## Dacă rezultatul funcției <code>compare</code> cu argumentele <code>tmpNode->pair.key</code> și <code>key</code> este mai mare ca 0 și <code>tmpNode->left</code> este egal cu <code>NULL</code>, atunci se alocă memorie pentru un nod <code>newNode</code> nou după regula de la 1, <code>newNode->parent</code> ia valoarea lui <code>tmpNode</code>, <code>tmpNode->left</code> ia valoarea lui <code>newNode</code>, <code>size</code> se incrementează cu 1 și funcția se încheie.
-## Dacă rezultatul funcției <code>compare</code> cu argumentele <code>tmpNode->pair.key</code> și <code>key</code> este mai mică ca 0 și <code>tmpNode->right</code> este diferit de <code>NULL</code>, atunci <code>tmpNode</code> ia valoarea <code>tmpNode->right</code>.
-## Dacă rezultatul funcției <code>compare</code> cu argumentele <code>tmpNode->pair.key</code> și <code>key</code> este mai mică ca 0 și <code>tmpNode->right</code> este egal cu <code>NULL</code>, atunci se alocă memorie pentru un nod <code>newNode</code> nou după regula de la 1, <code>newNode->parent</code> ia valoarea lui <code>tmpNode</code>, <code>tmpNode->right</code> ia valoarea lui <code>newNode</code>, <code>size</code> se incrementează cu 1 și funcția se încheie.
-* Complexitate în '''timp''': O(1) best case (element adăugat imediat sub rădăcină), O(log<sub>2</sub>n) average case (arbore echilibrat), O(n) worst case (arbore dezechilibrat).
-* Complexitate în '''spațiu''': O(1)
-=== Verificarea dacă o cheie există în map ===
-Pentru operația de căutare a unei chei se definește următoarea funcție:
-<syntaxhighlight lang="C">
 /**
-  * Functia cauta cheia data în map.
+  * Metoda ia ca argument o cheie și intoarce o referinta (LVALUE) la
-  * @param key cheia de cautat
+ *  valoarea asociată. Dacă cheia nu există în map, se adaugă cu o valoare
-  * @return 1 daca cheia exista in map, 0 daca nu.
+ *  neutră.
+  * @param key cheia ce se dorește adăugată (sau interogată).
+  * @return o referință la valoarea asociată cheii.
   */
-char treeMapHasKey(struct TreeMap * map, char * key);
+V & operator[](K key);
 </syntaxhighlight>
-Căutarea unei chei într-un map se realizează în felul următor:
+Exemplu:
-# Se definește un pointer la nod numit <code>tmpNode</code> care se inițializează cu valoarea lui <code>root</code>.
+<syntaxhighlight lang="cpp" highlight="8-9">
-# Cât timp <code>tmpNode</code> este diferit de <code>NULL</code>:
+#include <map>
-#* Dacă rezultatul funcției <code>compare</code> cu argumentele <code>tmpNode->pair.key</code> și <code>key</code> este 0, se întoarce valoarea 1 (elementul a fost găsit).
+#include <string>
-#* Dacă rezultatul funcției <code>compare</code> cu argumentele <code>tmpNode->pair.key</code> și <code>key</code> este pozitiv, <code>tmpNode</code> ia valoarea lui <code>tmpNode->left</code>.
+#include <cstdio>
-#* Dacă rezultatul funcției <code>compare</code> cu argumentele <code>tmpNode->pair.key</code> și <code>key</code> este negativ, <code>tmpNode</code> ia valoarea lui <code>tmpNode->right</code>.
-# Când s-a ieșit din buclă, se întoarce 0 (elementul nu a fost găsit).
+int main() {
+    std::map<std::string, Person> myMap;
-* Complexitate în '''timp''': O(1) best case (element găsit în rădăcină), O(log<sub>2</sub>n) average case (arbore echilibrat), O(n) worst case (arbore dezechilibrat).
+    Person person;
-* Complexitate în '''spațiu''': O(1)
+    myMap.insert({"191010112345", person});
+    myMap["190010112345"] = person;
-=== Căutarea unei valori după o cheie dată ===
+    printf("Map-ul contine %lu elemente.\n", myMap.size());
+    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
-Pentru operația de căutare a unei valori după o cheie dată se definește următoarea funcție:
+    return 0;
+}
-<syntaxhighlight lang="C">
-/**
- * Functia cauta o valoarea dupa cheia data în map.
- * @param key cheia de cautat
- * @return valoarea asociată cheii sau o structura goala daca cheia nu exista in map.
- */
-struct Server treeMapGet(struct TreeMap * map, char * key);
 </syntaxhighlight>
-Căutarea unei valori după o cheie într-un map se realizează în felul următor:
+=== Eliminarea unei chei din map ===
-# Se definește un pointer la nod numit <code>tmpNode</code> care se inițializează cu valoarea lui <code>root</code>.
-# Cât timp <code>tmpNode</code> este diferit de <code>NULL</code>:
-#* Dacă rezultatul funcției <code>compare</code> cu argumentele <code>tmpNode->pair.key</code> și <code>key</code> este 0, se întoarce <code>tmpNode->pair.value</code> (elementul a fost găsit).
-#* Dacă rezultatul funcției <code>compare</code> cu argumentele <code>tmpNode->pair.key</code> și <code>key</code> este pozitiv, <code>tmpNode</code> ia valoarea lui <code>tmpNode->left</code>.
-#* Dacă rezultatul funcției <code>compare</code> cu argumentele <code>tmpNode->pair.key</code> și <code>key</code> este negativ, <code>tmpNode</code> ia valoarea lui <code>tmpNode->right</code>.
-# Când s-a ieșit din buclă, se întoarce valoarea unei structuri de tip Server fără conținut (elementul nu a fost găsit).
-* Complexitate în '''timp''': O(1) best case (element găsit în rădăcină), O(log<sub>2</sub>n) average case (arbore echilibrat), O(n) worst case (arbore dezechilibrat).
-* Complexitate în '''spațiu''': O(1)
-=== Eliminarea unui element din map ===
-Pentru operația de eliminare se definește următoarea funcție:
+Pentru operația de eliminare se definește următoarea metodă:
-<syntaxhighlight lang="C">
+<syntaxhighlight lang="cpp">
 /**
-  * Functia elimina perechea cu cheia dată din map daca acesta exista. Daca
+  * Metoda elimina cheia data din map daca acesta exista. Daca
   *  nu exista, functia nu are nici un efect.
- * @param map map-ul din care trebuie eliminat elementul.
+  * @param key cheia ce trebuie eliminata.
-  * @param key cheia perechii ce trebuie eliminată.
   */
-void treeMapRemove(struct TreeMap * map, char * key);
+void erase(K key);
-</syntaxhighlight>
-Eliminarea se realizează în felul următor (o descriere în imagini poate fi găsită [http://www.algolist.net/Data_structures/Binary_search_tree/Removal aici] - nu încercați să folosiți codul de pe acea pagină deoarece structurile din platformă diferă și în plus limbajul este C++ și nu va compila):
-# Folosind un pointer la nod <code>tmpNode</code>, se folosește tehnica de la căutarea chei în map pentru a identifica nodul care memorează cheia <code>key</code>. Dacă funcția ajunge la frunze fără a găsi server-ul căutat, funcția se încheie (cheia nu există în map). Altfel, <code>tmpNode</code> va fi pointer la nodul ce trebuie eliminat. În plus, se va defini o variabilă de tip char <code>direction</code> care la fiecare avansare în arbore va lua valoarea -1 dacă avansarea s-a făcut spre stânga și 1 dacă s-a făcut spre dreapta, astfel încât atunci când <code>tmpNode</code> este pointer la nodul ce trebuie șters, <code>direction</code> va fi 1 sau -1 în funcție de poziția nodului <code>tmpNode</code> față de nodul părinte.
-# Dacă <code>tmpNode->left</code> și <code>tmpNode->right</code> sunt ambele <code>NULL</code> (nodul ce trebuie șters este frunză), atunci, dacă <code>direction</code> este -1, <code>tmpNode->parent->left</code> ia valoarea <code>NULL</code>, altfel <code>tmpNode->parent->right</code> ia valoarea <code>NULL</code>, nodul <code>tmpNode</code> este dezalocat, <code>size</code> se decrementează și funcția se încheie.
-# Dacă <code>tmpNode->left</code> este <code>NULL</code> și <code>tmpNode->right</code> este diferit de <code>NULL</code> (nodul are un singur copil), atunci, dacă <code>direction</code> este -1, <code>tmpNode->parent->left</code> ia valoarea <code>tmpNode->right</code>, altfel <code>tmpNode->parent->right</code> ia valoarea <code>tmpNode->right</code>, nodul <code>tmpNode</code> este dezalocat, <code>size</code> se decrementează și funcția se încheie.
-# Dacă <code>tmpNode->left</code> este diferit de <code>NULL</code> și <code>tmpNode->right</code> este <code>NULL</code> (nodul are un singur copil), atunci, dacă <code>direction</code> este -1, <code>tmpNode->parent->left</code> ia valoarea <code>tmpNode->left</code>, altfel <code>tmpNode->parent->right</code> ia valoarea <code>tmpNode->left</code>, nodul <code>tmpNode</code> este dezalocat, <code>size</code> se decrementează și funcția se încheie.
-# Dacă <code>tmpNode->left</code> și <code>tmpNode->right</code> sunt ambele diferite de <code>NULL</code> (nodul ce trebuie șters are doi copii), atunci:
-#* Se foloște un al doilea pointer la nod numit <code>minSubtreeNode</code> cu care se caută cea mai mică cheie din subarborele din dreapta nodului <code>tmpNode</code>.
-#* <code>tmpNode->pair</code> ia valoarea <code>minSubtreeNode->pair</code> apoi se șterge <code>minSubtreeNode</code> după aceleași reguli de mai sus.
-* Complexitate în '''timp''': O(1) best case (element găsit imediat sub rădăcină), O(log<sub>2</sub>n) average case (arbore echilibrat), O(n) worst case (arbore dezechilibrat).
-* Complexitate în '''spațiu''': O(1)
-=== Ștergerea unui <code>TreeMap</code>===
-Pentru dezalocarea unui <code>TreeMap</code>, se definește următoarea funcție:
-<syntaxhighlight lang="C">
 /**
-  * Functia sterge tree map-ul specificat.
+  * Metoda sterge toate elementele din map.
- * @param map tree map-ul ce trebuie sters.
   */
-void deleteTreeMap(struct TreeMap * map);
+void clear();
 </syntaxhighlight>
-Pentru ștergerea unui <code>TreeMap</code> se urmează următorii pași:
+Exemplu:
-# Se realizează o parcurgere în post-ordine (stânga-dreapta-rădăcină) și se șterg toate nodurile din arbore.
+<syntaxhighlight lang="cpp" highlight="10,13,16">
-# Se șterge memoria alocată pentru structura de tip <code>TreeMap</code>.
+#include <map>
+#include <string>
+#include <cstdio>
+int main() {
+    std::map<std::string, Person> myMap;
+    Person person;
+    myMap.insert({"191010112345", person});
+    myMap["190010112345"] = person;
+    myMap.erase("098764321987");
+    printf("Map-ul contine %lu elemente.\n", myMap.size());
+    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
+    myMap.erase("191010112345");
+    printf("Map-ul contine %lu elemente.\n", myMap.size());
+    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
+    myMap.clear();
+    printf("Map-ul contine %lu elemente.\n", myMap.size());
+    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
-* Complexitate în '''timp''': O(n)
+    return 0;
-* Complexitate în '''spațiu''': O(1)
+}
+</syntaxhighlight>
-= Exerciții =
+=== Verificarea dacă o cheie există în map ===
-<!--
-== Săptămâna 2 ==
-<ol>
-<li> Dându-se fișierele [[Fișier:linkedList.h]], [[Fișier:linkedList.c]] și header-ele <code>hashSet.h</code> și <code>person.h</code> de mai jos, implementați toate funcțiile definite în două fișiere sursă numite <code>person.c</code> și <code>hashSet.c</code>:
-<ul><li> <code>person.h</code>:
-<syntaxhighlight lang="C">
-#ifndef PERSON_H
-#define PERSON_H
-struct Person {
+Pentru a verifica dacă o cheie există în map, se definește următoarea funcție:
-    char firstName[30];
-    char lastName[30];
-    char idNumber[9]; // seria si numarul de buletin
-    char address[255];
-    char birthday[11];
-    char cnp[14];
-};
+<syntaxhighlight lang="cpp">
 /**
-  * Functia intoarce 1 daca CNP-urile celor doua persoane sunt egale.
+  * Functia intoarce 1 daca cheia specificata exista in map, 0 in rest.
-  * @param person1 prima persoana de comparat.
+  * @param key cheia cautata.
- * @param person2 a doua persoana de comparat.
+  * @return 1 daca cheia exista in map, 0 daca nu.
-  * @return 1 daca CNP-urile celor doua persoane sunt identice.
   */
-char equals(struct Person person1, struct Person person2);
+uint64_t count(K key);
-/**
- * Functie hash pentru structurile de tip Person.
- * @param person peroana pentru care se doreste codul hash.
- * @return codul hash al persoanei person
- */
-unsigned hash(struct Person person);
-#define T struct Person
-#endif
 </syntaxhighlight>
-</li>
-<li> <code>hashset.h</code>:
-<syntaxhighlight lang="C">
-#ifndef HASH_SET_H
-#define HASH_SET_H
-#include "linkedList.h"
-#include "person.h"
-#define MAX_HASH 1000000
-struct HashSet {
+Exemplu:
-    struct LinkedList array[MAX_HASH]; // un vector de liste, una pentru fiecare valoare posibila de hash
+<syntaxhighlight lang="cpp" highlight="14,15">
-    unsigned size; // numarul de elemente din multime
+#include <map>
-};
+#include <string>
+#include <cstdio>
-/**
- * Functia creeaza un hashSet nou si intoarce adresa de memorie alocata.
- * @return un pointer la o structura de tip HashSet.
- */
-struct HashSet * createHashSet();
-/**
+int main() {
- * Functia intoarce numarul de elemente din multime.
+    std::map<std::string, Person> myMap;
- * @param set multimea a carei dimensiuni este ceruta.
+    Person person;
- * @return numarul de elemente din multime.
+    myMap.insert({"191010112345", person});
- */
+    myMap["190010112345"] = person;
-unsigned hashSetSize(struct HashSet * set);
+    myMap.erase("098764321987");
+    printf("Map-ul contine %lu elemente.\n", myMap.size());
+    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
+    myMap.erase("191010112345");
+    printf("Cheia 123 apare in map: %d\n", myMap.count("123"));
+    printf("Cheia 190010112345 apare in map: %d\n", myMap.count("190010112345"));
+    printf("Map-ul contine %lu elemente.\n", myMap.size());
+    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
+    myMap.clear();
+    printf("Map-ul contine %lu elemente.\n", myMap.size());
+    printf("Map-ul %s este gol!\n", myMap.empty() ? "" : "NU");
-/**
+    return 0;
- * Functia intoarce 1 dacă mulțimea nu conține nici un element.
+}
- * @param set multimea de interes.
- * @return 1 dacă mulțimea este goală, 0 în rest.
- */
-char hashSetIsEmpty(struct HashSet * set);
-/**
- * Functia adauga elementul dat in multime daca acesta nu exista. Daca
- *  exista deja, functia nu are nici un efect.
- * @param set multimea in care trebuie adaugat elementul.
- * @param person elementul ce trebuie adaugta.
- */
-void hashSetPut(struct HashSet * set, struct Person person);
-/**
- * Functia elimina elementul dat din multime daca acesta exista. Daca
- *  nu exista, functia nu are nici un efect.
- * @param set multimea din care trebuie eliminat elementul.
- * @param person elementul ce trebuie eliminat.
- */
-void hashSetRemove(struct HashSet * set, struct Person person);
-/**
- * Functia intoarce 1 daca elementul specificat exista in multime.
- * @param set multimea in care se cauta elementul.
- * @param person elementul cautat.
- * @return 1 daca elementul exista in multime, 0 daca nu.
- */
-char hashSetContains(struct HashSet * set, struct Person person);
-/**
- * Functia sterge hash set-ul specificat.
- * @param set hash set-ul ce trebuie sters.
- */
-void deleteHashSet(struct HashSet * set);
-#endif
 </syntaxhighlight>
-</li>
-</ul>
-</li>
-<li> Scrieți o altă sursă <code>main.c</code> în care să definiți o funcție <code>struct Person readFromKeyboard()</code> și o altă funcție <code>main</code> care să citească persoane de la tastatură până când numele introdus este egal cu "-" și care să afișeze câte persoane diferite au fost introduse.</li>
-</ol>
--->
-== Săptămâna 1 ==
+=== Căutarea unei valori după cheie ===
-<ol>
+Pentru a căuta o valoare după cheie, se definesc următoarele metode:
-<li> Dându-se header-ele <code>treeMap.h</code> și <code>server.h</code> de mai jos, implementați toate funcțiile definite în două fișiere sursă numite <code>server.c</code> și <code>treeMap.c</code>:
-<ul><li> <code>server.h</code>:
-<syntaxhighlight lang="C">
-#ifndef SERVER_H
-#define SERVER_H
-struct Server {
-    /* Numele server-ului in retea - sir de caractere */
-    char hostname[30];
-    /* Adresa IP a server-ului o secvență de 4 valori numerice între 0 și 255 (ex: 192.168.1.10) */
-    unsigned char ipv4[4];
-    /* Adresa hardware pentru adaptorul de retea - o secventa de 6 bytes, in hexa (ex: 60:57:18:6e:a8:e8). */
-    char hardwareAddress[6];
-    /* Tipul procesorului - sir de caractere. */
-    char cpuType[10];
-    /* Frecventa procesorului in Gigahertz. */
-    float cpuFrequencyGhz;
-    /* Cantitatea de memorie RAM, in Gigabytes. */
-    float ramMemoryGigaBytes;
-    /* Capacitatea discului, in Terabytes. */
-    float diskCapacityTeraBytes;
-};
-/**
- * Compara name1 cu name2 si intoarce o valoare corespunzătoare.
- * @param name1 primul nume de comparat.
- * @param name2 al doilea nume de comparat.
- * @return o valoare pozitivă dacă primul nume este mai mare, o
- *  valoare negativă dacă al doilea nume este mai mare și 0 dacă
- *  numele sunt egale.
- */
-int compare(char * name1, char * name2);
-#endif
-</syntaxhighlight>
-</li>
-<li> <code>treeMap.h</code>:
 <syntaxhighlight lang="C">
-#ifndef TREE_MAP_H
-#define TREE_MAP_H
-#include "server.h"
-struct Pair {
-    char * key;
-    struct Server value;
-};
-struct TreeNode {
-    struct TreeNode * parent;
-    struct TreeNode * left;
-    struct TreeNode * right;
-    struct Pair pair;
-};
-struct TreeMap {
-    struct TreeNode * root;
-    unsigned size;
-};
 /**
-  * Functia aloca memorie si intoarce un pointer la un nou TreeMap.
+  * Metoda intoarce a referinta la valoarea asociată cheii key.
-  * @return adresa noului TreeMap.
+ * @param key cheia cautata.
+  * @return valoarea asociată cheii, dacă aceasta există,
+ *  sau se generează o eroare daca cheia nu exista in map.
   */
-struct TreeMap * createTreeMap();
+V& at(K key);
 /**
-  * Functia intoarce numarul de elemente din map.
+  * Operatorul intoarce o referinta la valoarea asociată cheii key.
-  * @param map map-ul pentru care se cere dimensiunea.
+  * @param key cheia cautata.
-  * @return numarul de elemente din map.
+  * @return valoarea asociată cheii, dacă aceasta există,
+ *  sau o valoare neutra daca nu există (care se si adauga in map).
   */
-unsigned treeMapSize(struct TreeMap * map);
-/**
+V& operator[](K key);
- * Functia intoarce 1 dacă map-ul nu conține nici un element.
+</syntaxhighlight>
- * @param map map-ul de interes.
- * @return 1 dacă map-ul este gol, 0 în rest.
- */
-char treeMapIsEmpty(struct TreeMap * map);
-/**
- * Functia adauga elementul dat in map. Daca
- *  cheia exista deja, perechea existenta este suprascrisa.
- * @param map map-ul in care trebuie adaugat elementul.
- * @param key cheia din map (numele server-ului)
- * @param value server-ul ce trebuie adaugat.
- */
-void treeMapPut(struct TreeMap * map, char * key, struct Server value);
-/**
+Exemplu:
- * Functia cauta cheia data în map.
+<syntaxhighlight lang="cpp" highlight="10,11">
- * @param key cheia de cautat
+#include <map>
- * @return 1 daca cheia exista in map, 0 daca nu.
+#include <string>
- */
+#include <cstdio>
-char treeMapHasKey(struct TreeMap * map, char * key);
-/**
- * Functia cauta o valoarea dupa cheia data în map.
- * @param key cheia de cautat
- * @return valoarea asociată cheii sau o structura goala daca cheia nu exista in map.
- */
-struct Server treeMapGet(struct TreeMap * map, char * key);
-/**
- * Functia elimina perechea cu cheia dată din map daca acesta exista. Daca
- *  nu exista, functia nu are nici un efect.
- * @param map map-ul din care trebuie eliminat elementul.
- * @param key cheia perechii ce trebuie eliminată.
- */
-void treeMapRemove(struct TreeMap * map, char * key);
-/**
- * Functia sterge tree map-ul specificat.
- * @param map tree map-ul ce trebuie sters.
- */
-void deleteTreeMap(struct TreeMap * map);
-#endif
+int main() {
+    std::map<std::string, Person> myMap;
+    Person person;
+    person.firstName = "Ghita";
+    myMap.insert({"191010112345", person});
+    printf("Numele persoanei cu cheia 191010112345 este: %s\n", myMap.at("191010112345").fullName.c_str());
+    printf("Numele persoanei cu cheia 191010112345 este: %s\n", myMap["191010112345"].fullName.c_str());
+    return 0;
+}
 </syntaxhighlight>
-</li>
-</ul>
-</li>
-<li> Scrieți o altă sursă <code>main.c</code> în care să definiți o funcție <code>struct Server readFromKeyboard()</code> și o altă funcție <code>main</code> care să citească informații legate de servere de la tastatură până când ''hostname''-ul introdus este egal cu "-". Scrieți apoi o buclă care să citească nume de la tastatură, să caute server-ul în map și dacă nu este să afișeze un mesaj iar dacă este, să afișeze informații despre el. Programul se încheie când se introduce din nou "-".</li>
-</ol>

SDA Lucrarea 6: Diferență între versiuni

Versiunea curentă din 14 mai 2017 19:58

Structura de date asociativă - Map

Implementarea de structuri asociative cu funcții hash

Tipul de date și funcțiile de bază

Clasa std::unordered_map

Crearea unui std::unordered_map

Interogarea numărului de elemente din map

Adăugarea unei perechi cheie-valoare în map

Eliminarea unei chei din map

Verificarea dacă o cheie există în map

Căutarea unei valori după cheie

Implementarea de structuri asociative cu arbori binari de căutare

Clasa std::map

Crearea unui std::map

Interogarea numărului de elemente din map

Adăugarea unei perechi cheie-valoare în map

Eliminarea unei chei din map

Verificarea dacă o cheie există în map

Căutarea unei valori după cheie

Meniu de navigare

Căutare

Clasa `std::unordered_map`

Crearea unui `std::unordered_map`

Clasa `std::map`

Crearea unui `std::map`