1

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

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

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

  • 这需要在两个方向上工作：由于它存储一个唯一值，我需要能够非常快速地通过实际值（100% 唯一）访问索引，因为这种情况会发生很多次。

我不能授权，任何值类型都支持运算符，<如<===!=

如果有问题，请继续提问。如果有不清楚的地方，我会进一步解释。

编辑：

既然我被要求，这背后的实际问题就来了：

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

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

我希望这会有所帮助！

编辑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

我希望这更清楚。对于第二个，可能有多个容器。

4

5 回答 5

3

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

所以，我们有像这样的索引数据（索引在括号中）：

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

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

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

因此，如果我们将要删除的元素索引称为n，假设我们实际上所做的是将 [0..n-1] 沿一个位置移动，然后用额外的值覆盖 [0] 。

讨论

如果使用向量执行此操作，则移动操作可以任意大且相对较慢。但是，如果您使用其他一些容器，例如关联容器（地图、无序地图），则无论如何您都必须更新所有这些“移动”元素的键。其他常见的容器不提供 O(log2N) 或更好的索引，所以没有希望，所以让我们坚持使用向量，看看如何最小化痛苦。除了移动是 O(N) 之外，它还涉及移动任意大的对象：在对象比指针大得多的情况下，您可以拥有一个指向对象的数组，并且只需移动数组的指针而不移动对象：这可能会快得多（它对于不喜欢被移动的对象也很有用，

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

回到您的问题的模糊性-如果您将“索引”与“键”混淆，并且只需要一个键控容器但不需要对象在每次删除/插入操作时移动其键，那么映射或无序映射就很重要了更好的选择。

于 2013-01-29T05:43:47.540 回答
2

让我们看看您的要求：

  • 按位置访问
  • 按元素访问
  • 在任意位置删除
  • 元素的单一性

如何 ？

  • 您需要带有随机访问的东西来支持“按位置访问”，或者至少接近随机访问 O(log N) 可能就足够了
  • 鉴于元素可能不支持排序，唯一性将需要使用哈希集

我认为这可以使用 Boost.MultiIndex 轻松实现。示例部分已经给出了 MRU 缓存实现，您已经足够接近了。我建议结合：

这意味着类似：

typedef multi_index_container<
  T,
  indexed_by<
    random_access<>,
    hashed_unique</*...*/>
  > 
> cache_type;

注意：要使散列索引起作用，您需要同时支持==（或专门化std::equal<T>）和散列函子。如果类型尚不支持后者，则用户可以在容器声明时提供后者。

于 2013-01-29T08:32:17.650 回答
1

如果您使用的是 boost c++ 库，请查看多索引容器。

http://www.boost.org/doc/libs/1_52_0/libs/multi_index/doc/index.html

于 2013-01-29T07:24:12.280 回答
0

好的。谢谢大家，但我找到了一个非常有效的解决方案：

由于我的问题需要以下数据结构；

[0] d1  [1] d2  [2] d3  [3] d4
[0] i1  [1] i2  [2] i3  [3] i4
[i1] 0  [i2] 1  [i3] 2  [i4] 3

我决定使用这些容器：

  1. list
  2. list
  3. map

通过一些研究，我发现了std::advance和std::next，这使我能够有效地访问list. 要更新地图，我将只运行一个简单的 for 循环，它应该会非常有效。

如果您有更好的想法，请在此处发布！

再次感谢你！

于 2013-01-29T06:47:34.237 回答
0

只是想指出 multi_index_container 解决方案与使用向量支持随机访问具有同样的低效率：删除的成本与数据结构的大小成线性关系。在内部，random_access 索引使用类似于指针向量的数据结构。

没有那么多的数据结构允许在优于线性的时间内随机访问和删除任何元素。AFAIK std::deque 具有线性时间删除，除非该项目接近序列的末端之一。

这给我们留下了平衡的二叉树（和变体，如跳过列表）。自平衡二叉树可以以固定开销保持任何节点下方的子树的大小，并通过这种“增强”实现 O(log n) 中的随机访问。不幸的是，std::map 的默认实现通常没有这个特性。因此，使用 std::map 和 std::advance 可为您提供线性时间随机访问。您无法在 std::map 的“顶部”实现有效的随机访问，因为您的用户代码不知道 std::map 在内部完成的树操作。

您可以自己滚动（AVL 树相对容易实现）。除非您愿意接受随机访问查找或删除+插入操作的性能不佳，否则想不出任何更简单的方法。不涉及树的“最坏”解决方案可能是使用 std::deque

编辑：我提到的增强树数据结构被称为http://en.wikipedia.org/wiki/Order_statistic_tree。

于 2013-06-30T16:42:06.783 回答