#include <iostream>
#include <string>
#include <cassert>

using namespace std;
void reverse(string& str, int p, int q) {
    assert(p >= 0 && q >= 0 && p <= q && q < str.size());
    while (p < q) {
        swap(str[p], str[q]);
        p++;
        q--;
    }
}

void sentence_reverse(string& str) {
    int size = str.size();

    for (int i = 0; i < size; i++) {
        while(i < size && str[i] == ' ') i++;

        int word_begin = i;
        while (i < size && str[i] != ' ') i++;
        reverse(str, word_begin, i - 1);
    }
    reverse(str, 0, size - 1);
}

int main()
{
    string str{"I am a student."};
    sentence_reverse(str);
    cout << str << endl;
    cout << "Hello World" << endl;
    return 0;
}

namespace jump_game2_backtracing {
class Solution {
public:
    int jump(vector<int>& nums) {
        if (nums.empty()) return 0;
        return recursive(nums, 0, 0);
    }

    int recursive(const vector<int>& nums, int n, int iter) {
        int len = nums.size();
        if (n == len - 1) return iter;
        if (n >= len) return INT32_MAX;

        int step = nums[n];
        if (step == 0) return INT32_MAX;

        vector<int> v;
        for (int i = 1; i <= step; ++i) {
            int result = recursive(nums, n + i, iter + 1);
            v.push_back(result);
        }
        return *min_element(v.begin(), v.end());
    }
};
}

namespace jump_game2_dp {
    class Solution {
    public:
        int jump(vector<int>& nums) {
            int n = nums.size();

            if (n <= 1) return 0;

            vector<int> dp(n, 0);
            for (int i = 1; i < n; ++i) {
                int min = INT32_MAX;
                for (int j = 0; j < i; ++j) {
                    if ((j + nums[j] >= i) && (dp[j] + 1 < min)) {
                        min = dp[j] + 1;
                    }
                }
                dp[i] = min;
            }

            return dp[n - 1];
        }
    };
}

namespace jump_game2_greedy {
    class Solution {
    public:
        int jump(vector<int>& nums) {
            int n = nums.size();

            if (n <= 1) return 0;

            int last, curr, ret;
            last = curr = ret = 0;
            for (int i = 0; i < n; ++i) {
                if (i > last) {
                    last = curr;
                    ret++;
                }

                curr = max(curr, nums[i] + i);
            }

            return ret;
        }
    };
}

// 没有多态（因为操作对象不是class object）
int *pi;

// 没有语言所支持的多态
void *pvi;

// ok ： class x 视为一个base class（可以有多态的效果）
x *px;

class ZooAnimal{
  public:
    ZooAnimal();
    virtual ~ZooAnimal();

    virtual void rotate();
  protected:
    int loc;
    string name;
};
ZooAnimal za("Zoey");
ZooAnimal *pza = &za;

Bear b;
ZooAnimal za = b; // 这会引起切割，vptr设定为指向基类的virtual table
// 调用ZooAnimal::rotate()
za.rotate();

// 正确调用基类构造方法
Derived() : Base() {}

// 而不是
Derived() {Base()} // 基类构造方法会被调用两次，一次是编译器默认插入

class X{};
class Y : public virtual X{};
class Z : public virtual X{};
class A : public Y, public Z{};

// sizeof的结果视编译器而定，有没有empty virtual base class优化
/*
 sizeof(X) == 1 sizeof(Y) == 8 sizeof(Z) == 8 sizeof(A) == 12
 */
/*
 Visual C++ 5.0上执行结果
 sizeof(X) == 1 sizeof(Y) == 4 sizeof(Z) == 4 sizeof(A) == 8
 */

Point3d *pt3d;
pt3d->_x = 0.0;

Vertex3d *pv3d;
Vertex *pv;

pv = pv3d;
// C++内部转换操作
pv = pv3d ? (Vertex*)(((char*)pv3d) + sizeof(Point3d));

float Point2d::test(){}

// 增长过程
float Point2d::test(Point2d *const this)

// 如果memeber function 是 const
float Point2d::test(const Point2d *const this)

{
  return sqrt(this->x_ * this->x_ + this->y_ * this->y_);
}

extern test_7Point2dFv(const Point2d *const this);

obj.test();
test_7Point2dFv(&obj);

ptr->test();
test_7Point2dFv(ptr);

obj.normalize();

normalize_7Point3dSFv();
// 在C++引入静态成员函数之前，很少看到下面这种怪异写法
// 把0强制转换成一个class指针，因而提供出一个this指针实体
((Point3d*)0)->object_count();

Point3d::object_count();

Base2 *ptr = new Derived;

// 调用 Derived::~Derived
// ptr 必须向后调整sizeof(Base1)个bytes
delete ptr;

Derived *pder = new Derived;

// 调用Base2::mumble()
// pder必须被向前调整sizeof(Base1)个bytes
pder->mumble();

(((int) pmf ) & ~127) 
? // nonvirtual
(*pmf)(ptr)
: // virtual
(*ptr->vptr[(int)pmf](ptr));

Point *heap = new Point;

// C++伪码
Point *heap = __new(sizeof(Point));
if(heap!=0)
  heap->Point::Point();


// 与malloc的区别
Point *heap = static_cast<Point*>(malloc(sizeof(Poing)));
// 定位new
new (heap) Point;

// 析构
heap->Point::~Point();
// 该操作并不会导致destructor被调用，并没有明确的提供一个destrctor实体
delete heap;

int *p_array = new int[5];
int *p_array = (int*)__new(5 * sizeof(int));

// ok 
Point<float>::Status s;
// error
Point::Status s;

typedef std::pair<void*, std::size_t> mutable_buffer;
typedef std::pair<const void*, std::size_t> const_buffer;

size_t fake_read(boost::asio::streambuf::mutable_buffers_type buff) {
    size_t size_ = boost::asio::buffer_size(buff);

    srand(time(NULL));
    size_t max_size_ = rand() % size_;
    std::cout << "prepare out sequence size_ : " << size_ 
        << "\t random read size_ : " << max_size_ << std::endl;
    char* p = boost::asio::buffer_cast<char*>(buff);
    for (size_t i = 0;i < max_size_;i++) {
        p[i] = (i % 10) + 0x30;
    }

    return max_size_;
}

void stream_buff_test() {
    boost::asio::streambuf sb;
    auto prev = sb.data();
    std::ostream os(&sb);
    os << "Hello world\n";
    auto next = sb.data();

    // true
    std::cout << (boost::asio::buffers_begin(prev) 
        == boost::asio::buffers_begin(next)) << std::endl; 
    // false 说明输出序列的写指针pptr向后移动了
    std::cout << (boost::asio::buffers_end(prev) 
        == boost::asio::buffers_end(next)) << std::endl;

    std::cout << sb.size() << std::endl;
    // 移动输入序列读指针gptr，并调整尾指针egptr为pptr
    sb.consume(sb.size());
    std::cout << sb.size() << std::endl;

    std::cout << sb.max_size() << std::endl;

    /*
    主要调用reverse进行内存处理
    if epptr - pptr 空间够用，则直接返回
    else {
        将未读取的输入序列的内容移动到缓冲区头部
        buffer_.resize 底层存储申请内存
        setg 调整输入序列指针
        setp 调整输出序列指针
    }
    */
    boost::asio::streambuf::mutable_buffers_type out_bufs = sb.prepare(512);
    std::cout << sb.size() << std::endl;
    size_t bytes_transferred = fake_read(out_bufs);
    // 移动输出序列写指针
    sb.commit(bytes_transferred);
    std::cout << sb.size() << std::endl;

    boost::asio::streambuf::const_buffers_type in_bufs = sb.data();
    std::string data(boost::asio::buffers_begin(in_bufs), 
        boost::asio::buffers_begin(in_bufs) + bytes_transferred);
    std::cout << data << std::endl;

    sb.consume(bytes_transferred);
    std::cout << sb.size() << std::endl;
}

// Prepare 1024 bytes for the output sequence.  The input sequence is
// empty.
boost::asio::streambuf streambuf;
streambuf.prepare(1024);

// prepare() and write to the output sequence, then commit the written
// data to the input sequence.  The API contract has been violated.
std::ostream ostream(&streambuf);
ostream << "1234567890";

// Commit 10 unspecified bytes to the input sequence.  Undefined
// behavior is invoked.
streambuf.commit(10);

boost::asio::streambuf buf;
std::ostream os(&buf);
os << "Hello world\n";

using std::cout; // make cout available
cout << "Hello world" << endl;  // cout对象  插入运算符
  // << 运算符重载  | 左移
  // 同一个符号可以有多种含义，而编译器根据上下文来确定其含义

int chest = 42; // 基数为10
int waist = 0x42; // 基数为16
int inseam = 042; // 基数为8

cout << 1UL; // 被存储为unsigned long

char stack[10];
// index最大为9
stack[10] = 'z';
cout << stack[10] << endl;

char dog[8] = {'b', 'e', 'a', 'u', 'x', ' ', 'I', 'I'}; // not a string!
char cat[8] = {'f', 'a', 't', 'e', 's', 's', 'a', '\0'}; // a string
char bird[11] = "Mr. Cheeps"; // the \0 is understood

strlen("hello");

string str1;
string str2 = "panther";
string str3;

str3 = str1 + str2;
str1 = str2;

int *pn = new int;
delete pn;

// 对空指针使用delete是安全的
char *p = nullptr;
delete p;

int *pa = new int[10];
// 方括号告诉程序，应释放整个数组，而不仅仅是指针指向的元素
delete [] pa;

int tell[10];
// 数组的名称是第一个元素的地址
cout << tell << endl; // &tell[0]
cout << &tell << endl; // int (*p)[10]  (*p)[0]

#define BYTE char
typedef char byte;

const int *pt; // 指针指向一个常量对象，防止使用该指针修改所指向的值
int * const pt; // 将指针本身声明为常量，防止改变指针指向的位置

// 二维数组作为参数的函数，数组名被视为其地址，相应的形参是一个指针
int fun(int (*arr)[10], size_t n);
int fun(int [][10], size_t n);
// 也可以传递两个指针，其中一个指向数组开头，另一个指向数组末尾的下一个元素，以指定一个范围

// 返回一个指针，指向字符串前n个字符
char *left(const char *str, int n) {
  if (n < 0) n = 0;
  char *p = new char[n + 1]；
  int i;
  for (i = 0; i < n && str[i]; i++) {
    p[i] = str[i];
  }

  while (i <= n) {
    p[i++] = '\0';
  }

  return p;
}

void sink(double & r1); // lvalue
void sink(const double & r2); // const
void sink(const && r3); // rvalue

// typename OR class
template <typename T>
void swap(T &a, T &b) {
  T temp;
  temp = a;
  a = b;
  b = temp;
}

swap<int>(a, b);

int x;
decltype(x) y; // make y the same type as x

template<class T1, class T2>
auto gt(T1 x, T2 y) -> decltype(x + y)
{
  return x + y;
}

