CODEWITHSUNDEEP
c++c
Elorfin
Elorfin

Reputation: 19

String search algorithm used by string::find() c++

how its faster than cstring functions? is the similar source available for C?

Upvotes: 0

Views: 2369

Answers (4)

user287107
user287107

Reputation: 9417

There are many possiblities how you can implement a find string technique. The easiest way is to check every position of the destination string if there is the searchstring. You can code that very quickly, but its the slowest possiblity. (O(m*n), m = length search string, n = length destination string)

Take a look at the wikipedia page, http://en.wikipedia.org/wiki/String_searching_algorithm, there are different options presented. The fastest way is to create a finite state machine, and then you can insert the string without going backwards. Thats then just O(n).

Which algorithm the STL actually uses, I don't know. But you could search for the sourcecode and compare it with the algorithms.

Upvotes: 0

Puppy
Puppy

Reputation: 146970

The string class almost certainly stores far more data about the string than you'd find in a C string. Length is a good example. In tradeoff for the extra memory use, you will gain some spare CPU cycles.

Edit: However, it's unlikely that one is substantially slower than the other, since they'll perform fundamentally the same actions. MSDN suggests that string::find() doesn't use a functor-based system, so they won't have that optimization.

Upvotes: 0

Dan Story
Dan Story

Reputation: 10155

There's no standard implementation of the C++ Standard Library, but you should be able to take a look at the implementation shipped with your compiler and see how it works yourself.

In general, most STL functions are not faster than their C counterparts, though. They're usually safer, more generalized and designed to accommodate a much broader range of circumstances than the narrow-purpose C equivalents.

Upvotes: 3

Hans Passant
Hans Passant

Reputation: 941873

A standard optimization with any string class is to store the string length along with the string. Which will make any string operation that requires the string length to be known to be O(1) instead of O(n), strlen() being the obvious one.

Or copying a string, there's no gain in the actual copy but figuring out how much memory to allocate before the copy is O(1). The overall algorithm is still O(n). The basic operation is still the same, shoveling bytes takes just as long in any language.

String classes are useful because they are safer (harder to shoot your foot) and easier to use (require less explicit code). They became popular and widely used because they weren't slower.

Upvotes: 1

Related Questions