C++ array question

Is possible to declare an array with a variable number of entries without using dynamic memory allocation? My CS prof has promised $5.00 to anyone who can come up with a way.

An array? No. However, you can just use an STL vector, which does much the same thing.

What about this?

struct fishAttributes
{
char *pszFishName;
bool bTastesGood;
} fishArray =
{
{“Salmon”, true},
{“Sole”, false},
{“Trout”, true}
};

It’s dynamic at compile time, but not at run time.

How is that dynamic? It’s an array of 3 FishAttributes.

Do you mean an array with a number of entries that is determined at runtime? That would be yes.

Or, do you mean an array that you can change the size after it’s declared? That would be no.

For the first question, it’s so easy I won’t give you a code sample. Just try the obvious.

For the second question, you have to use dynamic allocation to change the size of an existing array. Or you can let the STL do it for you. (The STL is using dynamic allocation, so it’s still “no”.)

What about using a union?



union vararray
{
    int ten[10];
    int twenty[20];
    int thirty[30];
}


I don’t do C any more, so I don’t really know if this is legal.

flymaster I agree it’s not run-time dynamic, but it is compile time dynamic.

The only other solution I would suggest relies on the recognition that arrays are just C/C++ decoration for raw memory management. For example, when you say x[27] you are really saying take the address of x[0], add 26 times the size of x to it, and use that location. The solution consists of defining array elements that are fixed size, allocating a big block of memory, and doing the math yourself. Something like;

struct fishAttributes
{
char szfishname[20];
bool bTastesGood;
}

char *pStart = malloc(65536); // a big malloc

and now you can access anything in there to your hearts content by doing;

(fishAttributes )((pStart + (index * sizeof(fishAttributes)))

This seems like the point the teacher might be trying to make.

You could erect all kinds of testing around this to see if it’s necessary to do a realloc if you go beyond memory boundaries, etc.

Did your professor say it was possible? If he did, then I think the question needs to be clarified, exact wording if possible.

Though IMO, you could have a “variable” array like so:

struct VarItemArray
{
int nItems;
float afItem[1];
};

Wait, I’m not done yet. When used in the following manner, you can use it like it’s a variable array.

char newArray[sizeof(int) + (sizeof(float) * NUM_ITEMS)];
VarItemArray* pArray = (VarItemArray*) newArray;

pArray->nItems = NUM_ITEMS;
pArray->afItem = 1.0f;

NUM_ITEMS would be however many items you wanted. Then you could pass this structure to another function, which would use the nItems field to know how big it was.

It’s bad coding practice, so I wouldn’t use this in real production code (use an std::vector instead).

Well, you could put it on the stack. That would still be “dynamic allocation” (as opposed to static allocation), but it’s different from the heap, which is where most dynamic allocation (new and malloc) get done. I don’t see a nice way of making an actual array this way without using some assembly code, but you could make an dynamically-sized linked list on the stack in legal C++ (and then, if you want, build an array-like class on top of it, for access).

To (again) add my two bits, I’ll provide the simplest example, using the typesafe new and delete instead of the untypesafe malloc and free:

int nItems;
float *afItem;

//…

//Do something to put a size in nItems, then:
afItem=new float[nItems];

You can then use afItem as if it were an array (this point has already been adequately made here).

Remember to free it up:

deleteafItem;

If you need to resize it, you’ll have to make a new array, copy over the elements, delete the old array, move the pointer to the new array into the original variable, and update the nItems size variable appropriately.

Of course, isolating this behaviour within a struct, or better yet a class where the elements are properly protected from direct access (and providing perhaps an overloaded operator to mimic array behaviour) is best, but then you basically have the beginnings of the STL vector class.

All you really need is the pointer variable and a single new statement using array-new as above (plus, later, the array-delete as above), but without the size count held around somewhere, you’ve no way to know how big the allocated array is.

In the event you don’t have access to the prewritten STL vector class for any reason (and yes, this most definitely happens in production code), one of these many methods would have to be employed. It shouldn’t surprise anyone that much more code for C and C++ has been written before the existence and stabilization than after it. Personally I can’t use the standard STL because of its dependancy on exceptions for reporting errors, for another example.

Oops, smack me senseless for not reading the opening paragraph. I didn’t see the no dynamic allocation restriction. Of course most of the solutions here involve dynamic allocation so I don’t feel so bad.

My solution then involves declaring a large static array from which you grab ‘blocks’:

static char acBuf[MAXSIZE];

Then, an index into that buffer:

static int iCurBuf=0;

Later, at the start of your function, when you want to grab N items of type T:

int iLastBuf=iCurBuf;
iCurBuf+=sizeof(T)-iCurBuf%(sizeof(T)); //align the buffer
T arrayOfT=reinterpret_cast<T>(&acBuf[iCurBuf]);
iCurBuf+=sizeof(T)*N);

