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

Subject: Re: [Boost-users] Question on data structure usage
From: Dominique Devienne (ddevienne_at_[hidden])
Date: 2016-11-29 06:01:39

On Tue, Nov 29, 2016 at 10:23 AM, Ram <sourceopen_at_[hidden]> wrote:

> boost::unordered_map<string, string> 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