在多图中为一个键找到两个最大值

Question

我有一个 multimap 由一个键组成，键是一对整数，键的值是浮点数。现在我想为我的所有键设置最大的 2 个值。
在我的示例中，键 (1, 1) 应产生值 5.8 和 3.7。
键 (2, 2) 应生成 2.4 和 1.5。
需要指出的是：我不知道我的钥匙的数量和外观。所以我不知道键 (2, 2) 是否存在。

代码如下：

int main(int argc, char** argv)
{
    // Create some values - both vectors have the same size
    // The pairs and the thetas may be unsorted
    vector<pair<int, int>> pairs;
    pairs.push_back(make_pair(1, 1));
    pairs.push_back(make_pair(1, 1));
    pairs.push_back(make_pair(1, 1));
    pairs.push_back(make_pair(2, 2));
    pairs.push_back(make_pair(2, 2));
    pairs.push_back(make_pair(3, 3));
    pairs.push_back(make_pair(3, 3));
    pairs.push_back(make_pair(1, 1));

    vector<float> theta;
    theta.push_back(1.4);
    theta.push_back(2.4);
    theta.push_back(3.7);
    theta.push_back(2.4);
    theta.push_back(1.5);
    theta.push_back(1.6);
    theta.push_back(2.4);
    theta.push_back(5.8);

    multimap<pair<int, int>, float> similarities;

    for (size_t i = 0; i < pairs.size(); i++) {
        similarities.insert(make_pair(make_pair(pairs[i].first, pairs[i].second), theta[i]));
    }

}

在我的特定情况下，我不知道在我的多重映射中定义了哪些密钥对。我也认为 multimap 可能不是正确的选择，但我不确定哪种类型更好。
我试图保留 theta 的矢量格式，但很难跟踪相关对。

Answer 1

希望我没猜错：

auto range = similarities.equal_range(make_pair(1,1));

size_t found = 0; float highest, second_highest;

if (range.first != similarities.end() && range.first != range.second) {
  ++found;
  highest = (*std::max_element(range.first++, range.second)).second;
  if (range.first != range.second) {
    ++found;
    second_highest =
      (*std::max_element(range.first++, range.second, [&](auto a, auto b){ return a.second < b.second && b.second < highest; })).second;
  }
}

if (found > 0)
  std::cout << highest<< std::endl;
if (found > 1)
  std::cout << second_highest << std::endl;

以上不会给你两次相同的值。

Answer 2

这里有几个选项。

保留现有的 multimap 并对值进行线性搜索以找到两个最大的值。
改用map<pair<int, int>, set<float, std::greater<float> > >，然后在查找密钥后可以立即访问前两项。
使用map<pair<int, int>, vector<float> >并保持向量在插入时排序。执行比插入更多的查找时更好。
当需要检索最高的两个值时，使用map<pair<int, int>, vector<float> >和partial_sort前两项。做更多的插入比查找更好。

在多图中为一个键找到两个最大值

Find two biggest values for one key in a multimap

c++

key

multimap

std-pair