int * p1 = new int; // invoke new(sizeof(int))
int * p2 = new(buffer) int; // invoke new(sizeof(int), buffer)

char * buff = new char[512];
classname *pc = new (buff) classname;
pc->~classname(); // 显示调用析构
delete[] buff;

// using 声明
using std::cout;
// using 编译
using namespace std;

class Stock{
  private:
    void set_tot();
};

// 不仅是一个void类型的函数，而是一个术语Stock类的void函数
inline void Stock::set_tot() {}

// const成员函数，不修改调用对象
void Stock::show() const {}

// 成员函数重载
Time Time::operator*(double mult) const {}

A = B * 2.75; // 转换为A = B.operator*(2.75)函数调用
// 不能处理
A = 2.75 * B;
// 非成员函数重载运算符
Time operator*(double m, const Time &t){}
// 可以按成员函数相反顺序处理操作数， 不能访问类的私有成员
// A = operator*(2.75, B);

ostream & operator<<(ostream & os, const Time & t) {
  os << t.hours << " hours, " << t.minutes << " minutes";
  return os;
}

cout << "Trip time: " << trip << endl;

class Vector {
  enum Mode {RECT, POL};
};

Vector::RECT;

// 转换为double类型的函数原型
operator double();

class string {
  private:
    char *str;
    int len;
  public:
    string() {
      len = 0;
      str = new char[1];
      str[0] = '\0';
    }
    string(const char *s) {
      len = std::strlen(s);
      // 包含末尾的空字符
      str = new char[len + 1];
      strcpy(str, s);
    }

    // 复制构造函数
    string(const string & st) {
      len = st.len;
      str = new char[len + 1];
      strcpy(str, st.str);
    }

    // 赋值运算符
    string & operator=(const string & st) {
      // 自我赋值
      if (this == &st) return *this;

      delete [] str; // 删除旧str
      len = st.len;
      str = new char[len + 1];
      strcpy(str, st.str);

      return *this;
    }

    ~string() {
      delete[] str;
    }

    // 友元
    friend std::ostream & operator<<(std::ostream & os, const string & st);
};

std::ostream & operator<<(std::ostream & os, const string & st) {
  os << st.str;
}

class string {
  private: 
    string(const string & st){}
};

// 不允许
string str2(str1);
str2 = str1;

class Test{
  static int O_var;
};

int Test::O_var = 0;

string str1("test");
string str2 = str1; // 初始化，复制构造函数

str2 = str1; // = 赋值运算符

Vector max(const Vector &v1, const Vector & v2);
const Vector & max(const Vector &v1, const Vector & v2);

std::ostream & operator<<(std::ostream & os, const hasDMA &hs) {
  // type cast to match operator<<(std::ostream & os, const baseDMA &)
  os << (const baseDMA &)hs;
  os << "Style: " << hs.style << ednl;
  return os;
}

// 当派生类使用关键字virtual来指示派生时，基类就成为虚基类
class Singer : virtual public Worker {};
class Waiter : public virtual Worker {};
class SinngingWaiter : public Singer, public Waiter {};
// SinngingWaiter对象将只包含Worker对象的一个副本

#include <iostream>
using namespace std;

template <typename T>
class smart_ptr
{
private:
  T *ptr; // 智能指针底层保管的指针
  int *count; //引用计数
public:
  smart_ptr(T*); // 用普通指针初始化智能指针
  smart_ptr(smart_ptr&); // 拷贝构造函数

  T* operator->(); // 自定义指针运算符
  T& operator*(); // 自定义解引用运算符
  smart_ptr& operator=(smart_ptr&); // 自定义赋值运算符

  ~smart_ptr(); // 自定义析构函数
};

template <typename T>
smart_ptr<T>::smart_ptr(T *p): count(new int(1)), ptr(p) {}

template <typename T>
//对普通指针进行拷贝，同时引用计数器加1，因为需要对参数进行修改，所以没有将参数声明为const
smart_ptr<T>::smart_ptr(smart_ptr &p): count(&(++*p.count)), ptr(p.ptr)  {}

template <typename T>
T* smart_ptr<T>::operator->() {
    return ptr;
}

template <typename T>
T& smart_ptr<T>::operator*() {
    return *ptr;
}

// 左边指针不再指向原对象，考虑内存释放
// 定义赋值运算符，左边的指针计数减1，右边指针计数加1，当左边指针计数为0时，释放内存
template <typename T>
smart_ptr<T>& smart_ptr<T>::operator=(smart_ptr& sp) {
    ++*sp.count;
    if (--*count == 0) { //自我赋值同样能保持正确
        delete count;
        delete ptr;
    }
    this->ptr = sp.ptr;
    this->count = sp.count;
    return *this;
}

template <typename T>
smart_ptr<T>::~smart_ptr() {
    if (--*count == 0) {
        delete count;
        delete ptr;
    }
}

// To compile: g++ -O -g -fsanitize=address use-after-free.c
int main(int argc, char **argv)
{
  smart_ptr<int> p(new int(9));
  cout << *p << endl;
  return 0;
}

// 为何摒弃auto_ptr
auto_ptr<string> ps(new string("auto_ptr test"));
auto_ptr<string> vocation;
vocation = ps;
// vocatoin将剥夺ps的所有权，ps不再指向有效的数据

unique_ptr<string> p3(new string("unique_ptr test"));
unique_ptr<string> p4;
p4 = p3; // 非法，编译器将阻止

#include <stdio.h>
int main()
{
  printf("%d\r\n", sizeof(int));
  printf("%d\r\n", sizeof(int *));

  return 0;
}

> 4
> 8

// 通用套接字地址结构sockaddr
int bind(int, struct sockaddr*, socklen_t);

bind(sockfd, (strcut sockaddr*) &serv, sizeof(serv));

// 传递二进制结构和文本字符串
struct args {
  long arg1;
  long arg2;
};
// 二进制结构 需要考虑字节序
write(sockfd, &args, sizeof(args));

char line[MAXLINE];
// 文本字符串
write(sockfd, line, strlen(line));

union {
  short s;
  char c[sizeof(short)];
} un;
un.s = 0x0102;

// Berkeley
#include <strings.h>
void bzero(void *dest, size_t nbytes);
void bcopy(const void *src, void *dest, size_t nbytes);
int bcmp(const void *ptr1, const void *ptr2, size_t nbytes);

// ANSI c
#include <string.h>
void *memset(void *dest, int c, size_t len);
void *memcpy(void *dest, const void *src, size_t nbytes);
int memcmp(const void *ptr1, const void *ptr2, size_t nbytes);

#include <sys/socket.h>
// 协议族，套接字类型，协议类型
// SOCK_STREAM-字节流套接字  SOCK_DGRAM-数据报套接字
int socket(int family, int type, int protocol);

// 激发TCP的三次握手过程，而且仅在连接建立成功或出错时才返回
int connect(int sockfd, const struct sockaddr *servaddr, socklen_t addrlen);

// bind函数把一个本地协议地址赋予一个套接字 
// 通配地址 INADDR_ANY
int bind(int sockfd, const struct sockaddr *myaddr, socklen_t addrlen);

// SYN_RCVD和ESTABLISHED两队列之和不超backlog OR 模糊因子，乘以1.5得到未处理队列最大长度
// backlog参数的确切含义，它应该指定某个给定套接字上内核为之排队的最大已完成连接数
int listen(int sockfd, int backlog);

// 从已完成连接队列队头返回一个已完成连接，如果该队列为空，那么进程被投入睡眠
// 假定套接字为默认的阻塞方式
int accept(int sockfd, struct sockaddr *cliaddr, socklen_t *addrlen);

#include <unistd.h>
int close(int sockfd);
/*
 close一个TCP套接字的默认行为是把该套接字标记成已关闭，然后立即返回到调用进程。
 该套接字描述符不能再由调用进程使用，也就是说不能再作为read或write的第一个参数。
 然而TCP将尝试发送已排队等待发送到对端的任何数据，发送完毕后发生的是正常的TCP连接终止序列。
 */

#include <unistd.h>
// 调用一次，返回两次
// 父进程中调用fork之前打开的所有描述符在fork返回之后由子进程共享
/*
 我们将看到网络服务器利用了这个特性：父进程调用accept之后调用fork。所接受的已连接套接字随后就在父进程与子进程之间共享。
 通常情况下，子进程接着读写这个已连接套接字，父进程则关闭这个已连接套接字。
 */ 
pid_t fork(void);
/*
 fork有两个典型的用法：一个进程创建一个自身的副本 or 一个进程想要执行另一个程序，exec把当前进程映像替换成新的程序文件，而且该新程序通常从main函数开始执行。进程ID并不改变。
 进程在调用exec之前打开着的描述符通常跨exec继续保持打开
 */
/*
 这6个exec函数之间的区别在于：
 1. 待执行的程序文件是由文件名（filename）还是由路径名（pathname）指定
 2. 新程序的参数是一一列出还是由一个指针数组来引用
 3. 把调用进程的环境传递给新程序还是给新程序指定新的环境
 */
// 以空指针结束可变数量的这些参数
int execl(const char *pathname, const char *arg0, ... /* (char*)0 */);
// 常量指针 declare argv as array of const pointer to char
// 没有指定参数字符串的数目，argc数组必须含有一个用于指定其末尾的空指针
int execv(const char *pathname, char *const argv[]); 
  // 原书这里有笔误：char *const *argv[] 
int execle(const char *pathname, const char *arg0, ... /* (char*)0, char *const envp[] */); 
int execve(const char *pathname, char *const argv[], char *const envp[]); 
int execlp(const char *filename, const char *arg0, ... /* (char*)0 */);
int execvp(const char *filename, char *const argv[]);
/*
 这些函数只在出错时才返回到调用者。否则，控制将被传递给新程序的起始点，通常就是main函数
 */

// 信号处理函数由信号值这个单一的整数参数来调用，且没有返回值，原型如下：
void handler(int signo);
// 第一个参数是信号名，第二个参数指向函数的指针
void (*signal(int signo, void (*handler)(int))) (int);

#include <sys/wait.h>
pid_t wait(int *statloc);
pid_t waitpid(pid_t pid, int *statloc, int options);

#include <sys/select.h>
#include <sys/time.h>
// 允许进程指示内核等待多个事件中的任何一个发生
// 忘了对最大描述符+1，忘了描述符集是值-结果参数
int select(int maxfdp1, fd_set *readset, fd_set *writeset, fd_set *exceptset, const struct timeval *timeout);

struct timeval {
  long tv_sec; // seconds
  long tv_usec; // microseconds 微秒   millisecond-毫秒
};


#include <poll.h>
int poll(struct pollfd *fdarray, unsigned long nfds, int timeout);
struct pollfd {
  int fd;
  short events;
  short revents;
};

#include <sys/socket.h>

ssize_t recvfrom(int sockfd, void *buff, size_t nbytes, int flags, struct sockaddr *from, socklen_t *addrlen);
ssize_t sendto(int sockfd, const void *buff, size_t nbytes, int flags, const struct sockaddr *to socklen_t addrlen);

