C++实现游戏树BFS时遍历std::set类型nextMoves集合的问题求解

标"fix me"的set遍历逻辑修正 #

原代码的范围for循环存在可优化点，并非完全不符合std::set的遍历要求：

• std::set是有序关联容器，迭代器解引用返回的是const修饰的存储元素，即const std::shared_ptr<GameTreeNode>。原代码按值拷贝生成普通shared_ptr的写法虽然可以通过编译，但会触发智能指针引用计数的原子增减操作，产生不必要的性能开销。
• 正确的遍历写法直接通过const引用绑定容器内的元素，完全适配set的存储特性，无语法兼容问题：

for (const auto& child_node : cur_node->nextMoves) {
  // 后续节点访问判断逻辑保持原有逻辑即可
}

连带发现的代码逻辑问题 #

• 原代码用if(!visited[node])判断节点是否访问的写法存在副作用：std::map::operator[]在目标键不存在时，会自动插入值为0的默认键值对，这个无意义的插入操作会拉低BFS的遍历效率。推荐改用visited.find(child_node) == visited.end()判断节点访问状态，避免多余的内存操作。
• 原代码的大括号存在不闭合问题，会直接导致编译失败，需要补齐while循环、外层函数的结构括号。
• 缺少根节点为空的边界判断，会在空树场景下触发非法内存访问，需要在函数开头增加空指针校验。
• 原代码遍历时的元素拷贝没有做类型适配，结合set的const元素特性，用auto推导类型可以避免手写类型带来的不一致问题。

修正后的完整可运行BFS代码 #

std::list<Board> GameTree::bfs() const {
  std::list<Board> ret;
  std::map<std::shared_ptr<GameTreeNode>, int> visited;
  std::queue<std::shared_ptr<GameTreeNode>> q;
  
  // 空树边界处理
  if (!root) return ret;

  q.push(root);
  ret.push_back(root->board);
  visited[root] = 1;

  while (!q.empty()) {
    auto cur_node = q.front();
    q.pop();
    // 正确适配set的遍历写法
    for (const auto& child_node : cur_node->nextMoves) {
      // 避免map[]的副作用
      if (visited.find(child_node) == visited.end()) {
        ret.push_back(child_node->board);
        q.push(child_node);
        visited[child_node] = 1;
      }
    }
  }
  return ret;
}

补充说明：nextMoves集合内的元素会按照CompareGameTreeNodeSharedPtr的规则排序，BFS遍历子节点的顺序会完全匹配这个排序结果，这是std::set的固有容器特性，并非遍历逻辑错误。按照课程要求无需关注比较器实现的场景下，直接使用上述遍历写法即可满足需求，不需要额外调整顺序。

内容的提问来源于stack exchange，提问作者List-Pop Smoke