Differences

This shows you the differences between two versions of the page.

--- cpp:stl:map [2020/05/31 06:24] – created gthanos
+++ cpp:stl:map [Unknown date] (current) – external edit (Unknown date) 127.0.0.1
@@ Line 5: / Line 5: @@
 Τα στοιχεία-κλειδιά αποθηκεύονται εσωτερικά σε ένα ισοζυγισμένο δέντρο αναζητήσεως (π.χ.[[wp>Red–black_tree]], [[wp>AVL_tree]]), όπως ακριβώς και στο [[cpp:stl:set|std::set]].
-Η κατάταξη ενός νέου στοιχείου-κλειδιού γίνεται πάντα μέσω σύγκρισης με τα υπόλοιπα στοιχεία που είναι αποθηκευμένα στην δομή. Για τον λόγο αυτό, απαραίτητη προϋπόθεση για τη λειτουργία του //map// (όπως και στο [[cpp:stl:set|std::set]]) είναι για τον τύπο του κλειδιού να παρέχονται οι τελεστές σύγκρισης %%<%% και %%>%%. Δύο κλειδιά ιδίου τύπου θεωρούνται ίσα σε ένα //map// εάν η παρακάτω λογική έκφραση είναι αληθής.
+Η κατάταξη ενός νέου στοιχείου-κλειδιού γίνεται πάντα μέσω σύγκρισης με τα υπόλοιπα στοιχεία που είναι αποθηκευμένα στην δομή. Για τον λόγο αυτό, απαραίτητη προϋπόθεση για τη λειτουργία του //map// (όπως και στο [[cpp:stl:set|std::set]]) είναι για τον τύπο του κλειδιού να παρέχονται ο τελεστής σύγκρισης %%<%%. Δύο κλειδιά ιδίου τύπου θεωρούνται ίσα σε ένα //map// εάν η παρακάτω λογική έκφραση είναι αληθής.
 <code cpp>
@@ Line 17: / Line 17: @@
 | {{ :cpp:stl:map01.png? |}}| {{ :cpp:stl:multimap01.png? |}} |
 |  **Σχήμα 1. std::map**  |  **Σχήμα 2. std::multimap**  |
