526互联

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

发布时间 2023-10-23 22:22:59作者: escap1st

考前内心 OS：“CCF 不会出大模拟吧（（（”。

前置声明

辅助函数：偏移量

考虑一个结构体的偏移量。已知首个空地址 \(\mathrm{address}\) 和该结构体的对齐要求 \(\mathrm{align}\)，则该结构体正确的起始地址为 \(\mathrm{\lceil address / align \rceil \times align}\)。

i64 shiftToAlign(i64 address, i64 align) {
  return (address / align + ((address % align) > 0)) * align;
}

封装：结构体

注意到变量和结构体呈现了树状结构。但是由于变量个数是指数级的，所以应该维护结构体，里面保存每个成员变量的起始位置、名称、类型。

struct Struct {
  std::string typeName;
  std::map<std::string, std::pair<Struct*, i64>> memberVarByVarName;
  std::map<i64, std::pair<Struct*, std::string>> memberVarByAddress;
  i64 align, size;
  
  Struct(std::string typeName = "",
         std::map<std::string, std::pair<Struct*, i64>> memberVarByVarName =
             {std::make_pair("", std::make_pair(nullptr, -1))},
         std::map<i64, std::pair<Struct*, std::string>> memberVarByAddress =
             {std::make_pair(-1, std::make_pair(nullptr, ""))},
         i64 align = 0, i64 size = 0)
      : typeName(typeName),
        memberVarByVarName(memberVarByVarName),
        memberVarByAddress(memberVarByAddress),
        align(align),
        size(size) {}
  
  ~Struct() {
    for (auto [varName, varInfo] : memberVarByVarName) delete varInfo.first;
  }
};

使用 std::map 并插入哨兵是为了方便操作 3 和 4。

操作 1：声明结构体

怎样定义一个结构体呢？

维护成员变量是容易的，统统丢到 std::map 就好了。

考虑到要对类型名和类型做映射，因此搞一个 std::map<std::string, Struct*> 来存。

std::map<std::string, Struct*> structByName;

基本类型

基本类型当然也能看成结构体。

{
    structByName["byte"] =
        new Struct("byte", {std::make_pair("", std::make_pair(nullptr, -1))},
                   {std::make_pair(-1, std::make_pair(nullptr, ""))}, 1, 1);
                   
    structByName["short"] =
        new Struct("short", {std::make_pair("", std::make_pair(nullptr, -1))},
                   {std::make_pair(-1, std::make_pair(nullptr, ""))}, 2, 2);
                   
    structByName["int"] =
        new Struct("int", {std::make_pair("", std::make_pair(nullptr, -1))},
                   {std::make_pair(-1, std::make_pair(nullptr, ""))}, 4, 4);
                   
    structByName["long"] =
        new Struct("long", {std::make_pair("", std::make_pair(nullptr, -1))},
                   {std::make_pair(-1, std::make_pair(nullptr, ""))}, 8, 8);
}

维护对齐要求

对于基本类型：对齐要求等于其占据空间大小，如 int 类型需要对齐到 \(4\) 字节，其余同理。
对于结构体类型：对齐要求等于其成员的对齐要求的最大值，如一个含有 int 和 short 的结构体类型需要对齐到 \(4\) 字节。

将每个成员变量的对齐要求取最大值即可。

维护偏移量和大小

为了保证内存访问的效率，元素的地址占用需要满足对齐规则，即任何类型的大小和该类型元素在内存中的起始地址均应对齐到该类型对齐要求的整数倍。

每个成员变量相对于该结构体的起始地址的偏移量为：上一个变量的偏移量，上一个变量的大小，由对齐要求形成的“洞”，这三者之和。

大小的定义比较模糊：最后一个变量终止的地址，与“为满足对齐要求而平移的值”之和。

实现

保证所有操作均符合题目所述的规范和要求，即结构体的定义不会包含不存在的类型、不会访问不存在的元素或成员等。

所以似乎并不需要判奇怪的边界。

