HI there, Is there a generic radix trie container in boost which can be used for longest prefix match? I mean, I couldn't find one in the boost containers libraries but maybe some library uses such a container internally and it's generic enough to be used with types other than strings? Thanks, Pavel.
sounds like a good idea for a new library On Wed, Sep 10, 2025 at 6:44 AM Pavel Vazharov via Boost-users < boost-users@lists.boost.org> wrote:
HI there,
Is there a generic radix trie container in boost which can be used for longest prefix match? I mean, I couldn't find one in the boost containers libraries but maybe some library uses such a container internally and it's generic enough to be used with types other than strings?
Thanks, Pavel. _______________________________________________ Boost-users mailing list -- boost-users@lists.boost.org To unsubscribe send an email to boost-users-leave@lists.boost.org https://lists.boost.org/mailman3/lists/boost-users.lists.boost.org/ Archived at: https://lists.boost.org/archives/list/boost-users@lists.boost.org/message/CX...
-- Regards, Vinnie Follow me on GitHub: https://github.com/vinniefalco
On 2025-09-10 07:42, Pavel Vazharov via Boost-users wrote:
HI there,
Is there a generic radix trie container in boost which can be used for longest prefix match? I mean, I couldn't find one in the boost containers libraries but maybe some library uses such a container internally and it's generic enough to be used with types other than strings?
It started when I needed to do longest prefix match for long distance numbers. I came up with the following based upon Aho Corasick algorithm: https://github.com/rburkholder/trade-frame/blob/master/lib/OUCommon/KeyWordM... It could probably be made to be even more generic by replacing the char with a templated token for comparison operations. A use case can be seen in, where the value to lookup is an enum: enum class EMode { view_training, view_validate , train_then_validate, train_then_save, train_save_validate , load_then_validate , train_then_run_live, load_then_run_live , unknown } eMode; ou::KeyWordMatch<config::Choices::EMode> kwmMode( config::Choices::EMode::unknown, 10 ); kwmMode.AddPattern( "view_training_data", config::Choices::EMode::view_training ); kwmMode.AddPattern( "view_validate_data", config::Choices::EMode::view_validate ); kwmMode.AddPattern( "train/validate", config::Choices::EMode::train_then_validate ); choices.eMode = kwmMode.FindMatch( sMode ); above are excerpts from: https://github.com/rburkholder/trade-frame/blob/master/SP500/Config.hpp https://github.com/rburkholder/trade-frame/blob/master/SP500/Config.cpp
On 2025-09-10 07:42, Pavel Vazharov via Boost-users wrote:
Is there a generic radix trie container in boost which can be used for longest prefix match? I mean, I couldn't find one in the boost containers libraries but maybe some library uses such a container internally and it's generic enough to be used with types other than strings?
One other thought: boost spirit uses a trie structure for performing matches. That might provide a more generalized form of token parsing for you.
On Wed, Sep 10, 2025 at 5:43 PM Raymond Burkholder via Boost-users <boost-users@lists.boost.org> wrote:
On 2025-09-10 07:42, Pavel Vazharov via Boost-users wrote:
Is there a generic radix trie container in boost which can be used for longest prefix match? I mean, I couldn't find one in the boost containers libraries but maybe some library uses such a container internally and it's generic enough to be used with types other than strings?
One other thought: boost spirit uses a trie structure for performing matches. That might provide a more generalized form of token parsing for you.
I'll check the boost spirit. Thank you. I need to match IPv4/IPv6 prefixes. Currently I intend to use the policy based extensions of libstdc++ - https://gcc.gnu.org/onlinedocs/libstdc++/manual/policy_data_structures_desig.... I'm not sure if they are OK for production usage though.
_______________________________________________ Boost-users mailing list -- boost-users@lists.boost.org To unsubscribe send an email to boost-users-leave@lists.boost.org https://lists.boost.org/mailman3/lists/boost-users.lists.boost.org/ Archived at: https://lists.boost.org/archives/list/boost-users@lists.boost.org/message/3N...
Xpressive uses *ternary* search trie, IDK the details or if it fits your requirements, but you can check it out https://www.boost.org/doc/libs/latest/doc/html/xpressive/user_s_guide.html On Wed, Sep 10, 2025 at 3:44 PM Pavel Vazharov via Boost-users < boost-users@lists.boost.org> wrote:
HI there,
Is there a generic radix trie container in boost which can be used for longest prefix match? I mean, I couldn't find one in the boost containers libraries but maybe some library uses such a container internally and it's generic enough to be used with types other than strings?
Thanks, Pavel. _______________________________________________ Boost-users mailing list -- boost-users@lists.boost.org To unsubscribe send an email to boost-users-leave@lists.boost.org https://lists.boost.org/mailman3/lists/boost-users.lists.boost.org/ Archived at: https://lists.boost.org/archives/list/boost-users@lists.boost.org/message/CX...
On Wed, Sep 10, 2025 at 5:43 PM Ivan Matek <libbooze@gmail.com> wrote:
Xpressive uses ternary search trie, IDK the details or if it fits your requirements, but you can check it out
Thank you. Will check it.
https://www.boost.org/doc/libs/latest/doc/html/xpressive/user_s_guide.html
On Wed, Sep 10, 2025 at 3:44 PM Pavel Vazharov via Boost-users <boost-users@lists.boost.org> wrote:
HI there,
Is there a generic radix trie container in boost which can be used for longest prefix match? I mean, I couldn't find one in the boost containers libraries but maybe some library uses such a container internally and it's generic enough to be used with types other than strings?
Thanks, Pavel. _______________________________________________ Boost-users mailing list -- boost-users@lists.boost.org To unsubscribe send an email to boost-users-leave@lists.boost.org https://lists.boost.org/mailman3/lists/boost-users.lists.boost.org/ Archived at: https://lists.boost.org/archives/list/boost-users@lists.boost.org/message/CX...
participants (4)
-
Ivan Matek -
Pavel Vazharov -
Raymond Burkholder -
Vinnie Falco