C++ 在 vector 中动态访问 vector

Question

我正在为一个简单的解释器制作一个解析树。这是我的解析树中一个节点的代码:

struct rtok {
    std::string type;
    std::string val;
};

struct rnode  {
    rtok tok;
    vector<rnode> child;
} node;

vector<rnode> ptree;

如您所见，我的解析树只是一个“vector 的 vector ”。我还有一个函数可以将一个新节点插入到解析树中:

void add_term(rtok tok) {
    rnode n;
    n.tok = tok;
    ptree.back().child.push_back(n);
}

但是这个函数的问题是，它只将项目插入到第一个 vector 的子 vector 中。即如何让我的函数动态地将更多的 child 添加到解析树中？ 即我怎样才能让我的函数做这样的事情:

ptree.back().child.back().child.back()...push_back(n)

如果有办法动态添加 child.back() 就好了!显然我认为没有，但我希望这能说明我的观点。

Answer 1

你想要这样的东西吗？对不起，如果我误解了你的问题..

struct rnode  {
  rtok tok;
  vector<rnode> child;
  rnode& back() {
    // if our current node has empty child, return it
    if (child.empty()) return *this;
    // else recursive call this function for the last element of child vector of this node
    else return child.back().back(); // use recursion to get the last non empty vector
  }
  rnode& unrolled_back() {
    // get a pointer to the current struct
    rnode* ptr = this; 
    // if the child has non empty vector, move pointer to its last element
    while (!ptr->child.empty()) {
      // get the address of the last element (we have checked that it has elements already) and assign it to ptr
      ptr = const_cast<rnode*>(&(ptr->child.back())); 
    }
    return *ptr;
  }
  void unrolled_push_back(const rnode& node) {
    // get the last structure that has empty child vector
    auto& last = unrolled_back();
    // add element to it's child
    last.child.push_back(node);
  }

  void push_back(const rnode& node) {
    if (child.empty()) child.push_back(node);
    else return child.back().push_back(node);  // use recursion to get the last non empty vector
  }
} node;

int main() {
  rnode node;
  auto& r1 = node.back();
  assert(&r1 == &node);
  node.push_back(rnode());
  node.push_back(rnode());
  auto& r2 = node.back();
  assert(&r2 == &(node.child.back().child.back()));
  assert(!(&r2 == &(node.child.back())));
  return 0;
}

但是请注意，如果递归深度太高，此函数将崩溃，因为堆栈大小是有限的。所以有可能得到stackoverflow。