使用 std::map 查找 IP 范围

给定这样一个问题：

有一组从IP范围到地理位置信息的数据，不同地点的IP范围没有重叠，实现从单个IP地址查到相应的地理位置。

数据示例

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);

实现代码：

#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 就可以了，速度会更快，并且更省内存。具体代码，自己动手吧。

同样的思路，同样的方法，可以用在操作系统虚拟地址范围的查找，文件偏移范围的查找，时间范围的查找，等等，等等。