如何在修改Boost R-tree时优雅遍历其节点？

问题场景 #

使用Boost 1.65.1版本的R-tree（C++17）处理二维点集，需求为：对每个节点执行邻域搜索检测相邻节点，处理查询结果后将所有结果节点从R-tree中移除，重复此过程直至遍历完剩余节点。

但直接在遍历中调用remove会导致迭代器失效，引发死循环等问题，目前只能将迭代器重置为begin()，希望找到更优雅的解决方式。

基础代码片段：

for (auto it = someRTree.begin(); it != someRTree.end(); ++it) {
    std::vector<std::pair<point, size_t>> results;
    // 创建当前节点周围的查询框
    bgm::box<point> queryBox(point(bg::get<0>(it->first) - someConst,
                                   bg::get<1>(it->first) - someConst),
                             point(bg::get<0>(it->first) + someConst,
                                   bg::get<1>(it->first) + someConst));
    someRTree.query(bgi::intersects(queryBox), std::back_inserter(results));

    // 处理查询结果
    // ...

    someRTree.remove(results); // <- 此操作会使迭代器失效
}

优雅解决方案 #

方案一：批量处理剩余元素（推荐） #

彻底避开迭代器失效问题，每次从R-tree中取出第一个元素执行处理，移除相关节点后循环直到树为空，逻辑简洁且高效。

while (!someRTree.empty()) {
    // 获取当前要处理的第一个节点
    auto current = *someRTree.begin();
    std::vector<std::pair<point, size_t>> results;

    // 构造邻域查询框
    bgm::box<point> queryBox(
        point(bg::get<0>(current.first) - someConst, bg::get<1>(current.first) - someConst),
        point(bg::get<0>(current.first) + someConst, bg::get<1>(current.first) + someConst)
    );
    someRTree.query(bgi::intersects(queryBox), std::back_inserter(results));

    // 处理查询结果
    // ...

    // 移除所有结果节点
    someRTree.remove(results);
}

说明：每次循环直接从树的起始位置取节点，处理后移除所有相关节点，下一次循环自动处理剩余的第一个未处理节点，全程无需维护迭代器，完全规避失效问题。

方案二：手动维护迭代器（适合特殊场景） #

如果需要保留部分遍历逻辑，可以先保存当前节点的副本，执行删除后重新获取迭代器。不过因为删除操作可能移除大量元素，直接从begin()开始反而更高效。

while (!someRTree.empty()) {
    auto it = someRTree.begin();
    // 保存当前节点副本，防止删除后无法访问
    auto current = *it;
    std::vector<std::pair<point, size_t>> results;

    bgm::box<point> queryBox(
        point(bg::get<0>(current.first) - someConst, bg::get<1>(current.first) - someConst),
        point(bg::get<0>(current.first) + someConst, bg::get<1>(current.first) + someConst)
    );
    someRTree.query(bgi::intersects(queryBox), std::back_inserter(results));

    // 处理结果
    // ...

    someRTree.remove(results);
}

额外注意事项 #

• 如果查询结果中存在重复元素，建议先对results去重，避免重复调用remove造成不必要的性能损耗。
• Boost 1.65.1的R-treeremove函数会逐一移除传入的元素，确保所有匹配项都被删除。

内容的提问来源于stack exchange，提问作者Zacryon