4
\$\begingroup\$

I'm trying to reverse a string using pointers and recursion, and I send it a char array. Is this the best way, or is there a better one?

int display_string_reversep(char* astring)
{ 
  char* achar = astring;
  if((*achar) != '\0')
    {
      char* x= achar;
      x++;
      display_string_reversep(x);
      cout<<(*achar);
    }
    return 0;
} 

I'm also trying to do the same using smart pointers and that is proving to be more of a problem.

int display_string_reverseup(shared_ptr<char> astring)
{ 
  cout<<"\nEntering revup"; 
  shared_ptr<char> achar(astring);
  cout<<"\nAssigned achar";
  //if((*achar) != '\0')
  if(achar != nullptr)
    {
      cout<<"Forward String ";
      cout<<achar<<endl; 
      if(*(achar.get()+1) != '\0')
    {
      shared_ptr<char> x(achar.get()+1);
      //x++;
      cout<<"Forward + 1 String ";
      cout<<x<<endl;
      //if ((*x) != '\0')
      display_string_reverseup(x);
    }
      cout<<(achar);
    }
    return 0;
} 
\$\endgroup\$

1 Answer 1

6
\$\begingroup\$

General comments

This review might come across a little harsh, so I want to start out by saying that the code is overall pretty good. In particular, the first implementation is a completely reasonable implementation of a recursive approach to string reversal, and it's easy to read and follow.

Now, rather than comparing the two approaches (short version: the first one is vastly superior), I'm going to go over some design and style items.

Standard implementation

I assume this is a toy function. If not, you really should leverage the standard library instead:

std::string str("some string to be reversed");
std::copy(str.crbegin(), str.crend(), std::ostream_iterator<char>(std::cout));

Or if you want to use a C-style string:

const char str[] = "Some string to be reversed";
std::copy(std::reverse_iterator<const char*>(str + sizeof(str)),
          std::reverse_iterator<const char*>(str),
          std::ostream_iterator<char>(std::cout));

Side note: If you're importing individual names from std, great. If not, be very careful. using namespace std can be a dangerous option. Inside of implementations (i.e. source files) it's questionable; inside of headers, it's dangerous and harmful.

Bare pointer implementation

It seems you're always returning 0, and I can't think of a situation in which this function could fail (at least gracefully), so I wouldn't bother returning anything.


astring is a bit noisy (particularly the 'a'). I would just go with str. (string might be a questionable choice since it could shadow std::string in certain circumstances.)

achar is redundant (and like astring, I find the name a bit distracting -- instead, the typical option would be ch or chr, at least if it were actually a char and not a pointer to a char).


char* x and it's manipulation is unnecessary.

display_string_reversep(str + 1);

I feel like the outputting could use a little more room to breathe:

std::cout << *str;

This is essentially opinion though.


Since you're not modifying the input, you should be taking a const char*.


It's typically good practice to keep manipulations and output separate. In other words, it would be more reusable if you had a function for reversing strings and then just output the reversed copy. Or, if you wanted to compromise, you could have it take an arbitrary std::ostream instead of being stuck on std::cout.

void display_string_reverse(const char* str, std::ostream& os);

(Note that the standard library version both keeps concerns separate and it avoids making a copy of the string -- iterators are a powerful thing.)


This can act as a decent intro-to-recursion thing, but otherwise, I would go with iteration. Recursion avoids an extra linear scan (if length isn't already known), so that's a bit nice, but the overhead is likely not worth it.


I'm not sure I get the name display_string_reversep. I would drop the p.


Recursive example

void display_string_reverse(const char* str, std::ostream& os) {
    if (str == nullptr || str[0] == '\0') { return; }
    display_string_reverse(str + 1);
    os << str[0];
}

(I tend to prefer str[0] over *str in situations like this -- either one is equally valid. str[0] just clicks a bit better with my brain.)

Iterative example

void display_string_reverse(const char* str, std::size_t len, std::ostream& os) {
    for (std::size_t idx = 1; idx <= len; ++idx) {
        os << str[len - idx];
    }
}

void display_string_reverse(const char* str, std::ostream& os) {
    display_string_revserse(str, std::strlen(str), os);
}

Typically when you operate on C style strings (or strings that don't carry around their own length in general), you want to allow the user to provide the length, and then for usability purposes, you can offer a strlen fallback (which I would probably not do in a real application -- I'd rather force the caller to know what he's doing). This allows for avoid an unnecessary linear scan when the length is already known.

Note that you could generalize this to use two pointers instead of a pointer and a length. Then you could extract out that pointer concept (via templating) and you'd find yourself getting eerily close to the mentality of the standard library based implementation :).

Note: you could also use for (char* chr = beg + len - 1; chr != str; --chr) { os << chr[0]; }. Note: for (std::size_t idx = str + len - 1; idx >= 0; --idx) will underflow std::size_t and likely result in an ininite loop. If you were to go this route, care would have to be taken, or a signed type used (or use idx = str + len and then use idx - 1 inside of the loop instead of idx).

shared_ptr implementation

Correctness

I haven't tried to run it, but I'm going to guess that this segfaults. When you create a shared_ptr around a raw pointer, you're creating an ownership relation. When all of the shared pointers referencing the object go away, the object is cleaned up automatically. This is incredibly useful in certain situations, but you must be aware of the implications.

Your code is essentially doing this:

std::shared_ptr<char> ptr0(str);
std::shared_ptr<char> ptr1(str + 1);
std::shared_ptr<char> ptr2(str + 2);
// ...
std::shared_ptr<char> ptrn(str + n); // (str + strlen(str) - 1)

So what happens when all these shared_ptr go out of scope? Bad, bad things. In essence, str will be destructed n times. The problem is that the string isn't separate allocations of characters strung together. Instead it's either a C-string literal (so an automatically managed array of characters -- char[]), or it's a dynamically allocated array of characters. In the first situation, it should not be freed at all. In the second situation, it should be freed once and only once.

If you actually wanted to use smart pointers for this (and you shouldn't), you would have to use a single smart_ptr wrapping a dynamically allocated array of characters, and you would have to use either bare pointers or the smart pointer plus an offset.

In short, smart pointers are a powerful tool when they're required, but they are not only not required here, but, in my opinion, actively harmful. They convulute ownership semantics, introduce performance problems, and at the end of the day, a highly specialized smart pointer already exists for strings: std::string.

shared_ptr performance and semantics

Before you start passing around smart pointers, please go read this.

In short, you should only pass a shared_ptr by value if you're intending to share ownership with whatever you are passing it to. Since display_string_reversep has nothing to do with owning it's parameter, accepting a shared_ptr by value is incorrect both semantically and from a performance point of view. To make things worse a second shared_ptr is created.

shared_ptr is incredibly powerful for situations that truly require shared ownership semantics, but be mindful that its utility comes at a cost. Doing pretty much anything other than reading a shared pointer is very expensive compared to a bare pointer or a unique_ptr.

In this case, since there's not conditional logic of taking ownership of the shared pointer, you would still pass by a bare pointer.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks so much. This is exactly what I needed. I was fleshing out code for a class and I wanted an easy way to introduce smart pointers to them I think that would be in linked lists etc. \$\endgroup\$
    – canatan
    Commented Sep 7, 2014 at 12:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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