STL喜欢具有O(1)性能的容器

Question

我找不到答案,但我很确定我不是第一个寻找答案的人.没有人知道/使用/看到一个像STL容器用双向有权访问迭代O(1)复杂的插入/删除/查找 ？
谢谢.

Answer 1

插入,擦除和查找没有具有O(1)复杂度的抽象数据类型,它还提供了双向访问迭代器.

编辑:

对于任意大的域都是如此.给定一个足够小的域,您可以使用数组和双向链表实现插入,擦除和查找的O(1)复杂度集和双向访问迭代器:

std::list::iterator array[MAX_VALUE];
std::list list;

初始化:

for (int i=0;i<MAX_VALUE;i++)
    array[i] = list.end();

插入:

if (array[value] != list.end())
    array[value] = list.insert(value);

删除:

if (array[value] != list.end()) {
    array[value].erase();
    array[value] = list.end();
}

抬头:

array[value] != list.end()

Answer 2

在实践中，使用数组（向量）并推迟插入和删除的成本可能就足够了。

通过将元素标记为已删除来删除元素，将元素插入到所需位置的 bin 中，并记住较大索引的偏移量。

插入和删除将是 O(1) 加上在方便的时候进行 O(N) 清理；查找平均时间为 O(1)，最坏情况为 O(自上次清理以来的更改次数)。