C++ 最佳键值容器，可按值排序并快速访问删除

Question

我目前面临的问题可能是由于我在此类问题上缺乏经验。

我需要一个 Key-Value 容器，其中的键是一个唯一的特定值和一个基本类型 (double) 的值。我的应用程序会为每个候选项构造一个这种类型的容器，并存储该候选项被识别为特定类型的概率(double 值)(Key 值，实际上是一个枚举)。

然后我需要以最高概率对其进行排序，并从每个容器中选择最高的候选者，同时从其他每个容器中删除所选类型。

谢谢。

编辑:关于这个问题的更多解释。

我有一张图片，通过图片分析，我在上面找到了几个对象。这些对象将与一个类型匹配，算法返回该对象属于该类型的概率。假设我只有 3 个对象和 3 种类型，我将有 3 个容器，每个对象一个:

对象 A

类型 1 - 95%

类型 2 - 87%

类型 3 - 15%

对象 B

类型 2 - 85%

类型 1 - 23%

类型 3 - 5%

对象 C

类型 3 - 91%

类型 1 - 10%

类型 2 - 1%

如您所见，我将以 3 个容器结束，现在我将看看哪种容器更适合这些类型。由于每个容器的最高概率为 95%(对于对象 A)，我现在将说对象 A 是类型 1。我将继续从其他容器中删除该键的所有条目。现在我会:

对象 B

类型 2 - 85%

类型 3 - 5%

对象 C

类型 3 - 91%

类型 2 - 1%

该操作将重复。最高概率是对象 C 上的类型 3，有 91%，所以我现在对象 C 是类型 1。我现在将删除剩余容器中类型 1 的所有候选对象，并以:

对象 B

类型 2 - 85%

对象 B 现在将以类型 2 结束。

Answer 1

您可以使用完全不同的数据存储和算法。这是一些伪代码:

let data = vector<(object ID, type, probability)>;
run image analysis and fill data;
sort data on probability descending;
let seen_types = set<type>;
let seen_objects = set<object ID>;
for each tuple (oid, type, probability) in data {
  if (seen_types contains type or seen_objects contains oid) continue;
  assign type to oid;
  insert oid into seen_objects;
  insert type into seen_types;
}

删除操作是浪费时间。无论哪种方式，您都需要访问每条数据一次，并且重新排列数据以删除您不再看到的内容远比在进行时忽略它要复杂得多。对这两个集合使用哈希集或可能的位集(取决于对象 ID 和类型的形状)，这为您提供 O(1) 插入和查找，并且您的算法在数据数量上为 O(NlogN)项目(即对象类型)，这是当您需要对排序概率采取行动时可以达到的最低限度。