c++ 游戏 积分 排名 怎么弄

zwjzwj19891228

内容大概是这样的： 竞技场系统，里面的每个玩家(player_id)  打赢一盘都会有积分(player_score)，  我要知道  某个玩家 对应排了多少名，假设积分不重复

我的想法是这样的   类里面  有两个map，一个是以player_id 为索引，一个是 以player_score 为索引
                                  map<   player_id,        player_score>   m1
                                  map<   player_score,   player_id>   m2

当插入一个玩家的时候，插入到 两个map中

当要查询某个  player_id对应的 排名时 1.   通过第一个map 查询到  这个玩家  多少分，
                                                  2.   通过第二个map查询到   这个玩家 对应的 迭代器，再通过  这个 迭代器 和 第二个的开始迭代器 之间的距离 来查到 他 多少名
                                                                                                                        stl有一个自带的算法   std::distance( iter , m2.begin() )
这个 虽然看上去 还行，不过 在 步骤2  中， 由于 map 的迭代器 不是 随机迭代器，不支持相减，所以是一个线性遍历，来查到这个是  第几个

各位 大神，我就是  为了避免 遍历， 才想到 用两个map的 ，有没有 啥 好办法 找到 player_id 对应的排名，

面试官 和我说了 有更好的办法， 可就说了一个名词，没有具体说，我也不太记得了，虽然面试还是过了，可是 很好奇，很好奇

谢谢

linux_c_py_php

楼主的办法不是不行, distance的消耗我认为还真不容易搞掉, 但缺点就是红黑树要遍历太慢了, 为了找一个后继要跳N下才能找到. 另外, 用map存player_id->player映射也比hash慢.

可以参考redis的zset,

用skiplist存储score->player映射, 用hash存储player_id->player映射.

zyzbill

如果为了distance消除遍历树的消耗，可以用std::vector<std::pair<player, score>>， 用lower_bound/upper_bound, distance来操作。主要，你需要用std::sort给vector排序先

hellioncu

打赢一盘的积分与相比玩家的积分相比应该小得多，可以实时维护按积分排序的数组，有变动直接在数组中找新位置，寻找次数应该很小，名次就是在数组中的位置

yulihua49

zyzbill 发表于 2013-09-25 19:29
如果为了distance消除遍历树的消耗，可以用std::vector， 用lower_bound/upper_bound, distance来操作。主要 ...

排序的开销比遍历还大，况且数据还是动态的。

zhaohongjian000

用AVL树，在树的每个节点上维护一个额外的信息：当前节点的左子树有多少个节点。这个信息在每次插入、删除、旋转的时候都需要维护。插入新的节点之后，从新节点向上走到根节点就可以知道新节点的名次，复杂度log(n)。

红黑树维护这种信息是否可行就不知道了。

zhaohongjian000

更完美的答案：顺序统计树（order-statistitc tree），见算法导论14.1节。