address of substring

This is a discussion on address of substring within the C++ Programming forums, part of the General Programming Boards category; I've written a recursive function for a project that deals with strings and I'm unsure about whether or not I ...

  1. #1
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728

    address of substring

    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.

  2. #2
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    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.
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

  3. #3
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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.

  4. #4
    Registered User
    Join Date
    Dec 2002
    Posts
    119
    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

  5. #5
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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.
    Last edited by PJYelton; 12-07-2002 at 05:43 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. What does this do (Windows API)?
    By EVOEx in forum Windows Programming
    Replies: 4
    Last Post: 12-19-2008, 09:48 AM
  2. Writing array, to file
    By zootreeves in forum C Programming
    Replies: 9
    Last Post: 09-08-2007, 05:06 PM
  3. I thought pointers were pointers...
    By keira in forum C Programming
    Replies: 19
    Last Post: 08-15-2007, 11:48 PM
  4. DX - CreateDevice - D3DERR_INVALIDCALL
    By Tonto in forum Game Programming
    Replies: 3
    Last Post: 12-01-2006, 06:17 PM
  5. pointers
    By InvariantLoop in forum C Programming
    Replies: 13
    Last Post: 02-04-2005, 08:32 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21