c++ - 保存 URI 主机名的容器

Question

我遇到了一个问题，可能需要使用更不寻常的数据结构，但我不确定。

本质上，我想将 URI 主机名存储在容器中，并能够查询容器以判断主机名是否存在于容器中。但是，如果容器包含某个主机名的高级域，我希望查询在查找较低级域时返回 true。换句话说，如果容器包含 example.com，我希望能够查找 www.example.com，它会返回 true。或者，如果容器包含 foo.example.com，我希望能够查找 bar.foo.example.com，它会返回 true。

我考虑过这个问题，但似乎没有任何直接的方法可以解决这个问题。显而易见的解决方案是只使用常规关联容器，如哈希表或树(C++ 中的 std::unordered_set 或 std::set)。查找时，我将不得不遍历域名的每个部分，并继续查询容器以查看它是否包含每个部分。因此，如果我需要查找 www.example.com，我必须执行三个查询:一个用于 com，一个用于 example.com，还有一个用于 www.example.com。一旦得到肯定结果，我将返回 true，否则如果容器中没有这些，则返回 false。

这个解决方案很好，很可能是我最终会采用的解决方案。除了它看起来不对，因为我必须根据主机名的长度进行 N 次查询。由于主机名通常没有那么多段，所以我并不真正担心性能。但我很担心我应该在这里做一些更聪明的事情，尤其是因为这似乎是其他人已经考虑过的问题。

我考虑过使用更奇特的数据结构，比如 Patrica Trie或其他类型的前缀感知容器。我确实有一个很好的库实现了这个结构，所以使用它不是问题。但是，在考虑了这个问题之后，我认为 Patricia Trie 不会有帮助。尝试是为键是前缀而值是全长字符串的情况而设计的。在我的例子中，key 通常比容器中的任何值都长。换句话说，我的 key 可能是 www.example.com，如果容器有 example.com，我希望它能够找到 example.com。但是，Patricia Tries 的工作方式恰恰相反。

那么，常规的关联容器是最好的选择吗？或者有什么其他建议？

Answer 1

一个简单的解决方案，反转节点顺序(即，将 www.example.com 变成 com.example.www)并将其填充到您的 Patrica Trie 中。然后你可以遍历 trie 直到你一次找到你的匹配项