C++ map<int,pair<long,int>>插入语法问题及按pair首元素排序方法

插入代码的语法问题 #

你的这段插入代码的语法问题和C++版本支持有关：

• 如果你的编译器没有开启C++11及更高版本的编译支持，mp.insert({i, p})中的统一列表初始化语法是非法的，会直接触发编译报错。解决方法是显式构造键值对，修改为以下两种写法之一即可：

  mp.insert(std::make_pair(i, p));
  // 或者显式指定类型
  mp.insert(std::pair<int, std::pair<long, int>>(i, p));
  

• 如果已经开启C++11及以上的编译选项，这段代码本身没有语法错误，但要注意insert的行为特性：如果键i已经存在于map中，插入操作会静默失败，不会更新对应的值。如果需要覆盖已有键的值，建议用mp[i] = p的写法。

按pair第一个值排序的实现方案 #

注意：std::map默认是按键(Key)的升序排序，排序规则仅作用于键，无法直接按值(Value)中的字段排序，有两种成熟的实现方案可选：

方案1：调整map结构（推荐，性能最优）

直接把需要排序的pair<long, int>的第一个元素（也就是你代码里的x）作为map的键，修改map定义：

// 键为需要排序的long类型x，值存储原来的索引i和int类型的y
std::map<long, std::pair<int, int>> mp;

插入代码对应调整为：

for(int i = 0; i < 5; i++)
{ 
    std::cin >> x >> y;
    mp.insert({x, {i, y}});
}

修改后map会自动按你需要的规则排序，无需额外操作，性能和原生map完全一致。

方案2：拷贝后自定义排序

如果你必须保留原有map<int, pair<long, int>>的结构，可以把所有元素导出到vector后自定义排序规则：

#include <vector>
#include <algorithm>

// 将map所有元素转存到vector
std::vector<std::pair<int, std::pair<long, int>>> vec(mp.begin(), mp.end());
// 按pair第一个元素升序排序，要降序就把 < 改为 >
std::sort(vec.begin(), vec.end(), [](const auto& a, const auto& b) {
    return a.second.first < b.second.first;
});

排序完成后遍历vec即可得到符合要求的顺序。

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