使用 std::map 查找 IP 范围
给定这样一个问题：
有一组从IP范围到地理位置信息的数据，不同地点的IP范围没有重叠，实现从单个IP地址查到相应的地理位置。
数据示例
|
1 2 3 4 5 6 |
start end geo-loc 1000 2000 北京 3000 3500 上海 4000 5000 广州 5200 5500 延安 6000 7000 西藏 |
这里将只重点说明实现方式，具体为什么这么做，仅简单介绍。std::map 有三个不太常用的成员函数：
iterator lower_bound(const key_type& key);
iterator upper_bound(const key_type& key);
pair<iterator, iterator> equal_range(const key_type& key);
实现代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#include <map> //.... struct Data { unsigned startIP; std::string geoLoc; }; // Key is the 'end IP address' typedef std::map<unsigned, Data> ipmap_t; ipmap_t ipmap; // load data // .. // find ipmap_t::iterator iter = ipmap.upper_bound(ip); if (iter != ipmap.end() && iter->second.startIP <= ip) { // found } |
按照stl的惯例，upper_bound 返回的是比查找的key大的，iter->first 最小的那个iterator。这里正好利用，找到以后，我们可以保证 ip < iter->first, 也就是IP的上界（开区间上界，不包含），所以，只需要再判断ip是否大于等于下界，也就是startIP，就可以了。
整个过程，相当的简单，明了，不需要自定义Key，不需要多余的Key比较。
为什么不用startIP作为Key并且用lower_bound查找? 我还是说一下吧，lower_bound在查找失败时，其结果等于upper_bound，这样，我们需要对查找成功和失败的情况分别处理，逻辑上要复杂很多，并且容易出错。
使用endIP作为Key并且使用upper_bound查找，可以这样理解：找到endIP大于指定IP的第一个结点，如果这个结点的startIP小于等于指定IP，它就是我们要找的结点。
Map可以应付运行中添加删除的情况，如果不需要运行中添加删除，使用排序的 vector ，再结合 std::upper_bound 就可以了，速度会更快，并且更省内存。具体代码，自己动手吧。
同样的思路，同样的方法，可以用在操作系统虚拟地址范围的查找，文件偏移范围的查找，时间范围的查找，等等，等等。
请教：
如果刚好要查的ip等于一个条目的end_ip，ip库也是[start,end]闭区间，upper_buund就不能正确返回，是不是改成lower_bound就可以了。
如果你这里的 end_ip 指的是 global_end_ip==UINT32_MAX ，在这种情况下，我文中的方法就不适用了，除非至少用 33 个 bit 来表达 ip，或者，对于这种特殊情况，单独加一个判断