问帮助实现向量合并算法

EN

我需要一个非常快速的算法来完成以下任务。我已经实现了几种完成它的算法，但它们对于我需要的性能来说太慢了。它应该足够快，以至于算法在现代CPU上每秒至少运行100,000次。它将在C ++中实现。

我正在使用跨度/范围，一个在一条线上有一个开始和一个结束坐标的结构。

我有两个跨度向量（动态数组），我需要合并它们。一个向量是src而另一个是dst。矢量按跨度起始坐标排序，并且跨度不在一个矢量内重叠。

src向量中的跨距必须与dst向量中的跨距合并，这样得到的向量仍然是有序的并且没有重叠。IE浏览器。如果在合并期间检测到重叠，则将两个跨度合并为一个。（合并两个跨度只是改变结构中的坐标。）

现在，还有一个问题，src向量中的跨度必须在合并期间“加宽”。这意味着常量将添加到开始，另一个（更大）常量添加到src中每个跨度的结束坐标。这意味着在src spans加宽后它们可能会重叠。

到目前为止我所得到的是它不能完全就地完成，需要某种临时存储。我认为它应该在线性时间内超过src和dst求和的元素数量。

任何临时存储都可以在算法的多次运行之间共享。

我尝试过的两种主要方法是：

1. 将src的所有元素追加到dst，在追加它之前加宽每个元素。然后运行就地排序。最后使用“读”和“写”指针迭代结果向量，读指针在写指针之前运行，合并跨越。当所有元素已合并（读指针到达结尾）时，dst被截断。
2. 创建一个临时工作向量。通过重复从src或dst中选择下一个元素并合并到工作向量中，如上所述进行简单的合并。完成后，将工作向量复制到dst，替换它。

第一种方法的问题是排序是O（（m + n）* log（m + n））而不是O（m + n）并且有一些开销。这也意味着dst向量必须比实际需要的大得多。

第二个主要问题是大量复制并再次分配/释放内存。

如果您认为需要，可以更改用于存储/管理跨度/向量的数据结构。

更新：忘记说数据集有多大。最常见的情况是两个向量中的4到30个元素，并且dst为空或者src和dst中的跨度之间存在大量重叠。