cpp:stl:set
Differences
This shows you the differences between two versions of the page.
Next revision | Previous revision | ||
cpp:stl:set [2020/05/29 12:54] – created gthanos | cpp:stl:set [2023/05/30 11:04] (current) – [Παράδειγμα ένθεσης και διάτρεξης ενός set] gthanos | ||
---|---|---|---|
Line 1: | Line 1: | ||
- | ====== std::set ====== | + | ====== std:: |
Ένα [[http:// | Ένα [[http:// | ||
- | Η κατάταξη ενός νέου στοιχείου γίνεται πάντα μέσω σύγκρισης με τα υπόλοιπα στοιχεία που είναι αποθηκευμένα στην δομή. Για τον λόγο αυτό | + | Η κατάταξη ενός νέου στοιχείου γίνεται πάντα μέσω σύγκρισης με τα υπόλοιπα στοιχεία που είναι αποθηκευμένα στην δομή. Για τον λόγο αυτό, απαραίτητη προϋπόθεση |
+ | <code cpp> | ||
+ | if(!(a < b) && !(b < a)) | ||
+ | </ | ||
+ | Ένα [[http:// | ||
+ | Στα παρακάτω σχήματα διακρίνεται η δομή ενός [[http:// | ||
+ | | {{ : | ||
+ | | **Σχήμα 1. std:: | ||
+ | |||
+ | Το προγραμματιστικό // | ||
+ | |||
+ | |||
+ | ===== Επίδοσης της δομής ===== | ||
+ | |||
+ | * Η πράξη της ένθεσης ή της διαγραφής κοστίζει λογαριθμικό χρόνο **O(logN)**. | ||
+ | * Η πράξη της αναζήτησης κοστίζει επίσης λογαριθμικό χρόνο **O(logN)**. | ||
+ | * Η πρόσβαση στο i-στο στοιχείο της δομής δεν υφίσταται. | ||
+ | * Η διάτρεξη των στοιχείων γίνεται ξεκινώντας από το μικρότερο στοιχείο και καταλήγοντας στο μεγαλύτερο στοιχείο της δομής. | ||
+ | |||
+ | ===== Παράδειγμα ένθεσης και διάτρεξης ενός set ===== | ||
+ | |||
+ | === Παράδειγμα 1ο - std::string === | ||
+ | |||
+ | <code cpp string_set.cpp> | ||
+ | #include <set> | ||
+ | #include < | ||
+ | #include < | ||
+ | |||
+ | template< | ||
+ | void print(std:: | ||
+ | for(auto it = s.cbegin(); it!=s.cend(); | ||
+ | std::cout << *it << " "; | ||
+ | std::cout << std::endl; | ||
+ | } | ||
+ | |||
+ | int main(int argc, char *argv[]) { | ||
+ | std:: | ||
+ | | ||
+ | strset.emplace(" | ||
+ | strset.emplace(" | ||
+ | strset.emplace(" | ||
+ | strset.emplace(" | ||
+ | strset.emplace(" | ||
+ | strset.emplace(" | ||
+ | strset.emplace(" | ||
+ | strset.emplace(" | ||
+ | strset.emplace(" | ||
+ | strset.emplace(" | ||
+ | strset.emplace(" | ||
+ | | ||
+ | print(strset); | ||
+ | | ||
+ | return 0; | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | === Παράδειγμα 2ο - Student === | ||
+ | |||
+ | Κατεβάστε την κλάση //Student// από [[https:// | ||
+ | |||
+ | <code cpp student_set.cpp> | ||
+ | #include <set> | ||
+ | #include < | ||
+ | #include " | ||
+ | |||
+ | template< | ||
+ | void print(std:: | ||
+ | for(auto it = s.cbegin(); it!=s.cend(); | ||
+ | std::cout << *it << " "; | ||
+ | std::cout << std::endl; | ||
+ | } | ||
+ | |||
+ | int main(int argc, char *argv[]) { | ||
+ | std:: | ||
+ | | ||
+ | students.emplace(" | ||
+ | students.emplace(" | ||
+ | students.emplace(" | ||
+ | students.emplace(" | ||
+ | students.emplace(" | ||
+ | students.emplace(" | ||
+ | students.emplace(" | ||
+ | students.emplace(" | ||
+ | | ||
+ | print(students); | ||
+ | | ||
+ | return 0; | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | <WRAP todo 80% center round> | ||
+ | Αλλάξτε τον //STL container// από // | ||
+ | </ | ||
+ | |||
+ | <WRAP tip 80% center round> | ||
+ | Παρατηρήστε ότι η σειρά εκτύπωσης των στοιχείων κατά την διάτρεξη του // | ||
+ | </ | ||
+ | |||
+ | ===== Οι συναρτήσεις lower_bound, | ||
+ | |||
+ | Οι κλάσεις // | ||
+ | |||
+ | * **iterator lower_bound (const value_type& | ||
+ | * **iterator upper_bound (const value_type& | ||
+ | * **pair< | ||
+ | |||
+ | === Παράδειγμα upper_bound, | ||
+ | |||
+ | <code cpp string_multiset.cpp> | ||
+ | #include <set> | ||
+ | #include < | ||
+ | #include < | ||
+ | |||
+ | template< | ||
+ | void print(std:: | ||
+ | for(auto it = s.cbegin(); it!=s.cend(); | ||
+ | std::cout << *it << " "; | ||
+ | std::cout << std::endl; | ||
+ | } | ||
+ | |||
+ | int main(int argc, char *argv[]) { | ||
+ | std:: | ||
+ | | ||
+ | strset.emplace(" | ||
+ | strset.emplace(" | ||
+ | strset.emplace(" | ||
+ | strset.emplace(" | ||
+ | strset.emplace(" | ||
+ | strset.emplace(" | ||
+ | strset.emplace(" | ||
+ | strset.emplace(" | ||
+ | strset.emplace(" | ||
+ | strset.emplace(" | ||
+ | strset.emplace(" | ||
+ | | ||
+ | print(strset); | ||
+ | | ||
+ | auto lower_it = strset.lower_bound(" | ||
+ | auto upper_it = strset.upper_bound(" | ||
+ | |||
+ | strset.erase(lower_it, | ||
+ | print(strset); | ||
+ | | ||
+ | auto range = strset.equal_range(" | ||
+ | strset.erase(range.first, | ||
+ | print(strset); | ||
+ | | ||
+ | //Searching for mango again... | ||
+ | range = strset.equal_range(" | ||
+ | if(range.first == range.second) | ||
+ | std::cout << " | ||
+ | | ||
+ | return 0; | ||
+ | } | ||
+ | </ | ||
cpp/stl/set.1590756893.txt.gz · Last modified: 2020/05/29 11:54 (external edit)