Back to General and Gameplay Programming

c++ : std::string.find() what is the base algorithm...Boyer-Moore?

General and Gameplay Programming Programming

Started by random_thinker August 29, 2005 05:07 PM

4 comments, last by random_thinker 18 years, 7 months ago

random_thinker

282

Author

August 29, 2005 05:07 PM

Just wondering what the std::string.find() algorithm is base upon? Noted in another thread that Boyer-Moore is highly recommended for string finding. Can't find this info in my references or on the 'net. Anyone know? --random_thinker

--random_thinkerAs Albert Einstein said: 'Imagination is more important than knowledge'. Of course, he also said: 'If I had only known, I would have been a locksmith'.

Fruny

1,658

August 29, 2005 05:10 PM

It is implementation-defined. The C++ standard only mandates interface and asymptotic performance, not actual algorithms and implementations. Considering that the full source code for std::string is available, you could check by yourself how your standard library implementation does it.

"Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it." — Brian W. Kernighan

guyaton

130

August 29, 2005 05:11 PM

if it is it would save me from having to write my own [grin]

~guyaton

~guyaton

random_thinker

282

Author

August 29, 2005 05:18 PM

Quote:Original post by Fruny
It is implementation-defined. The C++ standard only mandates interface and asymptotic performance, not actual algorithms and implementations. Considering that the full source code for std::string is available, you could check by yourself how your standard library implementation does it.

Why do implementations vary, because of the compiler or platform?

--random_thinker

--random_thinkerAs Albert Einstein said: 'Imagination is more important than knowledge'. Of course, he also said: 'If I had only known, I would have been a locksmith'.

SiCrane

11,840

August 29, 2005 05:20 PM

Some vendors may want to optimize for code space, others may choose to optimize for runtime performance. New algorithms may come along that are better than old ones, and so on.

random_thinker

282

Author

August 29, 2005 05:27 PM

Quote:Original post by SiCrane
Some vendors may want to optimize for code space, others may choose to optimize for runtime performance. New algorithms may come along that are better than old ones, and so on.

I'm trying to stick with a relatively recent version of g++ (3.3.5). Should the algorithms be more-or-less the same regardless of platform?
--random_thinker

--random_thinkerAs Albert Einstein said: 'Imagination is more important than knowledge'. Of course, he also said: 'If I had only known, I would have been a locksmith'.

c++ : std::string.find() what is the base algorithm...Boyer-Moore?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

c++ : std::string.find() what is the base algorithm...Boyer-Moore?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines