ipv4存储的数据结构+算法 - 在前缀中高效搜索

Question

我正在寻找IPV4的数据结构.它应该存储什么？前缀:(base + mask) - >例如85.23.0.0/16

base = 85.23.0.0 - > 32位无符号

mask = 16 AKA 255.255.0.0 - > char 8 bit unsigned

所以min主机是85.23.0.0,最大主机是85.23.255.255(我知道在正常情况下应该是.0.1和.255.254,但我想简化它)

我需要的主要是在存储的前缀中搜索IP的速度.例如,我给unsigned int(32位),我需要告诉它是否存在.

我用C++编写,所以我可以使用STL

现在它存储在STL集(对基数+掩码)中,我一个接一个地搜索,所以它是O(n)的排序(不包括它可能是BST树,所以走过它可能比O慢( N))

总结一下:我不需要有效的方式来存储IPV4,我需要一种有效的方法来在某些数据结构中搜索它.并且数据结构不会存储端口或族类型等.它将存储PREFIX(base + mask).

而我正在寻找数据结构+一些搜索算法.

Answer 1

为什么不使用 std:unordered_map ？应该在 O(1) 和 O(n) 之间，或者如果您想要 O(log n) 的固定性能（如果您真的只对搜索阶段的性能感兴趣），则可以使用 std:map。除非您的数据集很大，否则您可能会发现没有显着差异。