SDA Lucrarea 6 - Revizia istoricului

Rhobincu: /* Implementarea de structuri asociative cu arbori binari de căutare */

2017-05-14T19:58:10Z

Implementarea de structuri asociative cu arbori binari de căutare

Rhobincu: /* Implementarea de structuri asociative cu arbori binari de căutare */

2017-05-14T19:57:45Z

Implementarea de structuri asociative cu arbori binari de căutare

Rhobincu: /* Implementarea de structuri asociative cu funcții hash */

2017-05-14T19:57:01Z

Implementarea de structuri asociative cu funcții hash

Rhobincu: /* Structura de date asociativă - Map */

2017-05-14T19:53:18Z

Structura de date asociativă - Map

Afișare diferențe

Rhobincu: /* Căutarea unei valori după cheie */

2017-05-03T22:11:14Z

Căutarea unei valori după cheie

Rhobincu: /* Căutarea unei valori după cheie */

2017-05-03T22:10:52Z

Căutarea unei valori după cheie

Rhobincu: /* Verificarea dacă o cheie există în map */

2017-05-03T22:06:05Z

Verificarea dacă o cheie există în map

Rhobincu: /* Verificarea dacă o cheie există în map */

2017-05-03T22:05:08Z

Verificarea dacă o cheie există în map

Rhobincu: /* Implementarea de structuri asociative cu funcții hash */

2017-05-03T22:02:05Z

Implementarea de structuri asociative cu funcții hash

Rhobincu: /* Eliminarea unei chei din map */

2017-05-03T21:59:57Z

Eliminarea unei chei din map

@@ Linia 285: / Linia 285: @@
 == Implementarea de structuri asociative cu arbori binari de căutare  ==
