5
\$\begingroup\$

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?

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Rev 3 fixes some compilation errors. Specifically, it uses const_cast rather than static_cast, and rearranges the functions. Please re-check. \$\endgroup\$ – 200_success Jun 13 '14 at 16:43
  • \$\begingroup\$ In your third code block, what's the point of strstrDo()? char const* strstr(char const* input, char const* find) { /* impl */ } along with char *strstr(char *input, char const*find) { return const_cast<char *>(strstr(input, find)); } seems to work just fine. \$\endgroup\$ – 200_success Jun 13 '14 at 16:44
  • \$\begingroup\$ Could you show an example of a potential error with (B)? \$\endgroup\$ – 200_success Jun 13 '14 at 16:48
  • \$\begingroup\$ The use of strstrDo() is to remove the need to add const(ness) with a const_cast<> in the non cost version of strstr(). \$\endgroup\$ – Martin York Jun 13 '14 at 18:25
  • \$\begingroup\$ Note: There is no error in (B) as it stands. The problem arises when it is used with char* value as input. In this case you have no protection from bugs being introduced when maintaining the code (ie the cost correctness of the code is compromised and the compiler will fail to see any errors introduced). \$\endgroup\$ – Martin York Jun 13 '14 at 18:28
2
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.