c++ - 找到数字属于哪个部分的快速方法是什么(在 C++ 中使用 vector )？

Question

有很多初始IP地址和结束IP地址，如:

1. 0.0.0.0 0.255.255.255
2. 1.0.0.0 1.51.255.255
3. 1.52.0.0 1.52.255.255
4. ....

我将每个初始 IP 地址存储在一个 vector 中，例如: 0.0.0.0 -> 1.0.0.0 -> 1.52.0.0 -> .....

当有一个ip地址进来，比如“1.52.4.5”，如何找出它属于哪个段(在这种情况下它属于第三段)？

我实现了某种二进制搜索来执行此操作，但速度很慢。 而且我发现 std::binary_search 比我自己实现的二进制搜索更快。

但是 std::binary_search 不能像上面的情况那样做 ip search。 有没有像 std::binary_search 这样的快速内置函数可以做到这一点？

我是怎么做的:

我将 ip 地址转换为 unsigned int，例如: 0.0.0.0 -> 0； 0.255.255.255 -> 16777215

然后我将“从”和“到”存储在一个 vector 中，例如: vector.push_back(from) 和 vector.push_back(to)。

然后我将所有这些 vector 放入一个二维 vector 中，例如: vector < vector <无符号整型>>。

当 IP 地址出现时，首先我将其转换为 unsigned int，然后在我的二维 vector 中进行二进制搜索:

int bsearch(vector<vector<unsigned int> >arr, unsigned int key){
 int low = 0;
 int high = arr.size() - 1 ;
 int mid = 0;
 while(low <= high){
     mid = (low + high)/2;
     if(key>arr[mid][1]){
         low = mid +1;
     }
     else if(key < arr[mid][0]){
         high = mid-1;
     }
     else{
         return mid;
     }
 }
 return -1;
}

非常感谢你帮助我!

Answer 1

我不知道您是如何存储 IP 地址的，但是如果您将它们存储为字符串，速度会非常慢。

由于 IPv4 地址是 4 个字节，您可以将 'from' 和 'to' 地址存储在单个 64 位 long 中变量。

如果您的列表没有增长或至少有一个有限的大小，您可以将它存储在一个数组 (long[]) 中以避免任何对象访问开销。对于几乎所有用途，二进制搜索应该足够快 (O(log n))。

但是如果你的列表很长并且 'from' 和 'to' 的第一个字节总是相同的，你可以将你的范围分成 256 个桶每个间隔都有相应的 IP 地址的第一个字节。在每个存储桶中，您都可以执行二进制搜索。这会将搜索减少最多 8 次比较(不多，但可能足够了)。