String stream producing memory-map

Question

I'm having some trouble with string streams; whenever I try to do use the in-operator (<<) on an non-empty string I get a memory-map printed when I run my program. Here's the code:

for(int i=1 ; i<djikstra_result[0] ; i++)
{
    cout << "DEBUG 5:10 - Round " << i << endl;
    if(i==djikstra_result[0]-1)
    {
        ss << djikstra_result[i] << "km.";
        cout << "DEBUG 5:11" << endl;
    }
    else
    {
        int j = djikstra_result[i];
        cout << "DEBUG 5:13 - j=" << j << endl;
        ss << this->airport[j] << " - ";
        cout << "DEBUG 5:14" << endl;
    }
}

ss is my stringstream, djikstra_result[] is a dynamic int array, this-airport[] is a dynamic string array.

The code compiles just fine, but it only runs until "cout << "DEBUG 5:13 - j=" << j << endl;". The result from that point and onward is:

DEBUG 5:13 - j=0
*** glibc detected *** ./graph: malloc(): memory corruption: 0x0000000000ec10f0 ***
======= Backtrace: =========
/lib/libc.so.6(+0x77806)[0x7f9f8403a806]
/lib/libc.so.6(+0x7b928)[0x7f9f8403e928]
/lib/libc.so.6(__libc_malloc+0x6e)[0x7f9f8403f7de]
/usr/lib/libstdc++.so.6(_Znwm+0x1d)[0x7f9f848ab24d]
/usr/lib/libstdc++.so.6(_ZNSs4_Rep9_S_createEmmRKSaIcE+0x59)[0x7f9f84887d79]
/usr/lib/libstdc++.so.6(_ZNSs4_Rep8_M_cloneERKSaIcEm+0x2b)[0x7f9f8488874b]
/usr/lib/libstdc++.so.6(_ZNSs7reserveEm+0x3c)[0x7f9f8488927c]
/usr/lib/libstdc++.so.6(_ZNSs6appendERKSs+0x4f)[0x7f9f848896ff]
./graph[0x402138]
./graph[0x4032ce]
/lib/libc.so.6(__libc_start_main+0xfd)[0x7f9f83fe1c4d]
./graph[0x401439]
======= Memory map: ========
00400000-00404000 r-xp 00000000 00:15 15341576                           /home/psyberion/Dropbox/algorithms/assign-3b/graph
00604000-00605000 r--p 00004000 00:15 15341576                           /home/psyberion/Dropbox/algorithms/assign-3b/graph
00605000-00606000 rw-p 00005000 00:15 15341576                           /home/psyberion/Dropbox/algorithms/assign-3b/graph
00ec1000-00ee2000 rw-p 00000000 00:00 0                                  [heap]
7f9f7c000000-7f9f7c021000 rw-p 00000000 00:00 0 
7f9f7c021000-7f9f80000000 ---p 00000000 00:00 0 
7f9f83fc3000-7f9f8413d000 r-xp 00000000 08:05 2887651                    /lib/libc-2.11.1.so
7f9f8413d000-7f9f8433c000 ---p 0017a000 08:05 2887651                    /lib/libc-2.11.1.so
7f9f8433c000-7f9f84340000 r--p 00179000 08:05 2887651                    /lib/libc-2.11.1.so
7f9f84340000-7f9f84341000 rw-p 0017d000 08:05 2887651                    /lib/libc-2.11.1.so
7f9f84341000-7f9f84346000 rw-p 00000000 00:00 0 
7f9f84346000-7f9f8435c000 r-xp 00000000 08:05 2884391                    /lib/libgcc_s.so.1
7f9f8435c000-7f9f8455b000 ---p 00016000 08:05 2884391                    /lib/libgcc_s.so.1
7f9f8455b000-7f9f8455c000 r--p 00015000 08:05 2884391                    /lib/libgcc_s.so.1
7f9f8455c000-7f9f8455d000 rw-p 00016000 08:05 2884391                    /lib/libgcc_s.so.1
7f9f8455d000-7f9f845df000 r-xp 00000000 08:05 2887634                    /lib/libm-2.11.1.so
7f9f845df000-7f9f847de000 ---p 00082000 08:05 2887634                    /lib/libm-2.11.1.so
7f9f847de000-7f9f847df000 r--p 00081000 08:05 2887634                    /lib/libm-2.11.1.so
7f9f847df000-7f9f847e0000 rw-p 00082000 08:05 2887634                    /lib/libm-2.11.1.so
7f9f847e0000-7f9f848d6000 r-xp 00000000 08:05 25175504                   /usr/lib/libstdc++.so.6.0.13
7f9f848d6000-7f9f84ad6000 ---p 000f6000 08:05 25175504                   /usr/lib/libstdc++.so.6.0.13
7f9f84ad6000-7f9f84add000 r--p 000f6000 08:05 25175504                   /usr/lib/libstdc++.so.6.0.13
7f9f84add000-7f9f84adf000 rw-p 000fd000 08:05 25175504                   /usr/lib/libstdc++.so.6.0.13
7f9f84adf000-7f9f84af4000 rw-p 00000000 00:00 0 
7f9f84af4000-7f9f84b14000 r-xp 00000000 08:05 2887636                    /lib/ld-2.11.1.so
7f9f84ceb000-7f9f84cef000 rw-p 00000000 00:00 0 
7f9f84d10000-7f9f84d13000 rw-p 00000000 00:00 0 
7f9f84d13000-7f9f84d14000 r--p 0001f000 08:05 2887636                    /lib/ld-2.11.1.so
7f9f84d14000-7f9f84d15000 rw-p 00020000 08:05 2887636                    /lib/ld-2.11.1.so
7f9f84d15000-7f9f84d16000 rw-p 00000000 00:00 0 
7fff9500a000-7fff9501f000 rw-p 00000000 00:00 0                          [stack]
7fff951ff000-7fff95200000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]
Aborted