Then, at the end of your function, to restore things:

iCurBuf=iLastBuf;

No pleasant type safety, and it does require a known maximum size for your whole program, and its not multithread safe, but for a typical single-threaded program with some known upper limits in data sizes, it’s a workable solution.

I’ve got a much MUCH more twisted solution brewing in my head. Stay tuned.

Hmm, if we’re inspired to consider twisted solutions, here is one, lifted from a bug I once experienced;

typedef struct
{
char szfishname[20];
bool bTastesGood;
} fishAttributes;

fishAttributes fa;
fishAttributes fa_extra[1000];

Using an MS compiler, under Windows, you can now access 1001 locations by indexing fa. This relies on the compiler allocating fa and fa_extra at contiguous memory locations – essentially seeing the two declarations as one. The bug I learned this from was;

int x[100];
int i;

for (i = 0; i <= 100; i++)
{
x* = 0;
}

This loop never finishes, because when x[100] is reached, it runs off the end of the array to the location reserved for i, i gets set to 0 and the loop starts again. Of course the fix is to replace <= with <.

How highly compiler dependant. :biggrin:

I’m after a solution inspired by Omphaloskeptic which should work on a fair number of machines/compilers but is almost certainly nonportable. :smiley:

I preface this solution with a warning:

This is a truly and impressively daft thing to do, should not be used in any production code lest ye be interested in the worst kind of debugging hell, and is nigh on disturbing Magikal Haquery (my own term).

Once again: Never ever ever do this.

Assumptions:

  1. that the compiler will not inline a recursive function
  2. that if a function takes up n bytes of stack space to call once, it will take the same amount any other time (pretty safe assumption).
  3. that an array of characters on its own will be aligned by the compiler such that any data type may be safely overlayed on top of it (if this is not true, some additional code can correct the problem).
  4. You want to have a run-time-defined array that has no compile-time fixed upper limit, but it does not need to be resized.
  5. That addresses in one function call are comparable in some way to addresses in another function call (somewhat outside the standard, but fairly typically workable).
  6. that the program has infinite stack space.

Assumption 6 is typically broken by the compiler and OS having a fixed relatively small stack size. However, assuming an n kilobyte stack, we’ll simply assume that that’s the hard upper limit to the number of bytes useable for the array (and of course somewhat less as other stuff is sitting on the stack).

So it’s not that important that that assumption is broken.
The program asks for a number of values the user will be entering. The program then asks for these values one by one, puts them in an array, and works out the number of them that are below the average of all of them. This can only be done by having access to all of the elements at once, so it is the ideal test case for the array.

Note something important: Once NumBelowAverageInternal is entered, we’re computing a place to put an integer by way of an assignment of a pointer piDynamicArrayPosition to somewhere in memory:

  int *piDynamicArrayPosition=(reinterpret_cast&lt;int *&gt;(acDynBuf+i*sizeof(int)+(i/iElementsPerBlock*iFrameOffset)));

While it doesn’t look like there’s any array in existence in that function, the computation of this results in a pointer which points to a unique integer in memory in which to store the n items of data.