template<typename T>  
class Singleton : boost::noncopyable  
{
    public:
        static T& instance()
        {
            pthread_once(&ponce_, &Singleton::init);
            return *value_;
        }

        static void init()
        {
            value_ = new T();
        }
    private:
        static pthread_once_t ponce_;
        static T* value_;

/*
private:
    Singleton();                            // ctor hidden
    Singleton(Singleton const&);            // copy ctor hidden
    Singleton& operator=(Singleton const&); // assign op. hidden
    ~Singleton();                           // dtor hidden
 */
};

template<typename T>  
pthread_once_t Singleton<T>::ponce_ = PTHREAD_ONCE_INIT;

template<typename T>  
T* Singleton<T>::value_ = NULL;  

#define N 1

int arr[N] = {0}; //初始化数组

enum {e1 = N, e2}; //匿名枚举

switch (cond) { //switch-case
  case N: break;
  default: break;
}

template<int i = N> //模板函数的默认模板参数
void func_args_template(){}

constexpr int get_compile_const() {return 1;}

const int i = 1;
constexpr int j = 1;

struct MyType{
  constexpr MyType(int x):i(x){}
  int i;
};
constexpr MyType mt = {0};

template<typename T>
constexpr T const_exp(T t) {return t;}

cmake_minimum_required(VERSION 3.8)
project(thread_test)

set(CMAKE_CXX_STANDARD 11)

set(SOURCE_FILES main.cpp)

add_executable(thread_test ${SOURCE_FILES})
target_link_libraries (thread_test pthread)

set(CMAKE_CXX_FLAGS -fno-elide-constructors)

#include <iostream>
#include <atomic>
#include <thread>

std::atomic<long long> total{0}; //只能从模板参数进行构造

void thread_func() {
    for (long long i = 0; i < 100000000LL; ++i) {
        total += 1;
    }
}

int main() {
    std::thread t1(thread_func);
    std::thread t2(thread_func);

    t1.join();
    t2.join();

    std::cout << total << std::endl;
    return 0;
}

/* 无锁编程 */
void lock(atomic_flag* lock){
    while(lock.test_and_set());//用于在一个内存空间原子地写入新值并且返回旧值
}
void un_lock(atomic_flag* lock) {lock.clear();}

#include <thread>
#include <atomic>
#include <iostream>
using namespace std;

atomic<int> a;
atomic<int> b;

int thread1(int) {
    int t = 1;
    a = t;
    b = 2;
}

int thread2(int) {
    while(b != 2) ; //自旋等待
    cout << a << endl; //总是期待a的值为1
}

int main() {
    thread t1(thread1, 0);
    thread t2(thread2, 0);
    
    t1.join();
    t2.join();
    return 0;
}

#include <iostream>

struct BigObject{
    BigObject() { std::cout << "construct.\n"; }
    BigObject(const BigObject&) { std::cout << "copy construct.\n"; }
    BigObject(BigObject&&) { std::cout << "move construct.\n"; }
    ~BigObject() { std::cout << "destruct.\n"; }
};

/*
NRVO Named Return Value Optimization
命名返回值优化
 */
BigObject foo() {
    BigObject localObj;
    std::cout << std::hex << &localObj << std::endl;
    return localObj;  
}

/*
RVO Return Value Optimization
返回值优化
 */
BigObject bar() {
    return BigObject(); 
}


int main() {
    BigObject o = foo();
    std::cout << std::hex << &o << std::endl;
    return 0;
}
/*
construct.
0x7ffd0e56deef
0x7ffd0e56deef
destruct.
 */

struct BigObject {};

BigObject foo() {
  BigObject ret;
  // generate ret
  return ret;
}

int main() {
  BigObject o = foo();
}

struct BigObject {};

BigObject * foo(BigObject * _hiddenAddress) {
  BigObject ret = {};
  // copy result into hidden object
  *_hiddenAddress = ret;
  return _hiddenAddress;
}

int main() {
  BigObject _hidden; // create hidden object
  BigObject o = *foo(&_hidden); // copy the result into d
}

struct BigObject {};

void f(BigObject& ret_value) {
  BigObject localObj;
  return ret_value.BigObject::BigObject(std::move(localObj));//显式构造
}

int main() {
  BigObject o; ///这里没有使用默认构造，定义而不构造
  f(&o);
}

#include <iostream>

struct C {
	C(int j) { i = j; }
	C(const C&) { std::cout << "A copy was made.\n"; }

	int i;
};

C  f(bool cond = false) {
	C first(101);
	C second(102);
	// the function may return one of two named objects
	// depending on its argument. RVO might not be applied
	return cond ? first : second;
}

int main() {
	std::cout << "Hello World!\n";
	C obj = f(true);
}

#define CALL_WITH_MAX(a, b) f((a) > (b) ？ (a) : (b))

// 可预料行为和类型安全检查
template<typename T>
inline void CallWithMax(const T& a, const T& b) {
  f(a > b ? a : b);
}

void print(const TextBlock& ctb) {
  std::cout << ctb[0]; // 调用const char& operator[](std::size_t position) const
}

// 令non-const operator[]调用其const —— 需要转型操作
// 反向做法，令const版本调用non-const版本是不应该做的事
// 因为const成员函数承诺绝不改变其内部对象，non-const却没有
char& operator[](std::size_t position) {
  return const_cast<char&>(
    static_cast<const T&>(*this)[position]
  );
}

T(const T&);
T& operator=(const T&);

// g++ -O -g -fsanitize=address virtual_base.cpp
#include <vector>
class Base
{
public:
  ~Base(){};
};

class Derived : public Base
{
private:
  std::vector<int> m_data;
};

int main()
{
  Base *obj = new Derived();
  delete obj;

  return 0;
}

class AWOV {
  public:
    virtual ~AWOV() = 0;
};

DBConn::~DBConn() {
  try {db.close();}
  catch (...) {
    // 记录下对close的调用失败
    std::abort();
  }
}

// 不能处理new异常
Widget& Widget::operator=(const Widget& rhs) {
  if (this == &rhs) return *this;

  delete pb;
  pb = new Bitmap(*rhs.pb);
  return *this;
}

// 如果new Bitmap抛出异常，pb会保持原状
// 对原bitmap做了一份复件，删除原bitmap，指向新制造的bitmap
Widget& Widget::operator=(const Widget& rhs) {
  Bitmap* pOrig = pb;
  pb = new Bitmap(*rhs.pb);
  delete pOrig;
  return *this;
}

// not good
// 工厂函数，返回动态分配对象
Investment* pInv = createInvestment();
...
delete pInv;

// 智能指针
std::auto_ptr<Investment> pInv(createInvestment());

class Lock{
  public:
  // 以某个mutex初始化shared_ptr，并以unlock函数为删除器
    explicit Lock(Mutex* pm) : mutexPtr(pm, unlock) {
      lock(mutexPtr.get());
    }
  private:
    shared_ptr<Mutex> mutexPtr;
};

// 在单独语句内以智能指针存储new的对象
// 如果不这样，一旦异常抛出，有可能导致难以察觉的资源泄露
shared_ptr<Widget> pw(new Widget);
processWidget(pw, priority());

const Rational& operator*(const Rational& lhs, const Rational& rhs) {
  // 更糟糕的写法，谁来为new出来的对象实施delete
  Rational* result = new Rational(lhs.n * rhs.n, lhs.d * rhs.d);
  return *result;
}
// 欲令诸如operator*这样的函数返回reference，只是浪费时间而已

class Rational{...}; // 不包括operator*
// non-member
const Rational operator*(const Rational& lhs, const Rational& rhs) {
  return Rational(lhs.numerator() * rhs.numerator(), 
    lhs.denominator() * rhs.denominator());
}
Rational oneHalf(1, 2);
Rational result = 2 * oneHalf;

namespace WidgetStuff{
  template<typename T> 
  class Widget{...}; // 内含swap成员函数

  template<typename T>
  void swap(Widget<T>& a, Widget<T>& b) {
    a.swap(b);
  }
}

class SpecialWindow: public Window {
  public:
    virtual void onResize() {
      Window::onResize();
      // 而不是 static_cast<Window>(*this).onResize();
    }
};

void PrettyMenu::changeBackground(std::iostream& imgSrc) {
  // 互斥器作为并发控制
  lock(&mutex);
  delete bgImage;
  ++imageChanges;
  bgImage = new Image(imgSrc);
  unlock(&mutex);
}

void PrettyMenu::changeBackground(std::iostream& imgSrc) {
  // 使用对象管理资源
  Lock ml(&mutex);
  Image* pIOrig = bgImage;
  bgImage = new Image(imgSrc);
  delete pIOrig;
  ++imageChanges;
}

class PrettyMenu{
  shared_ptr<Image> bgImage;
};
void PrettyMenu::changeBackground(std::iostream& imgSrc) {
  // 使用对象管理资源
  Lock ml(&mutex);
  bgImage.reset(new Image(imgSrc));
  ++imageChanges;
}

class Derived: public Base {
  public:
    using Base::mf1; // 让Base class内 名为mf1的所有东西可见
};

Shape* ps;
Shape* pc = new Circle;
Shape* pr = new Rectangle;

template<typename T>
void doProcessing(T& w) {
  if (w.size() > 10 && w != someNastyWidget) {
    T temp(w);
    temp.normalize();
    temp.swap(w);
  }
}

template<typename C>          // 允许使用typename或class
void f(const C& container,    // 不允许使用typename
  typename C::iterator iter); // 一定要使用typename

template<>
class MsgSender<CompanyZ> {
  public:
    void sendSecret(const MsgInfo& info){}
}

// This file is a "Hello, world!" in C++ language by GCC for wandbox.
#include <iostream>
#include <cstdlib>

class RunTest {
public:
    RunTest(): ptr(new int){}
    ~RunTest() { delete ptr; }
private:
    int* ptr;
};

int main()
{
    RunTest rt1;
    RunTest rt2 = rt1;
    
    std::cout << "Hello, Wandbox!" << std::endl;
}

// GCC reference:
// https://gcc.gnu.org/

template<class T> class Test; 
template<typename T> class Test; 

typedef typename T::NestType NT;

template<class T, class Ref, size_t BufSiz = 0>

// 类模板
template <class T1, class T2>
class A{
    T1 data1;
    T2 data2;
};

// 函数模板
template <class T>
T max(const T lhs, const T rhs){   
    return lhs > rhs ? lhs : rhs;
}

// 全特化类模板
template <>
class A<int, double>{
    int data1;
    double data2;
};

// 函数模板
template <>
int max(const int lhs, const int rhs){   
    return lhs > rhs ? lhs : rhs;
}

template <class T>
void f(){ T d; }

template <>
void f(){ int d; }

template <class T>
void f(){ T d; }

template <>
void f<int>(){ int d; }

template <class T2>
class A<int, T2>{
    ...
};

template<typename T>
class c{...}; // 这个泛化版本允许接受T为任何类型

template<typename T>
class c<T*> {...};
// 这个特化版本仅适用于“T为原生指针”的情况
// “T为原生指针”便是“T为任何类型”的一个更进一步的条件限制