Struct(std::string typeName = "",
        std::vector<std::pair<std::string, Struct*>> memberVarWithoutPos = {})
    : typeName(typeName),
      memberVarByVarName({std::make_pair("", std::make_pair(nullptr, -1))}),
      memberVarByAddress({std::make_pair(-1, std::make_pair(nullptr, ""))}),
      align(0),
      size(0) {
  for (auto [varName, varType] : memberVarWithoutPos) {
    align = std::max(align, varType->align);
  }
  i64 adjust = 0;
  for (auto [varName, varType] : memberVarWithoutPos) {
    adjust = shiftToAlign(adjust, varType->align);
    memberVarByVarName[varName] = std::make_pair(varType, adjust);
    memberVarByAddress[adjust] = std::make_pair(varType, varName);
    adjust += varType->size;
  }
  size = shiftToAlign(adjust, align);
}
case 1: {
  std::string typeName;
  std::cin >> typeName;
  int numberOfMember;
  std::cin >> numberOfMember;
  std::vector<std::pair<std::string, Struct*>> memberVarWithoutPos;
  for (int j = 0; j < numberOfMember; ++j) {
    std::string varTypeName, varName;
    std::cin >> varTypeName >> varName;
    memberVarWithoutPos.push_back(
        std::make_pair(varName, structByName[varTypeName]));
  }
  memberVarWithoutPos.shrink_to_fit();
  structByName[typeName] = new Struct(typeName, memberVarWithoutPos);
  std::cout << structByName[typeName]->size << ' '
            << structByName[typeName]->align << std::endl;
  break;
}

操作 2：声明变量

这个操作不是很复杂。

注意到声明的变量组成了一个森林，而森林的结点总数是极大的，不能存下所有的变量。

我们可以存每棵树的根节点，即输入的变量。为了方便操作 3 和 4，用两个 std::map 存输入的变量，两个的 key 分别是 std::string 和 i64，分别代表变量名和起始地址。

这里的起始地址等价于相对于 \(0\) 的偏移量。

std::map<std::string, std::pair<Struct*, i64>> varByVarName = {
    std::make_pair("", std::make_pair(nullptr, -1))};
std::map<i64, std::pair<Struct*, std::string>> varByAddress = {
    std::make_pair(-1, std::make_pair(nullptr, ""))};

直接丢到 std::map 里面就好。

注意更新空地址的起始位置。

i64 address = 0;

case 2: {
  std::string varTypeName, varName;
  std::cin >> varTypeName >> varName;
  Struct* varType = structByName[varTypeName];
  i64 adjust = shiftToAlign(address, varType->align);
  varByVarName[varName] = std::make_pair(varType, adjust);
  varByAddress[adjust] = std::make_pair(varType, varName);
  std::cout << adjust << std::endl;
  address = adjust + varType->size;
  break;
}

操作 3：查找变量所在地址

注意到这个变量名是 {}.{}.{} 的形式，因此我们每次取出第一个 . 以前的串，就是当前要访问的变量名。

跳到成员变量上

我们在跳的时候维护一个 std::map<std::string, std::pair<Struct*, i64>> path，可以根据变量名查询其类型和地址偏移量。

怎么维护呢？初始时 path 就是 varByVarName，设跳到的变量名称是 varName，则 path = path[varName].first->memberVarByVarName;。

维护地址

这个过程比较像 BST 求排名。我们之前对每个类型的成员变量维护了偏移量，所以用一个变量 address 维护，每次让 address += path[varName].second 即可。

实现

i64 findByVarName(std::string varName = "",
                  std::map<std::string, std::pair<Struct*, i64>> path = {
                      std::make_pair("", std::make_pair(nullptr, -1))}) {
  i64 currentAddress = 0;
  while (~varName.find('.')) {
    auto currentVarName = varName.substr(0, varName.find('.'));
    currentAddress += path[currentVarName].second;
    path = path[currentVarName].first->memberVarByVarName;
    varName = varName.substr(varName.find('.') + 1);
  }
  return currentAddress + path[varName].second;
}

case 3: {
  std::string varName;
  std::cin >> varName;
  std::cout << findByVarName(varName, varByVarName) << std::endl;
  break;
}

操作 4：查找包含某个地址的基本变量

与操作 3 类似。

跳到成员变量

设目标基本变量在当前变量的起始地址下，偏移量为 queryAddress 的变量。

