如何获取键为int对的multimap中每个键的两个最大值

Great question! Since std::multimap groups all entries with the same key together (it’s ordered by key), we can leverage this to efficiently extract the top two largest values for each unique key. Here’s a step-by-step solution:

Core Approach #

1. Iterate through the multimap, processing each unique key’s range of values using equal_range.
2. For each key’s values, track the two largest values in a single pass (no need to sort the entire list—saves performance if you have many entries per key).
3. Store results in a map where each key maps to its top two values (handling cases where a key has only one value).

Complete Working Code #

#include <iostream>
#include <map>
#include <vector>
#include <limits>
#include <utility>

int main(int argc, char** argv) {
    // Populate the multimap with sample data
    std::multimap<std::pair<int, int>, float> my_multimap;
    my_multimap.insert({{1, 1}, 3.7});
    my_multimap.insert({{1, 1}, 5.8});
    my_multimap.insert({{1, 1}, 2.1});
    my_multimap.insert({{2, 2}, 1.5});
    my_multimap.insert({{2, 2}, 2.4});
    my_multimap.insert({{3, 3}, 7.2}); // Key with only one value

    // Map to store top values per key (vector holds up to 2 elements)
    std::map<std::pair<int, int>, std::vector<float>> top_values;

    auto it = my_multimap.begin();
    while (it != my_multimap.end()) {
        const auto& current_key = it->first;
        // Get all entries for the current key (contiguous in multimap)
        auto [range_start, range_end] = my_multimap.equal_range(current_key);

        float max1 = -std::numeric_limits<float>::infinity();
        float max2 = -std::numeric_limits<float>::infinity();

        // Iterate through values to find top two
        for (auto range_it = range_start; range_it != range_end; ++range_it) {
            float val = range_it->second;
            if (val > max1) {
                max2 = max1;
                max1 = val;
            } else if (val > max2) {
                max2 = val;
            }
        }

        // Collect valid max values
        std::vector<float> current_top;
        if (max1 != -std::numeric_limits<float>::infinity()) {
            current_top.push_back(max1);
            if (max2 != -std::numeric_limits<float>::infinity()) {
                current_top.push_back(max2);
            }
        }

        top_values[current_key] = current_top;
        // Move to next unique key
        it = range_end;
    }

    // Print results
    std::cout << "Top values per key:\n";
    for (const auto& entry : top_values) {
        const auto& key = entry.first;
        const auto& values = entry.second;
        std::cout << "Key (" << key.first << ", " << key.second << "): ";
        for (size_t i = 0; i < values.size(); ++i) {
            if (i > 0) std::cout << ", ";
            std::cout << values[i];
        }
        std::cout << "\n";
    }

    return 0;
}

Key Details #

• equal_range: Returns a pair of iterators defining the start/end of all entries for a key. Since multimap is ordered, these entries are contiguous.
• Tracking Top Values: Initializing max1/max2 to negative infinity ensures we handle negative float values correctly. We update these variables in one pass through the key’s values.
• Edge Cases: If a key has only one value, we store just that value. If you’re using C++ versions older than C++17, replace the structured binding with explicit iterator pairs:

  std::pair<std::multimap<std::pair<int, int>, float>::iterator, 
            std::multimap<std::pair<int, int>, float>::iterator> range = my_multimap.equal_range(current_key);
  auto range_start = range.first;
  auto range_end = range.second;
  

Sample Output #

Top values per key:
Key (1, 1): 5.8, 3.7
Key (2, 2): 2.4, 1.5
Key (3, 3): 7.2

内容的提问来源于stack exchange，提问作者Grillteller