Ένα std::set αποτελεί ένα σύνολο μοναδικών στοιχείων. Τα στοιχεία αποθηκεύονται εσωτερικά σε ένα ισοζυγισμένο δέντρο αναζητήσεως (π.χ.Red–black_tree, AVL_tree).
Η κατάταξη ενός νέου στοιχείου γίνεται πάντα μέσω σύγκρισης με τα υπόλοιπα στοιχεία που είναι αποθηκευμένα στην δομή. Για τον λόγο αυτό, απαραίτητη προϋπόθεση για τη λειτουργία του set είναι για τους τύπους δεδομένων που αποθηκεύονται να παρέχονται ο τελεστής σύγκρισης <. Δύο στοιχεία ιδίου τύπου θεωρούνται ίσα σε ένα set εάν η παρακάτω λογική έκφραση είναι αληθής.
if(!(a < b) && !(b < a))
Ένα std::multiset αποτελεί ένα σύνολο όχι απαραίτητα μοναδικών στοιχείων (μπορεί να είναι, μπορεί και να μην είναι μοναδικά), τα οποία είναι αποθηκευμένα σε ένα ισοζυγισμένο δέντρο αναζητήσεως (όπως το set). Ο τρόπος σύγκρισης και η κατάταξη των στοιχείων είναι όμοια με την επίπλέον σημείωση ότι το δέντρο επιτρέπει την εμφάνιση ενός κλειδιού περισσότερες από μία φορές.
Στα παρακάτω σχήματα διακρίνεται η δομή ενός std::set και ενός std::multiset, όπου τα στοιχεία είναι ακέραιοι.
Το προγραμματιστικό interface των set και multiset είναι κοινό και έχει καλυφθεί στις προηγούμενες ενότητες.
#include <set> #include <string> #include <iostream> template<typename T> void print(std::set<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::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; }
Κατεβάστε την κλάση Student από εδώ.
#include <set> #include <iostream> #include "Student.hpp" template<typename T> void print(std::set<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::set<Student> 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; }
Αλλάξτε τον STL container από std::set σε std::multiset και παρατηρήστε την συμπεριφορά του προγράμματος σε αυτή την περίπτωση.
Παρατηρήστε ότι η σειρά εκτύπωσης των στοιχείων κατά την διάτρεξη του std::set ή του std::multiset είναι από το μικρότερο αποθηκευμένο στοιχείο προς το μεγαλύτερο. Τα αντικείμενα της κλάσης Student κατατάσσονται με βάση το ΑΕΜ.
Οι κλάσεις std::set και std::multiset διαθέτουν τις συναρτήσεις lower_bound, upper_bound και equal_range οι οποίες λειτουργούν ως εξής:
#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; }