C++ dynamic array without STL

Question

This is part of an assignment however I just asking for clarification:

Load data from ATM.txt and store them in a dynamic array (ATM type, not STL) when the program starts up.

How exactly do I do dynamic arrays without STL? I thought perhaps the assignment means using pointers, the "ATM Type" threw me off.

It's mentioned again:

file accounts.txt into a dynamic array (Account type, not STL)

--not part of Assignment

I've never understood the use of memory unsafe operations, eg pulling the number of items in a file from the first line:

eg.

5
abc
def
hij
kml
mno

Wouldn't it be smarter to use STL (vectors, or C++11 arrays) and not rely on the number in the file as it may not be accurate causing buffer overflows etc?

//Edit Define a class Account in a file Account.h which contains the data members: customer id, BSB number, etc.

I assume Account and ATM types are those classes.

Answer 1

The most basic form of dynamic array is one created using new[], and destroyed using delete[]:

ATM * atms = new ATM[count];
// do stuff with the array
delete [] atms;

However, this brings the danger that the code using the array might throw an exception, return from the function, or otherwise prevent the delete[] from happening. If that happens, then you will lose the only pointer to the allocated memory, and it will remain allocated but inaccessible; this is known as a memory leak. For this reason, it's better to wrap the array in a class, with:

• member variables to store a pointer to the array, and (optionally) its size
• constructors and/or functions to allocate the array
• a destructor to delete the array
• (optionally) function(s) to resize the array

Deleting the allocation in an object's destructor uses the principle of RAII to ensure that the array is deleted once it is no longer needed.

This leaves one more danger: if you copy this array object, then you will end up with two objects that both try to delete the same array, which is disasterous. To prevent this, you'll need to consider the Rule of Three. Either write a copy constructor and copy-assignment operator to allocate a new array and copy the contents; or delete them. (If you're learning old-fashioned C++, then you can't delete member functions, so you'll have to declare them private and not implement them instead).

Wouldn't it be smarter to use STL?

Usually, yes. But if you're learning C++, it's a good idea to understand how memory management works, as well as how to get the library to handle it for you. That's probably part of the point of this exercise.

Answer 2

Since this is homework we don't want to give answers directly, but in general what I suggest is:

1. Make a class myDynamicArray
2. Make the class contain an int or long to store array size
3. Allocate memory for your array using "new". From the assignment, it looks like it might be an array of strings or, if the professor is strictly banning STL (string is now considered STL), it will be an array of character arrays.
4. Write an insert method which, before inserting, checks the size (see #2) of your array and, if it isn't large enough, makes it bigger. One way to do this without using pre-C++ functions, which I assume is best since this is a C++ class, is to allocate a new array of larger size --> copy data from old array --> Insert any new data. How much larger? You might pick, say, 20% larger with each new allocation. Microsoft's C# allocates "the next largest prime number" of elements, though they have really fast memory allocation routines.
5. Don't forget to delete() the dynamic array when finished with it (what "finished" means depends on the assignment). Note that once the program exits, technically the memory should be freed up automatically, but it's very bad practice to not free it up yourself (think larger, non-academic programs that aren't regularly shut down).

I'd avoid the template code another user provided. I'm sure it's great code, but it's going to raise an eyebrow to use something that advanced in an early C++ class.

Suggested reading: http://www.cplusplus.com/doc/tutorial/dynamic/

Answer 3

Wouldn't it be smarter to use STL (vectors, or C++11 arrays) and not rely on the number in the file as it may not be accurate causing buffer overflows etc?

The internals of std::vector aren't magic. It's possible to manually do yourself what std::vector does for you.

It sounds like that's what you're supposed to do for this assignment; make your own 'ATM type' that can manage reading data safely from the ATM.txt file, and an 'Account type' that can hold data from the accounts.txt file. You should probably get some clarification from whomever wrote the assignment on how exactly they expect these types to be designed/used. Also looking back at whatever class materials you have should tell you what you need to know in terms of using dynamic arrays.

Answer 4

Basically if you need to implement a dynamic array without using STL, you have to deal explicitely with memory allocation/deallocation.

Basically you have to:

• Allocate space with malloc the first time array is constructed or used
• Keep track of inserted/removed elements
• Use realloc when you have finished the allocated space
• Free the allocated space when the array is destroyed

Of course implementing a good STL like container like std::vector isn't an easy task (eventually a nice homework!).

What I can suggest is the following:

• Avoid as much as possible reallocation. When the space is finished, allocate some more space in order to avoid to continuosly call realloc (see std::vector::reserve)
• Avoid to realloc space when elements are removed. Once you have allocated, unless memory usage is too high, let the allocated space as is, in order to avoid future reallocation.

Answer 5

A common approach for this kind of assignment would be to simulate the auto-expanding behavior of a vector on your own. Allocate an array for your data on the heap, and keep track of its length and the number of items you've stored in the array.

Once you've filled the array with your data, expand the maximum size by some amount and allocate a new array. This allows you to copy the data from the old array into the new array, and then continue adding items until you run out of space again.