This is an old revision of the document!
Table of Contents
std::set και std::multiset
Ένα std::set αποτελεί ένα σύνολο μοναδικών στοιχείων. Τα στοιχεία αποθηκεύονται εσωτερικά σε ένα ισοζυγισμένο δέντρο αναζητήσεως (π.χ.Red–black_tree, AVL_tree).
Η κατάταξη ενός νέου στοιχείου γίνεται πάντα μέσω σύγκρισης με τα υπόλοιπα στοιχεία που είναι αποθηκευμένα στην δομή. Για τον λόγο αυτό, απαραίτητη προϋπόθεση για τη λειτουργία του set είναι για τους τύπους δεδομένων που αποθηκεύονται να παρέχονται οι τελεστές σύγκρισης < και >. Δύο στοιχεία θεωρούνται είναι σε ένα set εάν η παρακάτω λογική έκφραση είναι αληθής.
if(!(a < b) && !(b < a))
Ένα std::multiset αποτελεί ένα σύνολο όχι απαραίτητα μοναδικών στοιχείων, τα οποία είναι αποθηκευμένα σε ένα ισοζυγισμένο δέντρο αναζητήσεως. Ο τρόπος σύγκρισης και η κατάταξη των στοιχείων είναι παρόμοια με την επίπλέον σημείωση ότι το δέντρο επιτρέπει την εμφάνιση ενός κλειδιού περισσότερες από μία φορές.
Στα παρακάτω σχήματα διακρίνεται η δομή ενός std::set και ενός std::multiset.
Επίδοσης της δομής
- Η πράξη της ένθεσης ή της διαγραφής κοστίζει λογαριθμικό χρόνο O(logN).
- Η πράξη της αναζήτησης κοστίζει επίσης λογαριθμικό χρόνο O(logN).
- Η πρόσβαση στο i-στο στοιχείο της δομής δεν υφίσταται.
- Η διάτρεξη των στοιχείων γίνεται ξεκινώντας από το μικρότερο στοιχείο και καταλήγοντας στο μεγαλύτερο στοιχείο της δομής.