Lab 3.10.2 Dynamic data – how to obtain it and how to get rid of it

Question

So, the problem presented is,

Look at the code below – it's a skeleton of a program operating on the dynamic collection of data.

The idea is to use a structure containing two fields: the first stores the number of elements in collections, and the second is the actualcollection (a dynamically allocated vector of ints).

As you can see, the collection is filled with the required amount of pseudo-random data.

Unfortunately, the program requires completion, as the most important function, intended to add elements to the collection, is still empty.

Here's what we expect from the function:

if the collection is empty, it should allocate a one-element vector and store a new value in it;

if the collection is not empty, it should allocate a new vector with a length greater by one than the current vector, then copy all elements from the old vector to the new one, append a new value to the new vector and finally free up the old vector.

I'm not hoping for the solution or anything but a pointer in the right direction would be greatly appreciated.

I've been tinkering at it for a while, and managed to get it to at least make array larger by one, but it only ever seems to copy over the location of the first value.

My code is just the stuff under AddToCollection, by the by.

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
struct Collection {
int elno;
int *elements;
};
void AddToCollection(Collection &col, int element) {
// Insert your code here


if(col.elements != NULL) {
    col.elno = sizeof(col.elements);
    ++col.elno;
    int *jeffry = new int[col.elno + 1];
    jeffry[col.elno] = element;
    for (int f = 0; f < (col.elno - 1); f++) {
        jeffry[f] = col.elements[f];
    }


    col.elements = jeffry;
}
if(col.elements == NULL){
    col.elements =new int[element];

    }

}

void PrintCollection(Collection col) {
cout << "[ ";
for(int i = 0; i < col.elno; i++)
    cout << col.elements[i] << " ";
cout << "]" << endl;
}

int main(void) {
Collection collection = { 0, NULL };
int elems;
cout << "How many elements? ";
cin >> elems;
srand(time(NULL));
for(int i = 0; i < elems; i++)
    AddToCollection(collection, rand() % 100 + 1);
PrintCollection(collection);
delete[] collection.elements;
return 0;

}

Answer 1

You are getting there, but what you are not quite getting is (1) col.elno = sizeof(col.elements); is invariant and is actually equivalent to col.elno = sizeof(a_pointer); (which is not what you want), and (2) there are two mutually-exclusive conditions you must handle within AddToCollection.

1. col.elements is not yet allocated, where you simply allocate an array of 1 and set the first element to element while incrementing col.elno; and
2. col.elements has been previously allocated and you must essentially realloc (col.elements, ...) using new and delete[].

Since you must copy your old col.elements to the new block of memory you allocate in the 2nd case above, it helps to include <cstring> to provide memcpy to help in that regard. The approach is simple. Create a new integer array of col.elno + 1 elements, then memcpy your existing col.elements to your new block before you delete[] col.elements. Then just assign your new block of memory to col.elements before setting col.elements[col.elno++] = element;.

You could do:

void AddToCollection (Collection &col, int element)
{
    if (!col.elements)
        col.elements = new int[1];
    else {
        int *tmp = new int[col.elno + 1];
        memcpy (tmp, col.elements, col.elno * sizeof *col.elements);
        delete[] col.elements;
        col.elements = tmp;
    }
    col.elements[col.elno++] = element;
}

note: you should always validate your memory use by using a memory error checking program such as valgrind for Linux. (there are similar checkers for each OS).

Your program then becomes:

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cstring>

using namespace std;

struct Collection {
    int elno;
    int *elements;
};

void AddToCollection (Collection &col, int element)
{
    if (!col.elements)
        col.elements = new int[1];
    else {
        int *tmp = new int[col.elno + 1];
        memcpy (tmp, col.elements, col.elno * sizeof *col.elements);
        delete[] col.elements;
        col.elements = tmp;
    }
    col.elements[col.elno++] = element;
}

void PrintCollection(Collection col) {
    cout << "[ ";
    for(int i = 0; i < col.elno; i++)
        cout << col.elements[i] << " ";
    cout << "]" << endl;
}

int main(void) {

    Collection collection = { 0, NULL };
    int elems;

    cout << "How many elements? ";
    cin >> elems;
    srand (time(NULL));

    for (int i = 0; i < elems; i++)
        AddToCollection (collection, rand() % 100 + 1);

    PrintCollection(collection);

    delete[] collection.elements;

    return 0;
}

Example Use/Output

$ ./bin/dyncolelements
How many elements? 10
[ 1 21 26 24 57 26 99 86 12 23 ]

Memory Use/Error Check

$ valgrind ./bin/dyncolelements
==11375== Memcheck, a memory error detector
==11375== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==11375== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info
==11375== Command: ./bin/dyncolelements
==11375==
How many elements? 10
[ 14 32 40 65 10 4 38 72 64 83 ]
==11375==
==11375== HEAP SUMMARY:
==11375==     in use at exit: 0 bytes in 0 blocks
==11375==   total heap usage: 11 allocs, 11 frees, 72,924 bytes allocated
==11375==
==11375== All heap blocks were freed -- no leaks are possible
==11375==
==11375== For counts of detected and suppressed errors, rerun with: -v
==11375== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Always verify all heap blocks were freed and there are no leaks are possible and there are no errors reported.

Look things over and let me know if you have further questions.