Is there a container for modeling publisher-subscriber relationship with fast lookup for either?

Question

I have a publisher-subscriber relationship I want to model. Publishers can have multiple subscribers, but each subscriber can only get data from a single publisher. I thought a map of vectors would be good for this:

std::map<publisher, std::vector<subscriber>>

Publisher lookup, insertion, and deletion is fast, subscriber insertion is fast, and getting all subscribers for a publisher is easy. But subscriber lookup and deletion from the map is cumbersome. It requires iterating all publishers until that subscriber is found. And I would still like an easy way of iterating through all subscribers, ideally without a double loop.

I'd like a container with these properties, where each operation is a single function call, or loop, where appropriate:

• Lookup, insertion, deletion of publishers/subscribers. O(1) or O(lg N); N = number of publishers/subscribers
• Iteration of publishers/subscribers. O(N); N = number of publishers/subscribers
• Iteration of subscriptions for a single publisher. lookup + O(N); N = number of subscribers for that publisher.

Is there a ready-made container that can do this or will I have to make a custom one?

Answer 1

I would suggest:

struct SubscriptionRecords {
    std::unordered_map<publisher, std::unordered_set<subscriber>>
        subscribers;
    std::unordered_map<subscriber, publisher>
        subscriptions;
};

Then some example methods:

void add_subscription(publisher p, subscriber s) {
    auto res = self->subscriptions.insert(s);
    assert(res->second);  // At most one subscription.
    self->subscribers[p].insert(s);
}

void remove_subscriber(subscriber s) {
    auto sp = self->subscriptions.find(s);
    if (sp != self->subscriptions.end()) {
        self->subscribers[*sp].erase(s);
        self->subscriptions.erase(sp);
    }
}

and similar.