Differences

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

--- cpp:stl:unordered_set [2020/06/01 05:16]
gthanos [Επίδοσης της δομής]
+++ cpp:stl:unordered_set [2020/06/01 06:05]
@@ Line 1: / Line 1: @@
-====== std::unordered_set και std::unordered_multiset ======
-Ένα [[http://www.cplusplus.com/reference/unordered_set/unordered_set/|std::unordered_set]] αποτελεί ένα σύνολο μοναδικών στοιχείων, τα οποία είναι αποθηκευμένα σε ένα πίνακα κατακερματισμού με αλύσίδες ([[wp>Hash_table#Separate_chaining]]).
-Η κατάταξη ενός νέου στοιχείου γίνεται πάντα μέσω της συνάρτησης κατακερματισμού (//hash function//), η οποία εξαρτάται από το είδος των στοιχείων που αποθηκεύονται στο //set//. Το ακόλουθο σχήμα περιγράφει συνοπτικά τη δομή της κλάσης //unordered_set//.
-| {{ :cpp:stl:internal_structure_of_unordered_sets_and_multisets.png?600 |}} |
-| Σχήμα 1. Η δομή της κλάσης [[http://www.cplusplus.com/reference/unordered_set/unordered_set/|std::unordered_set]] (Πηγή: [[https://conglang.github.io/2015/01/01/stl-unordered-container/|conglang.github.io]])|
-===== Επίδοσης της δομής =====
-  * Οι πράξεις της αναζήτησης, της ένθεσης και της διαγραφής κοστίζουν ανάλογο του μεγέθους της λίστας του πίνακα κατακερματισμού. Επειδή η //default// τιμή για τον βαθμό πληρώσεως του πινακα είναι 1.0 μπορείτε να υποθέσετε ότι το μέσο κόστος της λίστας είναι μικρότερο από 2.0 και κατά συνέπεια η επίδοση της δομής είναι σταθερή (**O(1)**) και για τις τρεις πράξεις.
-  * Η διάτρεξη των στοιχείων γίνεται κατά τη σειρά διάτρεξης του πίνακα κατακερματισμού, η οποία δεν ακολουθεί τη σειρά εισαγωγής, ούτε την πιθανή κατάταξη των στοιχείων.
-  * Σε σχέση με τις κλάσεις [[cpp:stl:set|std::set και std::multiset]] η συγκεκριμένη κλάση είναι πιο γρήγορη κατά αναζήτηση την ένθεση και διαγραφή, όμως σπαταλά συγκριτικά περισσότερο χώρο. Ο χώρος που σπαταλάται εξαρτάται από τον βαθμό πλήρωσης του πίνακα κατακερματισμού.
-===== Περισσότερα για τις κλάσεις std::unordered_set και std::unordered_multiset =====
-H δήλωση της κλάσης //std::unordered_set// έχει ως εξής:
-<code cpp>
-template < class Key,                        // unordered_set::key_type/value_type
-           class Hash = hash<Key>,           // unordered_set::hasher
-           class Pred = equal_to<Key>,       // unordered_set::key_equal
-           class Alloc = allocator<Key>      // unordered_set::allocator_type
-           > class unordered_set;
-</code>
-Από την παραπάνω δήλωση της κλάσης παρατηρούμε ότι εκτός από το κλειδί ''Key'' κατά την δήλωση απαιτείται η  δήλωση δύο επιπλέον κλάσεων της κλάσης ''Hash=hash<Key>'' και της κλάσης ''Pred=equal_to<Key>''. Οι κλάσεις αυτές λειτουργούν ως συναρτήσεις (θα δώσουμε σχετικό παράδειγμα στη συνέχεια), η πρώτη υλοποιεί το //hash function// και η δεύτερη ελέγχει την ισότητα μεταξύ δύο αντικειμένων του ιδίου τύπου. Οι κλάσεις οι οποίες έχουν ως στόχο την αποκλειστική χρήση τους ως συναρτήσεις ειδικού σκοπού ονομάζονται στη βιβλιογραφία //[[https://www.quantstart.com/articles/Function-Objects-Functors-in-C-Part-1/|function objects ή functors]]//.
-Για τους βασικούς τύπους δεδομένων οι συναρτήσεις αυτές υλοποιούνται μέσω των //templated// συναρτήσεων [[http://www.cplusplus.com/reference/functional/hash/|std::hash]] και [[http://www.cplusplus.com/reference/functional/equal_to/|std::equal_to]]. Για σύνθετους τύπους δεδομένων καλείστε να υλοποιήσετε εσείς τις συγκεκριμένες συναρτήσεις.
-===== Παράδειγμα 1ο - Αποθήκευση std::string σε unordered_set ή unordered_multiset =====
-<code cpp >
-#include <unordered_set>
-#include <string>
-#include <iostream>
-template<typename T, typename Hash, typename Pred>
-void print(std::unordered_set<T, Hash, Pred> s) {
-  for(auto it = s.cbegin(); it!=s.cend(); it++)
-    std::cout << *it << " ";
-  std::cout << std::endl;
-}
-int main(int argc, char *argv[]) {
-  std::unordered_set<std::string> strset;
-  strset.emplace("orange");
-  strset.emplace("apple");
-  strset.emplace("mango");
-  strset.emplace("cherry");
-  strset.emplace("melon");
-  strset.emplace("apricot");
-  strset.emplace("pineapple");
-  strset.emplace("mango");
-  strset.emplace("apricot");
-  strset.emplace("apple");
-  strset.emplace("apple");
-  print(strset);
-  return 0;
-}
-</code>
-<WRAP todo 80% center round>
-Αλλάξτε τον //STL container// από //std::unordered_set// σε //std::unordered_multiset// και παρατηρήστε την συμπεριφορά του προγράμματος σε αυτή την περίπτωση.
-</WRAP>
-Παρατηρήστε ότι και στις δύο περιπτώσεις η σειρά διάτρεξης είναι "τυχαία", αλλά ίδια όσες φορές και να επαναλάβετε την εκτέλεση του προγραάμματος. Η σειρά διάτρεξης δεν ακολουθεί τη σειρά εισόδου των στοιχείων όπως συμβαίνει στους //sequence containers//, ούτε διατρέχει τα στοιχεία με σειρά προτεραιτότητας.
-===== Παράδειγμα 2ο - Αποθήκευση Student σε unordered_set ή unordered_multiset =====
-<code cpp student_set.cpp>
-#include <unordered_set>
-#include <iostream>
-#include "Student.hpp"
-template<typename T, typename Hash, typename Eq>
-void print(std::unordered_set<T,Hash,Eq> s) {
-  for(auto it = s.cbegin(); it!=s.cend(); it++)
-    std::cout << *it << " ";
-  std::cout << std::endl;
-}
-struct HashByAEM {
-  size_t operator()(const Student& st) const {
-    return std::hash<int>()(st.getAEM());
-  }
-};
-struct EqualToByAEM {
-  bool operator() (const Student& st1, const Student& st2) const {
-    return st1.getAEM() == st2.getAEM();
-  }
-};
-int main(int argc, char *argv[]) {
-  std::unordered_set<Student, HashByAEM, EqualToByAEM> students;
-  students.emplace("Mickie Mouse", 1239);
-  students.emplace("Mary Poppins", 1240);
-  students.emplace("Minnie Mouse", 1234);
-  students.emplace("Peter Pan",    1235);
-  students.emplace("Tinker Bell",  1233);
-  students.emplace("Donald Duck",  1230);
-  students.emplace("Minnie Mouse", 1234);
-  students.emplace("Tinker Bell",  1233);
-  print(students);
-  return 0;
-}
-</code>
-<WRAP todo 80% center round>
-Αλλάξτε τον //STL container// από //std::unordered_set// σε //std::unordered_multiset// και παρατηρήστε τη συμπεριφορά του προγράμματος και σε αυτή την περίπτωση.
-</WRAP>

Αντικειμενοστραφής Προγραμματισμός

User Tools

Site Tools

Differences

Page Tools