根据pair的第一个值对映射排序

Question

假设我必须将我的映射描述为:

map<int, pair<long, int>> mp;

现在我插入元素为:

int y; long x;
pair<long, int> p;
for(int i = 0; i < 5; i++)
{ 
cin >> x >> y;
p.first = x;
p.second = y;
mp.insert({i, p});   // What is wrong here syntax wise?
}

进一步，我想根据这对的第一个值对它排序。

Answer 1

你可以在这里使用一个小技巧。

c++中的Map自动按键对所有内容进行排序，因此您可以执行以下操作=>

map <long, (set,vector) < int > > mp; //Create this kind of map
//it will sort elements by first value and depending on your needs, select vector or set
//if you need to sort elements by second value use set
//if you do not care about it use vector
long x;
int y;
for (int i = 0; i < n; i++)
{
cin >> x >> y;
if (mp.find(x) != mp.end()) // if element exist
{
mp[x].push_back(y); // add it to vector
}
else
{
mp[x] = vector < int > (); // if not create new vector
mp[x].push_back(y); // and then push new element
}
}

Answer 2

按键索引排序的std::map。句号。

我只能想象两种可能的方法让它按照的值排序:

• 反转结构，让元素给出订单作为键(这是@ suspicious的答案)
• 使用数据库世界中所谓的二级索引，这是一个辅助的东西将根据您的要求进行排序，并指向真实的数据。

在这里，如果你可以接受在使用它之前对它进行一次排序，我会使用整数向量(你实际映射的键)(如果你的映射在填充后不改变，则不同)或std::multimap，如果你想要能够轻松添加(或删除)项目。

multimap<long, int> indices;
for (auto elt : mp) {
indices.insert({ elt.second.first, elt.first });
}

你现在可以处理你的排序映射:

for (auto index : indices) {
auto elt = mp.find(index.second); // *elt will give the elements in order
...
}

你只需要更新indicesmultimap每当你添加或删除元素到原来的mp映射。