A little challenge: "Reverse a string"

  • (6 Pages)
  • +
  • 1
  • 2
  • 3
  • 4
  • 5
  • Last »

86 Replies - 41225 Views - Last Post: 27 August 2013 - 02:43 PM

#31 raspinudo  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 61
  • View blog
  • Posts: 232
  • Joined: 19-September 11

Re: A little challenge: "Reverse a string"

Posted 29 February 2012 - 04:25 PM

My idea was to use a char stack:

Spoiler

This post has been edited by raspinudo: 29 February 2012 - 04:25 PM

Was This Post Helpful? 0
  • +
  • -

#32 Ricky65  Icon User is offline

  • D.I.C Head

Reputation: 38
  • View blog
  • Posts: 115
  • Joined: 03-June 10

Re: A little challenge: "Reverse a string"

Posted 01 March 2012 - 05:34 PM

Quote

How would you reverse a string without using, pointers, arrays, or c-strings.

Impossible, after all a string literal is an array of char.
Was This Post Helpful? 0
  • +
  • -

#33 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: A little challenge: "Reverse a string"

Posted 01 March 2012 - 10:30 PM

View PostRicky65, on 01 March 2012 - 07:34 PM, said:

Quote

How would you reverse a string without using, pointers, arrays, or c-strings.

Impossible, after all a string literal is an array of char.

Who says you have to use a string literal?
Was This Post Helpful? 0
  • +
  • -

#34 Ricky65  Icon User is offline

  • D.I.C Head

Reputation: 38
  • View blog
  • Posts: 115
  • Joined: 03-June 10

Re: A little challenge: "Reverse a string"

Posted 02 March 2012 - 05:16 AM

View Postr.stiltskin, on 18 February 2012 - 08:58 PM, said:

The original challenge said "reverse a string", not "print a string backwards", so I'd do it like this:

Spoiler

You're still using array subscription here.

r.stiltskin said:

Who says you have to use a string literal?

Nobody!
Was This Post Helpful? 0
  • +
  • -

#35 Ricky65  Icon User is offline

  • D.I.C Head

Reputation: 38
  • View blog
  • Posts: 115
  • Joined: 03-June 10

Re: A little challenge: "Reverse a string"

Posted 02 March 2012 - 06:38 AM

Whilst still using pointers, XOR is an interesting way of reversing. Here's my attempt at a generic reverse algorithm using XOR.

Spoiler

This post has been edited by Ricky65: 02 March 2012 - 06:43 AM

Was This Post Helpful? 0
  • +
  • -

#36 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: A little challenge: "Reverse a string"

Posted 02 March 2012 - 08:07 AM

View PostRicky65, on 02 March 2012 - 07:16 AM, said:

View Postr.stiltskin, on 18 February 2012 - 08:58 PM, said:

The original challenge said "reverse a string", not "print a string backwards", so I'd do it like this:

Spoiler

You're still using array subscription here.


Actually, I'm not. I'm using the std::string::operator[], which looks like an array subscript, but it's really just an overloaded operator -- "eye candy" for std::string::at().

There are some problems with your

View PostRicky65, on 02 March 2012 - 07:16 AM, said:

Spoiler

First, it doesn't compile. I cleaned it up for you so that part's solved. But if you're going to use that, you'll have to be willing to accept a segmentation fault whenever the two letters to be swapped are the same (or modify the code to skip that operation). Try it out:
Spoiler

Was This Post Helpful? 0
  • +
  • -

#37 Ricky65  Icon User is offline

  • D.I.C Head

Reputation: 38
  • View blog
  • Posts: 115
  • Joined: 03-June 10

Re: A little challenge: "Reverse a string"

Posted 03 March 2012 - 05:02 PM

View Postr.stiltskin, on 02 March 2012 - 08:07 AM, said:

View PostRicky65, on 02 March 2012 - 07:16 AM, said:

View Postr.stiltskin, on 18 February 2012 - 08:58 PM, said:

The original challenge said "reverse a string", not "print a string backwards", so I'd do it like this:

Spoiler

You're still using array subscription here.

r.stiltskin said:

Actually, I'm not. I'm using the std::string::operator[], which looks like an array subscript, but it's really just an overloaded operator -- "eye candy" for std::string::at().

Sorry but you are wrong here. "operator []" is the array subscript operator. It doesn't matter whether it is overloaded or not! Incidentally, how do you think the implementor of your C++ Standard Library is implementing their std::string container? They will be using pointers.

Also, std::string::operator[] is not the same as std::string::at(). The "at()" member function is bounds checked whereas "operator[]" isn't.

r.stiltskin said:

it doesn't compile. I cleaned it up for you so that part's solved.

This isn't true, it compiles fine.

r.stiltskin said:

But if you're going to use that, you'll have to be willing to accept a segmentation fault whenever the two letters to be swapped are the same (or modify the code to skip that operation). Try it out:
Spoiler

You make a valid point here. Keep in mind that I wrote the function quickly and to illustrate that XOR can be used to reverse a string. A solution would be to use "<" instead of "!=". However, the STL requires relational operators only for random access iterators so you wouldn't be able to use the algorithm with say, std::list.

This post has been edited by Ricky65: 03 March 2012 - 05:03 PM

Was This Post Helpful? 0
  • +
  • -

#38 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: A little challenge: "Reverse a string"

Posted 03 March 2012 - 05:55 PM

OK, the string::operator[] isn't exactly the same as string::at(), but what's the point, other than just to argue?

string::operator[] is still not an array subscript -- it's an overloaded operator (member function) of the string class, which returns a reference to a charT. And whatever [] is seems irrelevant anyway. The challenge says "reverse a string without using, pointers, arrays, or c-strings." It doesn't say "without using subscript notation."

