DaniWeb Forum Index > Software Development > C++

C++ RSS

How to improve program with string compairing?

Please support our C++ advertiser: Intel Parallel Studio Home

•

Join Date: Sep 2004

Posts: 7,630

Reputation: Narue has a reputation beyond repute

Solved Threads: 718

Narue

Offline

Code Goddess

Re: How to improve program with string compairing?

#11

Jul 6th, 2005

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

I'm here to prove you wrong.

•

Join Date: Feb 2005

Posts: 466

Reputation: winbatch is on a distinguished road

Solved Threads: 18

winbatch

Offline

Posting Pro in Training

Re: How to improve program with string compairing?

#12

Jul 6th, 2005

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..)

•

Join Date: Jun 2005

Posts: 2,044

Reputation: Rashakil Fol is just really nice

Solved Threads: 139

Rashakil Fol Rashakil Fol is offline

Offline

Super Senior Demiposter

Re: How to improve program with string compairing?

#13

Jul 6th, 2005

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.

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
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;
}
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.

•

Join Date: Feb 2005

Posts: 466

Reputation: winbatch is on a distinguished road

Solved Threads: 18

winbatch

Offline

Posting Pro in Training

Re: How to improve program with string compairing?

#14

Jul 6th, 2005

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

•

Join Date: Jun 2005

Posts: 2,044

Reputation: Rashakil Fol is just really nice

Solved Threads: 139

Rashakil Fol Rashakil Fol is offline

Offline

Super Senior Demiposter

Re: How to improve program with string compairing?

#15

Jul 7th, 2005

•

Originally Posted by winbatch

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

Dereferencing an iterator is faster because a[i] 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.

•

Join Date: Apr 2004

Posts: 4,359

Reputation: Dave Sinkula has a brilliant future

Solved Threads: 239

Dave Sinkula Dave Sinkula is offline

Offline

long time no c

Re: How to improve program with string compairing?

#16

Jul 7th, 2005

•

Originally Posted by Rashakil Fol

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...

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
for ( i = 0; i < strlen(s); ++i )
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.)

"One of the methods used by statists to destroy capitalism consists in establishing controls that tie a given industry hand and foot, making it unable to solve its problems, then declaring that freedom has failed and stronger controls are necessary." --Ayn Rand