This is an old revision of the document!
Table of Contents
std::map και std::multimap
Ένα std::map αποτελεί ένα σύνολο μοναδικών στοιχείων, όπου κάθε τέτοιο στοιχείο αποτελεί κλειδί για την εύρεση-αντιστοίχιση με ένα άλλο αντικείμενο που ονομάζουμε “τιμή” (value). Κάθε κλειδί προσδιορίζει μοναδικά μία “τιμή”, η οποία δεν είναι απαραίτητο να είναι μοναδική (οι τιμές μπορεί να επαναλαμβάνονται).
Τα στοιχεία-κλειδιά αποθηκεύονται εσωτερικά σε ένα ισοζυγισμένο δέντρο αναζητήσεως (π.χ.Red–black_tree, AVL_tree), όπως ακριβώς και στο std::set.
Η κατάταξη ενός νέου στοιχείου-κλειδιού γίνεται πάντα μέσω σύγκρισης με τα υπόλοιπα στοιχεία που είναι αποθηκευμένα στην δομή. Για τον λόγο αυτό, απαραίτητη προϋπόθεση για τη λειτουργία του map (όπως και στο std::set) είναι για τον τύπο του κλειδιού να παρέχονται οι τελεστές σύγκρισης < και >. Δύο κλειδιά ιδίου τύπου θεωρούνται ίσα σε ένα map εάν η παρακάτω λογική έκφραση είναι αληθής.
if(!(a < b) && !(b < a))
Ένα std::multimap αποτελεί ένα σύνολο από όχι απαραίτητα μοναδικά κλειδιά, τα οποία είναι αποθηκευμένα σε ένα ισοζυγισμένο δέντρο αναζητήσεως (όπως το map). Ο τρόπος σύγκρισης και η κατάταξη των στοιχείων είναι όμοια με την επίπλέον σημείωση ότι το δέντρο επιτρέπει την εμφάνιση ενός κλειδιού περισσότερες από μία φορές.
Στα παρακάτω σχήματα διακρίνεται η δομή ενός std::map και ενός std::multimap, όπου τα κλειδιά είναι ακέραιοι και οι τιμές είναι αντικείμενα τύπου std::string.
Επίδοσης της δομής
Η επίδοση της δομής είναι ανάλογη των δομών std::set και std::multiset λαμβάνοντας υπόψη τα στοιχεία-κλειδιά των std::map και std::multimap.
Η κλάση std::pair
Προκειμένου να μπορέσει να υπάρξει η αντιστοίχιση μεταξύ στοιχείου-κλειδιού και στοιχείου-τιμής τα δεδομένα σε ένα std::map αντιστοιχίζονται σε ζευγάρια. Η templated κλάση της STL που υποστηρίζει την αποθήκευση ζευγών δεδομένων είναι η κλάση std::pair. Η κλάση μπορεί να αποθηκεύσει δύο αντικείμενα ίδιου ή διαφορετικού τύπου. Στο παράδειγμα που ακολουθεί δημιουργούμε δύο αντικείμενο της κλάσης std::pair και προσπελαύνουμε τα στοιχεία τους μέσω των public πεδίων της κλάσης std::pair first και second.
- 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; }
Εκτός από τον κατασκευαστή της κλάσης std::pair υπάρχει και η συνάρτηση std::make_pair, η οποία κατασκευάζει και επιστρέφει ένα αντικείμενο τύπου std::pair με βάση τα ορίσματα που λαμβάνει.
Παραδείγματα
- 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 << " -> " << 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; }
Παρατηρήσεις:
- Τα στοιχεία εκτυπώνονται σε αύξουσα σειρά με βάση το κλειδί κάθε εγγραφής.
- Η συνάρτηση emplace σε ένα std::map κατασκεύαζει το αντικείμενο τύπου std::pair και όχι το κλειδί ή τιμή που αντιστοιχεί στο κλειδί.