使用C++标准库实现高效间隔存储

里面没有集装箱 std 这可以满足你的要求。

任何序列容器都不能插入到小于O(size())的任意位置。 vector , deque 和 inplace_vector 有O(大小) insert . list 和 forward_list 进行O(大小)查找。

关联或无序关联容器都无法在小于O(i)的范围内找到第i个索引。 std::advance et.al是O(i),除非迭代器满足 随机存取迭代器 ,但这些容器的情况并非如此。

容器适配器都没有帮助,因为它们仍然具有底层容器的插入特性。

您需要实现自己的容器来满足您的复杂性要求。类似于A Indexable Skip List 将工作。

在实践中:

• 使用排序向量,确保isnert保持排序
• 按间隔开始排序
• 插入使用 std::lower_bound ,比较间隔的开始,以找到插入位置(O log N)。
• 检查是否与找到的项目和之后的项目重叠。(O 1)

如果没有冲突,请在给定位置插入(列表为O(1),向量为O(N),但在许多实际情况下,后者可能仍然更快。)

理论上:使用 std::map 相反。满足Big-O,但对于那个元素大小,当Big-O开始重要时,它可能会变慢。

您可以通过将间隔标记为“未使用”来“降低”擦除成本;例如通过使它们等于长度0。这意味着插入必须检查的不仅仅是直接的继承者,而且它仍然在摊销O(1)附近 除了 对于最坏的工作负载。