what's the problem of this code that causes segmentation fault?

[qiqi]

Hello,

Here below is a piece of code, could you please help figure out what its problem is? It permutes a string, and uses recursion. It has no compiling errors, but segmentation fault when running it.

Thanks.


#include <iostream>
#include <string>
#include <set>

using namespace std;

set<string> permutation(string);
string insertCharAt(char,string,int);

int main ()
{
set<string> myset;
set<string>::iterator it;
myset = permutation("tree");
for (it=myset.begin(); it!=myset.end();it++)
{
cout << *it << endl;
}
}

set<string> permutation(string str)
{
set<string>* perms = new set<string>();
//if (str.length()==0)
if (str.empty())
{
perms->insert("");
return *perms;
}
char first = str[0];
string rest = str.substr(1);
set<string> perms_rest = permutation(rest);
set<string>::iterator it;
while (it!=perms_rest.end())
{
for (int i=0; i<=static_cast<string>(*it).length();i++)
{
string s =insertCharAt(first,static_cast<string>(*it),i);
perms->insert(s);
}
}
return *perms;

}

string insertCharAt(char c, string str, int i)
{
string newstring = str.substr(0,i);
newstring += c;
newstring += str.substr(i);
return newstring;
}

[Moschops]

This is something you can easily do yourself using a debugger. Here is some example output using a debugger:

Program received signal SIGSEGV, Segmentation fault.
0x00007ffff7b72018 in std::basic_string<char, std::char_traits<char>, std::allocator<char> >::basic_string(std::string const&) () from /usr/lib/libstdc++.so.6
(gdb) up
#1  0x0000000000401564 in permutation (str=...) at 010.cpp:36
36	for (int i=0; i<=static_cast<string>(*it).length();i++)
(gdb) print i
$1 = 0
(gdb) print *it
$2 = (
    const std::basic_string<char, std::char_traits<char>, std::allocator<char> > &) @0x20: <error reading variable>
(gdb) 

Hmmm. Looks like there's some problem with it. I can't see what its an iterator to. Let's have a look at it itself.

(gdb) print it
$3 = {_M_node = 0x0}

Oh, it seems to be pointing nowhere. Maybe we never set it to anything. Let's look back a little in the code:

set<string>::iterator it;
while (it!=perms_rest.end())
{
for (int i=0; i<=static_cast<string>(*it).length();i++)

Gosh, we created the iterator but we never actually set it to anything. Well that explains it. We cannot use an iterator before we set it to something.

[bluecoder]

not initialization of it in set<string>::iterator it;

[qiqi]

Thanks, Moschops and bluecoder! You're right. The problem was that the iterator "it" wasn't initialized and incremented in the while loop.

A follow-up question is: how could we collect the dynamically allocated memory by the set<string> variable "perms" in the function permutation(string)? Since C++ doesn't have a garbage collector.

[Moschops]

delete it when you no longer need it

[qiqi]

In the recursive function, we actually can't delete it before returning it, can we?

set<string> permutation(string str) {
......
set<string>* perms = new set<string>();
......
return *perms
}

[Moschops]

You can delete it whenever you like. If you delete it and then try to use it, you're asking for trouble, so delete it when you don't need it any more.

[qiqi]

Thanks Moschops for your helps!

The memory "new"ed during recursion is hard to track for free-up. Someone mentioned "smart pointer" in boost library for that purpose. Actually I just find out that it doesn't need to use "new" in the "permutation" function. Using local variable is good enough.
:-)