I claim this is equivalent to using an ordinary array because:

  1. any element i can be accessed in constant time, a requirement for behaving like a C/C++ ordinary array.
  2. the elements can be accessed in any order (random access), also a requirement.
  3. the elements are indexed from i==0 (not a requirement for an array, but done to remain consistent with C/C++ arrays)

It is semantically equivalent to:

int *piDynamicArrayPosition=&somearray[ i ];

to set the pointer to the ith element of a fixed sized array somearray, but some additional math needs to be done to move between stack frames.

Note that there is no dynamic memory allocation happening (in the traditional sense of malloc/free or new/delete). There is also no fixed upper limit (except for the artificial limitation of stack size, which is outside of the program). There is a buffer size constant RAWBLOCKSIZE that must be selected to be at least as large as the largest single element from which you’d like to make an array, but can be larger. This is the only compile-time constant needed.

Also, note that the amount of space actually used is proportional to the number of elements, although the usage goes up in increments of the RAWBLOCKSIZE.

Note, too, that this only works for one such array, but you could chain this effect indefinitely to chew up stack space for your dynamically sizeable arrays.

It’s interesting to note that some of the parameters to DynamicArray, including RAWBLOCKSIZE and iSize, could be removed by making DynamicArray a function template. By making it a function template you could also remove DynamicArray’s dependancy on the exact format of the function pointer and the parameter block it accepts, making it truly generic.

I await your oh my good sweet lord in heavens of fear, uncertainty, and horror. :smiley: I’ve truly tried to frighten you all. I hope you find my submission worthy.



**
#include <iostream>
using namespace std;

struct NumBelowAverageParameters;
const int RAWBLOCKSIZE=16;
void DynamicArray(int iElements,int iSize,void (*pf)(const NumBelowAverageParameters &stData,char *aiDynBuf,int iElementsPerBlock,int iFrameOffset),const NumBelowAverageParameters &stData,char *pcBase=0UL,int iFrameOffset=0)
{
   char acData[RAWBLOCKSIZE];
   iElements-=RAWBLOCKSIZE/iSize;

   //cout << (unsigned long)acData << endl;

   if (pcBase==0UL)
   {
      pcBase=acData;
   }
   else if (iFrameOffset==0)
   {
      iFrameOffset=acData-pcBase;
      iFrameOffset-=(RAWBLOCKSIZE-RAWBLOCKSIZE%iSize);
   }

   if (iElements<=0)
   {
      pf(stData,pcBase,RAWBLOCKSIZE/iSize,iFrameOffset);
   }
   else
   {
      DynamicArray(iElements,iSize,pf,stData,pcBase,iFrameOffset);
   }
}


struct NumBelowAverageParameters
{
   int n;
   int *piResult;
};
//--------------------------------------------------------------------
//NumBelowAverage takes a parameter block reference to a strucutre
//containing the number of items to ask for, as well as the address
//of the result variable.
//It also takes acDynBuf, a pointer to a char which constitutes the
//start of a series of blocks (hopefully equally spaced) sufficient
//to hold a certain number iElementsPerBlock of integer elements.
//Lastly, it takes iFrameOffset, the distance in characters between
//the end of one block and the start of the next.
//--------------------------------------------------------------------
void NumBelowAverageInternal(const NumBelowAverageParameters &stData,char *acDynBuf,int iElementsPerBlock,int iFrameOffset)
{
   //cout << "Starting..." << endl;
   int i;
   for (i=0;i<stData.n;++i)
   {
      int *piDynamicArrayPosition=(reinterpret_cast<int *>(acDynBuf+i*sizeof(int)+(i/iElementsPerBlock*iFrameOffset)));
      //cout << (unsigned long)piDynamicArrayPosition << endl;
      cout << "Enter item #" << i << " :";
      cin >> *piDynamicArrayPosition;
      cin.ignore();
   }

   int iSum=0;
   for (i=0;i<stData.n;++i)
   {
      int *piDynamicArrayPosition=(reinterpret_cast<int *>(acDynBuf+i*sizeof(int)+(i/iElementsPerBlock*iFrameOffset)));
      iSum+=*piDynamicArrayPosition;
   }

   double dAverage=static_cast<double>(iSum)/stData.n;
   
   int iCountBelowAverage=0;

   for (i=0;i<stData.n;++i)
   {
      int *piDynamicArrayPosition=(reinterpret_cast<int *>(acDynBuf+i*sizeof(int)+(i/iElementsPerBlock*iFrameOffset)));
      if (*piDynamicArrayPosition<dAverage)
         ++iCountBelowAverage;
   }
   *(stData.piResult)=iCountBelowAverage;
}

