LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 粗粒度锁，同时只能有一个哲学家进餐，进餐结束并放下叉子才解锁

class DiningPhilosophers {
 public:
  DiningPhilosophers() {}

  void wantsToEat(int philosopher, function<void()> pickLeftFork,
                  function<void()> pickRightFork, function<void()> eat,
                  function<void()> putLeftFork, function<void()> putRightFork) {
    m.lock();
    pickLeftFork();
    pickRightFork();
    eat();
    putLeftFork();
    putRightFork();
    m.unlock();
  }

 private:
  mutex m;
};

• 如果希望能同时有多个哲学家可以进餐，只需要对左右两侧叉子同时上锁即可，但多个锁有顺序先后，因此按顺序加锁前需要一把全局锁

class DiningPhilosophers {
 public:
  DiningPhilosophers() {}

  void wantsToEat(int philosopher, function<void()> pickLeftFork,
                  function<void()> pickRightFork, function<void()> eat,
                  function<void()> putLeftFork, function<void()> putRightFork) {
    int l = philosopher;            // 左侧叉子编号
    int r = (philosopher + 1) % 5;  // 右侧叉子编号
    mt.lock();  // 保证一个哲学家能同时拿到两个叉子
    lock_guard<mutex> lk1{m[l]};
    lock_guard<mutex> lk2{m[r]};
    pickLeftFork();
    pickRightFork();
    mt.unlock();  // 已同时拿到两个叉子，解锁全局锁
    eat();
    putLeftFork();
    putRightFork();
  }  // 进餐结束解锁叉子

 private:
  mutex mt;    // 全局锁
  mutex m[5];  // 每个叉子一把锁
};

• 用 std::lock 同时上锁

class DiningPhilosophers {
 public:
  DiningPhilosophers() {}

  void wantsToEat(int philosopher, function<void()> pickLeftFork,
                  function<void()> pickRightFork, function<void()> eat,
                  function<void()> putLeftFork, function<void()> putRightFork) {
    int l = philosopher;
    int r = (philosopher + 1) % 5;
    lock(m[l], m[r]);
    lock_guard<mutex> lk1{m[l], adopt_lock};
    lock_guard<mutex> lk2{m[r], adopt_lock};
    pickLeftFork();
    pickRightFork();
    eat();
    putLeftFork();
    putRightFork();
  }

 private:
  mutex m[5];
};

• C++17 直接用 std::scoped_lock 即可同时上锁

class DiningPhilosophers {
 public:
  DiningPhilosophers() {}

  void wantsToEat(int philosopher, function<void()> pickLeftFork,
                  function<void()> pickRightFork, function<void()> eat,
                  function<void()> putLeftFork, function<void()> putRightFork) {
    scoped_lock lk{m[philosopher], m[(philosopher + 1) % 5]};
    pickLeftFork();
    pickRightFork();
    eat();
    putLeftFork();
    putRightFork();
  }

 private:
  mutex m[5];
};