how its faster than cstring functions? is the similar source available for C?
+2
A:
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.
Dan Story
2010-04-02 23:30:21
Any STL function that takes functors will generally be faster than C's that take function pointers. For example, `std::sort` and `std::binary_search` are considerably faster than `qsort` and `bsearch` included with C's standard library.
Billy ONeal
2010-04-02 23:43:40
There's no such thing as a "close-source binary" version of the STL. Nobody has implemented exportable templates, everybody has to ship the source code for their STL implementation. Including Dinkumware.
Hans Passant
2010-04-03 08:59:54
Good to know. I've edited the answer accordingly, thanks. Doesn't Comeau C++ have exportable templates, though? I thought it was the only compiler which actually implemented it.
Dan Story
2010-04-03 10:13:04
Yes, EDG has implemented support for export templates. Of course, the feature is getting *removed* in C++0x (not just deprecated), so if you're going to use `export`, hurry up, you've got about a year left. ;)
jalf
2010-04-03 13:07:58
I heard about that. I think it's a shame -- the feature was a good one -- but I understand why they're doing it, since nobody was willing to actually build it in.
Dan Story
2010-04-03 15:42:56
+1
A:
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.
Hans Passant
2010-04-03 09:14:12
A:
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.
DeadMG
2010-04-03 11:03:18
A:
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.