You can detect a mismatch as soon as you see two characters that are different -- but you can't detect a match until you've reached the end of the string, and the characters are still identical.
At least in my opinion, most attempts at this get the basic idea sort of backwards, trying to compare characters immediately (with some special-casing for one or both strings being empty). Instead, it's usually best to start by just skipping non-zero bytes that are equal. Then, you're either at the end of (at least one) string, or else you've found a mismatch between bytes in the two strings. Either way, at that point you can sort out what's going on, and return the correct value.
int cmp_str(char const *a, char const *b) {
while (*a && *a == *b) {
++a;
++b;
}
if (*b < *a)
return 1;
if (*b > *a)
return -1;
return 0;
}
This keeps the loop very simple, with very few conditions, so it can execute quickly. All the more complex comparisons to figure out the actual ordering happen outside the loop where they happen only once, and have almost no effect on speed.
I should probably add one warning: this does not make any attempt at dealing with international characters correctly. To do that, you just about need to add collating tables that define the relative order of characters because (at least in many code pages) the values of characters don't correspond to the order in which the characters should be sorted.
For what it's worth, here's a quick test comparing the results and speed from this to Andreas's compare
and the strcmp
in the standard library:
int cmp_str(char const *a, char const *b) {
while (*a && *a == *b) {
++a;
++b;
}
if (*b < *a)
return 1;
if (*b > *a)
return -1;
return 0;
}
inline int compare(char const* const a, char const* const b)
{
/* Return -1 less than, 0 equal, 1 greater than */
if (!a[0] && b[0])
return -1;
else if (a[0] && !b[0])
return 1;
register int i = 0;
for (; a[i] && b[i]; i++) {
if (a[i] < b[i])
return -1;
if (a[i] > b[i])
return 1;
}
#if 1 /* this addition makes this code work like std::strcmp */
if (!a[i] && b[i])
return -1;
else if (a[i] && !b[i])
return 1;
#endif
return 0;
}
#ifdef TEST
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
int main(){
char *s1 [] = { "", "a", "one", "two", "three", "one", "final" };
char *s2 [] = { "x", "b", "uno", "deux", "three", "oneone", "" };
for (int i = 0; i < 7; i++) {
printf("%d\t", cmp_str(s1[i], s2[i]));
printf("%d\t", compare(s1[i], s2[i]));
printf("%d\n", strcmp(s1[i], s2[i]));
}
// Test a long string:
static const int size = 5 * 1024 * 1024;
static char s3[size];
for (int i = 0; i < size - 1; i++)
s3[i] = (rand() % 254) + 1;
s3[size - 1] = '\0';
static char s4[size];
strcpy(s4, s3);
s3[size - 5] = (s3[size - 5] + 4) % 255;
clock_t start = clock();
int val1 = cmp_str(s3, s4);
clock_t t1 = clock() - start;
start = clock();
int val2 = compare(s3, s4);
clock_t t2 = clock() - start;
start = clock();
int val3 = strcmp(s3, s4);
clock_t t3 = clock() - start;
double v1 = (double) t1 / CLOCKS_PER_SEC;
double v2 = (double) t2 / CLOCKS_PER_SEC;
double v3 = (double) t3 / CLOCKS_PER_SEC;
printf("Jerry: %d, %f\nAndreas: %d, %f\nstdlib: %d, %f\n", val1, v1, val2, v2, val3, v3);
}
#endif
Results:
-1 -1 -1
-1 -1 -1
-1 -1 -1
1 1 1
0 0 0
-1 -1 -1
1 1 1
Jerry: 1, 0.007000
Andreas: 1, 0.010000
stdlib: 1, 0.007000
Since Andreas has corrected his code, all three produce identical results for all the tests, but this version and the standard library do so about 30% faster than Andreas's versions. That does vary somewhat with the compiler though. With VC++, my code almost matches the code in the standard library (but if I use a huge string, like 200 megabytes, the version in the standard library is measurably better. With g++, the code in the standard library seems to be a little slower than the code in the VC++ standard library, but the result it generates for either Andreas's code or my code is quite a bit worse than VC++ produces for them. On a 200 megabyte string, I get these results with VC++:
Jerry: 1, 0.288000
Andreas: 1, 0.463000
stdlib: 1, 0.256000
...but with g++ (MinGW), I get results like this:
Jerry: 1, 0.419000
Andreas: 1, 0.523000
stdlib: 1, 0.268000
Although the ranking remains the same either way, the difference in speed between the standard library and my code is much larger with g++ than with VC++.
i
etc. to see what is actually going on. (Ideally, you must use a debugger) – Suvarna Pattayil Oct 17 '13 at 6:52return 0
after checking only one character! Your code does exactly what you have written, it's you who has made the mistake. Stop trying random modifications and think! – Dariusz Oct 17 '13 at 7:17