Providing const- and non-const overloads of a strstr() implementation

Question

In a question about reimplementing strstr(), I posted an answer. I pointed out a need for const- and non-const versions of the function, and provided Implementation A below, which received criticism about the ugliness of the const_cast. Therefore, I've written two more implementations (B and C).

Implementation A: const version that chains to a non-const version

char *strstr(char *input, const char *find) {
    do {
        const char *p, *q;
        for (p = input, q = find; *q != '\0' && *p == *q; p++, q++) {
        }
        if (*q == '\0') {
            return input;
        }
    } while (*(input++) != '\0');
    return NULL;
}

const char *strstr(const char *input, const char *find) {
    return strstr(const_cast<char *>(input), find);
}

Implementation B: template

template <typename T>
T *strstr(T *input, const T *find) {
    do {
        const T *p, *q;
        for (p = input, q = find; *q != '\0' && *p == *q; p++, q++) {
        }
        if (*q == '\0') {
            return input;
        }
    } while (*(input++) != '\0');
    return NULL;
}

Implementation C: template with char_traits

template <typename T>
struct char_traits {
    typedef T type;
    typedef const T const_type;
};

template <typename T>
static typename char_traits<T>::type *strstr(
        typename char_traits<T>::type *input,
        typename char_traits<T>::const_type *find) {
    do {
        typename char_traits<T>::const_type *p, *q;
        for (p = input, q = find; *q != '\0' && *p == *q; p++, q++) {
        }
        if (*q == '\0') {
            return input;
        }
    } while (*(input++) != '\0');
    return NULL;
}

// Explicit instantiation doesn't help with overloading?
// http://stackoverflow.com/a/8061522/1157100
//
// template char *strstr<char>(char *input, const char *find);
// template char *strstr<const char>(char *input, const char *find);

// So it seems that chaining is still necessary?
const char *strstr(const char *input, const char *find) {
    return strstr<const char>(input, find);
}

char *strstr(char *input, const char *find) {
    return strstr<char>(input, find);
}

---

I suspect that I may have done something stupid with (C), since I'm still chaining the calls. Is there a way to provide an overloaded strstr() just using template instantiation?

Of the three approaches, which is best, and why?

Answer 1

I don't like casting away const on a const object.
This opens you up to the possibility of maintenance errors.

const char *strstr(const char *input, const char *find)
{
    return strstr(const_cast<char *>(input), find);
}

Here you are assuming that the other version of strstr() will not attempt to mangle the input. This may be fair to assume in the original version, but what if somebody makes a mistake while updating to use a better algorithm. The compiler will not detect the problem and you are left with UB.

I would just do it the other way around:

char const* strstr(char const* input, char const* find)
{
   do {
        char const* p;
        char const* q;
        for (p = input, q = find; *q != '\0' && *p == *q; p++, q++) {
        }
        if (*q == '\0') {
            return input;
        }
    } while (*(input++) != '\0');
    return NULL;
}

char* strstr(char* input, char const* find)
{
    return const_cast<char*>(strstr(const_cast<char const*>(input), find));
}

OK. So we need to add another cast. But in this version we protect ourselves from errors. If there is an error in the algorithm (were input is modified) then the compiler will now be able to detect it.

The const_cast<> to remove const(ness) is in a safe place returning the pointer to its original state (after there is const_cast<> to add const (needed so we can differentiate the two functions).

Personally I would take it a step further (so we can remove one of the const_casts). By making the strstr() just wrapper functions around the function that does the work.

char const* strstrDo(char const* input, char const* find)
{
   do {
        char const* p;
        char const* q;
        for (p = input, q = find; *q != '\0' && *p == *q; p++, q++) {
        }
        if (*q == '\0') {
            return input;
        }
    } while (*(input++) != '\0');
    return NULL;
}

// Interface for backwards compatibility with old C code
// that does not handle const correctness well.
char* strstr(char* input, char const* find)
{
    // It is safe to cast away the const(ness) here.
    // The result of `strstrDo()` is a location inside
    // `input` (which we already know is non const) or
    // it is NULL (where the type is less relevant).

    return const_cast<char*>(strstrDo(input, find));
}

// Correct interface.
char const* strstr(char const* input, char const* find)
{
   return strstrDo(input, find);
}

Don't like Implementation B: template because it has the same problems in that errors (in modification input are not detected by the compiler (potentially)).

Same for Implementation C: template with char_traits. But that goes way over the top. I don't actually see the need for the traits on such a simple function.

Answer 2

I would like to propose implementation D

I'm using std::type_traits in the implementation template so that it is easy to implement for example case insensitive strstr by just providing an appropriate type trait. The detail namespace hides the implementation, although possible to abuse, I find it unlikely to happen by accident.

As the template is explicitly instantiated for both const and non const types any accidental modification of the non-const parameter will cause a compile error when instantiating the const version.

#include <iostream>
#include <string>
    
namespace detail{  
  template<typename T, class TR = std::char_traits<T> >
  struct impl_strstr{
    typedef typename TR::char_type* ptype;
    typedef const typename TR::char_type* cptype;
    
    ptype operator()(ptype input, cptype find){
      do {
        cptype p, q;
        for (p = input, q = find; !TR::eq(*q, 0) && TR::eq(*p, *q); p++, q++) {
        }
        if (TR::eq(*q, 0)) {
          return input;
        }
      } while (!TR::eq(*(input++) ,0));
      return NULL;
    }
  };
}

char* my_strstr(char* input, const char* find){
  return detail::impl_strstr<char>()(input, find);
}

const char* my_strstr(const char* input, const char* find){
  return detail::impl_strstr<const char>()(input, find);
}

wchar_t* my_strstr(wchar_t* input, const wchar_t* find){
  return detail::impl_strstr<wchar_t>()(input, find);
}

const wchar_t* my_strstr(const wchar_t* input, const wchar_t* find){
  return detail::impl_strstr<const wchar_t>()(input, find);
}

int main(){
  char str[] = "This is a simple string";
  char * pch = my_strstr(str, "simple");
  std::cout << pch<<std::endl;

  const char cstr[] = "This is a const simple string";
  const char * cpch = my_strstr(cstr, "simple");
  std::cout << cpch<<std::endl;
  
  wchar_t wstr[] = L"This is a simple wide string";
  wchar_t * wpch = my_strstr(wstr, L"simple");
  std::wcout << wpch<<std::endl;
  
  const wchar_t cwstr[] = L"This is a simple const wide string";
  const wchar_t * cwpch = my_strstr(cwstr, L"simple");
  std::wcout << cwpch<<std::endl;
  
  return 0;
}

Edit: Link to code on godbolt: http://goo.gl/74euWD