std::set και std::multiset

Ένα std::set αποτελεί ένα σύνολο μοναδικών στοιχείων. Τα στοιχεία αποθηκεύονται εσωτερικά σε ένα ισοζυγισμένο δέντρο αναζητήσεως (π.χ.Red–black_tree, AVL_tree).

Η κατάταξη ενός νέου στοιχείου γίνεται πάντα μέσω σύγκρισης με τα υπόλοιπα στοιχεία που είναι αποθηκευμένα στην δομή. Για τον λόγο αυτό, απαραίτητη προϋπόθεση για τη λειτουργία του set είναι για τους τύπους δεδομένων που αποθηκεύονται να παρέχονται ο τελεστής σύγκρισης <. Δύο στοιχεία ιδίου τύπου θεωρούνται ίσα σε ένα set εάν η παρακάτω λογική έκφραση είναι αληθής.

if(!(a < b) && !(b < a))

Ένα std::multiset αποτελεί ένα σύνολο όχι απαραίτητα μοναδικών στοιχείων (μπορεί να είναι, μπορεί και να μην είναι μοναδικά), τα οποία είναι αποθηκευμένα σε ένα ισοζυγισμένο δέντρο αναζητήσεως (όπως το set). Ο τρόπος σύγκρισης και η κατάταξη των στοιχείων είναι όμοια με την επίπλέον σημείωση ότι το δέντρο επιτρέπει την εμφάνιση ενός κλειδιού περισσότερες από μία φορές.

Στα παρακάτω σχήματα διακρίνεται η δομή ενός std::set και ενός std::multiset, όπου τα στοιχεία είναι ακέραιοι.

Σχήμα 1. std::set	Σχήμα 2. std::multiset

Το προγραμματιστικό interface των set και multiset είναι κοινό και έχει καλυφθεί στις προηγούμενες ενότητες.

• Η πράξη της ένθεσης ή της διαγραφής κοστίζει λογαριθμικό χρόνο O(logN).
• Η πράξη της αναζήτησης κοστίζει επίσης λογαριθμικό χρόνο O(logN).
• Η πρόσβαση στο i-στο στοιχείο της δομής δεν υφίσταται.
• Η διάτρεξη των στοιχείων γίνεται ξεκινώντας από το μικρότερο στοιχείο και καταλήγοντας στο μεγαλύτερο στοιχείο της δομής.

string_set.cpp

#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 από εδώ.

student_set.cpp

#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;
}

Οι κλάσεις std::set και std::multiset διαθέτουν τις συναρτήσεις lower_bound, upper_bound και 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 στην ενότητα std::map και std::multimap) που δείχνει στην αρχή και στο τέλος ενός εύρους στοιχείων στον container, όπου τα κλειδιά είναι ίδια με την τιμή val. Για ένα set το εύρος αυτό έχει μέγιστο μέγεθος ένα στοιχείο, ενώ για ένα multiset μπορεί να περιέχει περισσότερα στοιχεία. Εάν δεν βρεθεί κανένα στοιχείο με τιμή val οι iterators του ζεύγους δείχνουν και οι δύο σε κοινή θέση.

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;
}