HM235 倒序词典

来源： 第 235 集 map容器-排序

难度： 普及-

时间限制： 1s

空间限制： 64MB

题目描述

map 默认按键从小到大排列。插入顺序打乱也一样，因为默认比较器已经在创建时定死。想改成按键从大到小，必须在**尚未插入**时，于模板参数的第三位放入仿函数类型。插完再改已经来不及。

仿函数是重载了函数调用运算符 () 的类。对两个 int 键做降序时，返回布尔值，并在“前一个键大于后一个键”时为真。把这个类型写进 map<int, int, MyCompare>。遍历用的迭代器也要带上 MyCompare。

键若是自定义类型，同样必须指定排序规则，否则编译器不知道该比姓名还是年龄，插不进去。本题键和实值都是整数。

读入若干键值对，分别插入默认升序表 m1 和创建时就指定降序仿函数的表 m2。按各自迭代器顺序打印。

输入格式

第一行一个整数 \(n\)。

接下来 \(n\) 行，每行两个整数 \(k\)、\(v\)。当 \(n=0\) 时没有这些行。

输出格式

第一行：m1（按键升序）。

第二行：m2（按键降序）。

一对写成 key:value，对与对之间一个空格。空表输出空行。

样例

输入 #1

5
1 10
2 20
5 50
3 30
4 40

输出 #1

1:10 2:20 3:30 4:40 5:50
5:50 4:40 3:30 2:20 1:10

输入 #2

3
2 20
1 10
2 99

输出 #2

1:10 2:20
2:20 1:10

说明

\(0 \le n \le 1000\)，键与值的绝对值不超过 \(10^9\)。重复键进不去。

不要插完再拷到数组里排序。必须在创建 m2 时放入仿函数，插入过程中按该规则落点。样例 #1 即使按 \(1,2,5,3,4\) 插入，升序仍是 \(1\) 到 \(5\)，降序是 \(5\) 到 \(1\)。