Can you fix this program? : C++ Dynamic Array Problems

I have written the following program using VS2005. The program is a Dynamic
Array similar to System.Collections.ArrayList in .NET. The program works
okay until I reach 65536, I can't seem to figure out why, as it seems my
logic is working okay. I am a .NET programmer so I am not used to dealing
with un-managed C++ code. Please criticize my code if you think it is poorly
written.

This is the loop from main() that will blow up the program if you change
65536 to a larger value.
for(int i = 0; i < 65536; i++)
{
folder.entryID = "Testing";
fc->Add(folder);
}

Thanks
Russell Mangel
Las Vegas, NV

// Begin Code


#include "stdafx.h"
#include <iostream>

using namespace std;

struct Folder
{
char *entryID;
};
class FoldersCollection
{
public:
FoldersCollection::FoldersCollection()
{
Count = 0;
Capacity = 0;
}
FoldersCollection::~FoldersCollection()
{
delete []m_Folders;
}
int Count;
int Capacity;
void FoldersCollection::Add(Folder folder)
{
if(Capacity == 0)
{
m_Folders = new Folder[INITIAL_CAPACITY];
m_Folders[0].entryID = folder.entryID;
Count ++;
Capacity = INITIAL_CAPACITY;
}
else
{
if(Count < Capacity)
{
m_Folders[Count].entryID = folder.entryID;
Count ++;
}
else
{
printf("Resizing Array. Capacity: %d.\n", Capacity);
Resize();

m_Folders[Count].entryID = folder.entryID;
Count ++;
}
}
}
Folder* FoldersCollection::GetList()
{
return m_Folders;
}
private:
Folder *m_Folders;
Folder *m_Temp;
static const int INITIAL_CAPACITY = 4;
void FoldersCollection::Resize()
{
// Double Capacity
int newCapacity = Capacity*=2;
// Create new Array
m_Temp = new Folder[newCapacity];
// Copy elements
for(int i = 0; i < Capacity; i++)
{
m_Temp[i].entryID = m_Folders[i].entryID;
}

delete []m_Folders;
m_Folders = m_Temp;
Capacity = newCapacity;
}
};
void main(void)
{
FoldersCollection *fc = new FoldersCollection;
Folder folder;

// Works okay up to 65536, change to larger value to crash program...
// What I am doing wrong...
for(int i = 0; i < 65536; i++)
{
folder.entryID = "Testing";
fc->Add(folder);
}
printf("Finished... Count: %d Capacity: %d \n", fc->Count, fc->Capacity);
delete fc;
}

re: Can you fix this program? : C++ Dynamic Array Problems