template <class T1, class T2>
void f(){}

template <class T2>
void f<int, T2>(){}

template <class T2>
void f(){}              // 注意：这里没有"模板实参"

// Function Template
template <typename T> 
T square (T x) {
  return x * x;
}

int main() {
  cout << square<int>(5) << endl;
  cout << square<double>(5.5) << endl;
}

// Class Template
template <typename T> 
T square (T x) {
  return x * x;
}

template <typename T> 
class BoVector {
  T arr[1000];
  int size;
public:
  BoVector() : size(0) {}
  void push(T x) { arr[size] = x; size++; }
  T get(int i) const { return arr[i]; }
  int getSize() const { return size; }
  void print() const { for(int i = 0; i < size; i++) { cout << arr[i] << endl; } }
};

template<typename T>
BoVector<T> operator* (const BoVector<T>& rhs1, const BoVector<T>& rhs2) {
  BoVector<T> ret;
  for (int i = 0; i < rhs1.getSize(); i++) {
    ret.push(rhs1.get(i) * rhs2.get(i));
  }

  return ret;
}

int main() {
  BoVector<int> bv;
  bv.push(2);
  bv.push(5);

  bv = square(bv);
  bv.print();
}

using namespace std;

// dynamic array allocated on the heap 
// the size of it is not fixed
vector<int> vec;
vec.push_back(4);
vec.push_back(1);
vec.push_back(8); // vec: {4, 1, 8}

// half-open : [begin, end) 前闭后开
// vector中的对象是没有命名的，可以按vector中对象的位置来访问它们
vector<int>::iterator itr1 = vec.begin();
vector<int>::iterator itr2 = vec.end();

// iterator just like the pointer
for (vector<int>::iterator itr = itr1; itr != itr2; ++itr) { cout << *itr << endl; }

sort(itr1, itr2); // vec : {1, 4, 8}

// STL Headers

#include <vector>
#include <deque>
#include <list>
#include <set>  // set and multiset
#include <map>  // map and multimap
#include <unordered_set> // unordered set/multiset
#include <unordered_map>  // unordered map/multimap
#include <iterator>
#include <algorithm>
#include <numeric>  // some numeric algorithm
#include <functional>

/*
 * Vector
 */
vector<int> vec; // vec.size() = 0;
vec.push_back(4);
vec.push_back(1);
vec.push_back(8);

// Vector specific operations
cout << vec[2];  // 8 (no range check)
cout << vec.at(2);  // 8 (throw range_error exception of out of range)

for (int i = 0; i < vec.size(); i++) cout << vec[i] << " ";

// usually faster than random access
for (vector<int>::iterator itr = vec.begin(); itr != vec.end(); ++itr) cout << *itr << " ";

for (it : vec)  // C++ 11
  cout << it << " ";

// Vector is dynamically allocated contiguous array in memory
int* p = &vec[0];  p[2] = 6;

// Common member functions of all containers

if (vec.empty()) cout << "Not possible.\n";

cout << vec.size();

vector<int> vec2(vec); // Copy construct, vec2 : {4, 1, 8}
vector<int> vec3(3, 0); // vec3 : {0, 0, 0}

vec.clear();  // Remove all items in vec; vec.size() == 0

vec2.swap(vec); // vec2 becomes empty, and vec has 3 items

/* Properties of Vector:
 * 1. fast insert/remove at the end: O(1)
 * 2. slow insert/remove at the begining or in the middle: O(n)
 * 3. slow search: O(n)
 */

/*
 * Deque
 */
deque<int> deq = {4, 6, 7};
deq.push_front(2);
deq.push_back(3);

cout << deq[1] << endl;

/* Properties of Deque:
 * 1. fast insert/remove at the begining and the end: O(1)
 * 2. slow insert/remove in the middle: O(n)
 * 3. slow search: O(n)
 */

/*
 * List (double linked)
 */
list<int> mylist = {5, 2, 9};
mylist.push_back(6);
mylist.push_front(4); // mylist : {4, 5, 2, 9, 6}

list<int>::iterator itr = find(mylist.begin(), mylist.end(), 2);
mylist.insert(itr, 8); // mylist : {4, 5, 8, 2, 9, 6}

itr++;  // itr -> 9
mylist.erase(itr); // mylist : {4, 5, 8, 2, 6}

// mylist2切片后添加到mylist1
mylist1.splice(itr, mylist2, itr_a, itr_b);  // O(1)

/* Properties of List:
 * 1. fast insert/remove at any place: O(1)
 * 2. slow search: O(n), much slower than vector (cache missing)
 * 3. no random access, no [] operator
 */

/*
 * Array 
 */
int a[3] = {3, 4, 5};
// element type and size
array<int, 3> a = {3, 4, 5};
a.begin();
a.end();
a.size();
a.swap();

array<int, 4> b = {1, 3, 4, 5};

/* Properties of Array:
 * 1. the size can not be changed
 * 2. two array of integer may have different type
 */

/*
 * 1. Is always sorted
 * 2. No push_back(), push_front()
 */

/*
 * Set - No duplicates 
 */
set<int> myset;
myset.insert(3);  // myset : {3}
myset.insert(1);  // myset : {1, 3}
myset.insert(7);  // myset : {1, 3, 7}, sorted, O(log(n))

set<int>::iterator it;
it = myset.find(7);  // O(log(n)), it points to 7
                             // Sequence containers don't even have find() member function

pair<set<int>::interator, bool> ret;
ret = myset.insert(3); // no new element inserted
if (ret.second == false) it = ret.first; // it now points to element 3

myset.insert(it, 9); // myset : {1, 3, 7, 9}, just provide hint, may O(log(n)) => O(1)
                             // it points to 3
myset.erase(it); // myset : {1, 7, 9}
myset.erase(7); // myset : {1, 9}, remove an item by its value

// multiset is a set that allows duplicated items
multiset<int> myset;

// set/multiset: value of the elements cannot be modified
*it = 10; // *it is read-only

/* Properties:
 * 1. Fast search: O(log(n))
 * 2. Traversing is slow (compared to vector & deque)
 * 3. No random access, no [] operator
 */

/*
 * map - No duplicated key
 */
map<char, int> mymap;
mymap.insert ( pair<char, int>('a', 100) );
mymap.insert ( make_pair('z', 200) );

map<char, int>::iterator it = mymap.begin();
mymap.insert(it, pair<char, int>('b', 300)); // it -> just a hint

it = mymap.find('z'); // O(log(n))

for (it = mymap.begin(); it != mymap.end(); ++it) cout << (*it).first << " => " (*it).second << endl;

// multimap is a map that allows duplicated keys
multimap<char, int> mymap;

// map/multimap: keys cannot be modified 
// type of *it : pair<const char, int>
(*it).first = 'd'; // Error, *it is read-only

/*
 * unordered set
 */
unordered_set<string> myset = {"red", "green", "blue"};
unordered_set<string>::const_iterator itr = myset.find("green"); // O(1)
if (itr != myset.end()) // Important check
 cout << * itr << endl;
myset.insert("yellow"); // O(1)

vector<string> vec = {"purple", "pink"};
myset.insert(vec.begin(), vec.end());

// Hash table specific APIs
cout << "load_factor = " << myset.load_factor() << endl;
string x = "red";
cout << x << " is in bucket #" << myset.bucket(x) << endl;
cout << "Total bucket #" << myset.bucket_count() << endl;

// unordered multiset : allows duplicated elements
// unordered map : unoredred set of pairs
// unordered multimap: allows duplicated keys

// hash collision => performance degrade[降级]

/* Properties of Unordered Containers:
 * 1. Fastest search/insert at any place: O(1)
 * 2. Unordered set/multiset: element value cannot be changed
 *     Unordered map/multimap: element key cannot be changed
 */

/*
 * Associative Array - map and unordered map
 */
unordered_map<char, string> day = {{'S', "Sunday"}, {'M', "Monday"}};

cout << day['S'] << endl; // No range check
cout << day.at('S') << endl; // Has range check

vector<int> vec = {1, 2, 3};
vec[5] = 5; // Compile Error

day['W'] = "Wednesday"; // Insert {'W', "Wednesday"}
day.insert(make_pair('F', "Friday")); 

day.insert(make_pair('M', "MONDAY")); // Fail to modify, it's an unordered map
day['M'] = "MONDAY"; // Succeed to modify

void foo(const unordered_map<char, string>& m) {
  // m['S'] = "SUNDAY"; 
  // cout << m['S'] << endl;  not compile

  auto itr = m.find('S');
  if (itr != m.end()) cout << *itr << endl;
}
foo(day);

/*
 * Container Adapter
 * 1. stack: LIFO, push(), pop(), top()
 * 2. queue: FIFO, push(), pop(), front(), back()
 * 3. priority queue: first item always has the greatest priority 
 *                       push(), pop(), top()
 */

/*
 * Another way of categorizing containers:
 * 1. Array based containers: vector, dequeue
 *  2. Node based containers: list + associative containers + unordered containers
 */

vector<int> vec = {1, 2, 3, 4};
int *p = &vec[2];
vec.insert(vec.begin(), 0);
cout << *p << endl;  // 2, or ?, or crash 指针失效
                              // 基于节点的容器不存在此问题

/*
 * Iterators
 */
// 1. Random Access Iterator : vector, deque, array
vector<int> itr;
itr = itr + 5; 
itr = itr - 4;
if (itr2 > itr1) ...
++itr;  // faster than itr++
--itr;

// 2. Bidirectional[双向] Iterator : list, set/multiset, map/multimap
list<int> itr;
++itr;
--itr;

// 3. Forward[前向] Iterator : forward_list
forward_list<int> itr;
++itr;
// Unordered Containers provide at least forward iterators

// 4. Input Iterator : read and process values while iterating forward
int x = *itr;

// 5. Output Iterator : output values while iterating forward
*itr = 100;

// Every container has a iterator and a const_iterator
set<int>::iterator itr;
set<int>::const_iterator citr; // Read_Only access to container elements

set<int> myset = {2, 4, 5, 1, 9};
for (citr = myset.begin(); citr != myset.end(); ++citr) {
  cout << *citr << endl;
  // *citr = 3;
}
// const_iterator
for_each(myset.cbegin(), myset.cend(), MyFunction); // Only in C++ 11

// Iterator Functions:
advance(itr, 5); // Move itr forward 5 spots. itr += 5;
distance(itr1, itr2); // Measure the distance between itr1 and itr2

/*
 * Iterator Adaptor (Predefined Iterator)
 * 1. Insert iterator
 * 2. Stream iterator
 * 3. Reverse iterator
 * 4. Move iterator (C++ 11)
 */
// 1. Insert Iterator:
vector<int> vec1 = {4, 5};
vector<int> vec2 = {12, 14, 16, 18};
vector<int>::iterator it = find(vec2.begin(), vec2.end(), 16);
insert_iterator<vector<int>> i_itr(vec2, it);
copy(vec1.begin(), vec1.end(),  //source
    i_itr);                                      //destination
  // vec2 : {12, 14, 4, 5, 16, 18}
