Diferență între revizuiri ale paginii „SDA Lucrarea 6”
(Nu s-au afișat 45 de versiuni intermediare efectuate de același utilizator) | |||
Linia 3: | Linia 3: | ||
= Structura de date asociativă - Map = | = Structura de date asociativă - Map = | ||
− | Structura de date asociativă este o structură de date abstractă care stochează perechi de elemente cheie-valoare, | + | Structura de date asociativă (map) este o structură de date abstractă care stochează perechi de elemente cheie-valoare, |
− | astfel încât nu pot exista două perechi cu aceeași cheie | + | î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 | + | În esență, un ''map'' este o mulțime (set) de chei care sunt întotdeauna stocate împreună cu o valoare. |
[[Fișier:map.png]] | [[Fișier:map.png]] | ||
Linia 13: | Linia 13: | ||
# Datele sunt plasate într-o ordine oarecare stabilită arbitrar de structură. | # Datele sunt plasate într-o ordine oarecare stabilită arbitrar de structură. | ||
# Numărul de elemente ce poate fi stocat de structură este nelimitat. | # Numărul de elemente ce poate fi stocat de structură este nelimitat. | ||
− | # Elementele stocate în | + | # Elementele stocate în map sunt de același fel. |
# Tipul de date al cheii și tipul de date al valorii pot fi diferite. | # 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 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. | ||
Linia 20: | Linia 20: | ||
# Interogarea numărului de elemente din map. | # Interogarea numărului de elemente din map. | ||
# Verificarea dacă map-ul este gol. | # Verificarea dacă map-ul este gol. | ||
− | # Adăugarea perechi cheie-valoare ('' | + | # Adăugarea perechi cheie-valoare (''insert'') - dacă cheia există deja în map, aceasta nu se înlocuiește. |
− | # Verificarea dacă o | + | # Verificarea dacă o cheie există în map (''count''). |
− | # Căutarea unei valori după o cheie dată ('' | + | # Căutarea unei valori după o cheie dată (''at''); |
− | # Eliminarea unei chei din map ('' | + | # 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ă === | === Tipul de date și funcțiile de bază === | ||
− | În continuare vom prezenta un exemplu de | + | Î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=" | + | <syntaxhighlight lang="cpp"> |
struct Person { | 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; | |
}; | }; | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | + | 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]]). | |
− | < | + | === Clasa <code>std::unordered_map</code> === |
− | / | + | |
− | + | 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: | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | </ | ||
− | + | <syntaxhighlight lang="cpp"> | |
+ | #include <unordered_map> | ||
+ | #include <string> | ||
− | + | int main() { | |
+ | std::unorder_map<std::string, Person> myMap; // un map de la string la Person | ||
+ | return 0; | ||
+ | } | ||
+ | </syntaxhighlight> | ||
− | + | === Crearea unui <code>std::unordered_map</code>=== | |
− | <syntaxhighlight lang=" | + | Pentru crearea unui <code>std::unordered_map</code>, se definește următorul constructor: |
+ | <syntaxhighlight lang="cpp"> | ||
/** | /** | ||
− | * | + | * Constructorul creeaza un map nou și inițializează structurile de date interne. |
− | |||
− | |||
*/ | */ | ||
− | + | unordered_map(); | |
</syntaxhighlight> | </syntaxhighlight> | ||
− | + | Exemplu: | |
− | + | <syntaxhighlight lang="cpp" highlight="5"> | |
− | + | #include <unordered_map> | |
+ | #include <string> | ||
− | + | int main() { | |
+ | std::unorder_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 se definesc: | |
− | + | <syntaxhighlight lang="cpp"> | |
− | + | /** | |
− | + | * 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 | + | * @return true dacă map-ul este gol, false în rest. |
*/ | */ | ||
− | + | bool empty(); | |
+ | |||
</syntaxhighlight> | </syntaxhighlight> | ||
− | + | Exemplu: | |
− | # | + | <syntaxhighlight lang="cpp" highlight="9,10"> |
− | # | + | #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; | ||
+ | } | ||
+ | </syntaxhighlight> | ||
− | === | + | === Adăugarea unei perechi cheie-valoare în map === |
− | Pentru | + | Pentru operația de adăugare se definesc următoarele metode: |
− | <syntaxhighlight lang=" | + | <syntaxhighlight lang="cpp"> |
/** | /** | ||
− | * | + | * Metoda adauga perechea data in map daca cheia nu exista. |
− | * @param | + | * @param keyValuePair o pereche cheie-valoare |
− | * @return | + | * @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 |
− | * @param | + | * valoarea asociată. Dacă cheia nu există în map, se adaugă cu o valoare |
− | * @return | + | * neutră. |
+ | * @param key cheia ce se dorește adăugată (sau interogată). | ||
+ | * @return o referință la valoarea asociată cheii. | ||
*/ | */ | ||
− | + | V & operator[](K key); | |
</syntaxhighlight> | </syntaxhighlight> | ||
− | + | 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> | ||
− | === | + | === Eliminarea unei chei din map === |
− | Pentru operația de | + | Pentru operația de eliminare se definește următoarea metodă: |
− | <syntaxhighlight lang=" | + | <syntaxhighlight lang="cpp"> |
/** | /** | ||
− | * | + | * Metoda elimina cheia data din map daca acesta exista. Daca |
− | * exista | + | * nu exista, functia nu are nici un efect. |
− | * @param | + | * @param key cheia ce trebuie eliminata. |
− | |||
*/ | */ | ||
− | void | + | void erase(K key); |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
/** | /** | ||
− | * | + | * Metoda sterge toate elementele din map. |
− | |||
− | |||
− | |||
*/ | */ | ||
− | void | + | void clear(); |
</syntaxhighlight> | </syntaxhighlight> | ||
− | + | Exemplu: | |
− | + | <syntaxhighlight lang="cpp" highlight="10,13,16"> | |
− | # | + | #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; | |
− | + | } | |
+ | </syntaxhighlight> | ||
− | === Verificarea dacă | + | === Verificarea dacă o cheie există în map === |
− | Pentru a verifica dacă | + | Pentru a verifica dacă o cheie există în map, se definește următoarea funcție: |
− | <syntaxhighlight lang=" | + | <syntaxhighlight lang="cpp"> |
/** | /** | ||
− | * Functia intoarce 1 daca | + | * Functia intoarce 1 daca cheia specificata exista in map, 0 in rest. |
− | + | * @param key cheia cautata. | |
− | * @param | + | * @return 1 daca cheia exista in map, 0 daca nu. |
− | * @return 1 daca | ||
*/ | */ | ||
− | + | uint64_t count(K key); | |
</syntaxhighlight> | </syntaxhighlight> | ||
− | + | Exemplu: | |
− | + | <syntaxhighlight lang="cpp" highlight="14,15"> | |
− | # | + | #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; | ||
+ | } | ||
+ | </syntaxhighlight> | ||
− | + | === Căutarea unei valori după cheie === | |
− | |||
− | + | Pentru a căuta o valoare după cheie, se definește următoarele metode: | |
− | |||
<syntaxhighlight lang="C"> | <syntaxhighlight lang="C"> | ||
/** | /** | ||
− | * | + | * Metoda intoarce a referinta la valoarea asociată cheii key. |
− | * @param | + | * @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 | + | * @param key cheia cautata. |
− | + | * @return valoarea asociată cheii, dacă aceasta există, | |
− | * @return | + | * sau o valoare neutra daca nu există (care se si adauga in map). |
− | * valoare | ||
− | |||
*/ | */ | ||
− | + | ||
+ | V& operator[](K key); | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | + | Exemplu: | |
− | + | <syntaxhighlight lang="cpp" highlight="10,11"> | |
− | + | #include <unordered_map> | |
− | <syntaxhighlight lang=" | + | #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; | |
− | + | } | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | |||
− | |||
− | |||
− | + | == 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 <code>std::map</code> === | |
− | < | + | 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: |
− | |||
− | |||
− | |||
− | |||
− | + | <syntaxhighlight lang="cpp"> | |
− | + | #include <map> | |
− | + | #include <string> | |
− | |||
− | |||
− | |||
− | + | int main() { | |
− | + | std::map<std::string, Person> myMap; // un map de la string la Person | |
− | + | return 0; | |
− | } | + | } |
</syntaxhighlight> | </syntaxhighlight> | ||
− | === Crearea unui <code> | + | === Crearea unui <code>std::map</code>=== |
− | Pentru | + | Pentru crearea unui <code>std::map</code>, se definește următorul constructor: |
− | + | <syntaxhighlight lang="cpp"> | |
− | <syntaxhighlight lang=" | ||
/** | /** | ||
− | * | + | * Constructorul creeaza un map nou și inițializează structurile de date interne. |
− | |||
*/ | */ | ||
− | + | map(); | |
</syntaxhighlight> | </syntaxhighlight> | ||
− | + | Exemplu: | |
− | + | <syntaxhighlight lang="cpp" highlight="5"> | |
− | # | + | #include <map> |
+ | #include <string> | ||
− | + | int main() { | |
− | + | std::map<std::string, Person> myMap; | |
+ | Person person; | ||
+ | myMap["190010112345"] = person; | ||
+ | return 0; | ||
+ | } | ||
+ | </syntaxhighlight> | ||
=== Interogarea numărului de elemente din map === | === Interogarea numărului de elemente din map === | ||
− | Pentru interogarea numărului de elemente din map | + | Pentru interogarea numărului de elemente din map se definesc: |
− | <syntaxhighlight lang=" | + | <syntaxhighlight lang="cpp"> |
/** | /** | ||
− | * | + | * Metoda intoarce numarul de elemente din map. |
− | |||
* @return 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. | |
− | * @return | ||
*/ | */ | ||
− | + | bool empty(); | |
+ | |||
</syntaxhighlight> | </syntaxhighlight> | ||
− | + | Exemplu: | |
+ | <syntaxhighlight lang="cpp" highlight="9,10"> | ||
+ | #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; | ||
+ | } | ||
+ | </syntaxhighlight> | ||
− | === Adăugarea | + | === Adăugarea unei perechi cheie-valoare în map === |
− | Pentru operația de adăugare se | + | Pentru operația de adăugare se definesc următoarele metode: |
− | <syntaxhighlight lang=" | + | <syntaxhighlight lang="cpp"> |
/** | /** | ||
− | * | + | * Metoda adauga perechea data in map daca cheia nu exista. |
− | + | * @param keyValuePair o pereche cheie-valoare | |
− | * @param | + | * @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 |
− | * @param key cheia | + | * valoarea asociată. Dacă cheia nu există în map, se adaugă cu o valoare |
− | * @return | + | * neutră. |
+ | * @param key cheia ce se dorește adăugată (sau interogată). | ||
+ | * @return o referință la valoarea asociată cheii. | ||
*/ | */ | ||
− | + | V & operator[](K key); | |
</syntaxhighlight> | </syntaxhighlight> | ||
+ | Exemplu: | ||
+ | <syntaxhighlight lang="cpp" highlight="8-9"> | ||
+ | #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; | ||
+ | } | ||
+ | </syntaxhighlight> | ||
+ | === Eliminarea unei chei din map === | ||
− | + | Pentru operația de eliminare se definește următoarea metodă: | |
− | + | <syntaxhighlight lang="cpp"> | |
− | |||
− | <syntaxhighlight lang=" | ||
/** | /** | ||
− | * | + | * Metoda elimina cheia data din map daca acesta exista. Daca |
* nu exista, functia nu are nici un efect. | * nu exista, functia nu are nici un efect. | ||
− | * @param | + | * @param key cheia ce trebuie eliminata. |
− | |||
*/ | */ | ||
− | void | + | void erase(K key); |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
/** | /** | ||
− | * | + | * Metoda sterge toate elementele din map. |
− | |||
− | |||
− | |||
*/ | */ | ||
− | + | void clear(); | |
</syntaxhighlight> | </syntaxhighlight> | ||
− | + | Exemplu: | |
− | + | <syntaxhighlight lang="cpp" highlight="10,13,16"> | |
− | # | + | #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; | |
− | + | } | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
</syntaxhighlight> | </syntaxhighlight> | ||
− | + | === Verificarea dacă o cheie există în map === | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | = | ||
− | + | Pentru a verifica dacă o cheie există în map, se definește următoarea funcție: | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
+ | <syntaxhighlight lang="cpp"> | ||
/** | /** | ||
− | * Functia intoarce 1 daca | + | * Functia intoarce 1 daca cheia specificata exista in map, 0 in rest. |
− | * @param | + | * @param key cheia cautata. |
− | + | * @return 1 daca cheia exista in map, 0 daca nu. | |
− | * @return 1 daca | ||
*/ | */ | ||
− | + | uint64_t count(K key); | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
</syntaxhighlight> | </syntaxhighlight> | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | Exemplu: | |
− | #include | + | <syntaxhighlight lang="cpp" highlight="14,15"> |
− | + | #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; | |
+ | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | == | + | === Căutarea unei valori după cheie === |
+ | |||
+ | Pentru a căuta o valoare după cheie, se definesc următoarele metode: | ||
− | |||
− | |||
− | |||
<syntaxhighlight lang="C"> | <syntaxhighlight lang="C"> | ||
− | + | /** | |
− | + | * 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 | + | * @param key cheia cautata. |
− | + | * @return valoarea asociată cheii, dacă aceasta există, | |
− | * @return | + | * sau o valoare neutra daca nu există (care se si adauga in map). |
− | * valoare | ||
− | |||
*/ | */ | ||
− | |||
− | + | V& operator[](K key); | |
</syntaxhighlight> | </syntaxhighlight> | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | Exemplu: | |
− | + | <syntaxhighlight lang="cpp" highlight="10,11"> | |
− | + | #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; | ||
+ | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | |||
− | |||
− | |||
− | |||
− |
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;
}