How to improve program with string compairing?

[JoBe]

Hello ladies and gents,

I had to do an exercise in wich I was required to compair two standaardtype strings opposits, meaning: name = "Johan", name2 = "nahoJ"

The idea was to return a bool value True or False. I did this with the following code I wrote:

#include <iostream>
#include <string>

using namespace std;

bool compair(const string &name, const string &name2)
{
	int i, j;

	if (name.length() != name2.length())return false;

	for(i = name.length() - 1, j = 0;i >= 0 ;i--, j++)
		{if (name[i] != 0 name[j]) return false;}

	return true;
}

int main()
{
	string name = "Johan", name2 = "nahoJ";

	int c = compair(name, name2);

	if(c == 1)
		cout<<"True!"<<endl;
		else
		cout<<"False!"<<endl;

	cout<<"Press any key to continue!\n";cin.get();

	return 0;
}

Alltough I managed to get 'a' solution, I was wondering if any of you could tell me how I could improve/shorten or make the code more clearly to follow :?:

The idea is solely to try and code a program as best as possible.

Thanks for any assistance ;)

[Rashakil Fol]

if (name[i] != 0 name[j])

Is this right?

I might write it like this:

#include <iostream>
#include <string>

using namespace std;

bool are_mirrored(const string &name, const string &name2);

int main()
{
	string name = "Johan", name2 = "nahoJ";

	bool c = are_mirrored(name, name2);

	if (c) {
		cout << "True!" << endl;
	} else {
		cout << "False!" << endl;
	}

	cout << "Press any key to continue!\n";
	cin.get();

	return 0;
}

bool are_mirrored(const string &name, const string &name2)
{

	if (name.size() != name2.size()) {
		return false;
	}

	string::size_type i = name.size();
	string::size_type j = 0;

	while (i) {
		if (name[--i] != name2[j++]) {
			return false;
		}
	}

	return true;
}

Generally, readability improves when every control structure uses braces and when operators have spaces on them. Also, string::size_type is an integer type that is guaranteed to be larger than any stored string. (It's just an unsigned long int on most systems, though: nothing terribly exciting.)

Also, it's a good idea to only use for loops of the form

for (int i = m; i < n; ++i)

or of the form

for (int i = n; i > m; --i)

Or maybe even:

for (string::iterator i = s.begin(); i != s.end(); ++i)

When you are not looping a single variable through a range of numbers, I consider it better form to use a while loop. You might find this to be the case also.

[JoBe]

Is this right?

No, it's a typo :)

if (name.size() != name2.size()) 
        {
	return false;
        }

Can you tell me why you prefer to use .size instead of .length?

while (i)
         {
	if (name[--i] != name2[j++])
            ...

Man, this is a very very good tip, never thought about using a while loop and didn't even think that during the selection you could compare name with name2 by subtracting i and adding towards j during the while loop.

Also, string::size_type is an integer type that is guaranteed to be larger than any stored string.

Don't completly understand why you prefer to use this, but, I'll google to see what string::size_type just is :?:

string::size_type i = name.size()-1;

Has to be -1, otherwise your comparing '\n' ;)

Thanks for the very usefull tips and improvements on my code Rashakil Fol :!:

[Rashakil Fol]

Can you tell me why you prefer to use .size instead of .length?

All or almost all other standard library containers use size() exclusively. length() was left in the string class for backwards compatibility with something, according to my current unknowledgeable theory. Also, size is four characters while length is six.

Don't completly understand why you prefer to use this, but, I'll google to see what string::size_type just is :?:

Usually I'll just use size_t (which is an integer type large enough to contain the length of any old array). Using string::size_type just makes for more portable code (but this would have to be some bizarre, Star Trek-like pseudocomputer.) You don't have to use it, and size_t will always work. (The only situation where I imagine using string::size_type could ever actually matter is one where strings are for some reason stored in a different memory space than other objects.)

int is generally fine, too, on 32-bit systems, as long as strings are smaller than 2 million-something characters long.

string::size_type i = name.size()-1;

Has to be -1, otherwise your comparing '\n' ;)

There's no '\n' character in the string. i starts after the end of the string because --i returns the decremented value of i, meaning that the first comparison uses the last character and first character of the respective strings. (Whereas i-- would return the original value of i.)

Unless there's a bug. I have not compiled and run.

[JoBe]

There's no '\0' character in the string. i starts after the end of the string because --i returns the decremented value of i, meaning that the first comparison uses the last character and first character of the respective strings. (Whereas i-- would return the original value of i.)

Unless there's a bug. I have not compiled and run.

Euh, yes I ment '\0'

Hmm strange :confused: But, If I don't use it, it doesn't show the correct result :!:

[Dave Sinkula]

Here's an ever so minor nitpick.

bool are_mirrored(const string &name, const string &name2)
{

	if (name.size() != name2.size()) {
		return false;
	}

	string::size_type i = name.size();
	string::size_type j = 0;

	while (i) {
		if (name[--i] != name2[j++]) {
			return false;
		}
	}

	return true;
}