// Other insert iterators : back_insert_iterator, front_insert_iterator

// 2. Stream Iterator:
vector<string> vec4;
copy(istream_iterator<string>(cin), istream_iterator<string>(), back_inserter(vec4));

copy(vec4.begin(), vec4.end(), ostream_iterator<string>(cout, " "));

copy(istream_iterator<string>(cin), istream_iterator<string>(), ostream_iterator<string>(cout, " "));

// 3. Reverse Iterator:
vector<int> vec = {4, 5, 6, 7};
reverse_iterator<vector<int>::iterator> ritr;
for (ritr = vec.rbegin(); ritr != vec.rend(); ritr++) cout << *ritr << endl;

/*
 * Algorithms - mostly loops
 */
vector<int> vec = {4, 2, 5, 1, 3, 9};
vector<int>::iterator itr = min_element(vec.begin(), vec.end()); 

// ranges in a half-open way : [begin, end)
sort(vec.begin(), itr);
reverse(itr, vec.end());

vector<int> vec2(3);
copy(itr, vec.end(), //source
    vec2.begin());  //destination
// vec2 needs to have at least space for 3 elements

vector<int> vec3;
copy(itr, vec.end(), back_inserter(vec3)); // Inserting instead of overwriting
                              // back_insert_interator  Not efficient
vec3.insert(vec3.end(), itr, vec.end()); // Efficient and safe


// Algorithm with function
bool isOdd(int i) {
  return i%2;
}

int main() {
  vector<int> vec = {2, 4, 5, 9, 2};
  vector<int>::iterator itr = find_if(vec.begin(), vec.end(), isOdd);
                                           // itr -> 5
}

// Algorithm with native C++ array
int arr[4] = {6, 3, 7, 4};
sort(arr, arr + 4);

/*
 * STL Algorithm Walkthrough:
 * Non-modifying Algorithms
 * count, min and max, compare, linear search, attribute
 */

vector<int> vec = {9, 60, 90, 8, 45, 87, 90, 69, 69, 55, 7};
// 1. Counting
int n = count(vec.begin(), vec.end(), 69);  //2
// C++ 11 Lambda Function:
int m = count_if(vec.begin(), vec.end(), [](int x) { return x < 10; }); //3

// 2. Min and Max
itr = max_element(vec.begin() + 2, vec.end()); //90
itr = max_element(vec.begin(), vec.end(), [](int x, int y) { return (x%10) < (y%10)}); //9

// 3. Linear Searching (used when data is not sorted or use binary search) 
// Return the first match
itr = find(vec.begin(), vec,end(), 55);
itr = find_if(vec.begin(), vec.end(), [](int x) {return x > 80;});
itr = find_if_not(vec.begin(), vec.end(), [](int x) {return x > 80;});
itr = search_n(vec.begin(), vec.end(), 2, 69); //Consecutive 2 items of 69

// Search subrange
vector<int> sub = {45, 87, 90};
itr = search(vec.begin(), vec.end(), sub.begin(), sub.end());
       // search first subrange
itr = find_end(vec.begin(), vec.end(), sub.begin(), sub.end());
       // search last subrange

// Search any_of
vector<int> items = {87, 69};
itr = find_first_of(vec.begin(), vec.end(), items.begin(), items.end());
       // Search any one of the item in items

// 4. Comparing Ranges
if (equal(vec.begin(), vec.end(), vec2.begin())) cout << "vec and vec2 are same" << endl;

// 5. Check Attributes
is_sorted(vec.begin(), vec.end());
itr = is_sorted_until(vec.begin(), vec.end());

is_heap(vec.begin(), vec.end());

all_of(vec.begin(), vec.end(), [](int x) {return x > 80;});
any_of(vec.begin(), vec.end(), [](int x) {return x > 80;});
none_of(vec.begin(), vec.end(), [](int x) {return x > 80;});

/*
 * Algorithm Walkthrough:
 *     Value-changing Algorithm - Changes the element values
 *     copy, move, transform, swap, fill, replace, remove
 */
vector<int> vec = {9, 60, 70, 8, 45, 87, 90};
vector<int> vec2 = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; //11 items
vector<int>::iterator itr, itr2;
pair<vector<int>::iterator, vector<int>::iterator> pair_of_itr;

// Copy
copy(vec.begin(), vec.end(),  // Source
    vec2.begin());                     // Destination. vec2.size() > vec.size()

copy_if(vec.begin, vec.end(),
    vec2.begin(),
    [](int x) { return x > 80; });
// vec2 : {87, 90, 0, 0, 0, 0, 0, 0, 0, 0, 0}

copy_n(vec.begin(), 4, vec2.begin());
// vec2 : {9, 60, 70, 8, 0, 0, 0, 0, 0, 0, 0}

copy_backward(vec.begin(), vec.end(),
    vec2.end());
// vec2 : {0, 0, 0, 0, 9, 60, 70, 8, 45, 87, 90}

unique(vec.begin(), vec.end()); // Remove consecutive[连续] equal elements

/*
 * Order-Changing Algorithms
 *     - reverse, rotate, permute, shuffle
 * They changes the order of elements in container, but not necessarily the elements themselves.
 */

/*
 * Sorting in STL
 */
// Sorting algorithm requires random access iterators : 
//     - vector, deque, container array, native array

vector<int> vec = {9, 1, 10, 2, 45, 3, 90, 4, 9, 5, 8};
sort(vec.begin(), vec.end()); // sort with operator < 
// vec : 1 2 3 4 5 8 9 9 10 45 90

bool lsb_less(int x, int y) {
  return (x%10) < (y%10);
}
sort(vec.begin(), vec.end(), lsb_less);
// vec : {10, 90, 1, 2, 3, 4, 45, 5, 8, 9, 9}

/*
 * Heap Algorithms
 * 
 * Heap: 
 * 1. First element is always the largest 
 * 2. Add/remove takes O(log(n)) time
 */

vector<int> vec = {9, 1, 10, 2, 45, 3, 90, 4, 9, 5, 8};

make_heap(vec.begin(), vec.end());
// vec : {90, 45, 10, 9, 8, 3, 9, 4, 2, 5, 1}

// Remove the largest element
pop_heap(vec.begin(), vec.end()); // 1. Swap vec[0] with last item vec[size - 1]
         // 2.Heapify [vec.begin(), vec.end() - 1] 
         // vec : {45, 9, 10, 4, 8, 3, 9, 1, 2, 5, 90}

vec.pop_back(); // Remove the last item (the largest one)
// vec : {45, 9, 10, 4, 8, 3, 9, 1, 2, 5}

// Add a new element
vec.push_back(100);
push_heap(vec.begin(), vec.end()); // Heapify the last item in vec
// vec : {100, 45, 9, 10, 4, 8, 3, 9, 1, 2, 5}

// Heap Sorting
sort_heap(vec.begin(), vec.end());
// vec : {1, 2, 3, 4, 5, 8, 9, 9, 10, 45, 100}
// Note : sort_heap can only work on a heap

/*
 * Sorted Data Algorithms
 *   - Algorithms that require data being pre-sorted
 *   - binary_serach, merge, set operations
 */

vector<int> vec = {8, 9, 9, 9,45, 87, 90};

// 1. Search Elements
bool found = binary_search(vec.begin(), vec.end(), 9);

vector<int> s = {9, 45, 66};
bool found = includes(vec.begin(), vec.end(),  // Range #1
    s.begin(), s.end());                       // Range #2
// Return true if all elements of s is included in vec
// Both vec and s must be sorted

// Search Position
itr = lower_bound(vec.begin(), vec.end(), 9);
// Find the first position where 9 could be inserted and still keep the sorting

itr = upper_bound(vec.begin(), vec.end(), 9);

pair_of_itr = equal_range(vec.begin(), vec.end(), 9);
// Return both first and last position

// 2. Merge
vector<int> vec = {8, 9, 9, 10};
vector<int> vec2 = {7, 9, 10};
merge(vec.begin(), vec.end(),          // Input Range #1
    vec2.begin(), vec2.end(),             // Input Range #2
    vec_out.begin());
    // Nothing is dropped, all duplicates are kept
// vec_out : {7, 8, 9, 9, 10, 10}

vector<int> vec = {1, 2, 3, 4, 1, 2, 3, 4, 5};  // Both part of vec are already sorted
inplace_merge(vec.begin(), vec.begin() + 4, vec.end());
// vec : {1, 1, 2, 2, 3, 3, 4, 4, 5}  -  One step of merge sort

// 3. Set operations
vector<int> vec = {8, 9, 9, 10};
vector<int> vec2 = {7, 9, 10};
vector<int> vec_out[5];
set_union(vec.begin(), vec.end(),
    vec2.begin(), vec2.end(),
    vec_out.begin());
    // If X is in both vec and vec2, only one X is kept in vec_out
// vec_out : {7, 8, 9, 9, 10}

// set_intersection[交集]， set_difference[差集] 

int main() {
  // Constructors
  string s1("Hello");
  string s2("Hello", 3);  // size, s2 : Hel
  string s3(s1, 2);  // start, s3: llo
  string s4(s1, 2, 2);  // start, size s4 : ll
  string s5(5, 'a');  // s5 : "aaaaa"
  string s6({'a', 'b', 'c'});  // s6 : "abc"

  // Size
  s1 = "Goodbye";
  s1.size(); s1.length(); // both return 7
  s1.capacity();  // size of storage space currently allocated to s1, >s1.size()
  s1.reserve(100); // allocate, 100 chars
  s1.reserve(5); // s1 : Goodbye, s1.size() ==7, s1.capacity() == 7
// reserve does not change the content of s1 and does not change the size
  s1.shrink_to_fit();  // shrink the capacity to hold the content

  s1.resize(9);  // s1: Goodbye\0\0
  s1.resize(12, 'x');
  s1.resize(3);  // s1: Goo
}

// Single Element Access
s1 = "Goodbye";
s1[2];  // 'o'
s1[2] = 'x';  // Goxdbye
s1.at(2) = 'y';  // Goydbye
s1.at(20);  // throw exception of out_of_range
s1[20];  // undefined behavior

s1.front(); // 'G'  reference
s1.back(); // 'e'
s1.push_back('z');
s1.pop_back();
s1.begin();  // iterator
s1.end();
// Like vector, but string doesn't have push_front() and pop_front()

string s3(s1.begin(), s1.begin() + 3); // s3 : Goo

// Ranged Access
// assign, append, insert, replace
string s2 = "Dragon land";

s1.assign(s2); // s1 = s2, assign[分配]
s1.assign({'a', 'b', 'c'});

s1.append(" def"); // s1 : abc def
s1.insert(2, "mountain", 4); // s1 : abmounc def
s1.erase(1, 4); // position size

// 一个参数size，两个参数position, size

// Member Function Algorithms: copy, find, compare
s1 = "abcdefg";
char buf[20];
size_t len = s1.copy(buf, 3); // buf : abc  len == 3
// buf[] is not terminated -> \0

