====== std::set και std::multiset ======

Ένα [[http://www.cplusplus.com/reference/set/set/|std::set]] αποτελεί ένα σύνολο μοναδικών στοιχείων. Τα στοιχεία αποθηκεύονται εσωτερικά σε ένα ισοζυγισμένο δέντρο αναζητήσεως (π.χ.[[wp>Red–black_tree]], [[wp>AVL_tree]]). 

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

<code cpp>
if(!(a < b) && !(b < a))
</code> 

Ένα [[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]], όπου τα στοιχεία είναι ακέραιοι.

| {{ :cpp:stl:set01.png? |}}| {{ :cpp:stl:multiset01.png? |}} |
|  **Σχήμα 1. std::set**  |  **Σχήμα 2. std::multiset**  |

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


===== Επίδοσης της δομής =====

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

===== Παράδειγμα ένθεσης και διάτρεξης ενός set =====

=== Παράδειγμα 1ο - std::string ===

<code cpp 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;
}
</code>

=== Παράδειγμα 2ο - Student ===

Κατεβάστε την κλάση //Student// από [[https://courses.e-ce.uth.gr/ECE326/doku.php?do=export_code&id=cpp:stl:intro&codeblock=0|εδώ]].

<code cpp 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;
}
</code>

<WRAP todo 80% center round>
Αλλάξτε τον //STL container// από //std::set// σε //std::multiset// και παρατηρήστε την συμπεριφορά του προγράμματος σε αυτή την περίπτωση.
</WRAP>

<WRAP tip 80% center round>
Παρατηρήστε ότι η σειρά εκτύπωσης των στοιχείων κατά την διάτρεξη του //std::set// ή του //std::multiset// είναι από το μικρότερο αποθηκευμένο στοιχείο προς το μεγαλύτερο. Τα αντικείμενα της κλάσης //Student// κατατάσσονται με βάση το ΑΕΜ.
</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>