[Boost-users] Question on data structure usage

[Ram]

Hi,

I have a map as follows,

boost::unordered_map<string, string> sample_map;

I would like to look up the keys using wildcards/regex from the user and
get the values corresponding to it(get multiple matches). It looked like
there is no straightforward way to do it.

So, I was thinking as an when I populate the map, I create a seperate data
structure to store the keys, so that I can get the values(list) that match
my user inputted regex/wildcard search. The I use this list to get the
values from the map.

What data structure can I use for this purpose? Is my approach correct? Or
can I do this directly using the map?

Please help me solve this problem.

Thanks,
-R

[Sebastian Messerschmidt]

Hi Ram,

If you're looking for something like autocompletion "Tries" might be
more suited than maps/multimaps:

https://en.wikipedia.org/wiki/Trie

Cheers
Sebastian

Post by Ram
Hi,
I have a map as follows,
boost::unordered_map<string, string> sample_map;
I would like to look up the keys using wildcards/regex from the user and
get the values corresponding to it(get multiple matches). It looked like
there is no straightforward way to do it.
So, I was thinking as an when I populate the map, I create a seperate
data structure to store the keys, so that I can get the values(list)
that match my user inputted regex/wildcard search. The I use this list
to get the values from the map.
What data structure can I use for this purpose? Is my approach correct?
Or can I do this directly using the map?
Please help me solve this problem.
Thanks,
-R
_______________________________________________
Boost-users mailing list
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Ram]

Yes I wanted to use Tries, that was my first choice. I didnt find an
implementation in boost. I dont want to write anything from the scratch.

Thanks,
-R

[Ram]

Also since I would like to use it for official purposes, I would like to be
safe in whatever I am using.

Thanks,
Ram

[Sebastian Messerschmidt]

Hi Ram,

In this case you can, if you absolutely want to, use a map. You can
construct a map of prefixes, mapping to the respective complete string.

But this will result in a ridiculously big data structure. There are
certain optimizations and pitfalls with this, and I used tries because
they are much simpler and much more efficient.

But I'm unaware of any boost-internal implementation of tries.
A quick peek into the web revealed this however [0]



Cheers
Sebastian

[0] https://github.com/ithlony/Boost.Trie/tree/master/boost/trie

Post by Ram
Yes I wanted to use Tries, that was my first choice. I didnt find an
implementation in boost. I dont want to write anything from the scratch.
Thanks,
-R
_______________________________________________
Boost-users mailing list
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Ram]

Thanks for this,
[0] https://github.com/ithlony/Boost.Trie/tree/master/boost/trie

Can I trust and use this? Or there any other open implementations that I
can use?

Thanks,
-R

[Sebastian Messerschmidt]

Hi Ram

Thanks for this,
[0] https://github.com/ithlony/Boost.Trie/tree/master/boost/trie
<https://github.com/ithlony/Boost.Trie/tree/master/boost/trie>
Can I trust and use this? Or there any other open implementations that I
can use?

I have no idea ... You have the code, you can analyze it. This basically
is always your responsibility if security is a concern. I'm unaware of
any other implementations, so I leave this to your research.

Maybe there is something buried within boost's fancy multi-containers
stuff that meets your requirements. So maybe wait if someone drops in
some new ideas.

Cheers
Sebastian

Thanks,
-R
_______________________________________________
Boost-users mailing list
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Ram]

[
Maybe there is something buried within boost's fancy multi-containers stuff
that meets your requirements. So maybe wait if someone drops in some new
ideas.
]
Thanks Sebastian!

-R

[Paul A. Bristow]

From: Boost-users [mailto:boost-users-***@lists.boost.org] On Behalf Of Ram
Sent: 29 November 2016 09:54
To: boost-***@lists.boost.org
Subject: Re: [Boost-users] Question on data structure usage



Thanks for this,



[0] https://github.com/ithlony/Boost.Trie/tree/master/boost/trie



Can I trust and use this?



http://lists.boost.org/Archives/boost/2014/01/210688.php



No recent work, No docs, No review, No tests L



But it may still work OK for you.



Suck it and see?



Paul



---

Paul A. Bristow

Prizet Farmhouse

Kendal UK LA8 8AB

[phone]

[Ram]

[

http://lists.boost.org/Archives/boost/2014/01/210688.php


No recent work, No docs, No review, No tests L

]
Thanks Paul! Will try it and let you know.

Thanks,
-R

[Dominique Devienne]

Post by Ram
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