Both sides previous revisionPrevious revisionNext revision | Previous revision |
cpp:stl:set [2020/05/31 04:52] – [Παράδειγμα ένθεσης και διάτρεξης ενός set] gthanos | cpp:stl:set [2023/05/30 11:04] (current) – [Παράδειγμα ένθεσης και διάτρεξης ενός set] gthanos |
---|
Ένα [[http://www.cplusplus.com/reference/set/set/|std::set]] αποτελεί ένα σύνολο μοναδικών στοιχείων. Τα στοιχεία αποθηκεύονται εσωτερικά σε ένα ισοζυγισμένο δέντρο αναζητήσεως (π.χ.[[wp>Red–black_tree]], [[wp>AVL_tree]]). | Ένα [[http://www.cplusplus.com/reference/set/set/|std::set]] αποτελεί ένα σύνολο μοναδικών στοιχείων. Τα στοιχεία αποθηκεύονται εσωτερικά σε ένα ισοζυγισμένο δέντρο αναζητήσεως (π.χ.[[wp>Red–black_tree]], [[wp>AVL_tree]]). |
| |
Η κατάταξη ενός νέου στοιχείου γίνεται πάντα μέσω σύγκρισης με τα υπόλοιπα στοιχεία που είναι αποθηκευμένα στην δομή. Για τον λόγο αυτό, απαραίτητη προϋπόθεση για τη λειτουργία του //set// είναι για τους τύπους δεδομένων που αποθηκεύονται να παρέχονται οι τελεστές σύγκρισης %%<%% και %%>%%. Δύο στοιχεία ιδίου τύπου θεωρούνται ίσα σε ένα //set// εάν η παρακάτω λογική έκφραση είναι αληθής. | Η κατάταξη ενός νέου στοιχείου γίνεται πάντα μέσω σύγκρισης με τα υπόλοιπα στοιχεία που είναι αποθηκευμένα στην δομή. Για τον λόγο αυτό, απαραίτητη προϋπόθεση για τη λειτουργία του //set// είναι για τους τύπους δεδομένων που αποθηκεύονται να παρέχονται ο τελεστής σύγκρισης %%<%%. Δύο στοιχεία ιδίου τύπου θεωρούνται ίσα σε ένα //set// εάν η παρακάτω λογική έκφραση είναι αληθής. |
| |
<code cpp> | <code cpp> |
</code> | </code> |
| |
Ένα [[http://www.cplusplus.com/reference/set/multiset/|std::multiset]] αποτελεί ένα σύνολο όχι απαραίτητα μοναδικών στοιχείων, τα οποία είναι αποθηκευμένα σε ένα ισοζυγισμένο δέντρο αναζητήσεως. Ο τρόπος σύγκρισης και η κατάταξη των στοιχείων είναι παρόμοια με την επίπλέον σημείωση ότι το δέντρο επιτρέπει την εμφάνιση ενός κλειδιού περισσότερες από μία φορές. | Ένα [[http://www.cplusplus.com/reference/set/multiset/|std::multiset]] αποτελεί ένα σύνολο όχι απαραίτητα μοναδικών στοιχείων (μπορεί να είναι, μπορεί και να μην είναι μοναδικά), τα οποία είναι αποθηκευμένα σε ένα ισοζυγισμένο δέντρο αναζητήσεως (όπως το //set//). Ο τρόπος σύγκρισης και η κατάταξη των στοιχείων είναι όμοια με την επίπλέον σημείωση ότι το δέντρο επιτρέπει την εμφάνιση ενός κλειδιού περισσότερες από μία φορές. |
| |
Στα παρακάτω σχήματα διακρίνεται η δομή ενός [[http://www.cplusplus.com/reference/set/set/|std::set]] και ενός [[http://www.cplusplus.com/reference/set/multiset/|std::multiset]]. | Στα παρακάτω σχήματα διακρίνεται η δομή ενός [[http://www.cplusplus.com/reference/set/set/|std::set]] και ενός [[http://www.cplusplus.com/reference/set/multiset/|std::multiset]], όπου τα στοιχεία είναι ακέραιοι. |
| |
| {{ :cpp:stl:set01.png? |}}| {{ :cpp:stl:multiset01.png? |}} | | | {{ :cpp:stl:set01.png? |}}| {{ :cpp:stl:multiset01.png? |}} | |
=== Παράδειγμα 2ο - Student === | === Παράδειγμα 2ο - Student === |
| |
Κατεβάστε την κλάση //Student// από [[https://courses.e-ce.uth.gr/ECE326/doku.php?do=export_code&id=cpp:templates&codeblock=0|εδώ]]. | Κατεβάστε την κλάση //Student// από [[https://courses.e-ce.uth.gr/ECE326/doku.php?do=export_code&id=cpp:stl:intro&codeblock=0|εδώ]]. |
| |
<code cpp student_set.cpp> | <code cpp student_set.cpp> |
Παρατηρήστε ότι η σειρά εκτύπωσης των στοιχείων κατά την διάτρεξη του //std::set// ή του //std::multiset// είναι από το μικρότερο αποθηκευμένο στοιχείο προς το μεγαλύτερο. Τα αντικείμενα της κλάσης //Student// κατατάσσονται με βάση το ΑΕΜ. | Παρατηρήστε ότι η σειρά εκτύπωσης των στοιχείων κατά την διάτρεξη του //std::set// ή του //std::multiset// είναι από το μικρότερο αποθηκευμένο στοιχείο προς το μεγαλύτερο. Τα αντικείμενα της κλάσης //Student// κατατάσσονται με βάση το ΑΕΜ. |
</WRAP> | </WRAP> |
| |
| ===== Οι συναρτήσεις lower_bound, upper_bound και equal_range ===== |
| |
| Οι κλάσεις //std::set// και //std::multiset// διαθέτουν τις συναρτήσεις [[http://www.cplusplus.com/reference/set/set/lower_bound/|lower_bound]], [[http://www.cplusplus.com/reference/set/set/upper_bound/|upper_bound]] και [[http://www.cplusplus.com/reference/set/set/equal_range/|equal_range]] οι οποίες λειτουργούν ως εξής: |
| |
| * **iterator lower_bound (const value_type& val) const:** Επιστρέφει έναν //iterator// που δείχνει στη θέση ενός στοιχείου που είναι ίσο ή μεγαλύτερο από την τιμή //**val**//. |
| * **iterator upper_bound (const value_type& val) const:** Επιστρέφει έναν //iterator// που δείχνει στην θέση ενός στοιχείου που είναι ίσο ή μικρότερο από την τιμή //**val**//. |
| * **pair<iterator,iterator> equal_range (const value_type& val):** Επιστρέφει έναν ζεύγος //iterator// (δες περισσότερα σχετικά με την κλάση //pair// στην ενότητα [[cpp:stl:map|std::map και std::multimap]]) που δείχνει στην αρχή και στο τέλος ενός εύρους στοιχείων στον //container//, όπου τα κλειδιά είναι ίδια με την τιμή //**val**//. Για ένα //set// το εύρος αυτό έχει μέγιστο μέγεθος ένα στοιχείο, ενώ για ένα //multiset// μπορεί να περιέχει περισσότερα στοιχεία. Εάν δεν βρεθεί κανένα στοιχείο με τιμή //**val**// οι //iterators// του ζεύγους δείχνουν και οι δύο σε κοινή θέση. |
| |
| === Παράδειγμα upper_bound, lower_bound, equal_range === |
| |
| <code cpp string_multiset.cpp> |
| #include <set> |
| #include <string> |
| #include <iostream> |
| |
| template<typename T> |
| void print(std::multiset<T> s) { |
| for(auto it = s.cbegin(); it!=s.cend(); it++) |
| std::cout << *it << " "; |
| std::cout << std::endl; |
| } |
| |
| int main(int argc, char *argv[]) { |
| std::multiset<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); |
| |
| auto lower_it = strset.lower_bound("apricot"); |
| auto upper_it = strset.upper_bound("kiwi"); |
| |
| strset.erase(lower_it, upper_it); |
| print(strset); |
| |
| auto range = strset.equal_range("mango"); |
| strset.erase(range.first,range.second); |
| print(strset); |
| |
| //Searching for mango again... |
| range = strset.equal_range("mango"); |
| if(range.first == range.second) |
| std::cout << "range.first == range.second\n"; |
| |
| return 0; |
| } |
| </code> |
| |
| |
| |