"Russell Mangel" <russell@tymer.net> wrote in message
news:%23$r8GleQGHA.2300@TK2MSFTNGP15.phx.gbl...[color=blue]
> <snip>
>
> void FoldersCollection::Resize()
> {
> // Double Capacity
> int newCapacity = Capacity*=2;[/color]

You probably meant:
int newCapacity = Capacity*2;
[color=blue]
> // Create new Array
> m_Temp = new Folder[newCapacity];
> // Copy elements
> for(int i = 0; i < Capacity; i++)
> {
> m_Temp[i].entryID = m_Folders[i].entryID;
> }[/color]


As it is now, the index goes beyond the allocated capacity of m_Folders
after midway through the loop.

re: Can you fix this program? : C++ Dynamic Array Problems

> int newCapacity = Capacity*=2;[color=blue]
> // Create new Array
> m_Temp = new Folder[newCapacity];
> // Copy elements
> for(int i = 0; i < Capacity; i++)
> {
> m_Temp[i].entryID = m_Folders[i].entryID;
> }[/color]

Hi,

you double the capacity variable and then index the original array beyond
its boundaries.
the fact that it worked until 65536 is pure luck.

My personal opinion is that you should never combine multiple statements and
assignments on 1 line. it is much too easy to make mistakes.

Had you written it like this, you would have seen the problem almost
immediatly probably.
Capacity*=2
int newCapacity = Capacity;

--

Kind regards,
Bruno.
bruno_nos_pam_van_dooren@hotmail.com
Remove only "_nos_pam"

re: Can you fix this program? : C++ Dynamic Array Problems

Russell Mangel wrote:[color=blue]
> I have written the following program using VS2005. The program is a
> Dynamic Array similar to System.Collections.ArrayList in .NET. The
> program works okay until I reach 65536, I can't seem to figure out
> why, as it seems my logic is working okay. I am a .NET programmer so
> I am not used to dealing with un-managed C++ code. Please criticize
> my code if you think it is poorly written.[/color]

The main criticism would be why write it at all? This code is spelled
std::vector<T> in C++. There's simply no need to write code like this
except for the learning exercise of it. A few other criticisms inline
below.
[color=blue]
>
> This is the loop from main() that will blow up the program if you
> change 65536 to a larger value.
> for(int i = 0; i < 65536; i++)
> {
> folder.entryID = "Testing";
> fc->Add(folder);
> }
>
> Thanks
> Russell Mangel
> Las Vegas, NV
>
> // Begin Code
>
>
> #include "stdafx.h"
> #include <iostream>
>
> using namespace std;
>
> struct Folder
> {
> char *entryID;
> };[/color]

Should the above have a destructor? In your example, you're only assigning
character literals to entryID, so the answer is NO, but in the real world,
that might be a different story. If entryID needs to be delete[]'d, then
you should define a destructor, assignment operator and copy constructor for
this class.
[color=blue]
> class FoldersCollection
> {
> public:
> FoldersCollection::FoldersCollection()
> {
> Count = 0;
> Capacity = 0;
> }
> FoldersCollection::~FoldersCollection()
> {
> delete []m_Folders;
> }
> int Count;
> int Capacity;[/color]

You might want to wrap these fields in accessors. As is, a client can
simply change your Count or Capacity, breaking your class from the outside.
[color=blue]
> void FoldersCollection::Add(Folder folder)
> {
> if(Capacity == 0)
> {
> m_Folders = new Folder[INITIAL_CAPACITY];
> m_Folders[0].entryID = folder.entryID;
> Count ++;
> Capacity = INITIAL_CAPACITY;
> }
> else
> {
> if(Count < Capacity)
> {
> m_Folders[Count].entryID = folder.entryID;
> Count ++;
> }
> else
> {
> printf("Resizing Array. Capacity: %d.\n", Capacity);
> Resize();
>
> m_Folders[Count].entryID = folder.entryID;
> Count ++;
> }
> }
> }[/color]

Rewrite the above:

void FoldersCollection::Add(Folder folder)
{
EnsureCapacity(Count+1);
m_Folders[Count++] = folder;
}
[color=blue]
> Folder* FoldersCollection::GetList()
> {
> return m_Folders;
> }[/color]

If you're going to simply expose the inner array, there's little point in
even making a class since a client can simply run roughshod all over your
array once you've returned a pointer. I'd reconsider this design.
[color=blue]
> private:
> Folder *m_Folders;
> Folder *m_Temp;[/color]

Eliminiate the above member varialbe- m_Temp
[color=blue]
> static const int INITIAL_CAPACITY = 4;
> void FoldersCollection::Resize()
> {
> // Double Capacity
> int newCapacity = Capacity*=2;
> // Create new Array
> m_Temp = new Folder[newCapacity];
> // Copy elements
> for(int i = 0; i < Capacity; i++)
> {
> m_Temp[i].entryID = m_Folders[i].entryID;
> }
>
> delete []m_Folders;
> m_Folders = m_Temp;
> Capacity = newCapacity;
> }[/color]

Rewrite this:

void FoldersCollection::EnusreCapacity(int requiredCapacity)
{
if (requiredCapacity <= Capacity)
return;

int newCapacity = Capacity*2;
if (newCapacity < INITIAL_CAPACITY)
newCapacity = INITIAL_CAPACITY;
if (newCapacity < requiredCapacity)
newCapacity = requiredCapacity;

Folder* temp = new Folder[newCapacity];

if (Count > 0)
{
for (int i = 0; i < Count; ++i)
temp[i] = m_Folders[i];
delete[] m_Folders;
}

m_Folders = temp;
}
[color=blue]
> };
> void main(void)
> {
> FoldersCollection *fc = new FoldersCollection;
> Folder folder;
>
> // Works okay up to 65536, change to larger value to crash program...
> // What I am doing wrong...
> for(int i = 0; i < 65536; i++)
> {
> folder.entryID = "Testing";
> fc->Add(folder);
> }
> printf("Finished... Count: %d Capacity: %d \n", fc->Count,
> fc->Capacity); delete fc;
> }[/color]

re: Can you fix this program? : C++ Dynamic Array Problems

> You probably meant:[color=blue]
> int newCapacity = Capacity*2;
> As it is now, the index goes beyond the allocated capacity of m_Folders
> after midway through the loop.[/color]

This fixes the worst of my problems, thanks...
Russ.

re: Can you fix this program? : C++ Dynamic Array Problems

> Carl Daniel wrote: The main criticism would be why write it at all? This[color=blue]
> code is spelled std::vector<T> in C++. There's simply no need to write
> code like this except for the learning exercise of it. A few other
> criticisms inline below.[/color]

The reason I didn't use std:vector is because I don't know how to marshal
the vector back to a Managed .NET client. I am dealing with an API which has
no managed equivilant "Extended MAPI 1.0". and I am calling this code from
Un-Managed clients and Managed clients. Of course I could loop through the
vector in Un-Managed code to build an Folder[] and return it to the clients,
but then this would be an additional loop. Is my thinking good here? Maybe
you have a better idea now that you know a little more what I am trying to
accomplish..

When doing C++/CLI Interop there are so many ways of doing things, it's head
spinning. My intention is to minimize marshalling data across the
Managed/Un-Managed zone. My idea is too pass a single string to the
unmanaged code, and then let the un-managed code build a collection and
return a pointer to the data. For a total of two Interops.

Thanks for taking the time to reply.
Russell Mangel
Las Vegas, NV

re: Can you fix this program? : C++ Dynamic Array Problems

>> struct Folder {[color=blue][color=green]
>> char *entryID;};[/color]
>
> Should the above have a destructor? In your example, you're only
> assigning character literals to entryID, so the answer is NO, but in the
> real world, that might be a different story. If entryID needs to be
> delete[]'d, then you should define a destructor, assignment operator and
> copy constructor for this class.[/color]

This is a great suggestion, and also exposes my weakness when programming in
Native C++ "Memory Management".

I don't know how to delete the memory on the heap for *folder. How would I
delete the memory once it gets inside the FoldersCollection when program is
finished?

Thanks
Russell Mangel

void main (void){
FoldersCollection *fc = new FoldersCollection;
Folder *folder = new Folder;

for(int i = 0; i < 16384; i++) {
folder->entryID = "Testing";
fc->Add(folder); }
}

re: Can you fix this program? : C++ Dynamic Array Problems

"Carl Daniel >[color=blue]
> If you're going to simply expose the inner array, there's little point in
> even making a class since a client can simply run roughshod all over your
> array once you've returned a pointer. I'd reconsider this design.[/color]

Is there some way I could return this (read-only), so the clients can not
change the list?

Thanks,
Russell Mangel

re: Can you fix this program? : C++ Dynamic Array Problems

>> If you're going to simply expose the inner array, there's little point in[color=blue][color=green]
>> even making a class since a client can simply run roughshod all over your
>> array once you've returned a pointer. I'd reconsider this design.[/color]
>
> Is there some way I could return this (read-only), so the clients can not
> change the list?[/color]

Not really. The best you can do is to return a const pointer, but even then
the caller is able to simply
cast away the const qualifier.

What you could do is to provide your own [] operator and not expose your
inner array.
that would give you the ability to implement bounds checking. your []
operator returns a copy of the actual
element, which the caller can abuse, but at least he won't mess up your
internal data.

That would result in more marshalling of course.

another thing you can do is to provide a function to which the caller has to
supply a pre allocated array that you can fill in.

As you said, there are multiple ways of doing things from which you can
choose, depending on needs and taste.

--

Kind regards,
Bruno.
bruno_nos_pam_van_dooren@hotmail.com
Remove only "_nos_pam"

re: Can you fix this program? : C++ Dynamic Array Problems

> Bruno wrote:[color=blue]
> What you could do is to provide your own [] operator and not expose your
> inner array.
> that would give you the ability to implement bounds checking. your []
> operator returns a copy of the actual
> element, which the caller can abuse, but at least he won't mess up your
> internal data.
>
> That would result in more marshalling of course.[/color]

This idea of yours may work, I'm not sure that this would cause any extra
marshalling. Maybe you can think about this a little more. Why would this
cause more marshalling?

What I am trying to do:
================
Pass a single string to Unmanaged code (First Marshal).
Unmanaged code loops and gathers an array of strings (char *).
Unmanaged code returns a pointer to the innerArray[] (Second Marshal).

Both managed and unmanaged clients can now unwind/access the inner array
using the [] operator.

What am I missing? This shouldn't cause any more marshaling should it?

Russell Mangel
Las Vegas, NV

PS
The Folder struct will have more members than were initially listed, there
will be at least 8 members consisting of:
3 Byte[] arrays, 2 Int32's, 1 Int64, 2 Strings.

re: Can you fix this program? : C++ Dynamic Array Problems

// Here is another complete version of the code which has some of the
changes suggested from a few people who replied to my original post
// Thanks for all your help everyone.

#include "stdafx.h"

struct Folder
{
char *entryID;
};
class FolderCollection
{
public:
FolderCollection::FolderCollection()
{
m_Count = 0;
m_Capacity = 0;
}
FolderCollection::~FolderCollection()
{
delete []m_Folders;
}
int FolderCollection::Count()
{
return m_Count;
}
int FolderCollection::Capacity()
{
return m_Capacity;
}
void FolderCollection::Add(Folder folder)
{
if(m_Count > 0)
{
if(m_Count < m_Capacity)
{
m_Folders[m_Count].entryID = folder.entryID;
m_Count ++;
}
else
{
printf("Resizing Array. Capacity: %d.\n", m_Capacity);

Resize();

m_Folders[m_Count].entryID = folder.entryID;
m_Count ++;
}
}
else
{
// First time initialization
m_Folders = new Folder[INITIAL_CAPACITY];
m_Folders[m_Count].entryID = folder.entryID;
m_Count ++;
m_Capacity = INITIAL_CAPACITY;
}
}
Folder *FolderCollection::GetList()
{
return m_Folders;
}
private:
int m_Count;
int m_Capacity;
Folder *m_Folders;
static const int INITIAL_CAPACITY = 4;
void FolderCollection::Resize()
{
// Double Capacity
int newCapacity = m_Capacity * 2;

Folder *temp = new Folder[newCapacity];

// Copy existing elements
for(int i = 0; i < m_Capacity; i++)
{
temp[i].entryID = m_Folders[i].entryID;
}

delete []m_Folders;

// Re-assign temp pointer
m_Folders = temp;
m_Capacity = newCapacity;
}
};
void main(void)
{
FolderCollection *fc = new FolderCollection;
Folder folder;

for(int i = 0; i < 8192; i++)
{
folder.entryID = "Testing";
fc->Add(folder);
}
printf("Finished... Count: %d Capacity: %d \n", fc->Count(),
fc->Capacity());

delete fc;
}