qt - 在 QMap 中查找丢失的键

Question

我有qmap一个<int , Myclass*>

键的范围为1to n_max。

当我插入地图时，我需要知道可用的最低未使用密钥。

例如，如果地图包含

<1，对象1>

<3、obj3>

当我在地图中插入下一个项目时，我希望将键分配为 2

这样做最有效的方法是什么

问候

Answer 1

您可能想要做一些事情来优化搜索。

首先，检查count()类似map.end() 的先前记录（即--）之类的内容。如果它们相同，您就知道它已满并且可以在最后添加。

如果它们不是（结束迭代器值大于count()），那么你知道你需要搜索一个洞。在搜索一个整体时，您可能希望拉出所有的uniqueKeys()，然后从它的中间开始搜索，看看中间的键是否与前一个匹配count()/2。如果不是，再往下走count()/4，否则往上走count()/4。重复直到你找到你要找的东西。

但实际上，我首先不确定地图是否是正确的容器。听起来您需要一个数组或链表，或者......这取决于您的数据。但是如果你需要用地图做上述操作我建议你可能需要找到合适的容器。

Answer 2

由于 QMap 保持项目按键排序，您可以使用 c++ 标准库中的相邻查找算法：

#include <QMap>
#include <algorithm>

bool missing (int i, int j) {
  return (i+1 < j);
}

int next_key(const QMap<int,int>& map) {
  if (!map.size()) 
    return 1; // or 0, if an acceptable key value

  QList<int>::iterator i = std::adjacent_find(map.keys().begin(), map.keys().end(), missing);

  if (i==map.keys().end()) // no missing values found
    --i; 

  return *i + 1;
}

复杂度恰好是谓词（“缺失”函数）的 (result - first) + 1 和 (last - first) - 1 应用程序中的较小者，其中 result 是返回值。