Print in Order 解题报告（C++）

我们提供了一个类：

public class Foo 
{
  public void one() { print("one"); }
  public void two() { print("two"); }
  public void three() { print("three"); }
}

三个不同的线程将会共用一个 Foo 实例。

线程 A 将会调用 one() 方法
线程 B 将会调用 two() 方法
线程 C 将会调用 three() 方法
请设计修改程序，以确保 two() 方法在 one() 方法之后被执行，three() 方法在 two() 方法之后被执行。

示例 1:

输入: [1,2,3]
输出: "onetwothree"
解释: 
有三个线程会被异步启动。
输入 [1,2,3] 表示线程 A 将会调用 one() 方法，线程 B 将会调用 two() 方法，线程 C 将会调用 three() 方法。
正确的输出是 "onetwothree"。
示例 2:

输入: [1,3,2]
输出: "onetwothree"
解释: 
输入 [1,3,2] 表示线程 A 将会调用 one() 方法，线程 B 将会调用 three() 方法，线程 C 将会调用 two() 方法。
正确的输出是 "onetwothree"。

注意:

尽管输入中的数字似乎暗示了顺序，但是我们并不保证线程在操作系统中的调度顺序。

你看到的输入格式主要是为了确保测试的全面性。

class Foo {
public:
    Foo() {
        
    }

    void first(function<void()> printFirst) {
        // 等待直至 main() 发送数据
	    std::unique_lock<std::mutex> lk(g_mutex);  
        // printFirst() outputs "first". Do not change or remove this line.
        printFirst();
        // 通知前完成手动解锁，以避免等待线程才被唤醒就阻塞（细节见 notify_one ）
        counter++;
        cv1.notify_one();
    }

    void second(function<void()> printSecond) {
	    std::unique_lock<std::mutex> lk(g_mutex);
        cv1.wait(lk, [this](){return counter == 2;}); // 阻塞当前线程，直到条件变量被唤醒 
        // printSecond() outputs "second". Do not change or remove this line.
        printSecond();
        counter++;
        cv2.notify_one();
    }

    void third(function<void()> printThird) {
        
	    std::unique_lock<std::mutex> lk(g_mutex);
        cv2.wait(lk, [this](){return counter == 3;});
        // printThird() outputs "third". Do not change or remove this line.
        printThird();
    }
    
private:
    int counter = 1;
    std::condition_variable cv1;
    std::condition_variable cv2;
    // 使用lock和unlock手动加锁
    std::mutex g_mutex;
};

题目大意
现在三个线程，每个线程分别调用三个函数中的一个。无论线程的产生和调用关系怎么样，最终输出的结果要求都是"firstsecondthird"。如何设计是三个函数。

解题方法
mutex锁
这个是Leetcode的新题型，也就是说并发类型，我觉得很实用，工作中能用到。

一般情况下，最简单的协调不同线程之间的调度关系，都可以使用mutex来做，本质是信号量。

std::mutex 的成员函数有四个：

构造函数，std::mutex不允许拷贝构造，也不允许 move 拷贝，最初产生的 mutex 对象是处于 unlocked 状态的。
lock()，调用线程将锁住该互斥量。线程调用该函数会发生下面 3 种情况：
(1). 如果该互斥量当前没有被锁住，则调用线程将该互斥量锁住，直到调用 unlock之前，该线程一直拥有该锁。
(2). 如果当前互斥量被其他线程锁住，则当前的调用线程被阻塞住。
(3). 如果当前互斥量被当前调用线程锁住，则会产生死锁(deadlock)。
unlock()， 解锁，释放对互斥量的所有权。
try_lock()，尝试锁住互斥量，如果互斥量被其他线程占有，则当前线程也不会被阻塞。线程调用该函数也会出现下面 3 种情况，
(1). 如果当前互斥量没有被其他线程占有，则该线程锁住互斥量，直到该线程调用 unlock 释放互斥量。
(2). 如果当前互斥量被其他线程锁住，则当前调用线程返回 false，而并不会被阻塞掉。
(3). 如果当前互斥量被当前调用线程锁住，则会产生死锁(deadlock)。
也就是说一个锁能控制两个线程的执行顺序。这个题中我们需要保持三个函数是按顺序执行的，则需要两个锁m1和m2。

在开始的时候，两个锁都锁起来。first()可以直接执行，second()等待m1释放之后执行，third()等待m2释放之后执行。first()结束之后释放m1，second()结束之后释放m2.因此三个的顺序都协调一致了。

C++代码如下：

class Foo {
private:
    mutex m1, m2;
public:
    Foo() {
        m1.lock();
        m2.lock();
    }

    void first(function<void()> printFirst) {
        // printFirst() outputs "first". Do not change or remove this line.
        printFirst();
        m1.unlock();
    }

    void second(function<void()> printSecond) {
        m1.lock();
        // printSecond() outputs "second". Do not change or remove this line.
        printSecond();
        m1.unlock();
        m2.unlock();
    }

    
    void third(function<void()> printThird) {
        m2.lock();
        // printThird() outputs "third". Do not change or remove this line.
        printThird();
        m2.unlock();
    }
};

void printFirst() {
    cout << "first";
}

void printSecond() {
    cout << "second";
}

void printThird() {
    cout << "third";
}

C++之future和promise

future和promise的作用是在不同线程之间传递数据。使用指针也可以完成数据的传递，但是指针非常危险，因为互斥量不能阻止指针的访问；而且指针的方式传递的数据是固定的，如果更改数据类型，那么还需要更改有关的接口，比较麻烦；promise支持泛型的操作，更加方便编程处理。

假设线程1需要线程2的数据，那么组合使用方式如下：

线程1初始化一个promise对象和一个future对象，promise传递给线程2，相当于线程2对线程1的一个承诺；future相当于一个接受一个承诺，用来获取未来线程2传递的值
线程2获取到promise后，需要对这个promise传递有关的数据，之后线程1的future就可以获取数据了。
如果线程1想要获取数据，而线程2未给出数据，则线程1阻塞，直到线程2的数据到达

这也是C++11中的新特性，可以把promise和future当做是在不同线程之间传递值的方式。在某个线程中对promise中生产一个数据，可以在另外一个线程中从future中获取这个数据。

promise和future是绑定在一起的，可以调用promise::get_future()获取与其绑定的future。
future.wait()方法对当前的线程进行阻塞，等待与其绑定的promise调用set_value()方法。
future.get()方法对当前的线程进行阻塞，等待与其绑定的promise调用set_value()方法的返回值。
因此实现线程的同步的方法会很方便。C++代码如下：

class Foo {
private:
    std::promise<void> p1;
    std::promise<void> p2;
public:
    Foo() {}

    void first(function<void()> printFirst) {
        // printFirst() outputs "first". Do not change or remove this line.
        printFirst();
        p1.set_value();
    }

    void second(function<void()> printSecond) {
        p1.get_future().wait();
        // printSecond() outputs "second". Do not change or remove this line.
        printSecond();
        p2.set_value();
    }

    
    void third(function<void()> printThird) {
        p2.get_future().wait();
        // printThird() outputs "third". Do not change or remove this line.
        printThird();
    }
};

void printFirst() {
    cout << "first";
}

void printSecond() {
    cout << "second";
}

void printThird() {
    cout << "third";
}