c++ - 什么样的数据结构适合facebook-model用户

Question

我想为这种情况建立一个有效的数据结构:
有很多用户，每个用户都有一个ID和一个名字。每个用户都可以关注其他人。我需要处理四种命令:创建用户、关注、删除用户和取消关注。这是一个例子:

create-user id=3 name="Chandler"
create-user id=7 name="Janice"
create-user id=2 name="Joey"
follow id=3 id=7     # Chandler follows Janice
follow id=7 id=3     # Janice follows Chandler
follow id=2 id=7
follow id=7 id=2
delete-user id=7
follow id=3 id=2
follow id=2 id=3
cancel-follow id=3 id=2

总之，我需要读取一个文件，其中包含许多上述命令并处理所有数据。

这是我尝试过的(处理四种命令的函数):

struct User
{
    unsigned long id;
    string name;
    unordered_set<User *> followers;
    unordered_set<User *> fans;

    User(unsigned long pid, const string & pname) : id(pid), name(pname) {}
};

list<User> users;

User & getUserById(list<User> & users, unsigned long id)
{
    auto it = std::find_if(users.begin(), users.end(), [&](User & u) {return id == u.id;});
    return *it;
}

void createUser(list<User> & users, unsigned long id, const string & str)
{
    users.emplace_back(User(id, str));
}

void deleteUser(list<User> & users, unsigned long id)
{
    auto itUser = std::find_if(users.begin(), users.end(), [&](User & u) {return id == u.id;});
    auto itFans = itUser->fans;
    for (auto it = itFans.begin(); it != itFans.end(); ++it)
    {
        (*it)->followers.erase(&*itUser);
    }
    auto itFollowers = itUser->followers;
    for (auto it = itFollowers.begin(); it != itFollowers.end(); ++it)
    {
        (*it)->fans.erase(&*itUser);
    }
    users.erase(itUser);
}

void buildRelation(list<User> & users, unsigned long follower, unsigned long fan)
{
    User & u1 = getUserById(users, follower);  //3
    User & u2 = getUserById(users, fan);  //7
    u1.fans.insert(&u2);
    u2.followers.insert(&u1);
}

void cancelRelation(list<User> & users, unsigned long follower, unsigned long fan)
{
    User & u1 = getUserById(users, follower);       //3
    User & u2 = getUserById(users, fan);  //2
    u1.fans.erase(&u2);
    u2.followers.erase(&u1);
}

它没有任何错误。

但是，我用我的代码处理一个文件，包含70000行命令，大约需要67秒。

我真的很想获得更好的性能(也许 20 秒？)，我知道我需要一个更好的数据结构，但现在我不知道如何设计一个更好的数据结构。

Answer 1

您的输入数据看起来很适合像 std::unordered_map ( https://en.cppreference.com/w/cpp/container/unordered_map ) 这样的键值数据结构

其中 id 值可以作为存储和检索用户数据结构的键。

如果你可以将数据处理成这样的结构std::unordered_map 而不是列表这样您的 getUserById 函数就不需要每次都搜索列表来检索用户数据。