// BAD : size, position
len = s1.copy(buf, 4, 2); // buf :  cdef  len == 4

s1 = "If a job is worth doing, it's worth doing well";
size_t found = s1.find("doing");  // found == 17
found = s1.find("doing", 20); // found == 35

found = s1.find_first_of("doing");  // found == 6, o, any of

s1.compare(s2); // return positive if (s1 > s2); negative if (s1 < s 2); 0 if (s1 == s2)

string ss = s1 + s2;

// Non-member functions
cout << s1 << endl;
cin >> s1;
getline(cin, s1);  // default delimeter of '\n'
getline(cin, s1, ';');  // delimeter is ';'

// convert a number into a string
s1 = to_string(0xa4); // s1 : 164

// convert a string into a number
s1 = "190";
int i = stoi(s1); // i : 190

s1 = "190 monkeys";
size_t pos;
i = stoi(s1, &pos); // i : 190  pos == 3

s1 = "a monkey";
i = stoi(s1, &pos);  // exception of invalid_argument
i = stoi(s1, &pos, 16); // hex, i == 10

// String and Algorithms
s1 = "Variety is the spice of life.";
int num = count(s1.begin(), s1.end(), 'e'); //4
num = count_if(s1.begin(), s1.end(), [](char c){ return (c <= 'e' && c >= 'a'); }); //6

s1 = "Goodness is better than beauty.";
string::iterator itr = search_n(s1.begin(), s1.begin() + 20, 2, 's'); // itr -> fisrt 's'
s1.erase(itr, itr + 5);

int main() {
  cout << "Hello" << endl;
  // cout : a global object of ostream (typedef basic_ostream<char> ostream)
  // <<:       ostream& ostream::operator<< (string v);
  // endl:     '\n' + flush
  
  {
    // What is stream? Serial IO Interface to external devices (file, stdin/stdout, network, etc...)
    ofstream of("Mylog.txt"); // create if not exist
    of << "Experience is the mother of wisdom" << endl;
    of << bitset<8>(14) << endl; // 00001110
    of << complex<int>(2, 3) << endl; // (2, 3)
  } // RAII

  {
    ofstream of("Mylog.txt", ofstream::app); // move the output pointer to the end of the file 
    of << "Experience is the mother of wisdom" << endl;
  } 

  {
    ofstream of("Mylog.txt", ofstream::in | ofstream::out); 
    of.seekp(10, ios::beg); //move the output pointer 10 chars after begin
    of << "12345" << endl;  // overwrite 5 chars
    of.seekp(-5, ios::end);
    of << "nothing gained" << endl;
    of.seekp(-5, ios::cur);
  } 

  ifstream inf("Mylog.txt");
  int i;
  inf >> i; // read one word
}

ostream& endl (ostream& sm) {
  sm.put('\n');
  sm.flush();
  return sm;
}

ostream& ostream::operator<<(ostream& (*func)(ostream&)) {
  return (*func)(*this);
}

cout << ends; // '\0'
cout << flush; 

strcut Dog {
  int age_;
  string name_;
};

istream& operator>>(istream& sm, Dog&d) {
  sm >> d.age_;
  sm >> d.name_;
  return sm;
}

ostream& operator<<(ostream& sm, const Dog& d) {
  sm << "My name is " << d.name_ << " and my age is " << d.age_ << endl;
  return sm;
}

int main() {
  Dog d{2, "Bob"};
  cout << d;

  cin >> d;
  cout << d;
}

#include <iostream>
#include <cxxabi.h>

struct NullType {};

/*
 * TypeList
 * */
template <typename...> struct TypeList;

template <typename Head, typename... Tail>
struct TypeList<Head, Tail...> {
    typedef Head head;
    typedef TypeList<Tail...> tails;
};

template <>
struct TypeList<> {
    typedef NullType head;
};

/*
 * length
 * */
template <typename> struct Length;

template <typename Head, typename... Tail>
struct Length<TypeList<Head, Tail...>> {
    enum { value = Length<TypeList<Tail...>>::value + 1 };
};

template <>
struct Length<TypeList<>> {
    enum { value = 0 };
};

/*
 * IndexOf
 * */
template <typename, typename> struct IndexOf;

template <typename Head, typename... Tail, typename T>
struct IndexOf<TypeList<Head, Tail...>, T> {
    using Result = IndexOf<TypeList<Tail...>, T>;
    enum { value = Result::value == -1 ? -1 : Result::value + 1 };
};

template <typename... Tail, typename T>
struct IndexOf<TypeList<T, Tail...>, T> {
    enum { value = 0 };
};

template <typename T>
struct IndexOf<TypeList<>, T> {
    enum { value = -1 };
};

/*
 * TypeAt
 * */
template <typename, size_t> struct TypeAt;

template <typename Head, typename... Tail, size_t i>
struct TypeAt<TypeList<Head, Tail...>, i> {
    static_assert(i < sizeof...(Tail), "i beyond the scope");
    typedef typename TypeAt<TypeList<Tail...>, i - 1>::type type;
};

template <typename Head, typename... Tail>
struct TypeAt<TypeList<Head, Tail...>, 0> {
    typedef Head type;
};

/*
 * Append
 * */
template <typename, typename> struct Append;

template <typename... TL, typename T>
struct Append<TypeList<TL...>, T> {
    typedef TypeList<TL..., T> Result;
};

template <typename... TL1, typename... TL2>
struct Append<TypeList<TL1...>, TypeList<TL2...>> {
    typedef TypeList<TL1..., TL2...> Result;
};

/*
 * Erase
 * */
template <typename> struct Erase;

template <typename Head, typename... Tail>
struct Erase<TypeList<Head, Tail...>> {
    typedef TypeList<Tail...> Result;
};

template <>
struct Erase<TypeList<>> {
    typedef NullType Result;
};


int main() {
    using namespace std;

    using TL1 = TypeList<int, char, double>;

    cout << Length<TL1>::value << endl;

    cout << IndexOf<TL1, char>::value << endl;

    cout << abi::__cxa_demangle(typeid(TypeAt<TL1, 0>::type).name(), nullptr, nullptr, nullptr) << endl;

    using AppendType1 = Append<TL1, int>::Result;
    cout << Length<AppendType1>::value << endl;
    using TL2 = TypeList<string, int>;
    using AppendType2 = Append<TL1, TL2>::Result;
    cout << Length<AppendType2>::value << endl;

    using EraseType = Erase<TL1>::Result;
    cout << abi::__cxa_demangle(typeid(EraseType).name(), nullptr, nullptr, nullptr) << endl;
}

vector<int> v = {3, 4, 1, 9}; // Calling initializer_list constructor

// auto type
for (auto it = vec.begin(); it != vec.end(); ++it) {
  cout << (*it) << endl;
}
auto a = 6; // integer
auto b = 9.6; // double

// foreach
for (int i : v) {  // works on any class that has begin() and end()
  cout << i ;    // readonly access
}
for (auto& i : v) {
  i++;  // changes the values in v
}

// nullptr
void foo(int i) {cout << "foo_int" << endl;}
void foo(char* pc) {cout << "foo_char*" << endl;}
int main() {
  foo(NULL);  // 歧义
  foo(nullptr); // call foo(char*)
}

// enum class
// c++ 03
enum apple {green_a, red_a};
// c++ 11
enum class apple {green, red};
apple a = apple::green;

// static_assert
// run-time assert
assert(myPointer != NULL);
// compile time assert ( C++ 11 )
static_assert(sizeof(int) == 4);

// Delegating Constrctor
// C++ 03
class dog {
  init() {...};
public:
  dog() {init();}
  dog(int a) {init(); doOtherThings();}
};
// C++ 11
class dog {
public: 
  dog() {...}
  dog(int a) : dog() {...} // dog() has to be called first
};

// virtual override [compile check]

// final (for virtual function and for class)

// Compiler Generated Default Constructor, eg: dog(){}

// delete
dog& operator=(const dog&) = delete

char* a = u8"string"; // define an UTF-8 string 

// lanbda function
cout << [](int x, int y) {return x + y} (3, 4) << endl; // 7

void printInt(int& i) {cout << "lvalue reference: " << i << endl;}
void printInt(int&& i) {cout << "rvalue reference: " << i << endl;}
int main() {
  int a = 5; // lvalue
  int& b = a; // lvalue reference
  int&& c;  // rvalue reference

  printInt(a); // Call printInt(int& i)
  printInt(6); // Call printInt(int&& i)
}

void foo(X x);
void foo_by_ref(X& x);
void main() {
  X x;
  foo_by_ref(x); // Call no constructor
  foo(x); // Call copy constructor
}

#include <iostream>
#include <vector>
#include <queue>
#include <list>

using namespace std;
struct tree_node {
    struct tree_node* left;
    struct tree_node* right;
    int data;
    tree_node(int d){
        data = d;
        left = NULL;
        right = NULL;
    }
};

tree_node* build_binary_tree(const vector<int>& nums) {
    if (nums.empty()) return NULL;

    tree_node* root = new tree_node(nums[0]);
    queue<tree_node*> q;
    q.push(root);
    int idx = 1;
    while(!q.empty()) {
        tree_node* cur = q.front();
        q.pop();

        if (idx < nums.size()) {
            tree_node* node = new tree_node(nums[idx++]);
            cur->left = node;
            q.push(node);
        } else break;

        if (idx < nums.size()) {
            tree_node* node = new tree_node(nums[idx++]);
            cur->right = node;
            q.push(node);
        } else break;
    }
    return root;
}

void binary_tree_travel(struct tree_node* node) {
    if (node == NULL) return;
    if (node->left) binary_tree_travel(node->left);
    cout << node->data << " ";
    if (node->right) binary_tree_travel(node->right);
}

void zigzag_travel(tree_node* root) {
    if (root == NULL) return;

    bool reverse = true ;
    list<struct tree_node*> last;
    list<struct tree_node*> cur;
    cur.push_back(root);

    while(!cur.empty()) {
        int size = cur.size();
        vector<int> level_node(size);
        for (int i = 0; i < size; i++) {
            tree_node* node = cur.front();
            cur.pop_front();

            if (node->left) last.push_back(node->left);
            if (node->right) last.push_back(node->right);

            int idx = reverse ? size - 1 - i : i;
            level_node[idx] = node->data;
        }

        swap(cur, last);
        reverse = !reverse;

        for (int d : level_node) {
            cout << d << " ";
        }
    }
}

int main()
{
    vector<int> nums{1,2,3,4,5,6,7,8,9,10};
    struct tree_node* root = build_binary_tree(nums);
    binary_tree_travel(root);
    cout << "\n";

    zigzag_travel(root);
    cout << "\n";
    cout << "Hello World" << endl;
    return 0;
}

/*
8 4 9 2 10 5 1 6 3 7
1 2 3 7 6 5 4 8 9 10
Hello World
 */

#include <iostream>
#include <vector>
#include <deque>
#include <typeinfo>
#include <cxxabi.h>

template <typename T,
        template<typename ELEM, typename ALLOC = std::allocator<ELEM>>
        class CONT = std::deque >
