P9754 [CSP-S 2023] 结构体 题解

前言

在考场上调了 2h+ 还没调出来，并且 T4 也没来得及做。希望看到这段文字的你能避免这样的悲剧。

正文

题目要求动态创建类型，于是我用结构体代表一个 struct（禁止套娃），要新建就 new 出来一个。（最后也没 delete）

struct Obj{
    typnam tnam;
    ll len, align;
    std::map<std::string, std::pair<Obj*, ll>> subs;
    Obj():tnam(), len(0), align(0){}
    Obj(std::string nam, ll le=0, ll ali=0):tnam(nam), len(le), align(ali){}
};

由于结构体的名称和变量名称容易混淆，我用 typnam 标注了结构体的名称。

using typnam = std::string;

声明了结构体之后，题目要求根据名称找出一个结构体，我用 std::set 保存。这里也可以用 std::map。

struct comp_obj_by_typnam{ bool operator()(Obj *a, Obj *b) const { return a->tnam < b->tnam; } };
std::set<Obj*, comp_obj_by_typnam> decl_objs = {&BByte, &SShort, &IInt, &LLong};
Obj *get_obj_by_tname(typnam &tnam){
    Obj tmp(tnam);
    return *decl_objs.find(&tmp);
}

对于已存在的变量，我用一个 map 保存名称，类型和起始位置。

其实这里也可以新建一个特殊的 struct，就像森林转树要加一个超级根一样。这样可以避免一些重复的代码。

std::map<std::string, std::pair<Obj*, ll>> exist_objs;
ll global_offset = 0;

关于如何计算对齐：

设第 \(i\) 个被定义的元素大小为 \(s_i\)，对齐要求为 \(a_i\)，起始地址为 \(b_i\);
则 \(b_1=0\)，对于 \(2\le i\)， \(b_i\) 为满足 \(b_{i−1}+s_{i−1} \le b_i\) 且 \(a_i\) 整除 \(b_i\) 的最小值。

记 \(k=b_{i-1}+s_{i-1}\)，若 \(k \equiv 0 \pmod {a_i}\)，则 \(b_i\) 正好可以放入；

否则，\(b_i = k+a_i-(k \bmod {a_i})\)。

ll get_start_addr(ll old_offset, Obj const *me){
    if(old_offset % me->align) old_offset += me->align - old_offset%me->align;
    return old_offset;
}

关于访问某个元素：

读入名称 s 后，可以用 s.substr(0, s.find(".")) 找到 struct 名。

附完整代码，用于 debug：