Re: [Boost-users] Question on data structure usage

On Tue, Nov 29, 2016 at 10:23 AM, Ram wrote:

boost::unordered_map sample_map;

I would like to look up the keys using wildcards/regex from the user [...] What data structure can I use for this purpose? Is my approach correct? Or can I do this directly using the map?

No data-structure that I know of can optimize a "regexp" lookup. You must scan all keys and try to match them against the (precompiled preferably) regexp. A trie (or any ordered) container would narrow down the search space in the case the "regexp" contain a literal prefix, by iterating on .equal_range(prefix) for example, but then you must "introspect" the regexp to know if that's really the case. Simple globbing could be optimized by a full-text search "index", similar to SQLite's fts4/fts5, but you'd need to have a very large container to really benefit from it IMHO. --DD