+===== Επίδοσης της δομής =====
+Η επίδοση της δομής είναι ανάλογη των δομών [[cpp:stl:set|std::set και std::multiset]] λαμβάνοντας υπόψη τα στοιχεία-κλειδιά των //std::map// και //std::multimap//.
+===== Η κλάση std::pair =====
+Προκειμένου να μπορέσει να υπάρξει η αντιστοίχιση μεταξύ στοιχείου-κλειδιού και στοιχείου-τιμής τα δεδομένα σε ένα [[http://www.cplusplus.com/reference/map/map/|std::map]] αντιστοιχίζονται σε ζευγάρια. Η //templated// κλάση της //STL// που υποστηρίζει την αποθήκευση ζευγών δεδομένων είναι η κλάση [[http://www.cplusplus.com/reference/utility/pair/|std::pair]]. Η κλάση μπορεί να αποθηκεύσει δύο αντικείμενα ίδιου ή διαφορετικού τύπου. Στο παράδειγμα που ακολουθεί δημιουργούμε δύο αντικείμενο της κλάσης //std::pair// και προσπελαύνουμε τα στοιχεία τους μέσω των public πεδίων της κλάσης [[http://www.cplusplus.com/reference/utility/pair/|std::pair]] **first** και **second**.
+<code cpp pair.cpp>
+#include <set>
+#include <string>
+#include <utility>
+#include <iostream>
+#include "Student.hpp"
+int main() {
+  std::pair<Student,std::string> peter_pan(
+       Student("Peter Pan", 1234),
+       std::string("Wendy House, Neverland")
+       );
+  std::pair<Student,std::string> mickey_mouse = make_pair(
+       Student("Mickey Mouse", 1235),
+       std::string("Walt Disney World Communications, P.O Box 10040, Lake Buena Vista, Florida 32830-0040 ")
+       );
+  std::cout << peter_pan.first << " -> " << peter_pan.second << std::endl;
+  std::cout << mickey_mouse.first << " -> " << mickey_mouse.second << std::endl;
+}
+</code>
+<WRAP tip 80% center round>
+Εκτός από τον κατασκευαστή της κλάσης [[http://www.cplusplus.com/reference/utility/pair/|std::pair]] υπάρχει και η συνάρτηση [[http://www.cplusplus.com/reference/utility/make_pair/|std::make_pair]], η οποία κατασκευάζει και επιστρέφει ένα αντικείμενο τύπου [[http://www.cplusplus.com/reference/utility/pair/|std::pair]] με βάση τα ορίσματα που λαμβάνει.
+</WRAP>
+===== Ένθεση και διάτρεξη ενός std::map ή std::multimap =====
+<code cpp color_map.cpp>
+#include <map>
+#include <utility>
+#include <string>
+#include <iostream>
+template<typename K, typename V>
+void print(std::map<K,V> s) {
+  for(auto it = s.cbegin(); it!=s.cend(); it++)
+    std::cout << it->first << " -> " << std::hex << std::uppercase << "0x" << it->second << std::endl;
+}
+int main(int argc, char *argv[]) {
+  std::map<std::string, int> colormap;
+  colormap.insert(std::pair<std::string, int>(std::string("orange"), 0xFF8C00 ));
+  colormap.insert(std::pair<std::string, int>(std::string("green"), 0x008C00 ));
+  colormap.insert(std::pair<std::string, int>(std::string("blue"), 0x0000FF ));
+  colormap.insert(std::make_pair(std::string("red"), 0x8C0000 ));
+  colormap.insert(std::make_pair(std::string("cyan"), 0x00FFFF));
+  colormap.insert(std::make_pair(std::string("orange"), 0xFF6347 ));
+  colormap.emplace(std::string("blue"), 0x0000AA );
+  colormap.emplace(std::string("purple"), 0x9400D3 );
+  colormap.emplace(std::string("magenta"), 0xFF00FF );
+  print(colormap);
+  return 0;
+}
+</code>
+Παρατηρήσεις:
+  * Τα στοιχεία εκτυπώνονται σε αύξουσα σειρά με βάση το κλειδί κάθε εγγραφής.
+  * Η συνάρτηση //emplace// σε ένα //std::map// κατασκεύαζει το αντικείμενο τύπου //std::pair// και όχι το κλειδί ή τιμή που αντιστοιχεί στο κλειδί.
+<WRAP todo 80% center round>
+Αλλάξτε την κλάση //std::map// σε //std::multimap// και παρατηρήστε τις αλλαγές στην εκτύπωση.
+</WRAP>
+===== Οι συναρτήσεις operator[] και at =====
+==== H συνάρτηση operator[] ====
+Η συνάρτηση [[http://www.cplusplus.com/reference/map/map/operator[]| operator[] ]] έχει διπλό ρόλο //α)// να επιστρέψει την τιμή ενός κλειδιού που είναι αποθηκευμένο στο //std::map// ή //std::multimap// και //β)// να θέσει την τιμή ενός κλειδιού που είναι ή δεν είναι αποθηκευμένο sto //std::map//, //std::multimap//.
+=== Παράδειγμα 1ο - Ανάγνωση με χρήση του operator [] ===
+<code cpp student_map_read_using_op.cpp>
+#include <map>
+#include <string>
+#include <utility>
+#include <iostream>
+#include "Student.hpp"
+int main() {
+  std::pair<Student,std::string> peter_pan(Student("Peter Pan", 1234), std::string("Wendy House, Neverland"));
+  std::pair<Student,std::string> mickey_mouse = make_pair(Student("Mickey Mouse", 1235), std::string("Walt Disney World Communications, P.O Box 10040, Lake Buena Vista, Florida 32830-0040 "));
+  std::map<Student, std::string> students;
+  students.insert( peter_pan );
+  students.insert( mickey_mouse );
+  std::string address_pp = students[ Student("Peter Pan", 1234) ];     // address_pp exists
+  std::string address_mm = students[ Student("Minie Mouse", 1240) ];   // address_mm does not exist
+  std::cout << "Peter Pan   address: " << address_pp << std::endl;
+  std::cout << "Minie Mouse address: " << address_mm << std::endl;             // empty string
+}
+</code>
+=== Παράδειγμα 2ο - Εγγραφή με χρήση του operator [] ===
+<code cpp student_map_write_using_op.cpp>
+#include <map>
+#include <string>
+#include <utility>
+#include <iostream>
+#include "Student.hpp"
+template<typename K, typename V>
+void print(std::map<K,V> s) {
+  for(auto it = s.cbegin(); it!=s.cend(); it++)
+    std::cout << it->first << " -> " << it->second << std::endl;
+}
+int main() {
+  std::pair<Student,std::string> peter_pan(Student("Peter Pan", 1234), std::string("Wendy House, Neverland"));
+  std::pair<Student,std::string> mickey_mouse = make_pair(Student("Mickey Mouse", 1235), std::string("Walt Disney World Communications, P.O Box 10040, Lake Buena Vista, Florida 32830-0040 "));
+  std::map<Student, std::string> students;
+  students.insert( peter_pan );
+  students.insert( mickey_mouse );
+  students[ Student("Peter Pan", 1234) ] = std::string("Home Under The Ground, Neverland");
+  students[ Student("Minnie Mouse", 1240) ] = std::string("Walt Disney World Communications, P.O Box 10040, Lake Buena Vista, Florida 32830-0040 ");
+  print(students);
+}
+</code>
+==== H συνάρτηση at ====
+Η συνάρτηση [[http://www.cplusplus.com/reference/map/map/at| at ]] έχει ανάλογο ρόλο με τη συνάρτηση [[http://www.cplusplus.com/reference/map/map/operator[]| operator[] ]], δηλαδή μπορεί να διαβάσει ή να θέσει την τιμή ενός κλειδιού στο //std::map//. Η διαφορά της συγκεκριμένης συνάρτησης σε σχέση με την [[http://www.cplusplus.com/reference/map/map/operator[]| operator[] ]] είναι ότι εάν το κλειδί δεν υπάρχει στο //std::map// παράγει ένα //exception// του τύπου [[http://www.cplusplus.com/reference/stdexcept/out_of_range/|std::out_of_range]] .
+=== Παράδειγμα 1ο - Ανάγνωση με χρήση της συνάρτησης at ===
+<code cpp student_map_read_using_at.cpp>
+#include <map>
+#include <string>
+#include <utility>
+#include <iostream>
+#include "Student.hpp"
+int main() {
+  std::pair<Student,std::string> peter_pan(Student("Peter Pan", 1234), std::string("Wendy House, Neverland"));
+  std::pair<Student,std::string> mickey_mouse = make_pair(Student("Mickey Mouse", 1235), std::string("Walt Disney World Communications, P.O Box 10040, Lake Buena Vista, Florida 32830-0040 "));
+  std::map<Student, std::string> students;
+  students.insert( peter_pan );
+  students.insert( mickey_mouse );
+  std::string address_pp;
+  std::string address_mm;
+  try {
+    address_pp = students.at(Student("Peter Pan", 1234));     // address_pp exists
+  }
+  catch(std::out_of_range& ex) {
+    std::cout << "Student '" << Student("Peter Pan", 1234) << "' does not exist in map\n\n";
+  }
+  try {
+    address_mm = students.at(Student("Minie Mouse", 1240));   // address_mm does not exist
+  }
+  catch(std::out_of_range& ex) {
+    std::cout << "Student '" << Student("Minie Mouse", 1240) << "' does not exist in map\n\n";
+  }
+  std::cout << "Peter Pan address: " << address_pp << std::endl;
+  std::cout << "Minie Mouse address: " << address_mm << std::endl;             // empty string
+}
+</code>
+=== Παράδειγμα 2ο - Εγγραφή με χρήση της συνάρτησης at ===
+<code cpp student_map_write_using_at.cpp>
+#include <map>
+#include <string>
+#include <utility>
+#include <iostream>
+#include "Student.hpp"
+template<typename K, typename V>
+void print(std::map<K,V> s) {
+  for(auto it = s.cbegin(); it!=s.cend(); it++)
+    std::cout << it->first << " -> " << it->second << std::endl;
+}
+int main() {
+  std::pair<Student,std::string> peter_pan(Student("Peter Pan", 1234), std::string("Wendy House, Neverland"));
+  std::pair<Student,std::string> mickey_mouse = make_pair(Student("Mickey Mouse", 1235), std::string("Walt Disney World Communications, P.O Box 10040, Lake Buena Vista, Florida 32830-0040 "));
+  std::map<Student, std::string> students;
+  students.insert( peter_pan );
+  students.insert( mickey_mouse );
+  try {
+    students.at( Student("Peter Pan", 1234) ) = std::string("Home Under The Ground, Neverland");
+  }
+  catch(std::out_of_range& ex) {
+    std::cout << "Student '" << Student("Peter Pan", 1234) << "' does not exist in map\n\n";
+  }
+  try {
+    students.at( Student("Minnie Mouse", 1240) ) = std::string("Walt Disney World Communications, P.O Box 10040, Lake Buena Vista, Florida 32830-0040 ");
+  }
+  catch(std::out_of_range& ex) {
+    std::cout << "Student '" << Student("Minie Mouse", 1240) << "' does not exist in map\n\n";
+  }
+  print(students);
+}
+</code>
+===== Οι συναρτήσεις lower_bound, upper_bound και equal_range =====
+Οι συναρτήσεις [[cpp:stl:set#%CE%BF%CE%B9_%CF%83%CF%85%CE%BD%CE%B1%CF%81%CF%84%CE%AE%CF%83%CE%B5%CE%B9%CF%82_lower_bound_upper_bound_%CE%BA%CE%B1%CE%B9_equal_range|lower_bound, upper_bound και equal_range]] υπάρχουν και για τις κλάσεις [[cpp:stl:map| std::map και std::multimap]]. Η λογική των συναρτήσεων αυτών είναι όμοια με το [[cpp:stl:set|std::set]] με την διαφορά ότι η αναζήτηση γίνεται στα κλειδιά του //std::map//. Το παρακάτω παράδειγμα είναι από την σελίδα [[http://www.cplusplus.com/reference/map/map/lower_bound/|cplusplus.com]].
+<code cpp map_upper_lower_bound.cpp>
+// map::lower_bound/upper_bound
+#include <iostream>
+#include <map>
+int main ()
+{
+  std::map<char,int> mymap;
+  std::map<char,int>::iterator itlow,itup;
+  mymap['a']=20;
+  mymap['b']=40;
+  mymap['c']=60;
+  mymap['d']=80;
+  mymap['e']=100;
+  itlow=mymap.lower_bound ('b');  // itlow points to b
+  itup=mymap.upper_bound ('d');   // itup points to e (not d!)
+  mymap.erase(itlow,itup);        // erases [itlow,itup)
+  // print content:
+  for (std::map<char,int>::iterator it=mymap.begin(); it!=mymap.end(); ++it)
+    std::cout << it->first << " => " << it->second << '\n';
+  return 0;
+}
+</code>