无法按索引从 boost::geometry::index::rtree 中删除元素

Question

来自我创建的示例页面：

typedef bg::model::point<float, 2, bg::cs::cartesian> point;
typedef bg::model::box<point> box;
typedef std::pair<box, unsigned> value;

我想向树中添加 value 个元素：

bgi::rtree< value, bgi::quadratic<16> > rtree;
box b(point(2.0f, 2.0f), point(2.5f, 2.5f));
// insert new value
rtree.insert(std::make_pair(b, 2));

现在我想知道是否可以通过知道 box 标识符（或它的所有元素，如果可以设置更多具有相同 ID 的元素）来删除一个元素。

我想做的是删除我在上面添加的元素，比如调用类似的东西：

rtree.remove(2); // why I can't do this?

我怎样才能做到这一点？

Answer 1

您将不得不使用迭代器。可能的重载是

remove(value_type const &)
remove(Iterator, Iterator)
remove(ConvertibleOrRange const &)

首先您应该通过搜索找到要删除的值（可能运行一个查询，但我认为您不需要它，因为您的问题不存在。）

因此，您可能想要使用 std::find_if。我不确定如何提高性能（不求助于反向映射）。我猜你的探查器应该用来提供保证。

更新：概念验证

天真的方法失败了：

// UNDEFINED BEHAVIOUR:
template <typename Rtree, typename Id>
size_t remove_ids_loop(Rtree& rtree, Id const& id) {
    using V = typename Rtree::value_type;
    static_assert(sizeof(V) == 0, "don't use; UNDEFINED BEHAVIOUR!");

    size_t removed = 0;
    std::for_each(rtree.begin(), rtree.end(), [&](V const& v) { 
            if (id == v.second)
                removed += rtree.remove(v);
        });

    return removed;
}

这是因为as documented:

⚠ Warning

The modification of the rtree may invalidate the iterators.

简单方法：

template <typename Rtree, typename Id>
size_t remove_ids_bulk(Rtree& rtree, Id const& id) {
    using V = typename Rtree::value_type;
    std::vector<V> v;
    std::copy_if(rtree.begin(), rtree.end(), back_inserter(v), [id](V const& v) { return v.second == id; });

    return rtree.remove(v.begin(), v.end());
}

这通过将查询与删除分开进行来回避竞争。请注意，这可能更有效，因为我们一次通过了整个范围。

Note: this should be ok with duplicate entries, because rtree::remove only deletes one value at a time.

现场演示

Live On Coliru

#include <boost/geometry.hpp>
#include <boost/geometry/index/rtree.hpp>

namespace bg = boost::geometry;
namespace bgi = bg::index;

typedef bg::model::point<float, 2, bg::cs::cartesian> point;
typedef bg::model::box<point> box;

typedef std::pair<box, unsigned> value;

template <typename Rtree, typename Id>
size_t remove_ids_bulk(Rtree& rtree, Id const& id) {
    using V = typename Rtree::value_type;
    std::vector<V> v;
    std::copy_if(rtree.begin(), rtree.end(), back_inserter(v), [id](V const& v) { return v.second == id; });

    return rtree.remove(v.begin(), v.end());
}

// UNDEFINED BEHAVIOUR:
template <typename Rtree, typename Id>
size_t remove_ids_loop(Rtree& rtree, Id const& id) {
    using V = typename Rtree::value_type;
    static_assert(sizeof(V) == 0, "don't use; UNDEFINED BEHAVIOUR!");

    size_t removed = 0;
    std::for_each(rtree.begin(), rtree.end(), [&](V const& v) { 
            if (id == v.second)
                removed += rtree.remove(v);
        });

    return removed;
}

int main() {
    //I want to add value elements to the tree:

    bgi::rtree< value, bgi::quadratic<16> > rtree;
    box b(point(2.0f, 2.0f), point(2.5f, 2.5f));
    // insert new value
    rtree.insert(std::make_pair(b, 2));
    std::cout << "Elements: " << rtree.size() << "\n";

    // remove id 2
    remove_ids_bulk(rtree, 2u);
    std::cout << "Elements: " << rtree.size() << "\n";
}

版画

Elements: 1
Elements: 0

无法按索引从 boost::geometry::index::rtree 中删除元素

Cannot remove element from boost::geometry::index::rtree by its index

c++

boost

r-tree

boost-geometry

更新：概念验证

⚠ Warning

简单方法：

现场演示