c++ - Efficient string to key matching in an unordered_map? -

the efficient way of mapping these strings functions hash-table:

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

unfortunately things more complicated when want match on simple pattern:

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

i have been told <regex> library overkill needs; , it's overhead considerable.

using hash-table (std::unordered_map) here might efficient option; [a-z|0-9]+ being checked in single parse within switch/case. number of arguments (split on /) , using number of / number of arguments decide path take:

"/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"} 

it possible implement; best approach?

an ideal data structure trie in each slash-separated segment matched against first last of wildcard-free strings in unordered_map or sorted vector (which can done in o(1) or o(logn) respectively), if no match found vector of regular expressions (which you'll need try 1 one - o(n)). depending on performance needs, simplify things treating constant strings regular expressions , doing o(n) searching @ each node in trie.

+----------+     +---------------+                   +-----------+ | fixed:   |     | fixed:        |                   | fixed:    | |    foo  -+---->|    bar       -|---> fn_foo_bar  --|   xxx    -|---> fn_foo_x_xxx |    abc  -+-    |               |                /  |           | | regexp:  | \   | regexp:       |               /   | regexp:   | +----------+  |  |    [a-z0-9]+ -|---------------    +-----------+               |  +---------------+               |               \->+---------------+                  | fixed:        |                   ... 

if have more specific insights potential number of variations of fixed , reg-exp components may able optimise further, general solution reasonable scalability.