address of substring

**PJYelton** · 12-07-2002

I've written a recursive function for a project that deals with strings and I'm unsure about whether or not I can pass by reference with substrings. Here is a short snippet of what I am talking about:

Code:

void recursiveFunc(string& s)
{
   .... // perform some stuff on the string here
   for (int x=0; x<s.length(); x++)
   {
       recursiveFunc(s.substr(x,s.length()-x));
   }
}

I know what I have written isn't a very useful program, but theres a lot more going on.

Now, I didn't think this would work at all because how does one send the address of a substring? But I tried in on MSVC++ and it worked, so I finished my project. Now I'm scared though, does anyone know if this is only a MSVC++ thing or would this work on any compiler? If I pass by value, the program runs WAY too slowly since the recursive function gets called millions of times. So I'm afraid that if other compilers complain about this that I need to rewrite it.

**SilentStrike** · 12-07-2002

It should work on any compiler. However, is it really THAT much faster with pass by reference than pass by value? I'd imagine it wouldn't be anymore than twice as fast. The substr member will copy a whole new string, copying each character in it. I'd try to rewrite it (if possible) so that you don't need to constantly be creating substrings, you could get a major gain there.

**PJYelton** · 12-07-2002

I haven't timed it, but I think you are right its about twice as fast - the problem is that its for an algorithm that must compute within 10 seconds, and passing by reference gets the worst case of 7 seconds or so.

I'll see if I can rewrite it a bit though, although I'm not sure how though... <ponder ponder ponder> If I can't figure anything out I'll ask it here to see what people think.

**Codulation** · 12-07-2002

Are you sure you want to loop through the entire remaining string each time you call the funct? Normally you'd use an if statement not a for loop in a recursive funct:

Code:

void recursiveFunc(string& s, int x)
{
    .... // perform some stuff on the string here
   if(x<s.length())
   {
       recursiveFunc(s.substr(x,s.length()-x), ++x);
   }
}

Post the relevant parts of what you're trying to do it'll make it easier to understand.
-Futura

**PJYelton** · 12-07-2002

Errrr... I've been thinking about this program for so long I can't think straight enough to see if a for loop is not needed. Here is the code, basically its a program that given a string such as "123" and an integer such as 10, it prints out the number of combinations of those three numbers adding and subtracting that equal or are less than 10. For example, the answer here is 6:

1+2+3
1-2-3
1+2-3
1-2+3
1-23
12-3

The only rule is that the first number must be positive, so "-123" or "-1+2-3" do not count .

Here is my code that works, but if I pass by value then something like string="927572819283748" and max value=123456789 goes past the 10 second limit.

Code:

#include<iostream>
#include<vector>
#include<string>
using namespace std;

class NumCombine
{
private:
   int counter;
public:
   NumCombine() : counter(0) {};

   double numParse(string& s, int beg, int end)
   {
	double num=0;

	while (isdigit(s[beg]) && beg<=end)
	{
		num=num*10+int(s[beg]-'0');
		beg++;
	}

	return num;
   }

   void recursion(string& s, double total, int max)
   {
	total+=numParse(s, 0, s.length()-1);

	if (total<=max)
		counter++;
	total-=numParse(s, 0, s.length()-1);

	for (int x=1; x<s.length(); x++)
	{
		total+=(numParse(s, 0, s.length()-x-1)); 
		recursion(s.substr(s.length()-x,x),total, max);
		total-=(numParse(s, 0, s.length()-x-1)); 
	}

	total-=numParse(s, 0, s.length()-1);

	if (total<=max)
		counter++;
	total+=numParse(s, 0, s.length()-1);

	for (int xx=1; xx<s.length(); xx++)
	{
		total-=(numParse(s, 0, s.length()-xx-1)); 
		recursion(s.substr(s.length()-xx,xx),total, max);
		total+=(numParse(s, 0, s.length()-xx-1)); 
	}

   }

   int numCombos(string& s, int max)
   {
	double total=0;
	total+=numParse(s, 0, s.length()-1);
	if (total<=max)
	           counter++;
	total-=numParse(s, 0, s.length()-1);

	for (int x=1; x<s.length(); x++)
	{
		total+=(numParse(s, 0, s.length()-x-1));
		recursion(s.substr(s.length()-x,x),total, max);
		total-=(numParse(s, 0, s.length()-x-1));
	}
	return counter;
   }
};

The user only uses numCombos. I don't have time at the moment to place commentw, but I'll do it if it is hard to understand.

Thread: address of substring

Thread Tools

Search Thread

Display

address of substring

Similar Threads

What does this do (Windows API)?

Writing array, to file

I thought pointers were pointers...

DX - CreateDevice - D3DERR_INVALIDCALL

pointers