我们在跳的时候维护一个 std::map<i64, std::pair<Struct*, std::string>> path，可以根据地址偏移量查询其类型和变量名。

每次往成员变量跳，就要往最靠近查询地址（最后一个偏移量小于等于当前查询地址）的变量跳，即 std::prev(path.upper_bound(queryAddress))。

跳到成员变量前，当前的 queryAddress 要减去成员变量的地址偏移量。

但是由于 path 为空时 std::prev(path.end()) 是个 UB，所以要插个哨兵。当然也可以直接判是否为空。

初始时 path 就是 varByAddress，设跳到的变量名称是 varName，则 path = path[varName].first->memberVarByAddress;。

维护名称

遍历的过程中维护字符串 currentName（初始为空），每次让 currentName += path[varName].second + "."，返回时删掉最后的 . 即可。

判断合法

额外维护当前变量的 Struct 指针 currentType（初始时为空），如果跳完成员变量之后，queryAddress 不小于 currentType->size，即代表询问的地址没有被任何基本变量占用。

注意特判 currentType == nullptr，此时必然没有执行过操作 2，因此输出 ERR。

实现

const std::string Fail = "ERR";

std::string findByAddress(
    i64 address = 0, std::map<i64, std::pair<Struct*, std::string>> path = {
                         std::make_pair(-1, std::make_pair(nullptr, ""))}) {
  std::string currentName;
  Struct* currentType = nullptr;
  while (std::prev(path.upper_bound(address)) != path.begin()) {
    currentType = std::prev(path.upper_bound(address))->second.first;
    currentName += std::prev(path.upper_bound(address))->second.second + ".";
    address -= std::prev(path.upper_bound(address))->first;
    path = currentType->memberVarByAddress;
  }
  if (currentType == nullptr || address >= currentType->size)
    return Fail;
  else
    return currentName.substr(0, currentName.size() - 1);
}

case 4: {
  i64 queryAddress;
  std::cin >> queryAddress;
  std::cout << findByAddress(queryAddress, varByAddress) << std::endl;
  break;
}

完整代码

#include <iostream>
#include <map>
#include <vector>

using i64 = long long;

i64 shiftToAlign(i64 address, i64 align) {
  return (address / align + ((address % align) > 0)) * align;
}

struct Struct {
  std::string typeName;
  std::map<std::string, std::pair<Struct*, i64>> memberVarByVarName;
  std::map<i64, std::pair<Struct*, std::string>> memberVarByAddress;
  i64 align, size;
    
  Struct(std::string typeName = "",
         std::map<std::string, std::pair<Struct*, i64>> memberVarByVarName =
             {std::make_pair("", std::make_pair(nullptr, -1))},
         std::map<i64, std::pair<Struct*, std::string>> memberVarByAddress =
             {std::make_pair(-1, std::make_pair(nullptr, ""))},
         i64 align = 0, i64 size = 0)
      : typeName(typeName),
        memberVarByVarName(memberVarByVarName),
        memberVarByAddress(memberVarByAddress),
        align(align),
        size(size) {}
    
  Struct(std::string typeName = "",
         std::vector<std::pair<std::string, Struct*>> memberVarWithoutPos = {})
      : typeName(typeName),
        memberVarByVarName({std::make_pair("", std::make_pair(nullptr, -1))}),
        memberVarByAddress({std::make_pair(-1, std::make_pair(nullptr, ""))}),
        align(0),
        size(0) {
            
    for (auto [varName, varType] : memberVarWithoutPos) {
      align = std::max(align, varType->align);
    }
    i64 adjust = 0;
    for (auto [varName, varType] : memberVarWithoutPos) {
      adjust = shiftToAlign(adjust, varType->align);
      memberVarByVarName[varName] = std::make_pair(varType, adjust);
      memberVarByAddress[adjust] = std::make_pair(varType, varName);
      adjust += varType->size;
    }
    size = shiftToAlign(adjust, align);
  }
    
  ~Struct() {
    for (auto [varName, varInfo] : memberVarByVarName) delete varInfo.first;
  }
};

