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

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

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

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

Στα παρακάτω σχήματα διακρίνεται η δομή ενός 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;
}