#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 <iostream>
#include <string>
using namespace std;

int main() {
    int a = 9;
    int b = 4;
    // a + b = 42; // error: lvalue required as left operand of assignment

    string s1("Hello ");
    string s2("World");
    s1 + s2 = s2; // s1 + s2 可以当做左值！
    cout << s1 << endl;
    cout << s2 << endl;
    string() = "World"; // 可以对临时对象赋值！
}

union U { int a; double b; } u;
void* x = &u;                        // x 的值为“指向 u 的指针”
double* y = static_cast<double*>(x); // y 的值为“指向 u.b 的指针”
char* z = static_cast<char*>(x);     // z 的值为“指向 u 的指针”

std::for_each(files.begin(), files.end(),
              static_cast<std::ostream&(*)(std::ostream&)>(std::flush));

#include <iostream>
using namespace std;

class A {
   public:
    A() { cout << "default ctor\n"; }
    A(const A& b) { cout << "copy ctor\n"; }
    ~A() { cout << "dtor\n"; }
};

A foo() {
    A b;
    return b;
}

int main() {
    A a = foo();
    return 0;
}

// G++ 8.1.0, 64-bit
#include <iostream>
using namespace std;

class Point3d {
   public:
    virtual ~Point3d() {}
    static Point3d origin;
    float x, y, z;
};

struct Base1 {
    int val1;
};
struct Base2 {
    int val2;
};
struct Derived : Base1, Base2 {
    int val3;
};

Point3d Point3d::origin;

#define show(ptrToDataMember) printf(#ptrToDataMember " = %d\n", ptrToDataMember)

int main() {
    // 注意不能用 cout << &Point3d::x，会匹配到 operator<<(bool)
    // 为了简便，这里定义宏（与书上不同）
    show(&Point3d::x);  // 8
    show(&Point3d::y);  // 12
    show(&Point3d::z);  // 16

    show(&Base1::val1);    // 0
    show(&Base2::val2);    // 0
    show(&Derived::val1);  // 0
    show(&Derived::val2);  // 0（比较奇怪）
    show(&Derived::val3);  // 8
    return 0;
}

struct Base1 {
    int val1;
};

int main() {
    int Base1::* p = 0;
    cout << boolalpha << p << endl; // false
    p = &Base1::val1;
    printf("%d\n", p); // 0
    cout << boolalpha << p << endl; // true
    return 0;
}

#include <iostream>
#include <string>
using namespace std;

int main() {
    int64_t x;
    string& str = *new string();
    int64_t y;

    cin >> str; // 对引用做一次操作，避免编译器把变量优化掉

    cout << &x << endl;
    cout << &y << endl;
    cout << str << endl;

    return 0;
}

#include <iostream>
#include <string>
using namespace std;

void foo(int64_t q, string& s, int64_t r) {
    cout << "&q: " << &q << endl;
    cout << "&r: " << &r << endl;

    cout << "*(string**)(&q + 1): " << *(string**)(&q + 1) << endl;
}

int main()
{
    string& str = *new string();
    cout << "main(): " << &str << endl;
    foo(0, str, 0);
    return 0;
}

#include <iostream>
#include <string>
using std::cout;
using std::endl;
using std::string;

class Pet
{
public:
    virtual void print();
    string name;
};

class Dog : public Pet
{
public:
    virtual void print();
    string breed; // 品种
};

void Pet::print()
{
    cout << "Pet name: " << name << endl;
}

void Dog::print()
{
    cout << "Dog name: " << name << ", breed: " << breed << endl;
}

int main()
{
    Pet vPet;
    Dog vDog;
    vDog.name = "Tiny";
    vDog.breed = "Great Dane";
    vPet = vDog;
    // cout << vPet.breed;
    return 0;
}

#include <iostream>
#include <string>

using std::cout;
using std::endl;
using std::string;

class Demo
{
public:
    Demo(const string& s): str(s)
    {
        cout << "Demo constructor called (" + str + ").\n";
    }
    ~Demo()
    {
        cout << "Demo destructor called (" + str + ").\n";
    }
    Demo(const Demo& other)
    {
        str = other.str;
        cout << "Demo copy constructor called (" + str + ").\n";
    }
    Demo& operator=(const Demo& other)
    {
        str = other.str;
        cout << "Demo operator= called (" + str + ").\n";
        return *this;
    }
private:
    string str;
};

class Base
{
public:
    Demo member1 = Demo("member1");
};

class Derived : public Base
{
public:
    Demo member2 = Demo("member2");
};

int main()
{
    Derived derived;
    Base base;
    base = derived;
}
/* Output
Demo constructor called (member1).
Demo constructor called (member2).
Demo constructor called (member1).
Demo operator= called (member1).
Demo destructor called (member1).
Demo destructor called (member2).
Demo destructor called (member1).
*/

Pet *pPet;
Dog *pDog;
pDog = new Dog;
pDog->name = "Tiny";
pDog->breed = "Great Dane";
pPet = pDog;
pPet->print(); // prints "Dog name: Tiny, breed: Great Dane"

#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;
}