I have encountered this problem before, but I haven't been able to work out what's causing it, other than some kind of memory problem. Could someone please help? Here's the code for the whole function:

string graph::get_shortest(string name1, string name2)
{
int* djikstra_result;
int result[this->nr_airport];
int source=-1;
int goal=-1;
bool source_found = false;
bool goal_found = false;
string final="";
string space=" - ";
stringstream ss;
cout << "DEBUG 5:1" << endl;
for(int i=0 ; i<this->nr_airport ; i++)
{
    cout << "DEBUG 5:2 - Round " << i << endl;
    if(name1==this->airport[i])
    {
        cout << "DEBUG 5:3" << endl;
        source = i;
        source_found = true;
    }
    else if(name2==this->airport[i])
    {
        cout << "DEBUG 5:4" << endl;
        goal = i;
        goal_found = true;
    }
}
cout << "DEBUG 5:5" << endl;
if(!source_found || !goal_found)
{
    throw "Starting point or destination not found";
}
cout << "DEBUG 5:6" << endl;
for(int i=0 ; i<this->nr_airport ; i++)
{
    result[i] = -1;
    cout << "DEBUG 5:7 - Round " << i << endl;
}
cout << "DEBUG 5:8" << endl;
djikstra_result = djikstra(source, goal);
cout << "DEBUG 5:9" << endl;
for(int i=1 ; i<djikstra_result[0] ; i++)
{
    cout << "DEBUG 5:10 - Round " << i << endl;
    if(i==djikstra_result[0]-1)
    {
        ss << djikstra_result[i] << "km";
        cout << "DEBUG 5:11" << endl;
    }
    else
    {
        int j = djikstra_result[i];
        cout << "DEBUG 5:13 - j=" << j << endl;
        //string val = this->airport[j];
        cout << "DEBUG 5:14" << endl;
        ss << this->airport[j];
        cout << "DEBUG 5:15" << endl;
    }
}
ss >> final;
return final;   
}

EDIT:

The array this->airport[] is declared like this:

this->cap_airport = 1;
this->airport = new string[this->cap_airport];

When I add something to the array I expand it with the following function:

