c++ - 有效的容器，保持顺序并快速从任何位置删除元素

Question

我正在寻找满足我以下需求的 C++ 容器:

• 我需要按索引删除元素。
• 删除一个元素后，我会在前面插入另一个元素(总是!!!!!!)
• 除此之外，尺寸没有变化。
• 它需要被索引。
• 存储在容器中的值是唯一的，作为索引。
• 一个索引应该分配给一个值。除非我删除或添加一个值。然后应该调整索引。

对于与该容器并行工作的另一组数据，我需要一个具有这些功能和这些附加功能的数据集:

• 这个需要在两个方向上工作:因为它存储了一个唯一值，我需要能够通过实际值(100% 唯一)非常快速地访问索引，因为这种情况会经常发生次。

我不能保证任何值类型都支持像 < 这样的运算符, <= , ... 除了 ==和 !=

如有疑问，请继续提问。 如果有什么不明白的地方，我会进一步解释。

编辑:

自从我被要求以来，这背后的实际问题就来了:

我正在编写一个由模板容器类组成的库，它能够存储一定数量的对象。所有这些对象都是同一类型。 (嗯，当然...)这些对象的另一个非常重要的属性必须是，它们可以通过唯一索引重新创建。该索引也可以是任何东西。在这种情况下的一个例子是二维空间，您可以在其中创建位于平面上的对象，并且可以通过为对象类提供坐标(在这种情况下作为单个对象)来重新创建所有属性。 现在，当容器达到最大容量时，它会删除上次使用的对象。我的想法是，你给容器一个唯一的索引。如果仍然存储所需的对象，则该函数返回对象上的指针并将其移到内部容器中的前面。如果所需对象未存储在内部容器中，则内部容器中的最后一个对象将被删除，并生成新的对象并放在最前面。

我需要这个，因为我有一个程序可以轻松使用我所有的 RAM，甚至更多。好吧，我每次都可以生成和销毁对象，但这对我来说似乎是在浪费计算能力。所以我想出了这个容器，它只删除对象，如果它没有被使用很长一段时间。这在我的特殊情况下非常有用(在 HUGE map 上寻找路径)

希望对您有所帮助!

编辑 2:

好的。我会更清楚地说明这一点。

让我们从一个简单的数据缓存开始:

[0] d1  [1] d2  [2] d3  [3] d4

现在假设我使用了 d3。 该结构现在应如下所示:

[0] d3  [1] d1  [2] d2  [3] d4

现在我向容器 (d5) 添加一个全新的元素。

[0] d5  [1] d3  [2] d1  [3] d2

这就是背后的想法。现在代替 int -values 作为索引，我允许有一个自定义索引类，它能够恢复每个可能被删除的对象(这不是问题。只是为了让我的类工作的要求)。

让我们从开头的陈述开始。第一种情况看起来像这样:

[0] i1  [1] i2  [2] i3  [3] i4
[i1] 0  [i2] 1  [i3] 2  [i4] 3

第二个例子是这样的:

[0] i3  [1] i1  [2] i2  [3] i4
[i1] 1  [i2] 2  [i3] 0  [i4] 3

最后的状态是这样的:

[0] i5  [1] i3  [2] i1  [3] i2
[i1] 2  [i2] 3  [i3] 1  [i5] 0

我希望这能让它更清楚。对于第二个容器，可能不止一个容器。

Answer 1

抱歉 - 我发现你的问题有点含糊 - 但我会说明我认为你的要求必须是什么，然后讨论数据结构需求...

因此，我们对数据进行了索引 - 类似这样(索引在括号中):

[0] a  [1] h  [2] b  [3] q

您的主要操作是删除/插入 - 假设我们确实删除了元素 2 并插入了值 x，我们将有:

[0] x  [1] a  [2] h  [3] q

因此，如果我们将被删除的元素索引称为 n，假设我们有效地完成了将 [0..n-1] 移动到一个位置，然后用额外的值(value)。

讨论

如果您对 vector 执行此操作，则移动操作可以任意大并且相对较慢。但是，如果您使用其他一些容器，例如关联容器( map 、无序 map )，您无论如何都必须更新所有这些“移动”元素的键。其他常见容器不提供 O(log2N) 或更好的索引，因此前景不佳，所以让我们坚持使用 vector，看看如何最大程度地减少痛苦。除了移动是 O(N) 之外，它还涉及移动任意大的对象:在对象比指针大得多的情况下，您可以有一个指向对象的数组，只移动数组的指针而不移动对象: 这可能会快得多(它对于不喜欢被移动的对象也很有用，典型的原因是 C++11 引入移动运算符的 C++03 复制缓慢)。

我想不出比这种 vector 方法更好的方法了。

回到你的问题的含糊之处 - 如果你混淆了“索引”和“键”并且只需要一个键控容器但不需要对象在每次删除/插入操作时移动它们的键，那么 map 或无序 map 是一个更好的选择。