c++ - 在 C++ 中的多对多关系和实现中查找两个不相关对象的最快方法

Question

基本设置是，假设我们有两个简单的类:

class User {
     private:
        int id;
     public:
        User(int id){ this->id = id };
};

class Channel {
     private:
        std::string name;
     public:
        Channel(std::string name) { this->name = name };
};

这两个类之间应该是多对多关系，例如每个 User 可以加入多个 Channel，每个 Channel 可以有多个 User。

Channel 对象的数量 - 几百个。 User 对象的数量 - 数万。

任务制定:给定一个特定的 Channel 对象，我必须找到一个与其无关的User , 尽可能快。

问题:

1) 考虑到给定的任务，这种多对多关系的最佳实现是什么？对于这样的问题是否有任何特定的算法(除了通过所有关系直接迭代)？

2) 如果关系应该具有一些额外的属性，例如存储用户加入 channel 的时间？

我的想法:第一个想法是创建一些额外的类，例如

class UserChannelRel {
    private:
        User* userPtr;
        Channel* chPtr;
        float timeJoined;
    public:
        UserChannelRel(User* user, Channel* channel, float tm) {
             this->userPtr = user;
             this->chPtr = channel;
             this->timeJoined = tm;
        }
};

并将它们存储在一些大的标准容器( vector ？)中。但是遍历所有元素似乎很慢。

Answer 1

首先，您可以创建两个存储库，一侧保存完整的用户列表，另一侧保存完整的 channel 列表。通常，您会使用 maps 来执行此操作:

map<int, User> users;
map<std::string, Channel> channels;  

然后，我建议为每个 channel 设置一个 set用户:

class Channel {
     private:
        std::string name;
        std::set<int> subscribers; 
     public:
        Channel(std::string name):name(name) { };
        void add(int userid) {
            subscribers.insert(userid);
        }
};

然后要查找与 channel 无关的用户，您可以遍历用户并轻松检查是否包含在 channel 中。

或者，您也可以使用一组全局用户(与存储库同时维护集合成员资格，或者通过 creating the set from the map )并使用 set_difference()生成非订户的用户集。

Example of use set_difference:

set<int> a { 1,2,3,4,5,6,7};   // imagine a set of all the users
set<int> b{ 2,3,8};            // imagine a set of the subscribers of a channel
vector<int> c;                 // container with the users who are not subscribers

set_difference(a.begin(),a.end(), b.begin(), b.end(), back_inserter(c)); 
copy(c.begin(), c.end(), ostream_iterator<int>(cout," "));

如何在这两种方法之间进行选择？第一种方法，迭代和检查，具有快速找到第一批用户并开始对提案进行处理的优势。可以利用集合和映射已排序的事实来优化迭代。您不需要找到所有用户。第二种方法很优雅，但是对于庞大的用户群，它可能需要更多时间，因为您需要在做任何事情之前获得完整的结果。