void graph::expand_list()
{
if(this->nr_airport==this->cap_airport)
{
    this->cap_airport++;
    string* temp = new string[this->cap_airport];
    for(int i=0 ; i<this->nr_airport ; i++)
    {
        temp[i] = "";
        if(this->airport[i]!="")
        {
            temp[i] = this->airport[i];
        }
    }
    delete [] this->airport;
    this->airport = temp;
}
}

I do this to avoid allocating more space than needed, and I only add info to the array when reading from file.

EDIT:

After removing the << " - "; from the string, it seems to make some progress. I'm calling the function get_shortest(string name1, string name2) in my main-function, like this:

graph g1;
cout << g1.get_shortest("A","E") << endl;

I can now see some more output when I run the program:

DEBUG 5:15
DEBUG 5:10 - Round 5
DEBUG 5:11
AAAA0km
*** glibc detected *** ./graph: free(): invalid pointer: 0x0000000001ba7070 ***
======= Backtrace: =========
/lib/libc.so.6(+0x77806)[0x7f400d9cf806]
/lib/libc.so.6(cfree+0x73)[0x7f400d9d60d3]
//And so on as before

So the problem doesn't seem to be connected to the string stream itself. Any ideas?

`j` may be going beyond the bounds of array: `this->airport[j]`? — hmjd, May 01 '12 at 16:34
Unrelated to your problem, but still good practice: pass your variables by const reference. http://stackoverflow.com/questions/2582797/why-pass-by-const-reference-instead-of-by-value — luke, May 01 '12 at 16:38
@hmjd, I don't think that's the case, since `j` is equal to 0 when the program crashes. I'll add this in the question though, so thanks for pointing it out! — EscalatedQuickly, May 01 '12 at 16:51
@Psyberion, can you post declaration and population of `airport[]` ? — hmjd, May 01 '12 at 16:52
@hmjd `this->cap_airport = 1; this->airport = new string[this->cap_airport];` It's values are: A, B, C, D, E, F And it's expanded every time I add something to it. — EscalatedQuickly, May 01 '12 at 17:02
can you check what happens when you do `cout << this->airport[j] << endl;` ? — deebee, May 01 '12 at 17:07
Also, how are you expanding `this->airport` everytime you add something? I would suggest to use `vector` if your array is dynamic. — deebee, May 01 '12 at 17:11
@deebee Yes, I can, and it works perfectly. `cout << this->airport[j] << endl;` produces and "A", just as it should. As for the expansion, I'm allocating a new temporary string array with a greater capacity, copies all values to the new array, delete the old one and assign the new array to the old array's pointer. I hope that made sense. — EscalatedQuickly, May 01 '12 at 17:17
I can make sense of what your saying, but it will be helpful if you can post that code in your question. Also, could you check if the error goes away if you remove `<< this->airport[j]` from the line `ss << this->airport[j] << ' - '`. This ensures that problem is in `this->airport[j]` like @hmjd originally suspected. — deebee, May 01 '12 at 17:57
@deebee I've added the code now, hope it helps. Also, I've already tried removing `<< this->airport[j]` the first thing I did, only problem is that just `ss << " - ";` is causing the exact same problem. — EscalatedQuickly, May 01 '12 at 18:34

score 0 · Accepted Answer · answered May 02 '12 at 10:19

I found the problem in a whole other part of the program; the memory map is the result of an invalid memory operation, but it's not reading from neither djikstra_result[] or this->airport[], as suggested. Just trying to read from an invalid position in an array would result in a segmentation fault. The problem is that I in the function djikstra(int source, goal) tried to add data to an invalid position in an array. Here's the code:

result = new int[nr_visited];
for(int i=0 ; i<nr_visited+2 ; i++)
{
    if(i==0)
    {
        result[i] = nr_visited;
    }
    else if(i==nr_visited+1)
    {
        result[i] = distance;
    }
    else
    {
        result[i] = route[i-1];
    }
}
return result;

I create a dynamic int array with the length nr_visited, but I try to put data in the position nr_visited+1, which is invalid. This causes the memory map. Thus, the fix is to declare the int array with the length nr_visited+2:

result = new int[nr_visited+2];

So, now, it all works.

String stream producing memory-map

1 Answers1