#include <iostream>
#include <chrono>
#include <random>
#include <unordered_set>
#include <set>
#include <map>
#include <unordered_map>


int main() {
    // set : store only keys
    std::set<int> a;     // unique keys, sorted
    std::multiset<int> b; // dublicated keys, sorted
    std::unordered_set<int> c; // unique keys, not sorted, faster then std::set
    std::unordered_multiset<int> d; // dublicated keys, not sorted, faster then std::multiset

    // associative array: key -> value
    std::map<int, double> m; // unique keys, sorted
    std::unordered_map<int, double> z; // unique keys, not sorted, faster then std::map

    //                        map/set         unordered_{map/set}
    //insert/erase/search   O(logN)          O(1)

    for (int i = 0; i < 20; ++i) {
        b.insert(i);
        b.insert(i);
    }
    std::multiset<int>::iterator it = b.find(100);
    if (it != b.end()) {
        std::cout << "found " << (*it) <<  std::endl;
        b.erase(it); // must be valid
    } else {
        std::cout << "not found" << std::endl;
    }
    b.erase(100); // may be not exists


    if (b.count(10)) {

    }

    for (auto x : b) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

}