这就是情况我有一个名为gallery的未排序数组（非常大），它包含成对的模板（std::vector<uint8_t>）及其关联的id（std::string）。
我有一个函数，其中向我提供了一个模板，并且必须返回库中最相似模板的id（我使用余弦相似度在模板之间生成相似度得分）。
我考虑使用this post中讨论的堆。
但是，问题是库可以包含多个不同的模板，这些模板属于一个ID。在我的函数中，我必须返回k唯一的ID。
为了上下文，我正在做一个面部识别应用程序。我可以有多个不同的模板属于我的库中的一个人（此人是使用多个不同的图像注册到库中的，因此多个模板属于他们的id）。搜索函数应该将大多数相似的人返回到提供的模板（因此不会多次返回相同的id）。
将欣赏一个有效的算法，这样做在C++中。
编辑：为我建议的堆解决方案截取的代码（不能正确处理重复项）
std::priority_queue<std::pair<double, std::string>, std::vector<std::pair<double, std::string> >, std::greater<> > queue;
for(const auto& templPair : m_gallery) {
try{
double similairty = computeSimilarityScore(templPair.templ, idTemplateDeserial);
if (queue.size() < candidateListLength) {
queue.push(std::pair<double, std::string>(similairty, templPair.id));
} else if (queue.top().first < similairty) {
queue.pop();
queue.push(std::pair<double, std::string>(similairty, templPair.id));
}
} catch(...) {
std::cout << "Unable to compute similarity\n";
continue;
}
}
// CandidateListLength number of IDs with the highest scores will be in queue
这里有一个希望能帮助你的例子。为了简单起见，我假设已经为模板计算了相似度得分。
模板1：相似度得分：0.4，id:cyrus
模板2：相似度得分：0.5，ID:James
模板3：相似度得分：0.9，ID:Bob
模板4：相似度得分：0.8，ID:Cyrus
模板5：相似度得分：0.7，ID:Vanessa
模板6：相似度得分：0.3，ID:Ariana
获取前3个评分模板的ID将返回[Bob、Cyrus、Vanessa]
最佳答案
使用std：：set structure（balanced BST）而不是heap它还按顺序放置元素，让您可以找到插入的最大和最小元素。此外，当使用insert函数时，它会自动检测到一个重复项并忽略它，因此内部的每个元素都将始终是唯一的。复杂性是完全相同的（因为一个较大的常数，它有点慢）。
编辑：我可能不太理解这个问题。据我所见，您可以拥有多个具有不同值的元素，这些元素应该被视为重复元素。
我会做什么：
用对（模板值，ID）创建一个集合
制作一个映射，其中key是ID，value是当前集合中模板的模板值。
如果要添加新模板：
如果它的身份证在地图上-你找到了一个副本。如果它的值比映射中与id配对的值差，则不要执行任何操作，否则从set和insert（new value，id）中删除一对（old value，id），将映射中的值更改为新值。
如果它不在地图中，只需将其添加到地图和集合中。
当集合中的项目太多时，只需从集合和映射中删除最差的项目。