// Первое знакомство с set-ом

#include <set>

using namespace std;

// set -- cбалансированное дерево (красно-чёрное дерево)
// set умеет делать insert, erase, lower_bound за O(log n) и size, begin()=min, rbegin()=max за O(1)
// удобно set использовать, как кучу (add, del, extractMin)

set<int> heap; // упорядоченное множество {2,3,4}
multiset<int> s; // отличается от set тем, что элемент может встречаться несколько раз {2,2,3,3,3,4}

int main() {
  s.insert(3); // добавить элемент "3" в множество
  s.erase(3); // удалить элемент "3" из множества

  for (int i = 0; i < 10; i++)
    s.insert(i);

  int Size = s.size(); // Размер множества
  int Min = *s.begin(); // Минимальный элемент множества (если не пусто)
  int Max = *s.rbegin(); // Максимальный элемент множества (если не пусто)
  int is = s.count(3); // Сколько раз число 3 встречается в множестве (для set всегда или 0, или 1)

  // s.begin() - указатель на первый элемент
  // s.end() - указатель на первый элемент после конца
  // set = [s.begin(), s.end())

  // k-й элемент:
  set<int>::iterator it = s.begin(); // минимальный элемент за O(1)
  int k = 2;
  for (int i = 0; i < k; i++)
    it++; // следующий элемент за O(1) в среднем
  int res = *it; // нашли k-й элемент за O(k)

  int x = 10;
  auto it1 = s.begin(); // более кортокая запись, авто-вывод типа
  auto it2 = s.find(x); // нашли x, O(logn)
  auto it3 = s.lower_bound(x); // нашли первый >= x, O(logn)
  return 0;
}