<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Tue, Nov 29, 2016 at 10:23 AM, Ram <span dir="ltr"><<a href="mailto:sourceopen@gmail.com" target="_blank">sourceopen@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>boost::unordered_map<string, string> sample_map;</div><div><br></div><div>I would like to look up the keys using wildcards/regex from the user [...]</div><div>What data structure can I use for this purpose? Is my approach correct? Or can I do this directly using the map?</div></div></blockquote><div><br></div><div>No data-structure that I know of can optimize a "regexp" lookup.</div><div>You must scan all keys and try to match them against the (precompiled preferably) regexp.</div><div><br></div><div>A trie (or any ordered) container would narrow down the search space in the case the "regexp" contain a literal prefix,</div><div>by iterating on .equal_range(prefix) for example, but then you must "introspect" the regexp to know if that's really the case.</div><div><br></div><div>Simple globbing could be optimized by a full-text search "index", similar to SQLite's fts4/fts5,</div><div>but you'd need to have a very large container to really benefit from it IMHO. --DD</div></div></div></div>