代码之家 › 专栏 › 技术社区 › b39b332d

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

data-structures algorithm c++

0

b39b332d · 技术社区 · 1 年前

我正在研究一个问题,其中每对代表一个封闭区间,我需要一个数据结构来存储这些对的集合。此数据结构应支持两种操作:插入(配对)和删除(idx)。插入操作需要检查要插入的间隔是否与集合中的任何现有间隔重叠;如果有重叠,插入应该失败并返回-1。删除操作应删除集合中第idx个最大的对。

我的目标是只使用C++标准库来实现这一点,同时尽可能减少代码。此外,插入和删除方法的时间复杂度必须小于O(log n),这一点至关重要。

我非常感谢您就如何在不需要编码的情况下高效实现这一目标提出的任何建议或想法。非常感谢您的帮助!到目前为止,我提出的唯一解决方案是使用B+树,但它需要一点代码。

class CustomDataStructure {
// some underlying private data structures
public:
    bool insert(pair<int ,int> interval);
    bool delete(unsigned int idx);
}

2 回复 | 直到 1 年前

1

2

Caleth 1 年前

里面没有集装箱 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 将工作。

2

0

peterchen 1 年前

在实践中:

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

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

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

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