#include <iostream>
#include <iomanip>

// 原则上不要直接引用这个头文件，这里只是为了测试
#include <bits/stl_tree.h>

using namespace std;

struct Node {
    int first, second;
    Node(int _first, int _second) : first(_first), second(_second){};

    friend ostream& operator<<(ostream& outs, const Node& node) {
        outs << '{' << node.first << ',' << node.second << '}';
        return outs;
    }
};

template <class T>
struct Selector {
    // MUST return const int&, not int.
    // if return int, segmentation fault will occur.
    // I have spent much time because of this.
    const int& operator()(const T& obj) const {
        return obj.first;
    }
};

int main() {
    // _Rb_tree: red-black tree in STL.
    using tree_type = _Rb_tree<int, Node, Selector<Node>, less<int>>;
    using iterator_type = tree_type::iterator;
    using result_pair_type = pair<tree_type::iterator, bool>;
    tree_type tree;

    // 插入元素Node(1, 2)
    result_pair_type res = tree._M_insert_unique(Node(1, 2));
    cout << "insert address = " << res.first._M_node << endl;
    cout << "insert result = " << boolalpha << res.second << endl; // true

    iterator_type it = tree.begin();
    cout << "begin address = " << it._M_node << endl;

    it = tree.find(1);
    cout << "address = " << it._M_node << ", value = " << *it << endl;

    // 再插入元素Node(1, 2)但是因为调用的是insert_unique
    // 它不会添加重复值，所以插入会被拒绝
    res = tree._M_insert_unique(Node(1, 2));
    cout << "insert result = " << boolalpha << res.second << endl; // false

    // 再插入元素Node(1, 2)但这次调用insert_equal
    // multiset和multimap就是利用这个函数来插入重复值
    // 也就是这个函数允许重复值，所以插入成功
    tree._M_insert_equal(Node(1, 3));
    cout << "size = " << tree.size() << endl; // 大小就变为2

    pair<iterator_type, iterator_type> result = tree.equal_range(1);
    for (iterator_type ite = result.first; ite != result.second; ++ite) {
        cout << "address = " << ite._M_node << ", value = " << *ite << endl;
    }
    
    return 0;
}

// main.cpp, main()
int main() {
    ...
    it = tree.find(1);
    ...
}

// stl_tree.h, std::_Rb_tree::find(const _Key&)
template<typename _Key, typename _Val, typename _KeyOfValue,
         typename _Compare, typename _Alloc>
typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    find(const _Key& __k) {
        iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
        return (__j == end() || _M_impl._M_key_compare(__k,
            _S_key(__j._M_node))) ? end() : __j;
   }

// stl_tree.h, std::_Rb_tree::_M_lower_bound(_Link_type, _Link_type, const _Key&)
template<typename _Key, typename _Val, typename _KeyOfValue,
         typename _Compare, typename _Alloc>
typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    _M_lower_bound(_Link_type __x, _Link_type __y, const _Key& __k) {
        while (__x != 0)
            if (!_M_impl._M_key_compare(_S_key(__x), __k))
                __y = __x, __x = _S_left(__x);
            else
                __x = _S_right(__x);
        return iterator(__y);
    }

// stl_tree.h, std::_Rb_tree::_S_key(_Const_Base_ptr)
static const _Key& _S_key(_Const_Base_ptr __x) {
    return _KeyOfValue()(_S_value(__x));
}

#include <chrono>
#include <iostream>
#include <random>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

// 生成 [a, b] 范围内的整数
// 其中 INT_MIN <= a <= b <= INT_MAX
int rand(int a, int b) {
    static mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    return uniform_int_distribution<int>(a, b)(rng);
}

// 生成 [a, b] 范围内的整数
// 其中 0 <= a <= b <= UNSIGNED_INT_MAX
unsigned rand(unsigned a, unsigned b) {
    static mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    return uniform_int_distribution<unsigned>(a, b)(rng);
}

// 生成 [a, b] 范围内的整数
// 其中 LONG_LONG_MIN <= a <= b <= LONG_LONG_MAX
LL rand(LL a, LL b) {
    static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    return uniform_int_distribution<LL>(a, b)(rng);
}

// 生成 [a, b] 范围内的整数
// 其中 0 <= a <= b <= UNSIGNED_LONG_LONG_MAX
ULL rand(ULL a, ULL b) {
    static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    return uniform_int_distribution<ULL>(a, b)(rng);
}

int main() {
    const LL MAX = 1e10;
    cout << rand(-MAX, MAX);
    return 0;
}

#include <iostream>
#include <map>

using namespace std;

typedef multimap<int, char>::iterator iterType;

int main() {
    multimap<int, char> mp;
    mp.insert(make_pair(1, 'A'));
    mp.insert(make_pair(2, 'B'));
    mp.insert(make_pair(2, 'C'));
    mp.insert(make_pair(2, 'D'));
    mp.insert(make_pair(4, 'E'));
    mp.insert(make_pair(3, 'F'));
    pair<iterType, iterType> range = mp.equal_range(2);
    for (iterType it = range.first; it != range.second; ++it) {
        cout << it->first << ' ' << it->second << '\n';
    }
    return 0;
}