pre
- 之前的排行榜实现为
std::vector<rank_info>+std::unordered_map<player_id, rank_index>- 问题1：每次更新排行榜需要全量排序，因为容器存储了具体角色的排名
- 问题2：全量排序后需要全量存储
- 没有引发灾难性的问题是因为排行榜最大尺寸只有100
- 取舍：是否需要存储具体玩家所在排行榜的具体位置？
- 当前游戏更多的操作是查看排行榜榜单，榜单数据无论是反序列化或者遍历拼ui的动作上都可以获得我具体的排名
- 需要指定玩家具体排名数据是可以遍历榜单，时间复杂度O(N) 相比全量排序O(N^2)还是小的
- 遍历的方式还可以优化（todo）
快速重构
- 最简单的方式
std::set set::iterator是稳定的，只有erase动作有影响 https://en.cppreference.com/w/cpp/container#Iterator_invalidation1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
namespace rank {
class container_interface {
public:
virtual ~container_interface() = default;
// todo:
// virtual std::string serialize() = 0;
// virtual std::string unserialize() = 0;
};
template <std::size_t count_vv, class sort_key_tt, class element_tt,
class element_key_tt, class compare_tt = std::less<sort_key_tt> >
class container : public container_interface {
using sort_data =
std::map<sort_key_tt, std::pair<element_key_tt, element_tt>, compare_tt>;
using sort_data_iterator = typename sort_data::iterator;
private:
const std::size_t _count = count_vv;
sort_data _data;
std::unordered_map<element_key_tt, sort_data_iterator> _elements;
std::unordered_set<element_key_tt> _dirty_elements;
public:
container() = default;
container(compare_tt&& compare_call) : _data(compare_call) {}
~container() override = default;
[[maybe_unused]] bool insert(const sort_key_tt& skey, const element_tt& ev, const element_key_tt& ekey) {
remove(ekey);
if (auto [data_it, res] = _data.emplace(skey, std::make_pair(ekey, ev));
res) {
if (auto [ele_it, res] = _elements.emplace(ekey, data_it); res) {
_dirty_elements.emplace(ekey);
}
}
while (_data.size() > _count) {
auto last_data_it = std::prev(_data.end());
remove(last_data_it->second.first);
}
return exist(ekey);
}
[[maybe_unused]] bool remove(const element_key_tt& ekey) {
if (const auto it = _elements.find(ekey); it != _elements.end()) {
_dirty_elements.emplace(ekey);
_data.erase(it->second);
_elements.erase(it);
return true;
}
return false;
}
bool exist(const element_key_tt& ekey) const {
return _elements.contains(ekey);
}
};
}; // namespace rank- 测试代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57namespace rank_test {
struct sort_key {
uint32_t level = 0;
uint32_t exp = 0;
uint64_t ts = 0;
uint64_t auto_increment = 0;
};
using element_key = uint64_t;
struct element_value {
std::string name;
};
}; // namespace rank_test
template <>
struct std::less<rank_test::sort_key> {
bool operator()(const rank_test::sort_key& left,
const rank_test::sort_key& right) const {
return left.level < right.level ||
(left.level == right.level && left.exp < right.exp) ||
(left.level == right.level && left.exp == right.exp &&
left.ts < right.ts) ||
(left.level == right.level && left.exp == right.exp &&
left.ts == right.ts && left.auto_increment < right.auto_increment);
}
};
template <>
struct std::greater<rank_test::sort_key> {
bool operator()(const rank_test::sort_key& left,
const rank_test::sort_key& right) const {
return left.level > right.level ||
(left.level == right.level && left.exp > right.exp) ||
(left.level == right.level && left.exp == right.exp &&
left.ts > right.ts) ||
(left.level == right.level && left.exp == right.exp &&
left.ts == right.ts && left.auto_increment > right.auto_increment);
}
};
rank::container<10, rank_test::sort_key, rank_test::element_value,
rank_test::element_key>
rc;
rank::container<10, rank_test::sort_key, rank_test::element_value,
rank_test::element_key, std::greater<rank_test::sort_key>>
rcg;
for (int i = 0; i < 100; ++i) {
rank_test::sort_key sk{1, 1, 1, i};
rank_test::element_value ev{"name_" + std::to_string(i)};
rc.insert(sk, ev, i);
rcg.insert(sk, ev, i);
}
至此都很美好，一个标准可用的排序容器
- 新需求：lua 需要决定用哪些属性排序，并指定具体属性的顺序
- 第一反应是：假设用 level, exp 双属性排序，想要得到 等级相同，经验大的排前面的样子，可以: level << 32 | exp 得到一个新值作为 sort_key
- 然而这种方式…策划不懂（或者只是觉得算着麻烦…）
- 策划提出了想要的样子: 构建排行榜时给定 table[“level”] = 升序/降序; table[“exp”] = 升序/降序
- 还是要实现….
- 一个排序规则数据而已，但是容器本身只有 sort_key 的类型，排序是需要 operator < 函数处理的…
- 并且这里实现的 container 想作为一个单纯的容器使用，并不想引入外部特殊规则….只能想办法把数据引入到 compare_tt 里
- 数据可以作为lambda的闭包： operator < 使用lambda
- https://stackoverflow.com/questions/72673837/c11-how-to-use-lambda-as-type-parameter-where-it-requires-a-functor-type-l
- 于是就有了：
container(compare_tt&& compare_call) : _data(compare_call) {}
1 | namespace lua_rank_test { |
- 明显有性能问题，但是先能跑吧
set comparator exception
1 | void test_set() { |