减少垂直线段和水平线段的"直线扫描"所花费的时间

Question

我使用std：：set来实现垂直线和水平线的扫线算法。但是，在"状态"集的下界和上界上的最终范围搜索需要大量时间。有什么办法可以避免这种情况吗？我选择std:：set是因为它基于平衡的BST，插入、删除和搜索需要logn时间。是否有更好的数据结构来实现这一点？

// before this I initialize the events set with segments with increasing x co-ordinates. The segment struct has 2 points variable and 1 type variable for identifying vertical segment(1), horizontal segment starting(0) and ending(2).
for(auto iter = events.begin(); iter != events.end(); iter++)
{
segment temp = *iter;
if(temp.type == 0)
status.insert(temp.p1);
else if(temp.type == 2)
status.erase(temp.p2);
else
{    
auto lower = status.lower_bound(std::make_pair(temp.p1.x, temp.p1.y));
auto upper = status.upper_bound(std::make_pair(temp.p2.x, temp.p2.y));

// Can the no of elements in the interval be found without this for loop
for(;lower != upper; lower++)
{
count++;
}
}
}

这里，event和status分别是段、结构和点的集合。

typedef std::pair<int, int> point;
struct segment
{
point p1, p2;
int type;
segment(point a, point b, int t)
:p1(a), p2(b), type(t){}
};
std::set<segment, segCompare> events;
...
std::set<point, pointCompare> status;

Answer 1

为了有效地计算距离，树需要维护每个子树的大小计数。由于在大多数情况下不需要该服务，因此std::set不会为每个人带来成本也就不足为奇了。

我在C++标准库中还没有找到任何现成的东西可以做到这一点。我认为在这种情况下，你可能需要自己滚，或者找其他人滚。

Answer 2

如果批量插入事件，请使用始终排序的std：：向量。对于一批n个插入，无症状运行时没有区别，两者都是O(n log n(。

这让您可以执行迭代器算术等操作。