Now it's nothing much when strings are short, but if such a function were used on something bigger and/or in a large loop, there is quite a bit of waste there. Let's say name is 1000 chars long: let's loop through 1000 chars to the end to find the length. Then later let's loop through 1000 chars to the end again to again find the length. A minor change would be to save the value and only calculate it once.

bool are_mirrored(const string &name, const string &name2)
{

	string::size_type i = name.size();

	if (i != name2.size()) {
		return false;
	}

	string::size_type j = 0;

	while (i) {
		if (name[--i] != name2[j++]) {
			return false;
		}
	}

	return true;
}

Nit-picky, yes. But it is helpful to always be thinking about such things as you code.

[JoBe]

@ Dave, thanks for the tip on that, I think it's important not only to get your code working, but improve it where possible :!:

@ Rashakil Fol, now I know why you didn't need to use the -1, you used

--i

and I used

i--

So, you subtracted 1 from i before you entered the loop.

[Rashakil Fol]

Here's an ever so minor nitpick.
Now it's nothing much when strings are short, but if such a function were used on something bigger and/or in a large loop, there is quite a bit of waste there. Let's say name is 1000 chars long: let's loop through 1000 chars to the end to find the length. Then later let's loop through 1000 chars to the end again to again find the length. A minor change would be to save the value and only calculate it once.

This inefficiency is not actually the case. The standard library string class usually stores three pointers: One to the beginning of the string's array of characters, one to the end of the string's array, and one to the end of the string. (The string might not use all of its allocated space.) Some implementations might store one pointer and two size_t integers -- but either way, the size() function is guaranteed to be a constant-time operation.

The standard library's size() member function could look something similar to this (never mind that it really gets implemented in the basic_string class):

string::size_type string::size() const
{
    return end_ - beg_;
}

And that would get inlined by a compiler -- making it one extra subtraction operation instead of one thousand-something operations. Only the C library's strlen function has to loop through the string, because C-style strings are simply pointers to arrays of characters that have a zero somewhere at the end.

And note that a compiler might have a mind to optimize any inefficiency away. It turns out that gcc will output identical-length executables

[Narue]

>length() was left in the string class for backwards compatibility with something
The string class existed in C++ before the STL was adopted, so length() was kept for backward compatibility with existing code and size() added in a poor attempt to make string more like a standard container.

>Also, size is four characters while length is six.
I find that hard to believe, since length() returns size(). Perhaps you're thinking of capacity(), in which case your suggestion is incorrect because the result of capacity() is largely implementation-dependent.

>You don't have to use it, and size_t will always work.
Chapter and verse, please.

>but either way, the size() function is guaranteed to be a constant-time operation.
Um, no. The standard says that size() "should" have constant complexity, not "shall" have constant complexity. That means that you can generally assume that calling size() is constant, but it's not guaranteed.

[Rashakil Fol]

>Also, size is four characters while length is six.
I find that hard to believe, since length() returns size(). Perhaps you're thinking of capacity(), in which case your suggestion is incorrect because the result of capacity() is largely implementation-dependent.

Four characters as in s-i-z-e. It's easier to code with shorter names.

[Narue]

>Four characters as in s-i-z-e. It's easier to code with shorter names.
Don't use your infernal logic on me! ;)

[winbatch]

Would using the STL iterators be useful here? Do they provide a reverse function? (I would think we could call a reverse function once and then simply do an == check..)

[Rashakil Fol]

Here's a version that uses STL iterators. Reverse iterators make the while loop rather elegant. You can also decrement to backup on a regular iterator, but this version uses a reverse iterator instead.

bool are_mirrored(const string &name, const string &name2)
{

	if (name.size() != name2.size()) {
		return false;
	}

	string::const_iterator p = name.begin();
	string::const_reverse_iterator r = name2.rbegin();

	string::const_iterator e = name.end();

	while (p != e) {
		if (*p++ != *r++) {
			return false;
		}
	}

	return true;
}

Because r is a reverse_iterator, it starts at the last character and faces in the opposite direction. It perceives the string backwards.

[winbatch]

I guess the real question is speed - whether iterators or array [] type access is faster..

[Rashakil Fol]

I guess the real question is speed - whether iterators or array [] type access is faster..

Dereferencing an iterator is faster because a uses one addition operation. But comparing two iterators is slower than checking if an integer is zero. If compiled dumbly, the iterator solution should be slightly faster, but it would not be a very measurable difference.

With compiler optimizations in play, the end result is up for grabs. Trying to solve this problem as efficiently as possible is rarely worth the programmer's time -- there are some more tricks that you could pull, but most comparisons will have unequal lengths or will be decided unequal very early in the loop -- only the equal strings run all the way through.

[Dave Sinkula]

This inefficiency is not actually the case. [...]

[...] Only the C library's strlen function has to loop through the string, because C-style strings are simply pointers to arrays of characters that have a zero somewhere at the end.

That's where my thinking had stemmed...

for ( i = 0; i < strlen(s); ++i )

You'd think "the compiler should optimize that to do what I mean". Yet in fact it is prohibited from doing just that.

Still, why do twice what you can do once. (And yes, there are occasionally reasons.)