Boost logo

Boost :

Subject: Re: [boost] [spirit] scan_keyword: scan an InputIterator for a keyword.
From: Joel de Guzman (joel_at_[hidden])
Date: 2011-11-29 19:06:20

On 11/30/2011 6:23 AM, Vicente J. Botet Escriba wrote:
> Le 29/11/11 00:47, Joel de Guzman a écrit :
>> On 11/29/2011 5:45 AM, Vicente J. Botet Escriba wrote:
>>> Hi,
>>> for chrono input I'm using a scan_keyword function that adapted from libc++ library (you
>>> can find the code in[1]).
>>> Next follows the interface:
>> [snip]
>>> What is the better way to do that (or something similar) with Spirit/Lexer?
>>> Can we hope that the Spirit solution could perform much better?
>>> What about if the strings to parse are know at compile-time?
>>> [1]
>> The symbol parser seems to be your friend here.
>> The search is O(log n+k) using a TST.
> Hi,
> thanks for the pointer. This seems quite simple, I will try it and compare the performances.
> Does the parser try to scan the largest symbol?

Yes, it parses as much as it can.

> Shouldn't Lexer be more adequate/efficient to this use case?

Yes, you can also use Spirit Lex.

> Sorry, what is a TST?

Ternary Search Trees are faster than hashing for many typical search
problems especially when the search interface is iterator based.
Searching for a string of length k in a ternary search tree with
n strings will require at most O(log n+k) character comparisons.
TSTs are many times faster than hash tables for unsuccessful searches
since mismatches are discovered earlier after examining only a
few characters. Hash tables always examine an entire key when

For details see


Joel de Guzman

Boost list run by bdawes at, gregod at, cpdaniel at, john at