Hi, there was a long discusion about the complexity of wait_for_any some mounts ago. If I understood well the probleme was in the future_waiter::wait unsigned wait() { all_futures_lock lk(futures); for(;;) { for(unsigned i=0;i<futures.size();++i) // O(N) { if(futures[i].future->done) { return futures[i].index; } } cv.wait(lk); } } What we need is a synchonization structure that returns a user specific data (in this case the index). So we can replace by unsigned wait() { all_futures_lock lk(futures); return cv_with_value.wait(lk); } We need to pass to the register_external_waiter the specific data, in this case the index template<typename F> void add(F& f) { if(f.future) { futures.push_back(registered_waiter(f.future, f.future->register_external_waiter(cv_with_value,future_count),future_count)); } ++future_count; } So the list of waiters is now typedef std::list<std::pair<condition_variable_any_with_value<unsigned>*, unsigned> > waiter_list; waiter_list::iterator register_external_waiter( condition_variable_any_with_value<unsigned>& cv_with_value, unsigned indx) { boost::unique_lock<boost::mutex> lock(mutex); do_callback(lock); return external_waiters.insert(external_waiters.end(),std::make_pair(&cv, indx)); } The notification to the waiters will no use the new notify_all interface passing as parameter the index of the future relative to the condition_variable. void mark_finished_internal() { done=true; waiters.notify_all(); for(waiter_list::const_iterator it=external_waiters.begin(), end=external_waiters.end();it!=end;++it) { (it->first)->notify_all(it->second); } } The interface of the condition_variable_any_with_value is the same as condition_variable_any but template <typename T> class condition_variable_any_with_value { // add a get function T get(); // gets the value stored when notify called // change the interface for the notify functions bool notify_one(T val); bool notify_all(T val); }; What do you think?