This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Search algorithms in __gnu_cxx::


Dhruv Matani wrote:
__is_char which we
already have, and so on,
Where???? I did a complete grep -r "__is_char" . and didn't find
anything. Is it under some other name?
Of course, because you are not following our public and private recommendations that new features must be developed first vs *mainline*.
Yes, I understand your concerns fully. However, implementing the
Boyer-Moore in all it's entirety would imply that we would need to
maintain extra tables, and code complexity, etc.... which is not worth
the effort. The algorithm that I have implemented is a slight variant,
and is also sometimes called the Turbo Boyer Moore(a simpler version
of Boyer Moore, which captures the essence of the concept). The
complexity remains the same as that of Boyer Moore, since Boyer Moore
is not very easy to analyse when we get suffix matches, and depends
highly upon the input. The complexity for the normal case is the same
as the original concept.
Then, please cite the bibliographic reference for this variant and follow it in detail. Alternately, you can implement one among the well known variants in that web page (or elsewhere), there are no other options, sorry.

Also, I think we have to do something for that unordered_map, I don't think covering the general case via lookups in a map leads to something close to the original spirit, in any possible sense...

Paolo.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]