-Definirea arborilor binari de căutare și a proprietăților lor s-a făcut în laboratorul 5 ([[SDA Lucrarea 5#Implementarea de mulțimi cu arbori binari de căutare (BST)]]).
+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> ===

@@ Linia 285: / Linia 285: @@
 == Implementarea de structuri asociative cu arbori binari de căutare  ==
-Definirea arborilor binari de căutare și a proprietăților lor s-a făcut în laboratorul 5 ([[SDA Lucrarea 5#Implementarea de mulțimi cu arbori binari de căutare]]).
+Definirea arborilor binari de căutare și a proprietăților lor s-a făcut în laboratorul 5 ([[SDA Lucrarea 5#Implementarea de mulțimi cu arbori binari de căutare (BST)]]).
 === Clasa <code>std::map</code> ===

@@ Linia 283: / Linia 283: @@
-== Implementarea de structuri asociative cu funcții hash  ==
+== Implementarea de structuri asociative cu arbori binari de căutare  ==
-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]]).
+Definirea arborilor binari de căutare și a proprietăților lor s-a făcut în laboratorul 5 ([[SDA Lucrarea 5#Implementarea de mulțimi cu arbori binari de căutare]]).
-=== Tipul de date și funcțiile de bază ===
+=== Clasa <code>std::map</code> ===
-Î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ă:
+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">
-struct Person {
+#include <map>
 #include <string>
 int main() {
-     std::unorder_map<std::string, Person> myMap; // un map de la string la Person
+     std::map<std::string, Person> myMap; // un map de la string la Person
      return 0;
+}
 </syntaxhighlight>
-=== Crearea unui <code>std::unordered_map</code>===
+=== Crearea unui <code>std::map</code>===
-Pentru crearea unui <code>std::unordered_map</code>, se definește următorul constructor:
+Pentru crearea unui <code>std::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();
+map();
 </syntaxhighlight>
 Exemplu:
 <syntaxhighlight lang="cpp" highlight="5">
-#include <unordered_map>
+#include <map>
 #include <string>
 int main() {
-     std::unorder_map<std::string, Person> myMap;
+     std::map<std::string, Person> myMap;
      Person person;
      myMap["190010112345"] = person;
@@ Linia 362: / Linia 345: @@
 Exemplu:
 <syntaxhighlight lang="cpp" highlight="9,10">
-#include <unordered_map>
+#include <map>
 #include <string>
 #include <cstdio>
 int main() {
-     std::unorder_map<std::string, Person> myMap;
+     std::map<std::string, Person> myMap;
      Person person;
      myMap["190010112345"] = person;
@@ Linia 402: / Linia 385: @@
 Exemplu:
 <syntaxhighlight lang="cpp" highlight="8-9">
-#include <unordered_map>
+#include <map>
 #include <string>
 #include <cstdio>
 int main() {
-     std::unorder_map<std::string, Person> myMap;
+     std::map<std::string, Person> myMap;
      Person person;
      myMap.insert({"191010112345", person});
@@ Linia 437: / Linia 420: @@
 Exemplu:
 <syntaxhighlight lang="cpp" highlight="10,13,16">
-#include <unordered_map>
+#include <map>
 #include <string>
 #include <cstdio>
 int main() {
-     std::unorder_map<std::string, Person> myMap;
+     std::map<std::string, Person> myMap;
      Person person;
      myMap.insert({"191010112345", person});
@@ Linia 475: / Linia 458: @@
 Exemplu:
 <syntaxhighlight lang="cpp" highlight="14,15">
-#include <unordered_map>
+#include <map>
 #include <string>
 #include <cstdio>
 int main() {
-     std::unorder_map<std::string, Person> myMap;
+     std::map<std::string, Person> myMap;
      Person person;
      myMap.insert({"191010112345", person});
@@ Linia 502: / Linia 485: @@
 === Căutarea unei valori după cheie ===
-Pentru a căuta o valoare după cheie, se definește următoarele metode:
+Pentru a căuta o valoare după cheie, se definesc următoarele metode:
 <syntaxhighlight lang="C">
@@ Linia 525: / Linia 508: @@
 Exemplu:
 <syntaxhighlight lang="cpp" highlight="10,11">
-#include <unordered_map>
+#include <map>
 #include <string>
 #include <cstdio>
 int main() {
-     std::unorder_map<std::string, Person> myMap;
+     std::map<std::string, Person> myMap;
      Person person;
      person.firstName = "Ghita";

@@ Linia 265: / Linia 265: @@
 </syntaxhighlight>
 <syntaxhighlight lang="cpp" highlight="10,11">
 #include <unordered_map>

@@ Linia 244: / Linia 244: @@
 === Căutarea unei valori după cheie ===
-Pentru a căuta o valoare după cheie, se definește urmtoarea funcție:
+Pentru a căuta o valoare după cheie, se definește următoarele metode:
 <syntaxhighlight lang="C">
 /**
-  * Functia intoarce valoarea asociată cheii key.
+  * Metoda intoarce a referinta la valoarea asociată cheii key.
- * @param map map-ul in care se cauta cheia.
+  * @param key cheia cautata.
-  * @param key cheia (CNP-ul) cautata.
+  * @return valoarea asociată cheii, dacă aceasta există,
-  * @return valoarea asociată cheii.
+ *  sau se generează o eroare daca cheia nu exista in map.
   */
-struct Person hashMapGet(struct HashMap * map, char * key);
+V& at(K key);
 </syntaxhighlight>
-Căutarea unei valori după cheie se realizează în felul următor:
+<syntaxhighlight lang="cpp" highlight="10,11">
-# Se aplică funcția hash pe variabila <code>key</code>.
+#include <unordered_map>
-# Folosind valoarea obținută se accesează lista de pe poziția hash-ului din <code>array</code>.
+#include <string>
-# Se iterează peste nodurile din listă și se caută cheia folosind funcția <code>equals</code>.
+#include <cstdio>
-# Dacă cheia a fost găsită, se întoarce valoarea asociată; dacă s-a ajuns la sfârșitul listei fără a se găsi cheia, se întoarce o structură de tip <code>Person</code>, indiferent cu ce valori (comportament nedefinit).
+int main() {
-* 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).
+    std::unorder_map<std::string, Person> myMap;
-* Complexitate în '''spațiu''': O(1)
+    Person person;

@@ Linia 161: / Linia 161: @@
 === Eliminarea unei chei 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 cheia data 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.
   */
-void hashMapRemove(struct HashMap * map, char * key);
+void erase(K key);
 </syntaxhighlight>
-Eliminarea se realizează în felul următor:
+Exemplu:
-# Se aplică funcția hash pe variabila <code>key</code>.
+<syntaxhighlight lang="cpp">
-* 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).
+</syntaxhighlight>
 === Verificarea dacă o cheie există în map ===