5

Consider this function I wrote real quick to find the last occurrence of a given char in a string and return it's position within the array of chars that physically is the string:

size_t strlstchar(const char *str, const char ch)
{
    char *chptr = strrchr(str, ch);
    return chptr - str;
}

I just typed this up real quick here (haven't compiled or anyting yet) just because I have questions about a few things.

To me this seems like the simplest solution to find which array element holds the last instance of a particular char, but I have no idea how it works. I just made this following the documentation of strrchr, so it's technically strrchr doing all the work. I just can't imagine this being the best way (in terms of performance) to achieve this, and was hoping somebody could give some input on what would be the best way to do this.

Is strrchr an efficient way to do this? Or is strrchr best left for some other use?

perilbrain
  • 7,961
  • 2
  • 27
  • 35
Keith Miller
  • 1,337
  • 1
  • 16
  • 32
  • strrchr can return NULL, thus making the result of your function hard to predict when it fails to find the char. Typically "-str" can be seen as a random number, then converted to size_t, how will you know that you failed to find the char ? – xryl669 Apr 24 '14 at 17:15

3 Answers3

4

The approach you used is perfectly fine - unfortunately, array operations are expensive. Strrchr in most implementations simply steps through the string beginning from its end until it finds a matching character. That's O(n) time. Then you perform a subtraction which is O(1). This is not that bad.

  • Interesting, and thank you for the quick answer, I just always feel hesitant to use string functions, I guess it's a habbit or something not really sure why it's drilled into my brain that "if your using a function defined in string.h you're doing it wrong" – Keith Miller Aug 28 '12 at 20:35
  • 1
    @KeithMiller that's wrong. Those functions are there for a purpose. If there was a magical constant-time way for solving all algorithmical problems, libc implementors would use that. And always remember the sentence Linus Torvalds wrote: "Any sane man knows K&R was right" :) –  Aug 28 '12 at 20:38
  • 1
    Strings are really slow in C, due their specific nature (being 0x00 ended): strrchr() go from the beginning to the end of the string (either by calling strlen() to know the end of the string, that traverse the whole string, then taking it from the end until it find the character, either by doing it in a simple pass until the end of the string). So wherever is your found character, the whole string is scanned! – Parallelis Aug 28 '12 at 20:38
  • 1
    @H2CO3 I didn't saw it when I was writing, and would like to add a precision of the algorithms typically used by strrchr() :) – Parallelis Aug 28 '12 at 20:40
3

From the docs:

Returns a pointer to the last occurrence of character in the C string str.

So it does exactly what you want. The purpose of its existence is this.

Is strrchr an efficient way to do this?

It is almost certainly written at least as well or better than you could do it yourself.

Or is strrchr best left for some other use?

No. It written exactly for this purpose.

Mark Byers
  • 811,555
  • 193
  • 1,581
  • 1,452
0

It will be faster if you can supply the length of the string then just loop backwards. When you find the first occurrence of the character return right away.

If you don't know the length just use strrchr.

Richard Heath
  • 349
  • 3
  • 12
  • That's what I thought but in what case would I not know the length of the string unless it contained NULL chars or something, would it even be considered a string at that point? Or just a chunk of data? And if that would be more efficient why isn't it that way in the standard library? It seems so simple? This is why I'm confused because sometimes things just don't make sense to me :( – Keith Miller Aug 28 '12 at 20:43
  • Usually in C you don't know the length of the string so it makes more sense to not include the length in strrchr. So you don't need to do strlen to get the length every time you use strrchr. But also there's a lot of functions that returns the length when successful like scanf. If your code really needs to be more efficient you can loop backwards. – Richard Heath Aug 28 '12 at 21:06