c++ - 具有 O(1) 性能的类似 STL 的容器

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()