none
How shall I handle these memory allocation in recursive function RRS feed

  • Question

  • // Word out all permutations of a given string.
    	vector<char*> CppAlgorithms::permut(char s[], int length)
    	{
    		vector<char*> permutations;
    		if(length == 1)
    		{
    			if(s[0] != ' ')
    			{
    				permutations.insert(permutations.begin(), s);
    				return permutations;
    			}
    			else return permutations;
    		}
    
    		char firstChar = s[0];
    		string remainder = string(s).substr(1);
    		char * remainder_cstr = new char[length];
    		strcpy_s(remainder_cstr, length, remainder.c_str());
    
    		vector<char*> words = CppAlgorithms::permut(remainder_cstr, length-1);
    
    		char *newWord = NULL;
    		for(auto it = words.begin(); it<words.end(); ++it)
    		{
    			char *word = *it;
    			
    			for(int position = 0; position <= strlen(word); ++position)
    			{
    				// for each word, make it a modifiable string, stored in newWord;
    				// insert "firstChar" into each position of word. "word" has 5 positions: [0-4]
    				newWord = new char[strlen(word)+1];
    				strcpy_s(newWord, strlen(word)+1, word);
    				string *sNewWord = new string(newWord);
    				(*sNewWord).insert(position, 1, firstChar);
    				
    				permutations.insert(permutations.begin(),1, const_cast<char*>((*sNewWord).c_str()));
    
    			}
    		}
    		
    		return permutations;
    	}

    Thanks in advance.


    Remember to mark reply as answer if it answers the question.

    Thursday, December 19, 2013 2:39 PM

Answers

  • Try a vector<string> instead of vector<char *> -- this will take care of all the memory allocation for you and you shouldn't have to use new or delete.  In general you should treat use of new and especially delete as a code smell in modern C++ (i.e. it might be the right thing to do but it probably isn't and should be investigated)

    A note on your algorithm: If you have a vector where order is not important, never insert at the beginning of the vector, only add to the end.  It is much much much more efficient. 


    • Marked as answer by Forrest Guo Saturday, December 21, 2013 3:37 AM
    Thursday, December 19, 2013 3:44 PM

All replies

  • Try a vector<string> instead of vector<char *> -- this will take care of all the memory allocation for you and you shouldn't have to use new or delete.  In general you should treat use of new and especially delete as a code smell in modern C++ (i.e. it might be the right thing to do but it probably isn't and should be investigated)

    A note on your algorithm: If you have a vector where order is not important, never insert at the beginning of the vector, only add to the end.  It is much much much more efficient. 


    • Marked as answer by Forrest Guo Saturday, December 21, 2013 3:37 AM
    Thursday, December 19, 2013 3:44 PM
  • In addition to SimonRev's excellent answer, change the first parameter to type string&. You won't need the second parameter, as in:

    	vector<string> CppAlgorithms::permut(string& s)

    Thursday, December 19, 2013 4:20 PM
  • On 19/12/2013 17:20, Brian Muth [MVP] wrote:

    In addition to SimonRev's excellent answer, change the first parameter to type string&. You won't need the second parameter, as in:

            vector<string> CppAlgorithms::permut(string& s)

    In addition, if 's' is a input read-only parameter (i.e. if the permut() method "observes" s), consider passing it using const &:

       vector<string> CppAlgorithms::permut(const string& s)
    

    Giovanni

    Thursday, December 19, 2013 7:55 PM
  • Yeah, theoretically yes. I'll rewrite the algorithm with string type. The ideas of use reference and const are accepted as well.

    thank you guys.


    Remember to mark reply as answer if it answers the question.

    Saturday, December 21, 2013 3:37 AM