class NestTemplate{
public:
    NestTemplate() {
        std::cout << abi::__cxa_demangle(typeid(CONT<T>).name(), nullptr, nullptr, nullptr) << std::endl;
    }
    template <typename N>
    void nest_func(N n) {
        std::cout << n << std::endl;
    }
private:
    CONT<T> elem_;
};

int main() {
    NestTemplate<int> t;
//    t.nest_func(5);

    std::cout << abi::__cxa_demangle(typeid(int).name(), nullptr, nullptr, nullptr) << std::endl;

    return 0;
}

template <typename T>
void avoid_decay_func(T& args) { //这里必须是引用传递
    std::cout << typeid(T&).name() << std::endl;
    std::cout << abi::__cxa_demangle(typeid(T&).name(), nullptr, nullptr, nullptr) << std::endl;
    std::cout << sizeof(args) << std::endl;
}
int main() {
    char type_array[10]{'0'};
    avoid_decay_func(type_array);
}
/*
A10_c
char [10]
10
*/

template <typename T>
auto contains_of(typename T::X const*) -> char {
    return static_cast<char>(0);
}
template <typename T>
auto contains_of(...) -> char*{
    return static_cast<char*>(0);
}

#define type_has_member_type_X(T) \
    (sizeof(contains_of<T>(0)) == 1)

struct Test{
    typedef decltype(nullptr) X;
};

int main() {
    std::cout << type_has_member_type_X(Test) << std::endl; //1
    return 0;
}

// reference cannot be reassigned
string& m_name = "Hello";

// A compile time constraint that an object can not be modified 
const int i = 9;
i = 6  //assignment of read-only variable 'i'

const int *p1 = &i;  //data is const, pointer is not 
int* const p2 = &i;  //pointer is const, data is not
const int* const p3; //data and pointer are both const

// If const is on the left of *, data is const
// if const is on the right of *, pointer is const
int const *p4 = &i;
const int *p5 = &i;

// cast is not a good thing
const_cast<int&>(i) = 6;

int j;
static_cast<const int&>(j);

class Dog {
    int age;
    string name;

public:
    Dog() {
        age = 3;
        name = "dummy";
    }

    // const parameters
    void setAge(const int& a) { age = a; }

    // const return value
    const string& getName() {return name;}

    // const function
    // this function will not change any of the member valuables of this class
    // a const function can only call another const function
    void printDogName() const { cout << name << endl; }
    //can be overload
    void printDogName() const { cout << name << endl; }
};

int main() {
  Dog d;

  int i = 9;
  d.setAge(i);

  const string& n = d.getName();
  
  const Dog d2;
  d.printDogName();
  d2.printDogName();
}

class BigArray {
  vector<int> v; // huge vector
  int accessCounter;

  int* v2;  //another int array

public:
  int getItem(int index) const {
    //accessCounter++;
    const_cast<BigArray*>(this)->accessCounter++;
    return v[index];
  }

  // const can be remove
  void setV2Item(int index, int x) const {
    *(v2 + index) = x;
  }
};

class dog {};

/* equivalent to  */
class dog {
  public: 
    dog(const dog& rhs) {...}; // Member by member initialization
    dog& operator=(const dog& rhs) {...}; // Member by member copying
    dog() {...};  //1. Call base class's default constructor;
                     //2. Call data member's default constructor;
    ~dog() {...}; //1. Call base class's destructor;
                       //2. Call data member's destructor;
};

class OpenFile{
public:
  OpenFile(string filename) { cout << "Open a file " << filename << endl;}
  OpenFile(OpenFile& rhs) = delete;
  //or
/*
private:
  OpenFile(OpenFile& rhs);  // no function body
**/
};

int main() {
  OpenFile f(string("Bo_file"));
  
  // wrong
  OpenFile f2(f);
}

class OpenFile{
public:
  OpenFile(string filename) { cout << "Open a file " << filename << endl;}
  void destroyMe() { delete this; }

private:
  ~OpenFile() {cout << "OpenFile destructed."  << endl;}
};

int main() {
  // a class like OpenFile which has a private destructor can only be stored on heap,
  // it can not be stored on stack
  OpenFile* f = new OpenFile(string("Bo_file"));
  f->destroyMe();
}

/* Use virtual destructors in polymorphic(多态) base classes */
// base class
class Dog {
public: 
  // this class will be used polymorphically which means most likely it will need a virtual destructor
  virtual void bark() {}
  virtual ~Dog() { cout << "Dog destroyed." << endl; }
};

class Yellowdog : public Dog {
public: 
  ~Yellowdog() { cout << "Yellow dog destroyed." << endl; }
};

class DogFactory {
public:
  static Dog* createYellowDog() { return (new Yellowdog()); }
  // ... create other dogs
};

int main() {
  Dog* pd = DogFactory::createYellowDog();
  //... Do something with pd

  delete pd;
  return 0;
}

class Dog {
public: 
  ~Dog() { cout << "Dog destroyed." << endl; }
};

class Yellowdog : public Dog {
public: 
  ~Yellowdog() { cout << "Yellow dog destroyed." << endl; }
};

class DogFactory {
public:
  static shared_ptr<Dog> createYellowDog() { 
    return shared_ptr<Yellowdog>(new Yellowdog()); 
  }
  // ... create other dogs
};

int main() {
  shared_ptr<Dog> pd = DogFactory::createYellowDog();
  //... Do something with pd

  return 0;
}

class dog {
public: 
  string m_name;
  dog(string name) { m_name = name; cout << name << " is born." << endl;}
  ~dog() { cout << m_name << " is destroyed." << endl;}
  void bark() {...}
};

int main() {
  try {
    dog dog1("Henry");
    dog dog2("Bob");
    throw 20;
    dog1.brak();
    dog2.bark();
  } catch (int e) {
    cout << e << " is caught." << endl;
  }
}

// c++ doesn't like having work more than one exception pending at the same time
// so it will just crash
~dog() {
  try {
    // Enclose all the exception prone code here
  } catch (MYEXCEPTION e) {
    // Catch exception
  } catch (...) {
  }
}

// or 
class dog {
public: 
  string m_name;
  dog(string name) { m_name = name; cout << name << " is born." << endl;}
  ~dog() { cout << m_name << " is destroyed." << endl;}
  void prepareToDestr() {...; throw 20;}
  void bark() {...}
};
int main() {
  try {
    dog dog1("Henry");
    dog dog2("Bob");
    dog1.brak();
    dog2.bark();

    dog1.prepareToDestr();  // goto catch
    dog2.prepareToDestr();
  } catch (int e) {
    cout << e << " is caught." << endl;
  }
}

class Dog {
public: 
  Dog() { cout << "Dog born." << endl; }
  virtual void bark() { cout << "I am just a dog" }
  void seeCat() { bark(); }
};

class Yellowdog : public Dog {
public: 
  Yellowdog() { cout << "Yellow dog born." << endl; }
  virtual void bark() { cout << "I am a yellow dog" << endl; }
};

int main() {
  Yellowdog d;
  d.seeCat();

  return 0;
}

dog dd;
dd = dd; // Looks silly

dogs[i] = dogs[j]; // self assignment

class collar;
class dog {
  collar* pCollar;
  dog& operator=(const dog& rhs) {
    if (this == &rhs) {
      return *this;
    }

    collar* pOrigCollar = pCollar;
    pCollar = new collar(*rhs.pCollar);
    delete pOrigCollar;
    return *this;
  }
};

//or
class dog {
  collar* pCollar;
  dog& operator=(const dog& rhs) {
    *pCollar = *rhs.pCollar;  // member by member copying of collars or
                                          // call collar's operator=
    return *this;
  }
};

// not good 
Mutex_t mu = MUTEX_INITIALIXZER;

void functionA()
{
  Mutex_lock( &mu );
  //...
  Mutex_unlock( &mu ); // will this line always be executed?
}

class Lock {
  private:
    Mutex_t* m_pm;
  public: 
    explicit Lock(Mutex_t* pm) { Mutex_lock(pm); m_p = pm; }
    ~Lock() {Mutex_unlock(m_pm);}
};

void functionA()
{
  Lock mylock(&mu);
  // ...
  // The mutex will always be released when mylock is destroyed from stack.
}

int functionA() {
  // The default value for D is "delete"
  shared_ptr<dog> pd(new dog());
  //...
  // The dog is destructed when pd goes out of scope
}

class Lock {
private:
  shared_ptr<Mutex_t> pMutex;
public:
  explicit Lock(Mutex_t *pm) : pMutex(pm, Mutex_unlock) {
    Mutex_lock(pm);
  // The second parameter of shared_ptr constructor is "delete" function.
  }
};

Lock L1(&mu);
Lock L2(L1);

// Data container
struct Person_t {
  string name;  // public
  unsigned age;
};

// Complex Data Structure
class Person {
  string name_;  //private
  unsigned age_;
};

class Person {
public:
    Person(string name) { pName_ = new string(name); }
    ~Person() { delete(pName_); }
    void printName() { cout << *pName_ << endl;}

    // 构造拷贝
    Person(const Person& rhs) {
        // make a deep copy
        pName_ = new string(*(rhs.pName()));
    }
    // 赋值拷贝
    Person& operator=(const Person& rhs) {
        *pName_ = *rhs.pName();
        return *this;
    }

    string* pName() const { return pName_; }

private:
    string* pName_;
};
TEST(leetcode, advanced_test_resource_manage_class) {
    vector<Person> persons;
    persons.push_back(Person("Bob"));
    // 1. "Bob" is constructed
    // 2. A copy of "Bob" is saved in the vector persons (shallow copy)
    // 3. the copy of "Bob" is destroyed
    persons.back().printName();

    Person b = Person("nick");
    b.printName();

    cout << "Bye" << endl;
}

class Person {
public:
    Person(string name) { pName_ = new string(name); }
    ~Person() { delete(pName_); }
    void printName() { cout << *pName_ << endl;}

    string* pName() const { return pName_; }
    Person* clone() {
        return (new Person(*pName_));
    }

private:
    string* pName_;
    Person(const Person& rhs);
    Person& operator=(const Person& rhs);
};
TEST(leetcode, advanced_test_resource_manage_class) {
    vector<Person*> persons;
    persons.push_back(new Person("Bob"));

    persons.back()->printName();


    cout << "Bye" << endl;
}

class Dog {
public:
  virtual Dog* clone() { return (new Dog(*this)); }
};

class YellowDog ： public Dog {
  virtual YellowDog* clone() { return (new YellowDog(*this)); }
};

void foo(Dog* d) {  //d is a Yellowdog
  // Dog* c = new Dog(*d); // c is a Dog
  Dog* c = d->clone();  //c is a YellowDog
}

int main() {
  YellowDog d;
  foo(&d);
}

// implicit
char c = 'A';
int i = c;  // Integral promotion

char* pc = 0; // int -> Null pointer

void f(int i);
f(c);

dog* pd = new YellowDog(); // pointer type conversion

operator string() const { return name_; }

