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.

"Wouldn't it be smarter to use STL" of course it would. :) But if it's an assignment, this has educational value. — Luchian Grigore, Aug 22 '12 at 15:58
ATM isn't a standard or well-known term in C++. Does your assignment/course define it? — Mike Seymour, Aug 22 '12 at 16:01
Even if you always use STL for the rest of your life, it is never a bad thing to be able to use new and delete to do your own memory allocation. Even if only to be able to understand the code of other people — mathematician1975, Aug 22 '12 at 16:01
your assignment is a bit unclear, but in general you can easily emulate vector most important functionality if you wish so. But you dont need that since you know the number of elements. Regarding buffer overflows: You should throw exception if number of lines asfter number isnt number. :D — NoSenseEtAl, Aug 22 '12 at 16:03
ah seems the array isn't so dynamic as it won't expand or shrink according to the assignment Many thanks for clarification on real world use. — user1617478, Aug 22 '12 at 16:08
It's good to understand dynamic allocation and other basics so that you can know how STL, Boost, Qt, or any code or library works. — AJG85, Aug 22 '12 at 16:09
As regards buffer overflows, you could just treat the line count like a checksum or parity bit, etc. Read the file in line by line anyway, and throw an exception if you reach EOF prematurely, or fail to reach EOF when you've read as many lines as were specified. — Rook, Aug 22 '12 at 16:13
Most of my career has been spent in an environment building embedded systems where the use of new and delete is prohibited by the customer. What is "smarter" isn't always relevant in the real world :) — Poodlehat, Aug 22 '12 at 16:15

score 4 · Accepted Answer · edited May 23 '17 at 10:34

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.

This is a very informative post, thank you for explaining the dangers. Usually I use a de constructor to deallocate — user1617478, Aug 22 '12 at 16:25

score 1 · Answer 2 · answered Aug 22 '12 at 16:02

1

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.

answered Aug 22 '12 at 16:02

derekerdmann

17,696
11
76
110

5

Actually the *common* approach would be to decide that you can never have more than 1024 entries, use a fixed array and hope for the best ;-) – Martin Beckett Aug 22 '12 at 16:03
Does anyone actually do this in production? Or is this more of a learn how it works type of thing? – user1617478 Aug 22 '12 at 16:09
@user1617478: Lots of people *do*; but in my opinion none of them *should*. But it's certainly useful to learn how memory management works, and why you should avoid doing it yourself when possible. – Mike Seymour Aug 22 '12 at 16:24
@user1617478 Don't worry about what is done in production code just yet. Most of what you learn in college doesn't scale to the real world but when you graduate you can proudly say you've acquired the basics and are ready to start learning ;-) – AJG85 Aug 22 '12 at 16:27
@user1617478 - In the real world, just use the STL. This is mostly an exercise in a managing dynamic memory, not one you should replicate in production. – derekerdmann Aug 22 '12 at 19:26

score 0 · Answer 3 · answered Aug 22 '12 at 16:10

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.

I've always thought vector managed memory much more efficiently than a basic when full make a bigger array and copy it over. — user1617478, Aug 22 '12 at 16:13
@user1617478: Since the vector's memory has to be a single, contiguous block, that's the only way to manage it. It makes it as efficient as possible by growing exponentially (which reduces the number of reallocations as it grows), and allowing you to reserve space to avoid reallocations. — Mike Seymour, Aug 22 '12 at 16:39

score 0 · Answer 4 · answered Aug 22 '12 at 16:14

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.

score -1 · Answer 5 · answered Aug 22 '12 at 16:20

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

Make a class myDynamicArray
Make the class contain an int or long to store array size
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.
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.
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/

C++ dynamic array without STL

5 Answers5