//--------------------------------------------------------------------
//NumBelowAverage takes an integer number of parameters to read in.
//It will then (with the help of DynamicArray and
//NumBelowAverageInternal) ask the user for n integer items,
//and report back how many entered are below the average of those
//items.
//--------------------------------------------------------------------
int NumBelowAverage(int n)
{
   int iNumBelow;

   NumBelowAverageParameters stParms={n,&iNumBelow};
   DynamicArray(n,sizeof(int),NumBelowAverageInternal,stParms);

   return iNumBelow;
}

//--------------------------------------------------------------------

int main()
{
   int iResult;
   int iNumEntries=0;

   cout << "Number of Entries: ";
   cin >> iNumEntries;
   cout << endl;
   iResult=NumBelowAverage(iNumEntries);
   cout << "Num Below Average is: " << iResult << endl;

   cin.get();
   return 0;
}

**

If your compiler supports it, you can use the alloca() function for this. Works just like malloc(), but the allocated memory is part of the caller’s stack frame, so it’s automatically deallocated when the calling function returns.

Alloca isn’t exactly portable, but it’s available in Linux, 4.3BSD, and MacOS X, at least.

As to the OP - an array that can change size has got to involve dynamic allocation at some point, no matter how you implement it. However, if you just want the size to be determined at runtime, remember that the array bounds in a variable definition don’t have to be constant expressions.

ZenBeam: That declaration is legal but it isn’t dynamically sized. The union’s size is the size of the largest member, in this case the size of “thirty”. All the union members overlap in memory, so indexing “ten” or “twenty” is exactly equivalent to indexing “thirty” (since they’re all the same type).

This is not exactly correct. To quote from the ISO C++ 1998 standard, clause 8.3.4: Arrays:



In a declaration T D where D has the form

D1 [constant-expression-opt]

...  If the constant expression (5.19) is present, it shall be
an integral constant expression and its value shall be
greater than zero. The constant expression specifies the
bound of (number of elements in) the array...


For example, the following code is illegal:



void
xxx(int n)
{
    char a[n];
}


I have tried it on gcc 2.95.3, Sun WorkShop 6, and MS Visual Studio .NET. Both the Sun and MS compilers rejected this program, although strangely gcc accepted it. It is probably a GNU language extension.

IMHO, this is a very sensible constrain by the standard. Otherwise, compiling the above code fragment may get difficult.

I apologize… you are correct. I just tried the code, and C++Builder rejects it as well.

I knew I read somewhere that variables could be used as array bounds, but come to think of it, I probably read that in the GCC manual. :wink:

God, I’m glad I switched to Java.

I remember hearing about this in my C++ classes oh-so-many-years-ago. We did most of our programming with gcc, but we were instructed not to write code using this feature Because It Is Wrong. On the other hand, it does work, so the professor might accept it as an answer – can’t hurt to try.

Anybody tried my program on something other than MSVC++? I’m curious but don’t have another compiler immediately available.

w.r.t. Java, by the way, I defy you to create any array in Java without dynamic allocation, much less a run-time-sizeable one. :smiley: IMHO, whatever language you use will have its own pitfalls and benefits.

So, anyway, can someone try out what I did on gcc or Borland Builder or something non-Microsoft? Perhaps CodeWarrior or something on a Mac?

Anyhoo…