3
\$\begingroup\$

I am a new C++ developer who, coming from Java, am having issues in understanding some of C++'s key memory management features. Below is my attempt at an ArrayList implementation and I would really love criticism and ways to improve.

Problems I noticed: Can not create an ArrayList object

Questions: In expandArray(), is delete[] required since the data is set in the next line? In my functions such as add(T &d) I figured the parameter should be a reference. Is this necessary? Would the program still work with the variable as a reference? There is no null value in C++ (besides with pointers), so in my function get(int index) I just use return; for a value it could not find.

ArrayList.h:

#pragma once
template <class T> class ArrayList {

public:
    // Constructor to initialize the list.
    ArrayList();

    // Destructor to clean up the list.
    ~ArrayList();

    // Finds a specifies element of the array list based on the index. Returns null if nothing.
    T get(int index);

    //Finds the index of the given element.
    int indexOf(T &d);

    // Inserts an element at the end of the list.
    void add(T &d);

    // Inserts an element at a specified position in the array list.
    void add(T &d, int position );

    // Deletes the element at the given index.
    //TRUE if successful
    bool remove(int index);

    //TRUE if this array contains the given data
    bool contains(T &d);

    // Empties/clears out the array list structure.
    void clear( );

    // Tests to see if the array list structure is empty.
    bool isEmpty( );

    // Returns the size of the array.
    inline int listSize() { return size; }

private:

    int arraySize;// Size of the array.
    int size; // Number of elements in the array.
    T *data = nullptr;// Pointer to the array.

    // Checks if the array is full of elements.
    bool needsExpansion();

    //makes space in the array by doubling the arraySize
    void expandArray();

    //returns TRUE if the given index is in range (0 -> size)
    bool isValidIndex(int index);
};

ArrayList.cpp:

#include "ArrayList.h"

using namespace std;

//constructor
//set array size, size and data
template<class T>
ArrayList<T>::ArrayList() {
    arraySize = 2;
    size = 0;
    data = new T[arraySize];
}

//deconstructor
//cleanup objects
template <class T> ArrayList<T> :: ~ArrayList() {
//    delete arraySize;
//    delete size;
    delete []data;
};

//takes in and index and returns the object associated with it
//return NULL or nothing if index is outta range
template <class T> T ArrayList<T> :: get(int index) {
    if (!isValidIndex(index)) return 0;
    return data[index];
}

//returns the index of the given obj
//or -1 if not found
template <class T> int ArrayList<T> :: indexOf(T &d) {
    for (int i = 0; i < size; i++) {
        if (data[i] == *d) return i;
    }
    return -1;
}

//adds the given data to the end of the list
//expands the list if neccisary
template <class T> void ArrayList<T> :: add(T &d) {
    if (needsExpansion()) expandArray();
    data[size++] = d;
}

//adds the given data to the given index
//expands the list if necessary
template <class T> void ArrayList<T> :: add(T &d, int index) {
    if (needsExpansion()) expandArray();
    //accept index at size
    if (!(index >= 0 && index <= size)) return;
    //move all obj's at >= index up 1
    for (int i = size() - 1; i >= 0; i--) {
        if (i >= index) {
            data[i + 1] = data[i];
        }
    }
    data[index] = d;
    size++;
}

//removes the element at the given index
template <class T> bool ArrayList<T> :: remove(int index) {
    if (!isValidIndex(index)) return false;
    //shift elements down
    for (int i = index + 1; i < size(); i++) {
        data[i - 1] = data[i];
    }
    //remove last element
    data[size--] = nullptr;
    return true;
}

//TRUE if the element exists in the array
//FALSE otherwise.
template <class T> bool ArrayList<T> ::contains(T &d) {
    return indexOf(d) >= 0;
}

//clears out the data that this arraylist holds
template <class T> void ArrayList<T> :: clear() {
    size = 0;
    arraySize = 2;
    delete []data;
    *data = new T[arraySize];
}

//TRUE if this array list has no elements.
template <class T> bool ArrayList<T> :: isEmpty() {
    return size == 0;
}

//TRUE if this array needs to be expanded.
//needs expansion if it is full.
template<class T> bool ArrayList<T> :: needsExpansion() {
    return size >= arraySize;
}

//expands the array by twice the given size
template<class T> void ArrayList<T> :: expandArray() {
    arraySize *= 2;
    T *newData = new T[arraySize];
    for (int i = 0; i < size; i++) {
        newData[i] = data[i];
    }
    delete []data;
    data = newData;
}

//check if the index is valid
template<class T>
bool ArrayList<T>::isValidIndex(int index) {
    return index >= 0 && index < size;
}

It compiles after adding #pragma once.

\$\endgroup\$
  • \$\begingroup\$ How is this off topic? I am looking for best practices, potential performance issues with my memory allocation and general feedback on my code structure. Is it because it does not compile completely? \$\endgroup\$ – SirTrashyton Jun 27 at 12:56
  • 4
    \$\begingroup\$ The code should work as expected to the most of your knowledge. There are more details in the page I linked. \$\endgroup\$ – Incomputable Jun 27 at 12:57
  • 2
    \$\begingroup\$ It not only must compile, it must work as expected. Please see the help center as @Incomputable suggested. \$\endgroup\$ – pacmaninbw Jun 27 at 13:29
  • \$\begingroup\$ Is there a reason you are not using vector<TYPE> or array<TYPE, SIZE>? \$\endgroup\$ – pacmaninbw Jun 27 at 13:31
  • \$\begingroup\$ After adding the tag #pragma once, it compiles. And it works in storing items and retrieving items, so yes, my post applies. Thank you for helping me understand the rules. \$\endgroup\$ – SirTrashyton Jun 27 at 14:11
1
\$\begingroup\$

Some small structure feedback:

1. The template keyword should be above the function definition

Templated functions is usually written like you have written your constructor with the template keyword ontop of the function definition. Like this:

template<class T> 
T ArrayList<T>::get(int index)
{
      //Implementation here
}

It is easier to understand at a glance this way.

2. Don't use using namespace std;

It's bad practice, and the earlier you stop using it the easier it is.

If you don't know what it does, it removes the need to write std:: before functions in the standard namespace. Example: cout << instead of std::cout <<.

It might seem handy in the beginning but it will possibly cause problems in the future so it's better to just get used to it.

3. Templated classes should be implemented in the header

.cpp files should not be used when dealing with templates. See this for more information.

If you want to separate the definition from the implementation you can use a .inl file. Like this:

ArrayList.h:

#pragma once

template <class T> 
class ArrayList 
{
public:
     ArrayList();

     // Rest of your functions here.
};

//Notice this:
#include "ArrayList.inl"

ArrayList.inl:

//Notice: No #include here

template<class T>
ArrayList<T>::ArrayList()
{
      //Implementation here
}
\$\endgroup\$
  • \$\begingroup\$ Thank you for the advice, I did not know that splitting my function declaration's between .cpp files would cause issues. Am I using the correct parameters and dereferencing with my get function (and other functions)? \$\endgroup\$ – SirTrashyton Jun 28 at 8:32
  • \$\begingroup\$ I'd say that point 1 is really a style choice. I see you have a justification for it, but you do make it sound like an absolute rule (which it isn't). Points 2 and 3 are good observations. \$\endgroup\$ – Toby Speight Jun 28 at 9:50
  • \$\begingroup\$ @SirTrashyton You can only split the declaration and definition of a nontemplate function. You cannot do that for a template because of the way C++ templates work under the hood. \$\endgroup\$ – L. F. Jul 4 at 1:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.