memory leak?

[seanbp]

I was reading a post somewhere on this site about making a type-dynamic list and came up with this. The issue is I'm thinking it's leaking memory when the list grows. Finally, are there any ways to improve this code?

#include <iostream>

using namespace std;

class DynamicType {
public:
    union {
        int integer;
        char* string;
    };
    enum {
        is_int,
        is_string
    } what_type;
};

class DynamicTypeList {
    DynamicType* data;
    DynamicType* data_begin;
    DynamicType* data_end;
    int len;
    int actual_len;
    int increment;
    void expand() {
        int oldlen = actual_len;
        actual_len += increment;
        DynamicType* temp = new DynamicType[actual_len];
        data = data_begin;
        for (int i = 0; i < oldlen; i++) {
            temp->what_type = data->what_type;
            if (temp->what_type == temp->is_int)
                temp->integer = data->integer;
            else if (temp->what_type == temp->is_string)
                temp->string = data->string;
            temp++;
            data++;
        }
        //delete data;
        data = temp;
    }
public:
    DynamicTypeList() {
        len = 0;
        increment = 10;
        actual_len = increment;
        data = new DynamicType[increment];
    }
    void add(int i) {
        if (len == actual_len) expand();
        len++;
        data->what_type = data->is_int;
        data->integer = i;
        data_end = data;
        if (len == 1) data_begin = data;
        data++;
    }
    void add(char* sz) {
        if (len == actual_len) expand();
        len++;
        data->what_type = data->is_string;
        data->string = sz;
        data_end = data;
        if (len == 1) data_begin = data;
        data++;
    }
    DynamicType* begin() const {
        return data_begin;
    }
    DynamicType* end() const {
        return data_end + 1;
    }
};

int main (int argc, char** argv) {
    
    DynamicTypeList list;
    list.add(42);
    list.add("forty-two");
    list.add(44);
    list.add("forty-four");

    for (DynamicType* item = list.begin(); item != list.end(); item++) {
        if (item->what_type == item->is_int) {
            cout << item->integer << endl;
        } else if (item->what_type == item->is_string) {
            cout << item->string << endl;
        }
    }
    return 0;
}

[Nick Evan]

>> DynamicType* temp = new DynamicType[actual_len]; Where's the matching delete[] ?

[seanbp]

>> DynamicType* temp = new DynamicType[actual_len]; Where's the matching delete[] ?

temp is a copy of data, with more room. Its pointer then replaces data. I don't know how to delete the old data without deleting the DynamicType structures within.

[seanbp]

Here is what doesn't work.

void expand() {
        int oldlen = actual_len;
        actual_len += increment;
        DynamicType* temp = new DynamicType[actual_len];
        DynamicType* temp_begin = temp;
        data = data_begin;
        for (int i = 0; i < oldlen; i++) {
            temp->what_type = data->what_type;
            if (temp->what_type == temp->is_int)
                temp->integer = data->integer;
            else if (temp->what_type == temp->is_string)
                temp->string = data->string;
            temp++;
            data++;
        }
        delete data;
        data = temp;
        data_end = temp;
        data_begin = temp_begin;
    }

[mike_2000_17]

Here is how it should work:

void expand() {
        int oldlen = actual_len;
        actual_len += increment;
        DynamicType* temp = new DynamicType[actual_len];
        DynamicType* temp_begin = temp;
        data = data_begin;
        for (int i = 0; i < oldlen; i++) {
            temp->what_type = data->what_type;
            if (temp->what_type == temp->is_int)
                temp->integer = data->integer;
            else if (temp->what_type == temp->is_string)
                temp->string = data->string;
            temp++;
            data++;
        }
        delete[] data_begin; //notice this line has changed
        data = temp;
        data_end = temp;
        data_begin = temp_begin;
    }

Since you are allocating an array, you should use the delete[] operator (not just "delete"). Also, since you have been incrementing data up to the end of the "oldlen", you need to delete the original pointer, i.e. "data_begin".

Note: typically, these dynamic arrays are implemented by doubling the capacity every time you need an expansion (not using a fixed increment). Algorithmically, it makes no sense to use a fixed increment for the capacity because it's not scalable. If your program ends up needing 18 elements in the array, you will require 2 memory re-allocations and copy (instead of 18 if you keep only the exact number of elements needed). However, if your program needs one million elements, then you will require 100,000 reallocations (that is only a 90% improvement). If you grow the array size by a factor of 2 each time you need more space, you end-up needing at most 20 reallocations, that's much better!

[seanbp]

Thank you, Mike. I failed to realize deletion is done from offset zero.

void expand() {
        int oldlen = actual_len;
        actual_len *= 2;
        DynamicType* temp = new DynamicType[actual_len];
        DynamicType* temp_begin = temp;
        data = data_begin;
        for (int i = 0; i < oldlen; i++) {
            temp->what_type = data->what_type;
            if (temp->what_type == temp->is_int)
                temp->integer = data->integer;
            else if (temp->what_type == temp->is_string)
                temp->string = data->string;
            temp++;
            data++;
        }
        delete[] data_begin;
        data = temp;
        data_end = temp;
        data_begin = temp_begin;
    }