合适的数据结构

Question

如何实施的分组的缓冲器，其中每个分组是以下形式：

typedef struct{ 
    int32 IP;  //4-byte IP-address 
    int16 ID;  //unique sequence id 
}t_Packet; 

什么应该是最合适的数据结构，其中：

（ 1）允许收集至少8000个这样的数据包（快速插入和删除操作）
（2）允许使用IP地址进行非常快速的过滤，以便只有具有给定IP的数据包才会被选中
（3）允许非常快速的查找操作使用ID作为密钥（4）允许非常快（2），然后（3）在过滤结果内？

RAM大小很重要，例如，没有庞大的查找表是可以使用的。

Answer 1

您可以使用Patricia Trie的IP地址过滤。我相信大多数网络路由器都将这种数据结构用于IPV4 IP地址。还有其他一些针对IP地址设计的尝试，您可以考虑使用。这里是一个：http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.35.4871

相应于每个IP地址，你现在可以有一个基于ID的散列表。

如果IP地址是'充分'随机的，那么使用散列表进行基于IP的过滤可能会更好，但是，由于IP地址很适合大多数机器的单词，使得散列查找非常快而这种方法可能并不能真正为你节省太多空间。

当然，正确的选择取决于你的情况...

Answer 2

为数据创建两个索引（为快速插入等而非按顺序存储），一个按ID分割树，另一个按IP分割树。

如果您不能承担至少8000 * sizeof（Packet）+ 8000 * 12 + 8000 * 12的数据+两个索引，那么老实说，迭代8000个项目并不会花太长的时间。

这将是很容易用C++实现比C（如果仅仅是因为你可以使用boost :: multi_index，或类似）