c++ - boost R 树 : counting elements satisfying a query

Question

到目前为止，当我想计算我的 R 树中有多少元素满足特定空间查询时，归结为运行查询、收集匹配项然后对它们进行计数，大致如下:

std::vector<my_type> results;
rtree_ptr->query(bgi::intersects(query_box), std::back_inserter(results));
int nbElements = results.size();

有没有更好的方法，即直接计数而不检索实际元素的方法？我还没有找到任何可以做到的，但谁知道呢。 (我正在用打包算法构建我的树，以防它有任何相关性。)

我的动机是我注意到我的查询速度取决于匹配项的数量。如果有 0 个匹配项，则查询或多或少是瞬时的；如果有 10 000 个匹配项，则需要几秒钟。由于可以非常快地确定是否存在任何匹配项，因此遍历树似乎非常快(至少在我制作的索引中)；它正在收集所有结果，如果有很多匹配项，这些结果会使查询变慢。由于我对收集不感兴趣，而只是简单地计算(至少对于某些查询)，如果我可以跳过收集，那就太棒了。

Answer 1

我的脑电波迟到了。比使用 function_output_iterator 更好的方法是使用 boost::geometry::index query_iterators。

原则上，它会导致完全相同的行为，代码稍微简单一些:

box query_box;
auto r = boost::make_iterator_range(bgi::qbegin(tree, bgi::intersects(query_box)), {});
// in c++03, spell out the end iterator: bgi::qend(tree)

size_t nbElements = boost::distance(r);

NOTE: size() is not available because the query_const_iterators are not of the random-access category.

不过结合起来可能会稍微舒服一些。比方说，如果您想对每个项目进行额外检查，您可以使用标准库算法，例如:

size_t matching = std::count_if(r.begin(), r.end(), some_predicate);

我认为基于范围的解决方案更灵活(相同的代码可用于实现其他算法，如 partial_sort_copy 或 std::transform，这将很难适应输出- 来 self 的 earlier answer 的迭代器习语)。