1

我需要一个数据结构，其中每个元素都有一个特定的索引，但也可以使用一个键来检索。

我需要 Qt 中模型视图编程的数据结构。一方面，视图请求特定行中的元素。另一方面，模型想要插入和修改具有给定键的元素。这两个操作都应该在 O(1) 中运行。

这是我想要的一个例子：

视图看到以下内容：

list[0]: "Alice", aged 22
list[1]: "Carol", aged 15
list[2]: "Bob", aged 23

模型看到：

hash["Alice"]: "Alice", aged 22
hash["Bob"]: "Bob", aged 23
hash["Carol"]: "Carol", aged 15

我的想法如下：我有一个QList<Value>和一个QHash<Key, Value*>. 哈希指向列表中存储相应元素的位置。这是插入/编辑值的代码：

if (hash.contains(key))
    *hash[key] = value;
else
{
    int i = list.size();
    list << value;
    hash[key] = &list[i];
}

问题是这段代码并不总是有效。有时它按预期工作，但碰巧数据结构不再一致。
我怀疑，这是因为 QList 通过内存移动它的内容，因为它分配了新的空间或类似的东西。

重要的操作（应该在预期的 O(1) 中运行）：

  • 插入键/值对（将值附加到列表的末尾）
  • 使用键查找和修改值
  • 使用索引查找和修改值

其他必须可能但不必在恒定运行时间内可能的操作：

  • 按索引删除元素
  • 按键删除元素
  • 在数组中间插入
  • 交换数组/排序数组中的元素
  • 获取键的索引

我的两个问题是：

  • 是否有任何数据结构可以满足我的要求？
  • 如果没有，我该如何解决这个问题或有更好的方法？
4

1 回答 1

2

方法 1：您可以将列表索引存储在哈希中，而不是指针。然后你还有一个间接（从哈希，你得到索引，然后你从列表中检索），但它仍然是 O(1)。速度差异不应太大。

方法 2：列表和哈希都使用指针进行操作。然后它们将保持有效。但是，基于索引或键的删除将变成 O(n)，因为您必须在不对应的容器中手动查找对象。

我也想知道你想如何解决索引删除或中间插入的问题。在这两种情况下，散列都会指向错误的条目（在您的方法和方法 1 中）。在这里，您将被迫采用方法 2。

于 2012-07-31T11:16:46.477 回答