学步园

最近一个项目，需要根据给定的IP地址，查出它的线路类型（电信、网通、铁通……），很明显，二分法的效率比线性搜索要高，虽然目前IP表只有300条记录，但是好的算法总是应该被使用的。

抽象声明：

class IpKind {
public:
virtual ~IpKind(void) {}
virtual bool addItem(const unsigned ip, const unsigned mask, const int kind) = 0;
virtual bool find(const unsigned ip, int & outKind) = 0;
}; 

利用stl中map容器的实现：

using namespace std;
class IpKindImpl : public IpKind {
public:
bool addItem(const unsigned ip, const unsigned mask, const int kind) {
        MASK_CONTAINER::iterator itMask = maskContainer_.find(mask);
if (maskContainer_.end() == itMask)
            itMask = maskContainer_.insert(MASK_CONTAINER::value_type(mask, IP_CONTAINER())).first;
return itMask->second.insert( IP_CONTAINER::value_type(ip & mask, kind) ).second;
}
bool find(const unsigned ip, int & outKind) {
for (MASK_CONTAINER::const_iterator itMask = maskContainer_.begin();
            maskContainer_.end() != itMask; ++itMask)
{
unsigned maskedIP = ip & itMask->first;
            IP_CONTAINER::const_iterator it = itMask->second.find(maskedIP);
if (itMask->second.end() != it) {
                outKind =it->second;
return true;
}
}
return false;
}
private:
typedef map IP_CONTAINER;
typedef map MASK_CONTAINER;

    IP_CONTAINER ipContainer_;
    MASK_CONTAINER maskContainer_;
};

经测试，在一个只有300个记录的表中搜索给定IP地址，这个实现的速度是线性搜索的15倍，且随着记录的增多，“速度比”呈几何倍数递增。