> Furthermore, the complexity is rather bad: if T is the average number
> of waiting threads, an C the number of conditions being waited on, the
> wait is O(C) (appending to C wait queues) and wakeup is O(CT) (C
> removal from a T-length deque).

Which just means that waiting on C conditions is C times more expensive than waiting on 1 currently is.  That seems reasonable enough to me, and anyway, I would expect C to be fairly small.

Note that the alternative is to use a single condition and use notify_all() instead of notify().  That is likely to be much more expensive because every waiting thread must wake up to see if it should continue.

But I am still not sure it is worth it.

BTW, I think it would be better to have wait_for_any() return a list of ready conditions rather than a boolean.