在Java里，我常常使用Hashmap完成一些键值对的操作，Hashmap在查找Key时具有时间复杂度低的特点，在C++的STL库中也有着同样的类型，只不过操作略有不同。在完成CCF认证的一道题的过程中，我通过使用map使得这道题的运行时间大大降低。本文将简述我的思路和做法。下面先展示题目
看到这个题，为了存储垃圾位置信息，我的第一反应是使用抽屉原则，即建立一个bool型二维数组，初值为false，然后如果一个点有垃圾，就设为true。但是这个方法有以下几个问题：
1.对于测试点6、7和8，bool型二维数组的空间过大，10^9*10^9的数组会产生大量的存储空间浪费，事实上n<1000，即最多也只有1000个点。而且CCF对于运行空间也有所限制，一个bool型占用1个字节（注意不是1比特），也就是说对于测试点6、7、8，就会使用10^18字节，这显然超出了空间限制。
2.对于9、10测试点，由于坐标可能为负，如果使用上面的方法，数组会越界。即使将负空间映射到正数，也会导致1.的问题，而且映射后可能会超过int上界，还需使用unsigned int。
3.使用这种方法还需要建立一个vector来存储每一个点的坐标信息用于遍历。
当然很自然的，我也想到了一个用时间换空间的方法，即仅使用上述3.提到的存储每个点的vector，对于每个点，遍历vector看是否能找到其上下左右四个点，如果可以，再次遍历看是否可以找到四个评分点从而计算分数。这个算法的时间复杂度至少是O(n^2),有没有更好的方法呢，那就是使用map了。
建立一个map<point,bool>，这里将坐标信息自定义为一个结构体point作为Key，如果一个点有垃圾，就将该点写入map。因为在map中查找一个Key的时间复杂度是很低的，而且在这里就算Key是自定义类型，也和java一样不用自己写operator==（java里面为equalTo()）,编译器会根据比较各个成员的值，如果所有
成员的值都一样，这个Key才会被匹配。
但是需要注意的是，在C++STL库中的map不是Hashmap,就是说它不是使用hash函数去查找key的，而是通过排序查找的， map中的元素是自动按Key升序排序 ，所以如果Key为自定义类型，需要自己实现 operator<，否则是无法通过编译的，需要注意的点在代码中通过注释的形式展现了出来：
#include<iostream>
#include<map>
using namespace std;
/*test:
11
9 10
10 10
11 10
12 10
13 10
11 9
11 8
12 9
10 9
10 11
12 11*/
struct point{
int x, y;
point(int x, int y) : x(x), y(y) {};
//在使用map并将自定义类型作为Key时，必须实现下面这个函数，因为
//map中的元素是自动按Key升序排序,当Key是一个结构体,涉及到排序
//就会出现问题,因为它没有小于号操作,insert等函数在编译的时候过
//不去,所以加上小于号的实现即可,记得要加const
bool operator<(point const& x1) const {
if (x1.x == x) return y < x1.y;
return x < x1.x;
}
point up() {
return point(x, y + 1);
}
point down() {
return point(x, y - 1);
}
point left() {
return point(x - 1, y);
}
point right() {
return point(x + 1, y);
}
point upright() {
return point(x + 1, y + 1);
}
point upleft() {
return point(x - 1, y + 1);
}
point downleft() {
return point(x - 1, y - 1);
}
point downright() {
return point(x + 1, y - 1);
}
};
int main() {
map<point, bool> m;
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
point p(x, y);
m.insert(pair<point, bool>(p, true));
}
int a[5] = { 0 };
map<point, bool>::iterator iter; //设置迭代器
for (iter = m.begin(); iter != m.end(); iter++) {
point t = iter->first; //获取迭代器指向的pair的key
if (m.count(t.up()) && m.count(t.down()) && m.count(t.left()) && m.count(t.right())) { //该点具备合法条件，可以对其评分
int score = m.count(t.upright()) + m.count(t.downright()) + m.count(t.downleft()) + m.count(t.upleft());
a[score]++;
}
}
for (int i = 0; i < 5; i++) {
cout << a[i] << endl;
}
return 0;
}最后的运行时间如图所示：
