Find and delete a std::function object from a map of vectors

Question

I am currently trying to implement a messenger system for my game engine. It uses function callbacks of the form:

typedef std::function<void(const Message &)> Callback;

It maintains a message list:

mutable std::vector<std::unique_ptr<Message>> messageList;

And a callback dictionary of signature:

mutable std::map<std::string, std::vector<Callback>> callbackDictionary;

which is used to call all the callbacks 'bound' to a specific message type. When the callback function is called, the respective message is passed. So far so good.

For better understanding, here is the subscribe method that lets the user add a function method that is called for every message of the subscribed to type.

void Messenger::Subscribe(Message::Type type, Callback callbackFunction) 
const
{
    callbackDictionary[type].push_back(callbackFunction);
}

And here an example of how it used (by the clickable component class)

messageBus.Subscribe("Message/Click", [this](const Message & message) {this->OnClick(static_cast<const ClickMessage &>(message)); });

Now my problem:

I want to implement an unsubscribe method that finds a function/method in the dictionary's vector and removes it. Note that the function could be subscribed to more than one message type. I was thinking of something like this:

void Messenger::UnSubscribe(Callback callbackFunction)
{
    for (auto & pair : callbackDictionary)
    {
        auto & functionList = pair.second;
        for (auto function : functionList)
        {
            if (function == callbackFunction)
                functionList.erase(std::remove(functionList.begin(), functionList.end(), function), functionList.end());
            // I am aware of issues that may appear from looping deleting while looping
        }
    }
}

However, the comparison operator (==) appears to be undefined for function objects. I couldn't come up with an easy way to get around this. So any ideas are much apprechiated. I am just trying to avoid some kind of id system cause from experience the can be a chore to manage. Especially when all kinds of functions and members can be added everywhere throughout the program.

Answer 1

There is no equality operator in std::function. A rationale can be found in the old tr1::function N1667:

operator== is unimplementable for tr1::function within the C++ language, because we do not have a reliable way to detect if a given type T is Equality Comparable without user assistance

Also note that you're passing std::function<void(const Message &)> by-value. That means that you also can't just compare their addresses (not that it would've been a good solution, as std::function is easily copyable).

Solution 1:

Use some user-provided key and std::function as the value and store them in a map instead of a vector.

std::map<std::string, std::map<std::string, Callback>> callbackDictionary;
. . .
void Messenger::Subscribe(Message::Type type, const std::string& cbID, Callback cb);

void Messenger::UnSubscribe(const std::string& cbID);

Solution 2:

Use a weak_ptr to keep track of callbacks.

std::map<std::string, std::vector<std::weak_ptr<Callback>> callbackDictionary;
. . .
void Messenger::Subscribe(Message::Type type, std::shared_ptr<Callback> cb);

No UnSubscribe needed at all! You can auto-unsubscribe the callbacks as soon as weak_ptr turns nullptr. A prerequisite is that the listener must keep the callback alive via a shared_ptr.

Answer 2

std::function stores invokables that can be copied. It makes no requirement that its contents are == comparible, and lambdas are not == compariable.

You can extract the typeid of the stored invokable, assume false if they don't match, add in type erasure features that let you store == on various types and dispatch when the types are equal, but then you don't support lambdas as lambdas do not support ==.

If you say "no lambdas", you can do it, or if you say "no lambdas with bound state". I'll get into that possibility later, but first I'd advise trying this:

using std::shared_ptr<void> token;

template<class...Message>
struct broadcaster {
  using listener = std::function<void(Message...)>;
  using splistener = std::shared_ptr<listener>;
  using wplistener = std::weak_ptr<listener>;

  token listen( listener f ) {
    auto sf = std::make_shared<listener>(std::move(f));
    listeners.push_back(sf); // as weak ptr
    return sf; // as token
  }
  std::size_t operator()( Message... message ) const {
    // remove stale targets:
    targets.erase( std::remove_if( begin(targets), end(targets),
      [](auto&& ptr) { return !ptr.lock(); }
    ), end(targets) );
    auto tmp = targets; // copy, for reentrancy
    for (auto wf : tmp) {
      if(auto sf = wf.lock()) {
        sf( message... );
      }
    }
  }
private:
  mutable std::vector<wplistener> targets;
};

In the client, keep track of the tokens you are listening to. When the client object goes away, it is automatically deregistered from every broadcaster it is listening to. Just use a std::vector<token> and stuff your tokens in there.

If you have more complex logic where listening shouldn't be bound to the listeners lifetime, then you have to store said tokens separately.

This assumes that broadcasting happens roughly as often as registration/deregistration does, or moreso. If broadcasting is extremely rare and registration/deregistration is extremely common (like a million time more common), the weak pointers to listeners can build up. You can add a test in listen to periodically clean stale listeners.

---

Now, we can do a "no lambdas with bound state". Then we can bind the state separately, type erase the == operation there, and bob is your uncle.

state( some_state... )
([](some_state&&...){
  return [&](some_args...){
  /* code */
});

a construct like the above would let you return a function object that behaves much like a lambda but with a sensible == operation on it.

template<class F, class...Args>
struct bound_state {
  std::tuple<Args...> state;
  F f;
  friend bool operator==( bound_state const& lhs, bound_state const& rhs ) {
    return lhs.state==rhs.state;
  }
  template<class...Ts>
  decltype(auto) operator()(Ts&&...ts){
    return std::apply(f, state)( std::forward<Ts>(ts)... );
  }
};
template<class...Args>
auto state( Args&&... args ) {
  auto tup = std::make_tuple( std::forward<Args>(args)... );
  return [tup=std::move(tup)](auto&& f) {
    return bound_state<std::decay_t<decltype(f)>, std::decay_t<Args>...>{
      tup, decltype(f)(f)
    };
  };
}

or somesuch.

Next we create a derived type of std::function. When constructed from a type, it stores a type-erased == (either into a global or local location) for it (from a pair of std::functions).

It overrides == to first check if typeid is identical, and if so it invokes the type-erased == on the two elements.

template<class Sig>
struct func_with_equal : std::function<Sig> {
  using Base = std::function<Sig>;
  using Base::operator();
  using equality = bool( func_with_equal const&, func_with_equal const& );      
  equality* pequal = nullptr;

  template<class F>
  static equality* erase_equality() {
    return [](func_with_equal const& lhs, func_with_equal const&rhs)->bool {
      assert( lhs.target_type() == rhs.target_type() );
      assert( lhs.target_type() == typeid(F) );
      return *lhs.target<F>() == *rhs.target<F>();
    };
  }
  // on construction, store `erase_equality<F>()` into `pequal`.

  friend bool operator==( func_with_equal const& lhs, func_with_equal const& rhs ) {
    if (!lhs && !rhs) return true;
    if (!lhs || !rhs) return false;
    if (lhs.target_type() != rhs.target_type()) return false;
    return lhs.pequal( lhs, rhs );
  }
};

this is half done, but I hope you get the idea. It is complex and convoluted and forces extra work at every point you register a callback.