i64 findByVarName(std::string varName = "",
                  std::map<std::string, std::pair<Struct*, i64>> path = {
                      std::make_pair("", std::make_pair(nullptr, -1))}) {
    
  i64 currentAddress = 0;
  while (~varName.find('.')) {
    auto currentVarName = varName.substr(0, varName.find('.'));
    currentAddress += path[currentVarName].second;
    path = path[currentVarName].first->memberVarByVarName;
    varName = varName.substr(varName.find('.') + 1);
  }
    
  return currentAddress + path[varName].second;
}

const std::string Fail = "ERR";

std::string findByAddress(
    i64 address = 0, std::map<i64, std::pair<Struct*, std::string>> path = {
                         std::make_pair(-1, std::make_pair(nullptr, ""))}) {
    
  std::string currentName;
  Struct* currentType = nullptr;
  while (std::prev(path.upper_bound(address)) != path.begin()) {
    currentType = std::prev(path.upper_bound(address))->second.first;
    currentName += std::prev(path.upper_bound(address))->second.second + ".";
    address -= std::prev(path.upper_bound(address))->first;
    path = currentType->memberVarByAddress;
  }
    
  if (currentType == nullptr || address >= currentType->size)
    return Fail;
  else
    return currentName.substr(0, currentName.size() - 1);
}

int main() {
  int n;
  std::cin >> n;

  std::map<std::string, Struct*> structByName;
  std::map<std::string, std::pair<Struct*, i64>> varByVarName = {
      std::make_pair("", std::make_pair(nullptr, -1))};
  std::map<i64, std::pair<Struct*, std::string>> varByAddress = {
      std::make_pair(-1, std::make_pair(nullptr, ""))};

  {
    structByName["byte"] =
        new Struct("byte", {std::make_pair("", std::make_pair(nullptr, -1))},
                   {std::make_pair(-1, std::make_pair(nullptr, ""))}, 1, 1);
    structByName["short"] =
        new Struct("short", {std::make_pair("", std::make_pair(nullptr, -1))},
                   {std::make_pair(-1, std::make_pair(nullptr, ""))}, 2, 2);
    structByName["int"] =
        new Struct("int", {std::make_pair("", std::make_pair(nullptr, -1))},
                   {std::make_pair(-1, std::make_pair(nullptr, ""))}, 4, 4);
    structByName["long"] =
        new Struct("long", {std::make_pair("", std::make_pair(nullptr, -1))},
                   {std::make_pair(-1, std::make_pair(nullptr, ""))}, 8, 8);
  }

  i64 address = 0;

  for (int i = 0; i < n; ++i) {
    int op;
    std::cin >> op;
    switch (op) {
            
      case 1: {
        std::string typeName;
        std::cin >> typeName;
        int numberOfMember;
        std::cin >> numberOfMember;
        std::vector<std::pair<std::string, Struct*>> memberVarWithoutPos;
        for (int j = 0; j < numberOfMember; ++j) {
          std::string varTypeName, varName;
          std::cin >> varTypeName >> varName;
          memberVarWithoutPos.push_back(
              std::make_pair(varName, structByName[varTypeName]));
        }
        memberVarWithoutPos.shrink_to_fit();
        structByName[typeName] = new Struct(typeName, memberVarWithoutPos);
        std::cout << structByName[typeName]->size << ' '
                  << structByName[typeName]->align << std::endl;
        break;
      }
            
      case 2: {
        std::string varTypeName, varName;
        std::cin >> varTypeName >> varName;
        Struct* varType = structByName[varTypeName];
        i64 adjust = shiftToAlign(address, varType->align);
        varByVarName[varName] = std::make_pair(varType, adjust);
        varByAddress[adjust] = std::make_pair(varType, varName);
        std::cout << adjust << std::endl;
        address = adjust + varType->size;
        break;
      }
            
      case 3: {
        std::string varName;
        std::cin >> varName;
        std::cout << findByVarName(varName, varByVarName) << std::endl;
        break;
      }
            
      case 4: {
        i64 queryAddress;
        std::cin >> queryAddress;
        std::cout << findByAddress(queryAddress, varByAddress) << std::endl;
        break;
      }
            
      default:
        break;
    }
  }

  return 0;
}