dynamic memory, pointers not lvalue

[trebaruna]

Another programming exercise question. This is trying to teach me dynamic memory allocation, but I am lost.

I'm supposed to use "a pointer to pointers to strings" which I interpret as something like:

string *myStrings = new string[30];
string **myPtr = &myStrings;

This seems to work. (Can this be contracted?) However, this array is used to store stdin, and because I don't know how many lines there will be I need to be able to store more pointers. (I am not entirely sure this is what the exercise wants, but even so I've now stumbled across something I don't know) So I have a function enlarge:

#include "lines.ih"

void Lines::enlarge()
{
    string *tmp = new string[d_nStrings + 30];
    for (size_t idx = 0; idx < d_nStrings; ++idx)
        tmp + idx = *d_lines + idx;
    delete[] *d_lines;
    d_lines = &tmp;
    d_nStrings += 30;
}

d_nStrings is a datamember indicating how many strings are stored in the array. d_lines is the string** containing the strings.
This fails. The compiler tells me it needs an lvalue in the assignment. If I remove the assignment for a moment and replace it with an empty statement, execution segfaults at the delete[] line.
Clearly there are things I am overlooking, but I have no idea where to look. Could anyone give me any hints?

[jsmith]

Line 7 should be

*( tmp + idx ) = *( d_lines + idx );

Or, more simply,

tmp[ idx ] = d_lines[ idx ];

As for your segfault, it depends on the type of d_lines and how the memory was allocated. Line 8 tells me that d_lines is itself a pointer to a dynamically allocated array.

eg, this would fit the bill:

string* str_array = new string[ 10 ];
string** d_lines = &str_array;

as would

string* str_array = new string[ 10 ];
string** d_lines = new string*[ 20 ];
d_lines[ 0 ] = str_array;  // etc... 

[trebaruna]

Thanks for your reply!
Your suggestion needed a bit of modification:

tmp[idx] = *(d_lines)[idx];

Aren't I now copying the string objects themselves, rather than their pointers, though?

Also, yes, d_lines is defined like my example, and your first one. I understand that your line 2 in your last example would create something else than what I have. Accessing elements seems to work differently, for one. With the former method I can do:

*(*d_lines + idx) = "hello";

for instance. Dereference d_lines, now I'm at the array, take idx steps to the desired pointer, dereference to string.
With the latter method my program segfaults when I try to stick that string in there.

Lastly, when I have d_lines initialized like described, how would I go about deleting its content before assigning the new array to it?

[jsmith]

Let me make sure I understand. You have this declaration:

string** d_lines;

If d_lines is initialized as in my first example, then

tmp[ idx ] = (*d_lines)[ idx ];

I think shouldn't compile, because the left side is of type string and the right string*.
tmp is an array of strings, not an array of pointers to strings.

I would say you need to delete [] *d_lines; to deallocate the dynamic array.

[trebaruna]

jsmith, thanks for your help so far. I think I'm beginning to see.
I've tried

string **d_lines = new string *[10]

and it appears to work. Copying now seems to work, too:

    string **tmp = new string *[10];
    for (size_t idx = 0; idx < 10; ++idx)
        *(tmp + idx) = new string("hi");

    string **newtmp = new string *[10];
    for (size_t idx = 0; idx < 10; ++idx)
        *(newtmp + idx) = *(tmp + idx);

This compiles. I'm still having difficulties with delete, though.
Ignoring lines 4 and over, if I do

delete [] tmp;

and place the resulting lines in an endless loop I quickly discover there's a rather large memory leak. If I do

delete [] *tmp;

the program segfaults. For completeness' sake, with &tmp I get a very nasty looking error.

[jsmith]

Yes, there would be a memory leak. In your above example (lines 1-3) you call new 11 times, right? Once for tmp and then 10 times inside the loop.

To properly deallocate all the memory you just allocated, you will need to call delete 11 times also. First, 10 times to delete each element of the array, and then to delete tmp itself.

for( size_t idx = 0; idx < 10; ++idx )
    delete *( tmp + idx );
delete [] tmp;

[trebaruna]

Ah yes, of course!
I had assumed delete[] would take care of the stuff inside the array somehow.
I just hope I'm not the only one so confused by this stuff. Would slightly help my bruised self esteem.

One last question: I don't suppose there's a better way, is there? I have to allocate the strings with new because otherwise I'd have local initialization and wild pointers once my creating function goes out of scope, correct?

[jsmith]

I think you are writing a function that essentially wants to copy an array of strings. If that is the case, then I think you have one more level of pointers than you need. For example, this would work:

string* copy_string_array( string* array_of_strings, size_t num_strings ) {
    string* result = new string[ num_strings ];
    for( size_t index = 0; index < num_strings; ++index )
         result[ index ] = array_of_strings[ index ];
    return result;
}

Don't fret about arrays and pointers; they are confusing. I almost never use arrays any more; rather I use the various STL containers and occasionally I'll use either the boost::ptr_container library or the boost::multi_index_container library.

As an example, if all you wanted was an array of strings, you could do it this way (vector is the STL container that most closely parallels arrays, however other STL containers exist that might be better for your application):

vector<string> copy_string_array( string* array_of_strings, size_t num_strings ) {
    vector< string > result;
    result.reserve( num_strings );
    for( size_t index = 0; index < num_strings; ++index ) 
        result.push_back( array_of_strings[ i ] );
    return result;
}

And this could even be further simplified:

vector<string> copy_string_array( string* array_of_strings, size_t num_strings ) {
    vector< string > result;
    result.reserve( num_strings );
    copy( array_of_strings, array_of_strings + num_strings, back_inserter( result ) );
    return result;
}

[trebaruna]

Thanks again, you've been very helpful!

Indeed, I could probably suffice with just the array, but in general this exercise is about pointers and memory allocation, so I'd still need the extra pointer for other things. I'd love to use different tools, but that would sidestep what the course is trying to teach me. Also, I've no idea how any of that works, yet ;)
Anyway I think I'll manage now, thanks to your help. Thanks!

[jsmith]

Sure.

Yes, it's important to learn the fundamentals of arrays and pointers before learning the ways to avoid having to use them :)

The only way I can keep them straight is to understand how the memory is laid out in each case.

For example,

char* array = new char[ 10 ];
for( int i = 0; i < 10; ++i )
    array[ i ] = i;

array is a variable which contains a (32-bit) pointer. The array variable might be stored at memory location 0x1000. new char[] might have returned the pointer 0x2000. So in memory, if I look at memory locations 0x1000-0x1003, they will contain the value 0x00002000. If I cout << array, I'll get 0x1000. And if I look at memory locations 0x2000-0x2009, they will contain the values 00 01 02 03 04 05 06 07 08 09.

Contrast that to

char array[ 10 ];
for( int i = 0; i < 10; ++i )
    array[ i ] = i;

Same code, except now array is an array instead of a pointer to an array.
array is now a 10-byte "variable" which might be stored in memory at locations 0x2000-0x2009. If I cout << array; I'll get 0x2000. And if I look at memory locations 0x2000-0x2009, I'll see 00 01 02 03 04 05 06 07 08 09.

See the difference? In the first example, array is a pointer that occupies 4 bytes of memory. The value stored there is the address of the first element of the array. In the second example, there is no pointer stored in memory; rather when I reference "array" in code, this is automatically the address of the first element of the array. One less level of indirection.

That's the way I keep pointers and arrays straight, and it explains why arrays and pointers aren't quite the same thing, but they are very similar.