c++ - 具有随机访问元素删除的类队列数据结构

Question

是否有类似队列的数据结构也支持在任意点移除元素？入队和出队最常发生，但是队列中的元素移除在速度方面必须相似，因为在某些时期内这可能是最常见的操作。性能的一致性比绝对速度更重要。时间比内存更重要。队列长度很小，在绝对峰值负载下不到 1,000 个元素。如果不是很明显，我会明确说明:不需要随机插入。

已标记 C++，因为这是我的实现语言，但我没有使用(也不想使用)任何 STL 或 Boost。仅限纯 C 或 C++(我会将 C 解决方案转换为 C++ 类。)

编辑:我想我想要的是一种也有队列接口(interface)的字典(或也有字典接口(interface)的队列)，这样我就可以做这样的事情:

Container.enqueue(myObjPtr1);
MyObj *myObjPtr2 = Container.dequeue();
Container.remove(myObjPtr3);

Answer 1

我认为双链表正是您想要的(假设您不想要优先级队列):

1. 简单快速地向两端添加元素
2. 从任何地方轻松快速地删除元素

您可以使用 std::list 容器，但是(在您的情况下)很难删除元素 如果您只有一个指向元素(包装在 STL 的列表元素中)的指针(或引用)，则从列表的中间开始，但是 你没有迭代器。如果使用迭代器(例如存储它们)不是一个选项——那么实现一个双链表(即使有元素计数器)应该很容易。如果您实现自己的列表 - 您可以直接操作指向元素的指针(每个元素都包含指向其两个邻居的指针)。如果您不想使用 Boost 或 STL，这可能是最好的选择(也是最简单的)，并且您可以控制一切(您甚至可以为列表元素编写自己的 block 分配器以加快速度事物)。