C++11 std::condition_variable - notify_one() not behaving as expected?

Question

I don't see this program having any practical usage, but while experimenting with c++ 11 concurrency and conditional_variables I stumbled across something I don't fully understand.

At first I assumed that using notify_one() would allow the program below to work. However, in actuality the program just froze after printing one. When I switched over to using notify_all() the program did what I wanted it to do (print all natural numbers in order). I am sure this question has been asked in various forms already. But my specific question is where in the doc did I read wrong.

I assume notify_one() should work because of the following statement.

If any threads are waiting on *this, calling notify_one unblocks one of the waiting threads.

Looking below only one of the threads will be blocked at a given time, correct?

class natural_number_printer
{
public:
  void run()
  {
    m_odd_thread = std::thread(
      std::bind(&natural_number_printer::print_odd_natural_numbers, this));
    m_even_thread = std::thread(
      std::bind(&natural_number_printer::print_even_natural_numbers, this));

    m_odd_thread.join();
    m_even_thread.join();
  }

private:
  std::mutex m_mutex;
  std::condition_variable m_condition;

  std::thread m_even_thread;
  std::thread m_odd_thread;

private:
  void print_odd_natural_numbers()
  {
    for (unsigned int i = 1; i < 100; ++i) {
      if (i % 2 == 1) {
        std::cout << i << " ";
        m_condition.notify_all();
      } else {
        std::unique_lock<std::mutex> lock(m_mutex);
        m_condition.wait(lock);
      }
    }
  }

  void print_even_natural_numbers()
  {
    for (unsigned int i = 1; i < 100; ++i) {
      if (i % 2 == 0) {
        std::cout << i << " ";
        m_condition.notify_all();
      } else {
        std::unique_lock<std::mutex> lock(m_mutex);
        m_condition.wait(lock);
      }
    }
  }
};

Answer 1

The provided code "works" correctly and gets stuck by design. The cause is described in the documentation

The effects of notify_one()/notify_all() and wait()/wait_for()/wait_until() take place in a single total order, so it's impossible for notify_one() to, for example, be delayed and unblock a thread that started waiting just after the call to notify_one() was made.

The step-by-step logic is

1. The print_odd_natural_numbers thread is started
2. The print_even_natural_numbers thread is started also.
3. The m_condition.notify_all(); line of print_even_natural_numbers is executed before than the print_odd_natural_numbers thread reaches the m_condition.wait(lock); line.
4. The m_condition.wait(lock); line of print_odd_natural_numbers is executed and the thread gets stuck.
5. The m_condition.wait(lock); line of print_even_natural_numbers is executed and the thread gets stuck also.