/* static_cast */
int i = 9;
// convert object from one type to another
float f = static_cast<float>(i);

// Type conversion needs to be defined
dog d1 = static_cast<dog>(string("Bob"));

// convert pointer/reference from one type to a related type (down/up) cast
dog* pd = static_cast<dog*>(new yellowdog());

/* dynamic_cast */
// 1. It convert pointer/reference from one type to a related type (down cast)
// 2. run-time type check. If succeed, py == pd; if fail, py == 0;
// 3. It requires the 2 types to be polymorphic (have virtual function)

/* all yellowdogs are dogs, but not all dogs are yellowdog */
dog* pd = new yellowdog();
yellowdog* py = dynamic_cast<yellowdog*>(pd);

/* const_cast */
// Only works on pointer/reference
// Only works on same type, cast away constness of the object being pointed to

const char* str = "Hello, world.";
char* modifiable = const_cast<char*>(str);

/* reinterpret_cast */
// The ultimate cast that can cast one pointer to any other type of pointer

long p = 51110980;
dog* pd = reinterpret_cast<dog*>(p);

/* C-Style Casting */
short a = 200;
int j = (int)a;
int j = int(a);

/* They specifies different access control from the derived class to the base class */

class B {};

class D_pub : public B {};  // ''is-a'' relation
class D_priv : private B {};  // has-a
class D_prot : protected B {};

/*
 Access Control:
 1. None of the derived classes can access anything that is private in B.
 2. D_pub inherits public members of B as public and the protected members of B as protected.
 3. D_priv inherits public and protected members of B as private.
 4. D_prot inherits public and protected members of B as protected.

 Casting:
 1. Anyone can cast a D_pub* to B*. D_pub is a special kind of B.
 2. D_priv's members and friends can cast a D_priv* to B*.
 3. D_prot's members, fiends, and childrens can cast a D_prot* to B*.
 */

public:
  using dog::bark;

/*
 1. Precise definition of classes.
 2. Don't override non-virtual functions.
 3. Don't override default parameter values for virtual functions.
 4. Force inheritance of shadowed functions.
 */

/*
 Simplified Definition:
 lvalue - An object that occupies some identifiable location in memory
 "内存中,有特定位置(地址)的东西"或"指向一个确定对象的东西"
 
 rvalue - Any object that is not a lvalue
 */

struct TreeNode { TreeNode *left, *right; };
class Generic_Parser {
public: 
  void parse_preorder (TreeNode* node) {
    if (node) {
      process_node(node);
      parse_preorder(node->left);
      parse_preorder(node->right);
    }
  }

private:
  virtual void process_node(TreeNode* node){}
};

class EmployeeChart_Parser : public Generic_Parsesr {
private:
  void process_node(TreeNode* node) {
    cout << "Customized process_node() for EmployeeChart." << endl;
  }
};

int main() {
  ...
  EmployeeChart_Parser ep;
  ep.parse_preorder(root);
}

template<typename T> class Generic_Parser {
public: 
  void parse_preorder(TreeNode* node) {...}
  void process_node(TreeNode* node) {
    static_cast<T*>(this)->process_node(node);
  }
};

class EmployeeChart_Parser : public Generic_Parser<EmployeeChart_Parser> {
public:
  void process_node(TreeNode* node) {
    cout << "Customized process_node() for EmployeeChart." << endl;
  }
};

int main() {
  ...
  EmployeeChart_Parser ep;
  ep.parse_preorder(root);
  ...
  // 以空间换时间
  MilitaryChart_Parser mp;
}

template<typename T>
T Max(vector<T> v) {
  T max = v[0];
  for (typename std::vector<T>::iterator it = v.begin(); it != v.end(); ++it) {
    if (*it > max) {
      max = *it;
    }
  }
  return max;
}

// 菱形继承
class File {                 //                 File
public:                        //               /        \
  string name;             //  InputFile        OutputFile
  void open();              //               \        /
};                                 //               IOFile

class InputFile : public File {
public: 
  void read();
};

class OutputFile : public File {
public: 
  void write();
};

class IOFile : public InputFile, public OutputFile {};

int main() {
  IOFile f;
  f.InputFile::name = "file1";
  f.OutputFile::name = "file2";
}

class File {               
public:                      
  string name;          
  void open();             
};                                 
// only needs one instance of File
class InputFile : virtual public File {
public: 
  void read();
};

class OutputFile : virtual public File {
public: 
  void write();
};

class IOFile : public InputFile, public OutputFile {};

int main() {
  IOFile f;
  f.open();
}

class File {               
public:                      
  string name;          
  File(string fname);          
};                                 

class InputFile : virtual public File {
public: 
  InputFile(string fname) : File(fname) {}
};

class OutputFile : virtual public File {
public: 
  OutputFile(string fname) : File(fname) {}
};

class IOFile : public InputFile, public OutputFile {
  IOFile(string fname) : InputFile(fname), OutputFile(fname), File(fname) {}
};

int main() {
  IOFile f;
}

/*
 Abstract class : A class has one or more pure virtual functions
 Pure abstract class : A class containing only pure virtual functions
   - no data
   - no concrete functions 
 */
class OutputFIle {
public:
  void write() = 0;
  void open() = 0;
};

/*
 * C++ Keyword: using
 * 1. using directive : to bring all namespace members into current scope 
 */
using namespace std;

/*
 * 2. using declaration
 *   a. Bring one specific namespace member to current scope
 *   b. Bring a member from base class to current class's scope
 */
using std::cout;
cout << "Hello world.\n";

class B {
public: 
  void f(int a);
};
class D : private B {
public: 
  using B::f;  // only using in class scope
};
int main() {
  D d;
  d.f(8);
}

/*
 * Anonymous Namespace
 */
// accessed with the same file
namespace {
  void h() {std::cout << "h()\n";}
}
// static viod h() {std::cout << "h()\n";}
int main() {
  h();
}

// 使用多组括号
std::thread my_thread((background_task()));

// 或使用新统一的初始化语法
std::thread my_thread{background_task()};

// 使用lambda表达式，允许使用一个可以捕获局部变量的局部函数
std::thread my_thread([]{
  do_something();
});

struct func {
    int& i_;
    func(int& i) : i_(i){}
    void operator()() {
        using namespace std;
        for (unsigned int i = 0; i < 65535; ++i) {
            cout << i_ << endl;     // 潜在访问隐患：悬空引用
        }
    }
};

// oops崩溃
void oops() {
    int local_state = 0;
    func my_func(local_state);

    std::thread t1(my_func);
    t1.detach();
    /* 不等待线程结束，新线程可能还在运行
      * */
}

struct func {
    int& i_;
    func(int& i) : i_(i){}
    void operator()() {
        do_something(i_);
    }
};

void do() {
    int local_state = 0;
    func my_func(local_state);

    std::thread t1(my_func);
    try {
      do_something_in_current_thread();
    } catch(...) {
      t1.join(); // 异常流
      throw;
    }

    t1.join(); // 正常流
}

struct func;
class thread_guard{
    std::thread& t_;
public:
    explicit thread_guard(std::thread& t) : t_(t) {}
    ~thread_guard() {
        if (t_.joinable())
            t_.join();
    }

    thread_guard(const thread_guard&) = delete;
    thread_guard& operator=(const thread_guard&) = delete;
};

void do() {
    int local_state = 0;
    func my_func(local_state);

    std::thread t1(my_func);
    thread_guard tg(t1);

    do_something_in_current_thread();
}

void f(int i, std::string const& s);  
void oops(int some_param) {
  char buffer[1024];
  sprintf(buffer, "%i", some_param);
  std::thread t(f, 3, buffer);
  t.detach();
}

void add(int a, int b, int& r) {
    r = a + b;
}
int main() {
    int ret = 0;
    // 函数柯里化，_1相当于占位符
    auto f = std::bind(add, std::placeholders::_1, 20, std::ref(ret));
    f(10);
    std::cout << ret << std::endl; // 30
    return 0;
}

class X{
  public:
    void do_lengthy_work();
};
X my_x;
std::thread t(&X::do_lengthy_work(), &my_x);

void process_big_object(std::unique_ptr<big_object>);

std::unique_ptr<big_object> p(new big_object);
p->prepare_data(42);
std::thread t(process_big_object, std::move(p));

void some_function();
void some_other_function();

std::thread t1(some_function);
std::thread t2 = std::move(t1);

t1 = std::thread(some_other_function); // 右值，即将消亡  临时对象

std::thread t3;
t3 = std::move(t2);

t1 = std::move(t3); //赋值操作将使程序崩溃

void f(std::thread t);
void g() {
    void some_function();
    f(std::thread(some_function));

    std::thread t(some_function);
    f(std::move(t));
}

class scoped_thread{
    std::thread t_;
    public:
        explicit scoped_thread(std::thread t) : t_(std::move(t)) {
            if(!t_.joinable) 
                throw std::logic_error("No thread");
        }

        ~scoped_thread() {
            t_.join();
        }

        scoped_thread(scoped_thread const&) = delete;
        scoped_thread& operator=(scoped_thread const&) = delete;
};

struct func;
void f() {
    int some_local_state;
    // 新线程直接传递到scoped_thread中，而非创建一个独立的命名变量
    scoped_thread t(std::thread(func(some_local_state))); 
    do_something_in_current_thread();
}

void do_work(unsigned id);
void f() {
    std::vector<std::thread> threads;
    for (unsigned i = 0; i < 20; i++) {
        threads.push_back(std::thread(do_work, i));
    }

// 对每个线程调用join
    std::for_each(threads.begin(), threads.end(), 
        std::mem_fn(&std::thread::join));
}

template<typename Iterator, typename T> 
struct accumulate_block {
    void operator()(Iterator first, Iterator last, T& result) {
        result = std::accumulate(first, last, result);
    }
}

template<typename Iterator, typename T> 
T parallel_accumulate(Iterator first, Iterator last, T init) {
    unsigned long const length = std::distance(first, last);

    if (!length) return init;

    unsigned long const min_per_thread = 25;
    unsigned long const max_threads = (length + min_per_thread - 1) /
        min_per_thread;  // [1]

    unsigned long const hardware_threads = std::thread::hardware_concurrency();

    unsigned long const num_threads = std::min(hardware_threads != 0 ?
        hardware_threads : 2, 
        max_threads);  // [2]

    unsigned long const block_size = length/num_threads;

    std::vector<T> results(num_threads);
    std::vector<std::thread> threads(num_threads - 1); // [3]

    Iterator block_start = first;
    for (unsigned long i = 0; i < (num_threads - 1); ++i) {
        Iterator block_end = block_start;
        std::advance(block_end, block_size);
        threads[i] = std::thread(accumulate_block<Iterator, T>(),
            block_start, block_end, std::ref(results[i]));
        block_start = block_end;
    }

    accumulate_block<Iterator, T>()(
        block_start, last, results[num_threads - 1]
    );  // [4]

    std::for_each(threads.begin(), threads.end(), 
        std::mem_fn(&std::thread::join));

    return std::accumulate(results.begin(), results.end(), init);
}