各路大佬们！单 IP， IP 段， CIDR 之间如果做集合运算。

[YahuiAn]

用户输入支持如下格式：

10.0.17.35

192.168.1.1/23

www.baidu.com

192.37.3.3-192.168.39.39

现在有一个黑名单功能，也支持如上的形式，想问问这两个集合如何高效的去重呢？

😝

[GeruzoniAnsasu]

首先不考虑域名和 url

我当时的实现大概这样

一个 - 指定的范围可以解析成若干个 cidr 或 ip

那现在只需要考虑 cidr 一种情况（ ip 可以看做 /32 ）
用二叉 trie 来存这些 cidr，在深度为 N 的节点有一个 cidr 对象表示这个 cidr 是 /N

如果某个节点左右子树都存在则递归向上合并节点

插入过程中途遇到某个节点说明这节点已经包含了待插入地址，跳过

然后就没有去重这一说了，匹配就是走这个 trie 跟插入流程几乎一样的

当时没有去重合并完还要导出合并结果的需求

[GeruzoniAnsasu]

还有一种方式是直接把 ip 地址算成线性空间，每个区间有左右界，合并的时候先按左界排序，然后判断
下一个区间的左界有没有落在前一个区间中，如果在，那么区间右界设成下一个区间右界，如果否，那么第一个区间已处理完毕，可以处理 23 区间

[wbrobot]

ip2long，然后算数

[msg7086]

听上去就是个和 trie 差不多的结构。

[singerll]

转换为 10 进制？