c++ - 高效的字符串到 unordered_map 中的键匹配？

Question

将这些字符串映射到函数的最有效方法是哈希表:

std::string a="/foo/", b="/foo/car/", c="/foo/car/can/", d="/foo/car/haz/";

不幸的是，当您想要匹配最简单的模式时，事情会变得更加复杂:

/foo/[a-Z|0-9]+>/
/foo/[a-Z|0-9]+>/bar/[a-Z|0-9]+/

有人告诉我 <regex>图书馆对我的需求来说太过分了；而且它的开销是相当大的。

在这里使用哈希表(std::unordered_map)可能是一个有效的选择；与 [a-Z|0-9]+在开关/案例中的单个解析中进行检查。参数的数量(拆分为 / )和使用 / 的数量然后任意数量的参数来决定采用哪条路径:

"/foo/"                  => {<function>, "/foo/can/", "/foo/[a-Z|0-9]+/bar/"}
"/foo/xflkjkjc34v"       => {<function>, "/foo/can/", "/foo/[a-Z|0-9]+/bar/"}
"/foo/can"               => {<function>, "/foo/can/", "/foo/[a-Z|0-9]+/bar/"}
"/foo/vxcvxc86vzxc/bar/" => {<function>, "/foo/[a-Z|0-9]+/bar/haz"}

可以实现；但这是最好的方法吗？

Answer 1

一个理想的数据结构是一个 trie，其中每个斜杠分隔的段与 unordered_map 或什至排序的 vector 中的第一个和最后一个无通配符的字符串匹配(这可以分别在 O(1) 或 O(logN) 中完成)，然后如果没有找到匹配项的 vector 正则表达式(您可能需要一个一个地尝试 - O (N))。根据您的性能需求，您可以通过将常量字符串视为正则表达式并始终在 trie 中的每个节点进行 O(N) 搜索来简化事情。

+----------+     +---------------+                   +-----------+
| fixed:   |     | fixed:        |                   | fixed:    |
|    foo  -+---->|    bar       -|---> fn_foo_bar  --|   xxx    -|---> fn_foo_X_xxx
|    abc  -+-    |               |                /  |           |
| regexp:  | \   | regexp:       |               /   | regexp:   |
+----------+  |  |    [A-Z0-9]+ -|---------------    +-----------+
              |  +---------------+
              |
              \->+---------------+
                 | fixed:        |
                  ...

如果您对固定和正则表达式组件的潜在变体数量有更具体的了解，您很可能能够进一步优化它，但这是具有合理可扩展性的通用解决方案。