There is no array in my function, unless you object to any array that might be encapsulated in the string class. There's a good challenge: reverse a string without using a string. ;)
Was This Post Helpful? 0
  • +
  • -

#39 Ricky65  Icon User is offline

  • D.I.C Head

Reputation: 38
  • View blog
  • Posts: 115
  • Joined: 03-June 10

Re: A little challenge: "Reverse a string"

Posted 04 March 2012 - 06:21 AM

View Postr.stiltskin, on 03 March 2012 - 05:55 PM, said:

OK, the string::operator[] isn't exactly the same as string::at(), but what's the point, other than just to argue?

I'm just interested in correctness. If a beginner programmer read your post they would incorrectly think that both were the same. That is not good. No offence but it's a poor mistake for somebody who is supposed to be an "expert" in C++.

View Postr.stiltskin, on 03 March 2012 - 05:55 PM, said:

string::operator[] is still not an array subscript -- it's an overloaded operator (member function) of the string class, which returns a reference to a charT. And whatever [] is seems irrelevant anyway. The challenge says "reverse a string without using, pointers, arrays, or c-strings." It doesn't say "without using subscript notation."

There is no array in my function, unless you object to any array that might be encapsulated in the string class. There's a good challenge: reverse a string without using a string. ;)

I contend that whether a built-in subscript operator or an overloaded subscript operator is used, it is still array notation. I agree that the OP wasn't specific on this though.

Anyway, it doesn't change the fact that your solution still doesn't conform to the challenge as the std::string container will be using an array internally to store the data.

This post has been edited by Ricky65: 04 March 2012 - 06:22 AM

Was This Post Helpful? 0
  • +
  • -

#40 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: A little challenge: "Reverse a string"

Posted 04 March 2012 - 07:53 AM

View PostRicky65, on 04 March 2012 - 08:21 AM, said:

Anyway, it doesn't change the fact that your solution still doesn't conform to the challenge as the std::string container will be using an array internally to store the data.

That is absolutely ridiculous.

Do you have a solution for reversing a string without using a string? How about declaring an int without using an int?
Was This Post Helpful? 0
  • +
  • -

#41 Ricky65  Icon User is offline

  • D.I.C Head

Reputation: 38
  • View blog
  • Posts: 115
  • Joined: 03-June 10

Re: A little challenge: "Reverse a string"

Posted 04 March 2012 - 08:32 AM

View Postr.stiltskin, on 04 March 2012 - 07:53 AM, said:

View PostRicky65, on 04 March 2012 - 08:21 AM, said:

Anyway, it doesn't change the fact that your solution still doesn't conform to the challenge as the std::string container will be using an array internally to store the data.

That is absolutely ridiculous.

Do you have a solution for reversing a string without using a string? How about declaring an int without using an int?

It's not ridiculous, I'm just pointing out that your solution doesn't satisfy the OPs requirements. As I said in my first post on this thread, the challenge is impossible.
Was This Post Helpful? 0
  • +
  • -

#42 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: A little challenge: "Reverse a string"

Posted 04 March 2012 - 09:44 AM

Really? Where does the C++ Standard say that a string must be implemented with an array?
Was This Post Helpful? 0
  • +
  • -

#43 Ricky65  Icon User is offline

  • D.I.C Head

Reputation: 38
  • View blog
  • Posts: 115
  • Joined: 03-June 10

Re: A little challenge: "Reverse a string"

Posted 04 March 2012 - 10:25 AM

View Postr.stiltskin, on 04 March 2012 - 09:44 AM, said:

Really? Where does the C++ Standard say that a string must be implemented with an array?

You mean std::string, right? How else would they implement it?
Was This Post Helpful? 0
  • +
  • -

#44 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: A little challenge: "Reverse a string"

Posted 04 March 2012 - 10:55 AM

I mean exactly what I said. Where does the standard say that string must be implemented with an array?

Under the OOP paradigm we're only supposed to use the interface that the class offers and not its underlying implementation. But to answer your question, I suppose string could be implemented using a linked list of char_t. It might not be practical, or efficient, but offhand I don't see why it's not possible and I'm not aware of anything in the standard that would rule it out.

But even if I'm wrong about that, I still think it's beside the point. I think it was perfectly reasonable of the OP to pose an abstract problem regarding an encapsulated abstract data type without being concerned with implementation-specific details of the class. And I think that a solution is valid if it uses ONLY the methods and interface presented by the class and doesn't violate any explicit prohibitions of the problem.
Was This Post Helpful? 0
  • +
  • -

#45 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: A little challenge: "Reverse a string"

Posted 05 March 2012 - 09:21 AM

Quote

I'm not aware of anything in the standard that would rule it out.


there is a really strange clause that does just that; std::vector has the same clause.
in the C++11 draft n3242 in section 21.4.1 the 5th clause states...
"The char-like objects in a basic_string object shall be stored contiguously"

Because std::string is just a typedef for a basic_string with the 'char' type there oddly is something that states this. I never saw a reason for that; It's basically saying &str[0] or &str.front() gives you the front of the array.

either way this argument is kinda silly as it's really an argument of what the OP meant. at the core of things this is pretty impossible. if you abstract away the details and call that not using pointers this it's quite possible; the crux of this argument is what the OP meant when they said "without pointers". can we all get along now?

This post has been edited by ishkabible: 05 March 2012 - 09:27 AM

Was This Post Helpful? 0
  • +
  • -

  • (6 Pages)
  • +
  • 1
  • 2
  • 3
  • 4
  • 5
  • Last »